IETF MANET Working Group Hakim Badis INTERNET-DRAFT Institut Gaspard-Monge, Marne-la-Vallée, France Expires: March 5, 2007 Khaldoun A. Agha LRI Laboratory, Orsay, France Project Hipercom, INRIA, France October 2006 Quality of Service for Ad hoc Optimized Link State Routing Protocol (QOLSR) draft-badis-manet-qolsr-04.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on March 5, 2007. Copyright Notice Copyright (C) The Internet Society (2006). Abstract The Optimized Link State Routing (OLSR) protocol for mobile ad hoc networks provides shortest routes in terms of number of hops using Dijkstra's shortest path algorithm. In order to support multiple- metric routing criteria, a quality of service (QoS) extension can be added to OLSR functioning. No additional control traffic is Badis & A. Agha Expires March 2007 [Page 1] INTERNET-DRAFT QoS for OLSR October 2006 generated (only augmented HELLO and TC messages). QOLSR protocol uses standard multipoint relays (MPRs) to ensure that the overhead is as low as possible for forwarding control traffic. Local QoS metrics information on links are used to calculate quality of service MPRs (QMPRS) and then flooded in the network by TC messages to calculate routing tables. QOLSR can find optimal paths on the known partial topology having the same performances that those on the whole network. These paths contain only QMPRs as intermediate nodes between a source destination pair. This memo describes the QOLSR protocol, which is an enhancement of OLSR to support multiple-metric QoS routing. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. QOLSR Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 4. Useful Definitions . . . . . . . . . . . . . . . . . . . . . . 6 5. QOLSR Characteristics . . . . . . . . . . . . . . . . . . . . . 7 6. QOLSR Functioning . . . . . . . . . . . . . . . . . . . . . . . 8 7. Information Repositories . . . . . . . . . . . . . . . . . . . 10 7.1. Multiple Interface Association Information Base . . . . . 10 7.2. Link Sensing: Local Link Information Base. . . . . . . . . 11 7.2.1. Link Set. . . . . . . . . . . . . . . . . . . . . . 11 7.3. Neighbor and Best QoS Conditions Detection: Neighborhood Information Base . . . . . . . . . . . . . . . . . . . . . 11 7.3.1. Neighbor Set. . . . . . . . . . . . . . . . . . . . 12 7.3.2. 2-hop Neighbor Set. . . . . . . . . . . . . . . . . 12 7.3.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . 12 7.3.4. QMPR Neighbor Set . . . . . . . . . . . . . . . . . 13 7.3.5. MPR Selector Set. . . . . . . . . . . . . . . . . . 13 7.3.6. QMPR Slector Set. . . . . . . . . . . . . . . . . . 13 7.4. Topology Information Base. . . . . . . . . . . . . . . . . 13 8. Main Addresses and Multiple Interfaces . . . . . . . . . . . . 14 9. HELLO Message Format, Generation and Processing . . . . . . . . 14 9.1. HELLO Message Extension Format . . . . . . . . . . . . . . 14 9.1.1. Description of the fields . . . . . . . . . . . . . 16 9.1.2. Link Code as Link Type and Neighbor Type. . . . . . 17 9.2. HELLO Message Generation . . . . . . . . . . . . . . . . . 18 9.3. HELLO Message Processing . . . . . . . . . . . . . . . . . 18 10. Link Sensing . . . . . . . . . . . . . . . . . . . . . . . . 20 11. Link QoS measurement . . . . . . . . . . . . . . . . . . . . . 20 12. Neighbor and Best QoS Conditions Detection . . . . . . . . . . 20 12.1. Populating the Neighbor Set . . . . . . . . . . . . . . . 20 12.2. Populating the 2-hop Neighbor Set . . . . . . . . . . . . 22 Badis & A. Agha Expires March 2007 [Page 2] INTERNET-DRAFT QoS for OLSR October 2006 12.3. Populating the MPR Set. . . . . . . . . . . . . . . . . . 22 12.4. Populating the MPR Selector Set . . . . . . . . . . . . . 23 12.5. Populating the QMPR Set . . . . . . . . . . . . . . . . . 23 12.5.1. QMPR Computation . . . . . . . . . . . . . . . . . 24 12.6. Populating the QMPR Selector Set. . . . . . . . . . . . . 25 12.6.1. HELLO Message Processing . . . . . . . . . . . . . 25 13. TC Message Format, Generation and Processing . . . . . . . . . 25 13.1. TC Message Extension Format . . . . . . . . . . . . . . . 25 13.1.1. Description of the Fields. . . . . . . . . . . . . 26 13.2. TC Message Generation . . . . . . . . . . . . . . . . . . 27 13.3. TC Message Processing . . . . . . . . . . . . . . . . . . 27 14. Routing Table Calculation. . . . . . . . . . . . . . . . . . . 28 15. Oscillation Problem . . . . . . . . . . . . . . . . . . . . . 29 15.1. Oscillation-Avoidance at the Source . . . . . . . . . . . 29 15.2. Distributed Oscillation-Avoidance . . . . . . . . . . . . 30 16. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . 33 17. Proposed Values for Constants . . . . . . . . . . . . . . . . 33 18. Delay Metric Representation in Control Messages . . . . . . . 34 19. TLV Encoding for QoS Metrics . . . . . . . . . . . . . . . . . 35 20. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35 21. Security Considerations . . . . . . . . . . . . . . . . . . . 35 22. References . . . . . . . . . . . . . . . . . . . . . . . . . . 35 23. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 36 24. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 37 25. Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . 37 1. Introduction OLSR protocol is an optimization over the classical link state protocol, developed for the mobile Ad hoc networks. It performs hop- by-hop routing, i.e., each node uses its most recent information to route a packet. Therefore, each node selects a set of its neighbor nodes as "MultiPoint Relays" (MPR). In OLSR, only nodes, selected as MPRs, are responsible for forwarding control traffic, intended for diffusion into the entire network. MPRs provide an efficient mechanism for flooding control traffic by reducing the number of transmissions required. Nodes, selected as MPRs, also have a special responsibility when declaring link state information in the network. Hence, only a small subset of links to neighbor nodes is made known in the topology (partial topology). This information is then used by OLSR for route calculation. As of result, routes contain only MPRs as intermediate nodes between a source destination pair. OLSR provides optimal routes in terms of number of hops (shortest path routes). No explicit quality of service is taken into account. For more details, please see the OLSR base specification [1]. Badis & A. Agha Expires March 2007 [Page 3] INTERNET-DRAFT QoS for OLSR October 2006 This document presents the QOLSR protocol which is an extension introduced to OLSR to fulfill QoS requirements. It ensures that optimal metrics are made available along a route between communication partners. Additional fields about QoS conditions are added to HELLO and TC messages. No additional control messages are generated. Using QOLSR, a node measures QoS metrics like available bandwidth, delay, jitter, loss probability, cost, etc., on links to its neighbor nodes. These QoS metrics information are used to calculate QoS-MPRs (QMPRs) and then flooded in the network by TC messages to calculate routing tables. QOLSR routes contain only QMPRs as intermediate nodes between a source destination pair. As in OLSR, QOLSR uses MPRs to ensure that the overhead is as low as possible for forwarding control traffic. TC messages are generated By QMPRs and relayed only by MPRs. To select MPRs, QOLSR applies the same heuristic used for the selection of MPRs in OLSR. This heuristic limits its number in the network and reduces the flooding of broadcast packets in the network by minimizing the duplicate retransmissions locally. For QMPRs selection, a new algorithm based QoS metrics is used (see section 12.5). QOLSR specification uses conventional meanings [2] for capitalized words such as MUST, SHOULD, etc., to indicate requirement levels for various protocol features. 2. Changes Major changes from version 03 to version 04 - Generalization of QMPRs selection algorithm for all possible QoS metrics (QMPR-Metrics). Instead of QMPRs computation based only on bandwidth and delay, any QoS metric can be used, which may be applicable in specific scenarios. QMPRs-Metrics SHOULD be declared before QOLSR running. Otherwise, bandwidth and delay are used as default parameters for the QMPRs selection. - Introduction of support for multiple interfaces. Major changes from version 02 to version 03 - Standard MPRs are used to reduce the flooding of broadcast packets in the network instead of QMPRs. - TC messages are generated by QMPRs and relayed by MPRs. Badis & A. Agha Expires March 2007 [Page 4] INTERNET-DRAFT QoS for OLSR October 2006 - A new algorithm for QMPRs selection. - QOLSR routes contain only QMPRs as intermediate nodes between a source destination pair. - Using the QOLSR protocol, a node keeps information about the next hop alone. So, it loses the ability to distinguish the part of used capacity that is induced by the given flow from other ones. There are cases in which a source node continuously changes a flow's next hop in response to the change of available bandwidth on its path and cannot tell apart the traffic induced by itself from traffic generated by other nodes. This situation is called the oscillation problem. Tow solutions are proposed to resolve this problem: at the source or distributedly by each hop in the path. 3. QOLSR Terminology The QOLSR protocol uses the same terminology defined in [1]. Additionally, this document uses the following terminology: QOLSR interface A network device participating in a MANET running QOLSR. A node may have several QOLSR interfaces, each interface assigned an unique IP address. non QOLSR interface A network device, not participating in a MANET running QOLSR. A node may have several non QOLSR interfaces (wireless and/or wired). Routing information from these interfaces MAY be injected into the QOLSR routing domain. single QOLSR interface node A node which has a single QOLSR interface, participating in an QOLSR routing domain. multiple QOLSR interface node A node which has multiple QOLSR interfaces, participating in an QOLSR routing domain. Badis & A. Agha Expires March 2007 [Page 5] INTERNET-DRAFT QoS for OLSR October 2006 main address The main address of a node, which will be used in QOLSR control traffic as the "originator address" of all messages emitted by this node. It is the address of one of the QOLSR interfaces of the node. A single QOLSR interface node MUST use the address of its only QOLSR interface as the main address. A multiple QOLSR interface node MUST choose one of its QOLSR interface addresses as its "main address" (equivalent of "router ID" or "node identifier"). It is of no importance which address is chosen, however a node SHOULD always use the same address as its main address. quality of service multipoint relay (QMPR) Let X be a node and Y its symmetric 1-hop neighbour (X<--->Y). Y is selected by X as its QMPR if there exists a 1-hop symmetric neighbour of Y, node Z, such that the path Z-->Y-->X has the best performance based on more than one metric. Routes used by QOLSR only include QMPRs as intermediate nodes. quality of service multipoint relay selector (QMPR selector) A node which has selected its 1-hop neighbor, node Y, as its quality of service multipoint relay, will be called a quality of service multipoint relay selector of node Y. QMPR-Metrics The QoS metrics used for the QMPRs selection are applied QMPRs-Metrics. If they are not predefined, bandwidth and delay are used as default parameters. 4. Useful Definitions * A metric is additive if the sum of all metrics on each intermediate arc gives the metric value on the path. It is obvious that delay, jitter, hop-count and cost follow the additive composition rule. * A metric is multiplicative if the product of all metrics on each intermediate arc gives the metric value on the path. The probability of successful transmission follows the multiplicative Badis & A. Agha Expires March 2007 [Page 6] INTERNET-DRAFT QoS for OLSR October 2006 composition rule. The loss probability metric can be expressed in an equivalent probability of successful transmission, like (1 - probability of successful transmission). * Lagrange relaxation is a common technique for calculating lower bounds, and finding good solutions (See [3]). * A path delay is the sum of all delays on each intermediate arc. * A path bandwidth is the minimum bandwidth value on intermediate arcs. * A widest path between two nodes is the path having maximum path bandwidth between those two nodes. * A shortest path between two nodes is the path having minimum path delay between those two nodes. * A shortest-widest path is the widest path, and with shortest delay when there is more than one widest. 5. QOLSR Characteristics * Does the protocol function proactively? (if so, how?) Yes. QOLSR is an extension of OLSR (proactive protocol) to support QoS requirements without additional control messages. Each node periodically sends information about its QMPR selectors and their QoS conditions, which enables the nodes to construct routes to these QMPR selectors through the node. * Does the protocol support multi-constraint path QoS routing? Yes. * Does the protocol provide loop-free routing? (if so, how?) Yes. For routing table calculation, QOLSR uses shortest-widest path algorithm or a distributed algorithm based Lagrangian relaxation. As both algorithms are based on Dijkstra routing algorithm, routing is loop-free when in a stable state [3, 4]. * Does the protocol require using some form of source routing? (if so, how?) No. However, the use of some form of source routing may easily Badis & A. Agha Expires March 2007 [Page 7] INTERNET-DRAFT QoS for OLSR October 2006 be enabled through optional extensions to the protocol to provide for example reservation mechanism and admission control mechanism. * Does the protocol provide support for routing through a multi- technology routing fabric? Yes. * Does the protocol provide some form of security? (if so, how?) Yes. Security is considered as a QoS metric. * Does the protocol provide admission control mechanism? (if so, how?) No. However, it can interact with admission control mechanisms (see [5]). * Does the protocol provide reservation mechanism? (if so, how?) No. However, it can interact with reservation mechanisms (see [5]). 6. QOLSR Functioning QOLSR is a proactive QoS routing protocol for mobile ad hoc networks. The protocol inherits the stability of a link state algorithm and has the advantage of having optimal routes in terms of multiple-metric immediately available when needed due to its proactive nature. QOLSR provides end-to-end QoS requirements and minimizes flooding of control traffic by using only selected nodes, called MPRs, to retransmit control messages. This technique significantly reduces the number of retransmissions required to flood a message to all nodes in the network. QOLSR requires only partial link state and their QoS information to be flooded in order to provide optimal routes under QoS constraints as those in whole network topology. All nodes, selected as QMPRs, MUST declare the links QoS information to their QMPR selectors using TC messages. QOLSR carried out different functions which are required to perform the task of routing: Badis & A. Agha Expires March 2007 [Page 8] INTERNET-DRAFT QoS for OLSR October 2006 Link Sensing Link Sensing is accomplished through periodic emission of HELLO messages over the interfaces through which connectivity is checked. A separate HELLO message is generated for each interface and emitted in correspondence with the provisions in section 10. Resulting from Link Sensing is a local link set, describing links between "local interfaces" and "remote interfaces" - i.e., interfaces on neighbor nodes. If sufficient information is provided by the link-layer, this may be utilized to populate the local link set instead of HELLO message exchange Link QoS Measurement Each node MUST estimate the QoS conditions (available bandwidth, delay, loss probability, cost, security, power consumption, etc.) on links to each neighbour interface having direct and symmetric link. Neighbor and Best QoS Conditions Detection Given a network with only single interface nodes, a node may deduct the Neighbor Set and the *best* QoS conditions directly* from the information exchanged as part of link sensing: the "main address" of a single interface node is, by definition, the address of the only interface on that node. In a network with multiple interface nodes, additional information is required in order to map interface addresses to main addresses (and, thereby, to nodes). This additional information is acquired through multiple interface declaration (MID) messages, described in section 5 of [1]. Multipoint Relay Selection Each node selects its MPR set from among its 1-hop symmetric neighbors. This set is selected such that it covers (in terms of radio range) all symmetric strict 2-hop nodes. The information required to perform this calculation is acquired through the periodic exchange of HELLO messages. The MPR set is re-calculated when a change in 1-hop or 2-hop Neighbor sets with bi-directional link is detected. Badis & A. Agha Expires March 2007 [Page 9] INTERNET-DRAFT QoS for OLSR October 2006 Quality of Service Multipoint Relay Selection Each node of the network independently selects its own set of QMPRs. This set is calculated to contain a subset of the 1-hop neighbors which provides the best QoS guarantees from each 2-hop neighbour to the given node. The QMPR set needs not to be optimal, however it SHOULD be small enough to minimize the number of generated TC messages in the network. The information required to perform this calculation is acquired through the periodic exchange of HELLO messages. QMPRs of a given node are declared in the subsequent HELLOs transmitted by this node, so that the information reaches the QMPRs themselves. The QMPR set is re-calculated when a change in 1-hop or 2-hop Neighbor sets with bi-directional link is detected; or a change is detected in their QoS conditions. [4, 6] give an analysis and examples of QMPR selection algorithms. QMPR and Best QoS Conditions Declaration Topology Control (TC) extension messages are sent by each QMPR node in the network at regular intervals to declare its QMPR Selector set and QoS conditions. The information diffused in the network by these TC messages will help each node to calculate its routing table. Routing Table Calculation Each node maintains a routing table which allows it to route packets for the other destinations in the network with optimal metrics respecting QoS constraints. This is detailed in section 14. 7. Information Repositories Through the exchange of QOLSR control messages, each node accumulates information about the network. This information is stored according to the descriptions in this section. 7.1. Multiple Interface Association Information Base For each destination in the network, "Interface Association Tuples" (I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an interface address of a node, I_main_addr is the main address of this node. I_time specifies the time at which this tuple expires and *MUST* be removed. Badis & A. Agha Expires March 2007 [Page 10] INTERNET-DRAFT QoS for OLSR October 2006 In a node, the set of Interface Association Tuples is denoted the "Interface Association Set". 7.2. Link Sensing: Local Link Information Base The local link information base stores information about links to neighbors and their QoS constraints. 7.2.1. Link Set A node records a set of "Link Tuples" (L_local_iface_addr, L_neighbor_iface_addr, L_bandwidth, L_delay, L_met_1, ..., L_met_n, L_SYM_time, L_ASYM_time, L_time). L_local_iface_addr is the interface address of the local node (i.e., one endpoint of the link), L_neighbor_iface_addr is the interface address of the neighbor node (i.e., the other endpoint of the link). L_bandwidth, L_delay, L_met_1, ... and L_met_n designate the available bandwidth, delay and 1st to Nth additional metrics values respectively on this link. L_SYM_time is the time until which the link is considered symmetric, L_ASYM_time is the time until which the neighbor interface is considered heard, and L_time specifies the time at which this record expires and *MUST* be removed. When L_SYM_time and L_ASYM_time are expired, the link is considered lost. This information is used when declaring the neighbor interfaces in the HELLO messages. L_SYM_time is used to decide the Link Type declared for the neighbor interface. If L_SYM_time is not expired, the link MUST be declared symmetric. If L_SYM_time is expired, the link MUST be declared asymmetric. If both L_SYM_time and L_ASYM_time are expired, the link MUST be declared lost. In a node, the set of Link Tuples are denoted the "Link Set". 7.3. Neighbor and Best QoS Conditions Detection: Neighborhood Information Base The neighborhood information base stores information about neighbors, 2-hop neighbors, MPRs, MPR selectors, QMPRs, QMPR selectors and their QoS conditions. Badis & A. Agha Expires March 2007 [Page 11] INTERNET-DRAFT QoS for OLSR October 2006 7.3.1. Neighbor Set A node records a set of "neighbor tuples" (N_neighbor_main_addr, N_status, N_willingness, N_bandwidth, N_delay, N_met_1, ..., N_met_n), describing neighbors. N_neighbor_main_addr is the main address of a neighbor, N_status specifies if the node is NOT_SYM or SYM. N_willingness in an integer between 0 and 7, and specifies the node's willingness to carry traffic on behalf of other nodes. N_bandwidth, N_delay, N_met_1, ... and N_met_n designate the *best* values of the available bandwidth, delay and 1st to Nth additional metrics respectively to this neighbor. These metrics are calculated from the Link Set on the local node. For example, N_bandwidth and N_delay are assigned respectively the maximum value among all L_bandiwdth values and the minimum value among all L_delay values on links from any interface of the local node to any interface of this neighbor. N_bandwidth and N_delay can be values on tow different links to this neighbor. 7.3.2. 2-hop Neighbor Set A node records a set of "2-hop tuples" (N_neighbor_main_addr, N_2hop_addr, N_2hop_bandwidth, N_2hop_delay, N_2hop_met_1, ..., N_2hop_met_n N_time), describing symmetric (and, since MPR links by definition are also symmetric, thereby also MPR) links between its neighbors and the symmetric 2-hop neighborhood. N_neighbor_main_addr is the main address of a neighbor, N_2hop_addr is the main address of a 2-hop neighbor with a symmetric link to N_neighbor_main_addr. N_2hop_bandwidth, N_2hop_delay, N_2hop_met_1, ..., N_2hop_met_n designate the *best* known values of the available bandwidth, delay and 1st to Nth additional metrics respectively on the link from any interface of the node with N_neighbor_main_addr as its main address to any interface of its neighbor with N_2hop_addr as its main address. N_time specifies the time at which the tuple expires and *MUST* be removed. In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor Set". 7.3.3. MPR Set A node maintains a set of neighbors which are selected as MPR. Their main addresses are listed in the MPR Set. Badis & A. Agha Expires March 2007 [Page 12] INTERNET-DRAFT QoS for OLSR October 2006 7.3.4. QMPR Set A node maintains a set of neighbors which are selected as QMPR. Their main addresses are listed in the QMPR Set. 7.3.5. MPR Selector Set A node records a set of MPR-selector tuples (MS_main_addr, MS_time), describing the neighbors which have selected this node as a MPR. MS_main_addr is the main address of a node, which has selected this node as MPR. MS_time specifies the time at which the tuple expires and *MUST* be removed. In a node, the set of MPR-selector tuples are denoted the "MPR Selector Set". 7.3.6. QMPR Selector Set A node records a set of QMPR-selector tuples (QMS_main_addr, QMS_bandwidth, QMS_delay, QMS_met_1, ..., QMS_met_n, QMS_time), describing the neighbors which have selected this node as a QMPR and their QoS conditions. MS_main_addr is the main address of a node, which has selected this node as QMPR. QMS_bandwidth, QMS_delay, QMS_met_1, ... and QMS_met_n designate the *best* known values of the available bandwidth, delay and 1st to Nth additional metrics respectively on the link between any interface of the QMPR node and any interface of the local node. MS_time specifies the time at which the tuple expires and *MUST* be removed. In a node, the set of QMPR-selector tuples are denoted the "QMPR Selector Set". 7.4. Topology Information Base Each node in the network maintains topology information about the network. This information is acquired from TC-messages and is used for routing table calculations. Thus, for each destination in the network, at least one "Topology Tuple" (T_dest_addr, T_last_addr, T_bandwidth, T_delay, T_met_1, ..., T_met_n T_seq, T_time) is recorded. T_dest_addr is the main address of a node, which may be reached in one hop from the node with the main address T_last_addr. Typically, T_last_addr is a QMPR of T_dest_addr. T_bandwidth, T_delay, T_met_1, ... and T_met_n are the *best* known bandwidth, delay and 1st to Nth additional metrics Badis & A. Agha Expires March 2007 [Page 13] INTERNET-DRAFT QoS for OLSR October 2006 values respectively from T_last_addr to T_dest_addr. T_seq is a sequence number, and T_time specifies the time at which this tuple expires and *MUST* be removed. In a node, the set of Topology Tuples are denoted the "Topology Set". 8. Main Addresses and Multiple Interfaces For single QOLSR interface nodes, the relationship between an QOLSR interface address and the corresponding main address is trivial: the main address is the OLSR interface address. For multiple QOLSR interface nodes, the relationship between QOLSR interface addresses and main addresses is defined through the exchange of Multiple Interface Declaration (MID) messages. [1] describes in detail how MID messages are exchanged and processed. Each node with multiple interfaces MUST announce, periodically, information describing its interface configuration to other nodes in the network. This is accomplished through flooding a Multiple Interface Declaration message to all nodes in the network through the MPR flooding mechanism. Each node in the network maintains interface information about the other nodes in the network. This information acquired from MID messages, emitted by nodes with multiple interfaces participating in the MANET, and is used for routing table calculations. Specifically, multiple interface declaration associates multiple interfaces to a node (and to a main address) through populating the multiple interface association base in each node. 9. HELLO Message Format, Generation and Processing A common mechanism is employed for populating the local link information base and the neighborhood information base, namely periodic exchange of HELLO messages. 9.1. HELLO Message Extension Format This section describes the HELLO message extension to support QoS requirements including available bandwidth, delay, etc. Badis & A. Agha Expires March 2007 [Page 14] INTERNET-DRAFT QoS for OLSR October 2006 HELLO messages extension are broadcasted to all one-hop neighbors and are emitted on each MANET interface of the node. They are *not relayed* to further nodes. The proposed extension format of a HELLO message is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Htime | Willingness | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Code | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Code | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Interface Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : etc. This is sent as the data-portion of the general packet format described in [1], with the "Message Type" set to HELLO_MESSAGE, the TTL field set to 1 (one). Badis & A. Agha Expires March 2007 [Page 15] INTERNET-DRAFT QoS for OLSR October 2006 9.1.1. Description of the fields "Reserved", "Htime", "Willingness", "Link Code", "Link Message Size" and "Neighbor Interface Address" fields are described in [1]. QoS fields values QoS fields values are defined in accordance with QoS parameters to be used in the QOLSR. As the available bandwidth and delay are the most important parameters for the major of QoS flows and used as default parameters for QMPRs selection, bandwidth and delay SHOULD be included as permanent parameters in QoS fields. The following parameter fields are defined, and MUST appear in this order: - Available Bandwidth: 24-bit number, measured in Kbits/second. The first 16 highest bits are the integer part and the last 8 lowest bits represent the decimal part. - Delay: 8-bit number, measured in milliseconds. The delay on link is represented by its mantissa (four highest bits of Delay field) and by its exponent (four lowest bits of Delay field). In other words: Delay = C*(1+a/16)* 2^b [in milliseconds] where a is the integer represented by the four highest bits of Delay field and b the integer represented by the four lowest bits of Delay field. The proposed value of the scaling factor C is specified in section 17. - The remaining 32-bits represent the other QoS parameters that SHOULD be exchanged between neighbor nodes to get the final value on link. The loss probability (lp) metric is one example of those QoS metrics. Let A and B be tow neighbor nodes. Lp(A<--->B) = 1 - [(1 - Lp(A<---B))* (1 - Lp(A--->B))]. TVL (type/length/Value) encoding format is used to encode those (if exist) QoS metrics as follow: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |Length | Value... | Type |Length | Value... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type and Length are fixed according to section 19. Badis & A. Agha Expires March 2007 [Page 16] INTERNET-DRAFT QoS for OLSR October 2006 9.1.2. Link Code as Link Type and Neighbor Type If the Link Code value is less than or equal to 15, then it MUST be interpreted as holding two different fields, of two bits each: 7 6 5 4 3 2 1 0 +-------+-------+-------+-------+-------+-------+-------+-------+ | 0 | 0 | 0 | 0 | Neighbor Type | Link Type | +-------+-------+-------+-------+-------+-------+-------+-------+ The following four "Link Types" are REQUIRED by OLSR: - UNSPEC_LINK - indicating that no specific information about the links is given. - ASYM_LINK - indicating that the links are asymmetric (i.e., the neighbor interface is "heard"). - SYM_LINK - indicating that the links are symmetric with the interface. - LOST_LINK - indicating that the links have been lost. The following four "Neighbor Types" are REQUIRED by QOLSR: - SYM_NEIGH - indicating that the neighbors have at least one symmetrical link with this node. - MPR_NEIGH - indicating that the neighbors have at least one symmetrical link AND have been selected only as MPR and not as QMPR by the sender. - QMPR_NEIGH - indicating that the neighbors have at least one symmetrical link AND have been selected only as QMPR and not as MPR by the sender. - QMPR-MPR_NEIGH - indicating that the neighbors have at least one symmetrical link AND have been selected as QMPR and MPR by the sender. - NOT_NEIGH - indicating that the nodes are either no longer or have not yet become symmetric neighbors. Note that an implementation should be careful in confusing neither Link Type with Neighbor Type nor the constants (confusing SYM_NEIGH with SYM_LINK for instance). Badis & A. Agha Expires March 2007 [Page 17] INTERNET-DRAFT QoS for OLSR October 2006 9.2. HELLO Message Generation This involves transmitting the Link Set, the Neighbor Set, the MPR Set and the QMPR Set. In principle, a HELLO message serves three independent tasks: - Link Sensing - Link QoS Measurement - Neighbor and Best QoS Conditions Detection - MPR Selection Signalling - QMPR Selection Signalling HELLO message extension generation in QOLSR is exactly like in the standard OLSR. Moreover, it sets the bandwidth, the delay and the other QoS metrics fields for each neighbor interface address according to the associated link tuple. The lists of addresses declared in a HELLO message is a list of neighbor interface addresses computed as follows: For each tuple in the Link Set, where L_local_iface_addr is the interface where the HELLO is to be transmitted, and where L_time >= current time (i.e., not expired), L_neighbor_iface_addr is advertised with: 1 The Link Type set according to the following: 1.1 if L_SYM_time >= current time (not expired) Link Type = SYM_LINK 1.2 Otherwise, if L_ASYM_time >= current time (not expired) AND L_SYM_time < current time (expired) Link Type = ASYM_LINK 1.3 Otherwise, if L_ASYM_time < current time (expired) AND L_SYM_time < current time (expired) Link Type = LOST_LINK Badis & A. Agha Expires March 2007 [Page 18] INTERNET-DRAFT QoS for OLSR October 2006 2 The Neighbor Type is set according to the following: 2.1 If the main address, corresponding to L_neighbor_iface_addr, is included in the QMPR Set and MPR Set simultaneously: Neighbor Type = QMPR-MPR_NEIGH 2.2 Otherwise, 2.2.1 if the main address, corresponding to L_neighbor_iface_addr, is included in the QMPR Set or MPR set: Neighbor Type = QMPR_NEIGH (if in QMPR Set) Neighbor Type = MPR_NEIGH (if in MPR Set) 2.2.2 Otherwise, if the main address, corresponding to L_neighbor_iface_addr, is included in the Neighbor Set: 2.2.2.1 if N_status == SYM Neighbor Type = SYM_NEIGH 2.2.2.2 Otherwise, if N_status == NOT_SYM Neighbor Type = NOT_NEIGH For each tuple in the Neighbor Set, for which no L_neighbor_iface_addr from an associated link tuple has been advertised by the previous algorithm, N_neighbor_main_addr is advertised with: - Link Type = UNSPEC_LINK, - Neighbor Type set as described in step 2 above For a node with a single OLSR interface, the main address is simply the address of the OLSR interface, i.e., for a node with a single OLSR interface the main address, corresponding to L_neighbor_iface_addr is simply L_neighbor_iface_addr. Badis & A. Agha Expires March 2007 [Page 19] INTERNET-DRAFT QoS for OLSR October 2006 9.3. HELLO Message Processing Upon receiving a HELLO message, the node SHOULD update the neighbor information corresponding to the sender node. It provides the same algorithm described in OLSR [1] for HELLO processing. Moreover, it adds and updates the bandwidth, the delay and the other QoS metrics values in Link Set, Neighbor Set, 2-hop Neighbor Set, QMPR Set and QMPR Selector Set. 10. Link Sensing Link sensing populates the local link information base. Link sensing is exclusively concerned with QOLSR interface addresses and the ability to exchange packets between such QOLSR interfaces. The mechanism for link sensing is the periodic exchange of HELLO messages. It is described with more detail in section 7 of [1]. 11. Link QoS measurement Each node measures QoS metrics like available bandwidth, delay, jitter, loss probability, cost, etc., on each link to its neighbor nodes. Experimental methods to calculate the available bandwidth, delay, etc., from one local interface to a remote interface are shown in [6, 7, 8]. The QoS metric values are exchanged between neighbor interfaces using periodic HELLO messages and accumulated in the Link Set, the Neighbor Set and the 2-hop Neighbor Set. 12. Neighbor and Best QoS Conditions Detection Neighbor and best QoS detection populates the neighborhood and QoS in formation base and concerns itself with nodes and node main addresses. The mechanism for neighbor and QoS conditions detection is the periodic exchange of HELLO messages. 12.1. Populating the Neighbor Set A node maintains a set of neighbor tuples, based on the link tuples. This information is updated according to changes in the Link Set. Badis & A. Agha Expires March 2007 [Page 20] INTERNET-DRAFT QoS for OLSR October 2006 The Link Set keeps the information about the links and their QoS conditions, while the Neighbor Set keeps the information about the neighbors and the *best* known QoS condition en links to those neighbors. There is a clear association between those two sets, since a node is a neighbor of another node if and only if there is at least one link between the two nodes. In any case, the formal correspondence between links and neighbors is defined as follows: The "associated neighbor tuple" of a link tuple, is, if it exists, the neighbor tuple where: N_neighbor_main_addr == main address of L_neighbor_iface_addr The "associated link tuples" of a neighbor tuple, are all the link tuples, where: N_neighbor_main_addr == main address of L_neighbor_iface_addr The Neighbor Set MUST be populated by maintaining the proper correspondence between link tuples and associated neighbor tuples, as follows: Creation Each time a link appears, that is, each time a link tuple is created, the associated neighbor tuple MUST be created, if it doesn't already exist, with the following values: N_neighbor_main_addr = main address of L_neighbor_iface_addr (from the link tuple) In any case, the N_status, the N_bandwidth, the N_delay, the N_met_1, ... and the N_met_n MUST then be computed as described in the next step. Update Each time a link changes, that is, each time the information of a link tuple is modified, the node MUST ensure that the N_status, the N_bandwidth, the N_delay, the N_met_1, ... and Badis & A. Agha Expires March 2007 [Page 21] INTERNET-DRAFT QoS for OLSR October 2006 the N_met_n of the associated neighbor tuple respects the properties: If the neighbor has any associated link tuple which indicates a symmetric link (i.e., with L_SYM_time >= current time), then N_status is set to SYM else N_status is set to NOT_SYM N_bandwidh, N_delay, N_met_1, ... and N_met_n are set respectively to the *best* values of L_bandwidh, L_delay, L_met_1, ... and L_met_n from all associated links tuples having L_SYM_time >= current time Removal Each time a link is deleted, that is, each time a link tuple is removed, the associated neighbor tuple MUST be removed if it has no longer any associated link tuples. These rules ensure that there is exactly one associated neighbor tuple for a link tuple, and that every neighbor tuple has at least one associated link tuple. 12.2. Populating the 2-hop Neighbor Set The 2-hop Neighbor Set describes the set of nodes which have a symmetric link to a symmetric neighbour. Upon receiving a HELLO message from a symmetric neighbor, a node SHOULD update its 2-hop Neighbor Set. The procedure is described in section 8.2 of [1]. Moreover, the best values of each used QoS metric on links MUST be added and updated. 12.3. Populating the MPR Set MPRs are used to flood control messages from a node into the network while reducing the number of retransmissions that will occur in a region. Thus, the concept of MPR is an optimization of a classical flooding mechanism. Badis & A. Agha Expires March 2007 [Page 22] INTERNET-DRAFT QoS for OLSR October 2006 The MPR Set MUST be calculated by a node in such a way that it, through the neighbors in the MPR Set, can reach all symmetric strict 2-hop neighbors. (Notice that a node, a, which is a direct neighbor of another node, b, is not also a strict 2-hop neighbor of node b). This means that the union of the symmetric 1-hop neighborhoods of the MPR nodes contains the symmetric strict 2-hop neighborhood. MPR Set recalculation should occur when changes are detected in the symmetric neighborhood or in the symmetric strict 2-hop neighborhood. MPRs are computed per interface, the union of the MPR Sets of each interface make up the MPR Set for the node. QOLSR applies the same MPR selection heuristic used in OLSR. This procedure is detailed in in section 8.3 of [1]. 12.4. Populating the MPR Selector Set The MPR Selector Set of a node, n, is populated by the main addresses of the nodes which have selected n as MPR. MPR selection is signaled through HELLO messages. 12.5. Populating the QMPR Set The heuristic for the selection of multipoint relays in the standard OLSR does not take into account the QoS metrics information. It computes a multipoint relay set of minimal cardinality. Links with the best QoS guarantees (high bandwidth, low delay, cost, etc.) can be omitted. Consequently, the path calculated between two nodes using the known partial topology is not optimal (in terms of QoS metrics) in the whole network. The decision of how each node selects its QMPRs is essential to determinate the optimal QoS path in the network. In the QMPR selection, links with high QoS guarantees SHOULD not be omitted. Using QOLSR, each node in the network selects independently its own set of QMPRs. The QMPR Set MUST be calculated by a node X in such a way that it, through the neighbors in the QMPR Set, each 2-hop neighbour can reach X with the best metrics values (maximum bandwidth, minimum delay, etc.). QMPR Set allows a node to find optimal paths on the known partial topology having the same QoS performances that those on the whole network [4,5]. Badis & A. Agha Expires March 2007 [Page 23] INTERNET-DRAFT QoS for OLSR October 2006 The QoS metrics used for the QMPRs selection (QMPRs-Metrics) SHOULD be defined as parameters according to the ad hoc network scenarios. Otherwise, bandwidth and delay are used as default QMPRs-Metrics. 12.5.1. QMPR Computation The following specifies a proposed algorithm for selection of QMPRs. The following terminology will be used in describing this algorithm: - N(x): The 1-hop Neighbor set of node x containing only symmetric links to any local node (x) interface. - N2(x): The 2-hop Neighbor set of node x containing only symmetric neighbors in N(x). The 2-hop Neighbor set N2(x) of node x does not contain any 1-hop neighbor of node x. - QMPR(x): The QoS multipoint relay set of node x which is running this algorithm. The proposed algorithm is as follows: 1. Start with an empty QMPR set QMPR(x); 2. While there still exist nodes in N2(x) that are not covered by QMPR(x): 2.1. Let z be one of those nodes; 2.2. Select that node y in N(x) as QMPR which provide the best QoS two-hop path in terms of QMPR-Metrics from z to x (in the default case, z-->y-->x MUST be a shortest-widest two-hop path); 2.3. In case of a tie in the above step, select that node which is already in QMPR(x); 2.4. Mark z as covered; In this algorithm, step 2.3 reduces the size of QMPR(x). The QMPR Set is re-calculated when: - A change in the symmetric neighbourhood (see section 8 of [1]); or Badis & A. Agha Expires March 2007 [Page 24] INTERNET-DRAFT QoS for OLSR October 2006 - A change is detected in the symmetric strict 2-hop neighbourhood (see section 8.5 of [1]); or - A change of the *best* values of the QMPRs-Metrics on links of 1-hop or 2-hop neighborhood is detected. Therefore, a node measures for each symmetric 1-hop neighbor and 2-hop neighbor from Neighbor Set and 2-hop Neighbor Set respectively the percentage change between the previous and the new *best* QMPRs-Metric values. For example, in the default case, if the bandwidth or delay percentage changes exceed BANDWIDTH_THRESHOLD or DELAY_THRESHOLD respectively [6, 9], a change is detected. 12.6. Populating the QMPR Selector Set The QMPR Selector Set of a node, n, is populated by the main addresses of the nodes which have selected n as QMPR. QMPR selection is signaled through HELLO messages. 12.6.1. HELLO Message Processing Upon receiving a HELLO message, if a node finds one of its own interface addresses in the list with a Neighbor Type equal to QMPR-MPR_NEIGH or QMPR_NEIGH, information from the HELLO message MUST be recorded in the QMPR Selector Set. 13. TC Message Format, Generation and Processing A node must at least disseminate links and their QoS conditions between itself and the nodes in its QMPR-selector set, in order to provide sufficient information to enable QoS routing. 13.1. TC Message Extension Format An extension TC message is sent by a QMPR node in the network to declare its QMPR Selector set and its QoS conditions. I.e., the TC message contains the list of neighbors which have selected the sender node as a QMPR and their QoS constraints (bandwidth, delay and 1st to Nth additional metrics values). The sequence number (ANSN) associated with this QMPR Selector set is also sent with the list. The information diffused in the network by these extension TC messages will help each node to calculate its routing table. Badis & A. Agha Expires March 2007 [Page 25] INTERNET-DRAFT QoS for OLSR October 2006 The proposed extension format of a TC message is as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ANSN | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Qos Multipoint Relay Selector Main Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS Multipoint Relay Selector Main Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : etc. 13.1.1. Description of the fields ANSN, Reserved and QoS Multipoint Relay Selector Main Address are described in [1]. QoS fields values QoS fields values are defined in accordance with QoS parameters to be used in the QOLSR. As the available bandwidth and delay are the most important parameters for the major of QoS flows and are used as default parameters for QMPRs selection, bandwidth and delay SHOULD be included as permanent parameters in QoS fields. The other QoS parameters in QoS fields are only the The following parameter fields are defined, and MUST appear in this order: - Available Bandwidth: 24-bit number, measured in Kbits/second. The first 16 highest bits are the integer part and the last 8 lowest bits represent the decimal part. Badis & A. Agha Expires March 2007 [Page 26] INTERNET-DRAFT QoS for OLSR October 2006 - Delay: 8-bit number, measured in milliseconds. The delay on link is represented by its mantissa (four highest bits of Delay field) and by its exponent (four lowest bits of Delay field). In other words: Delay = C*(1+a/16)* 2^b [in milliseconds] where a is the integer represented by the four highest bits of Delay field and b the integer represented by the four lowest bits of Delay field. The proposed value of the scaling factor C is specified in section 17. - The remaining 32-bits represent the other QoS parameters on link between the QMPR node and its QMPR selector. TVL (type/length/Value) encoding format is used to encode those (if exist) QoS metrics as follow: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |Length | Value... | Type |Length | Value... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type and Length are fixed according to section 19. 13.2. TC Message Extension Generation In order to build the topology information base, each node, which has been selected as QMPR, broadcasts Topology Control (TC) messages. TC messages are flooded to all nodes in the network and take advantage of MPRs. MPRs enable a better scalability in the distribution of topology information. The list of addresses can be partial in each TC message (e.g., due to message size limitations, imposed by the network), but parsing of all TC messages describing the advertised Link Set of a node MUST be complete within a certain refreshing period (TC_INTERVAL). The information diffused in the network by these TC messages will help each node calculate its routing table. 13.3. TC Message Extension Processing The tuples in the Topology Set are recorded with the topology information that is exchanged through TC extension messages, following the same algorithm for TC message processing described in [1]. Moreover, it adds and updates QoS metrics values in Topology Set. Badis & A. Agha Expires March 2007 [Page 27] INTERNET-DRAFT QoS for OLSR October 2006 14. Routing table calculation Each node maintains a routing table which allows it to route the messages according to the QoS flow requirements for the other destinations in the network. The routing table is based on the information contained in the Link Set, the Neighbor Set, the 2-hop Neighbor Set, the Topology Set and the Multiple Interface Association Information Base. Therefore, if any of these tables is changed, the routing table is re-calculated to update the route information about each destination in the network. Each entry in the table consists of R_dest_addr, R_next_addr, R_iface_addr, R_dist, R_bandwidth, R_delay, R_met_1, ... and R_met_n. Such entry specifies that the node identified by R_dest_addr is estimated to be R_dist hops away from the local node, that the symmetric neighbor node with interface address R_next_addr is the next hop node in the route to R_dest_addr, and that this symmetric neighbor node is reachable through the local interface with the address R_iface_addr. The bandwidth, delay and 1st to Nth additional metrics values of the selected path to R_dest_addr are R_bandwidth, R_delay, R_met_1, ... and R_met_n respectively. Entries are recorded in the table for each destination in the network for which the route is known. All the destinations for which the route is broken or partially known are not entered in the table. The problem of finding a path with n additive and m multiplicative metrics in NP-Complete if n+m>=2 (see [10]). So, the combination of any two or more additive (delay, delay jitter, hop-count, cost, etc.) and/or multiplicative metrics (loss probability, etc.) yields to a NP-Complete problem. In other words, there is no efficient polynomial-time algorithm that can surely find a feasible path that simultaneously satisfies both constraints. Including a single metric, the best path can be easily defined. Otherwise, including multiple metrics, the best path with all parameters at their optimal values may not exist. For example, a path with both maximum bandwidth and minimum delay may not necessarily exist. Thus, the precedence among the metrics in order to define the best path MUST be decided. In [4], bandwidth is considered as the most important parameter. For best-effort flows, a shortest-widest path algorithm is run on the graph generated by Neighbor Set and Topology Set. The shortest-widest path algorithm [9] consists to find a path with maximum bandwidth (a widest path) using a variant of Dijkstra routing algorithm, and when there is more than one widest path, we choose the one with shortest path delay. Badis & A. Agha Expires March 2007 [Page 28] INTERNET-DRAFT QoS for OLSR October 2006 For QoS flows that need to satisfy a number of QoS constraints like badnwidth>Threshold_bandwidth and/or delay| NEW ANSN |<-----------------+----------------+------+ | +----------+ | | | | | | | | | | |No | | | V | | | | +-------------------+ NO +--------------+ | | | |Change of topology?|----->|Change of QoS?| | | | +-------------------+ +--------------+ | | | | | | | | |YES |YES | | | V V | | | +--------------------------+ +---------+ YES +----------+ | +-->|Routing table calculation?| |OA2 rule?|---->|Send Notif| | +--------------------------+ +---------+ +----------+ | | | |No | V | +------------------+ | |Backoff when Notif| | +------------------+ | | | | | V | +---------+ YES | |OA2 rule?|------------------+ +---------+ | | | |No | V | +--------------------------+ | |Routing table calculation?|----------+ +--------------------------+ Each TC message contains an Advertised Neighborhood Sequence Number (ANSN) which helps keeping track of topology and QoS changes. Upon reception of a TC message with a new ANSN, if the topology has changed, then the routing tables have to be recalculated using plain QOLSR methods. Otherwise, if the state of QoS of the network has changed for a given flow, then the OA2 rule must be applied to decide whether the path must be changed. If there exists at least one feasible path from the next node on the current path to the flow's Badis & A. Agha Expires March 2007 [Page 32] INTERNET-DRAFT QoS for OLSR October 2006 destination, then a change of path must be performed by some node downstream. To inform these that the current node maintains its next hop for the current flow, a notification message is sent to the next node. When a node receives the notification, it applies the OA2 rule if not done previously and behave exactly as the sender of the notification if a feasible path exists from the next node. Otherwise, it means that this node has to resolve the collision itself. When a node is in charge of resolving a collision, it selects a random backoff timer value and delays further actions. Upon timer expiration, the OA2 rule is applied again to decide whether the current path has been freed by the colliding flow, in which case the collision is resolved. If the flow is still colliding, then the node calculates the alternate path, not using the current next hop. To avoid sending the flow back through the previous node, the source address of the notification message is extracted and the link to the previous node is removed during path calculation. The size of the backoff window MUST be set to reflect the priorities of flows, since a larger window increases the probability of selecting a timer value larger than that of colliding flows and consequently decreases the probability that the flow will have to switch routes. The "older" flow should obviously be prioritized over the more recent one. Therefore, each time a collision occurs after route switching, the size of the backoff window has to be doubled. The next draft version will explicit the formula for the size of the backoff window. 16. IPv6 Considerations All the operations and parameters described in this document used by QOLSR for IP version 4 are the same as those used by OLSR for IP version 6. To operate with IP version 6, the only required change is to replace the IPv4 addresses with IPv6 address. The minimum packet and message sizes (under which there is rejection) should be adjusted accordingly, considering the greater size of IPv6 addresses. 17. Proposed Values for Constants The constants used in QOLSR (HELLO_INTERVAL, TC_INTERVAL, NEIGHB_HOLD_TIME , etc.) have the same values that those used in OLSR [2]. The new constants are BANDWIDTH_THRESHOLD and DELAY_ Badis & A. Agha Expires March 2007 [Page 33] INTERNET-DRAFT QoS for OLSR October 2006 THRESHOLD, and we proposed the following values: BANDWIDTH_THRESHOLD = 10% and DELAY_THRESHOLD = 10%. The proposed constant for C (a scaling factor for the delay metric calculation) is the following: C = 1/16 seconds (equal to 0.0625 seconds). 18. Delay metric representation in control messages The delay metric measured on link is represented by its mantissa (four highest bits of Delay field) and by its exponent (four lowest bits of Delay field). In other words: Delay = C*(1+a/16)* 2^b [in milliseconds] where a is the integer represented by the four highest bits of the field and b the integer represented by the four lowest bits of the field. Notice, that for the previous proposed value of C, (1/16 seconds), the values, in seconds, expressed by the formula above can be stored, without loss of precision, in binary fixed point or floating point numbers with at least 8 bits of fractional part. This corresponds with NTP time-stamps and single precision IEEE Standard 754 floating point numbers. Given one of the above holding times, a way of computing the mantissa/exponent representation of a number T (of seconds) is the following: - find the largest integer 'b' such that: T/C >= 2^b - compute the expression 16*(T/(C*(2^b))-1), which may not be a integer, and round it up. This results in the value for 'a' - if 'a' is equal to 16: increment 'b' by one, and set 'a' to 0 - now, 'a' and 'b' should be integers between 0 and 15, and the field will be a byte holding the value a*16+b For instance, for values of 2 milliseconds, 6 milliseconds, 15 milliseconds, and 30 milliseconds respectively, a and b would be: (a=0,b=5), (a=8,b=6), (a=14,b=7) and (a=14,b=8) respectively. Badis & A. Agha Expires March 2007 [Page 34] INTERNET-DRAFT QoS for OLSR October 2006 19. TLV encoding for QoS metrics The following table specifies the proposed TLV encoding for some useful QoS metrics. QoS metric | Type | Length ---------------------+--------+-------------- Loss probability | 0 | 8 bits Delay jitter | 1 | 8 bits Power consumption | 2 | 8 bits Cost | 3 | 8 bits Buffer space | 4 | 8 bits Network stability | 5 | 8 bits Security | 7 | 8 bits . | . | . . | . | . 20. IANA Considerations The type numbers for the extensions in section 4 are to be taken from the space of extensions to OLSR [2]. 21. Security Considerations This draft specifies mechanisms for handling quality of service. It does not introduce any special security vulnerabilities which were not already present in the OLSR routing protocol [2]. However, security can be one metric for QoS requirements. 22. References [1] T. Clausen and P. Jacquet. "Optimized Link State Routing Protocol". Request for Comments (Draft Standard) 3626. Internet Engineering Task Force, Oct. 2003. [2] S. Bradner. "Key words for use in RFCs to Indicate Requirement Levels". Request for Comments (Best Current Practice) 2119, Internet Engineering Task Force, Mar. 1997. [3] H. Badis and K. Al Agha. "Distributed Algorithm for Multiple- metric Link State QoS Routing Problem". IEEE MWCN2003, Oct. 2003. Badis & A. Agha Expires March 2007 [Page 35] INTERNET-DRAFT QoS for OLSR October 2006 [4] H. Badis, A. Munaretto, K. Al Agha, and G. Pujolle. "Optimal Path Selection in a Link State QoS Routing Protocol". IEEE VTC2004- spring, May 2004. [5] H. Badis. "CEQMM: A Complete and Efficient Quality of service Model for MANETs", draft-badis-manet-ceqmm-00.txt, April. 2006. [6] H. Badis and K. Al Agha. " QOLSR, QoS routing for Ad Hoc Wireless Networks Using OLSR". European Transactions on Telecommunications, , Vol. 15, No. 4, pp 427-442, 2005. [7] H. Badis and K. Al Agha. "Routing Bandwidth Guaranteed paths for QoS Flows in Ad Hoc Networks under Interferences Influence", IEEE CSIT Conference 2005, Algeria, July 2005. [8] Ignacy Gawkedzki, H. Badis and K. Al Agha. "Link capacity estimation in QOLSR Using IEEE 802.11", The 2nd OLSR Interop & Workshop, France, July 2005. [9] H. Badis, A. Munaretto, K. Al Agha, and G. Pujolle. "QoS for Ad hoc Networking Based on Multiple Metrics: Bandwidth and Delay". IEEE MWCN2003, Oct. 2003. [10] Z. Wang and J. Crowcroft. "Quality of service routing for supporting multimedia applications". IEEE JSAC, vol. 14, pp. 1228-1234, Sept. 1996. [11] H. Badis, I. Gawedzki and K. Al Agha. "QoS Routing in Ad hoc Networks Using QOLSR with no Need of Explicit Reservation". IEEE VTC'04-Fall: Vehicular Technology Conference, Los Angeles, USA, Sep. 2004. 23. Authors' Addresses Hakim Badis Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5133 EMail: Hakim.Badis@inria.fr Khaldoun Al Agha LRI Laboratory Paris-sud University, 91405 Orsay, France Phone: +33 1 6915 6617 Badis & A. Agha Expires March 2007 [Page 36] INTERNET-DRAFT QoS for OLSR October 2006 EMail: Alagha@lri.fr Project HIPERCOM, INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France Phone: +33 1 3963 5908, EMail: Alagha.Khaldoun@inria.fr 24. Full Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. "This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 25. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Badis & A. Agha Expires March 2007 [Page 37]