IETF MANET Working Group Hakim Badis INTERNET-DRAFT Project Hipercom, INRIA, France Expires: September 13, 2006 Khaldoun A. Agha LRI Laboratory, Orsay, France Project Hipercom, INRIA, France March 2006 Quality of Service for Ad hoc Optimized Link State Routing Protocol (QOLSR) draft-badis-manet-qolsr-03.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 September 13, 2006. 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 September 2006 [Page 1] INTERNET-DRAFT QoS for OLSR March 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 bandwidth 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 . . . . . . . . . . . . . . . . . . . . . . . 4 4. Useful Definitions . . . . . . . . . . . . . . . . . . . . . . 5 5. QOLSR Characteristics . . . . . . . . . . . . . . . . . . . . . 6 6. QOLSR Functioning . . . . . . . . . . . . . . . . . . . . . . . 7 7. Neighbor sensing and QoS measurement . . . . . . . . . . . . . 9 7.1. Neighbor sensing and QoS measurement information base . . 9 7.1.1. Neighbor Set . . . . . . . . . . . . . . . . . . . 9 7.1.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . 10 7.1.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . 10 7.1.4. MPR Selector Set . . . . . . . . . . . . . . . . . 10 7.1.5. QMPR Set . . . . .. . . . . . . . . . . . . . . . . 10 7.1.6. QMPR Selector Set . . . . . . . . . . . . . . . . 11 7.2. HELLO Message extension Format . . . . . . . . . . . . . . 11 7.2.1. Description of the fields . . . . . . . . . . . . . 12 7.3. HELLO Message extension processing . . . . . . . . . . . . 13 7.4. Multipoint relay (MPR) selection . . . . . . . . . . . . . 13 7.5. Quality of service Multipoint relay (QMPR) selection . . . 14 8. QMPR and QoS conditions information declaration . . . . . . . . 16 8.1. Topology information base . . . . . . . . . . . . . . . . 16 8.1.1. Topology Set . . . . . . . . . . . . . . . . . . . 16 8.2. TC Message Extension Format . . . . . . . . . . . . . . . 16 8.2.1. Description of the fields . . . . . . . . . . . . . 17 8.3. TC Message Extension Processing . . . . . . . . . . . . . 18 9. Routing table calculation . . . . . . . . . . . . . . . . . . . 18 10. Oscillation problem . . . . . . . . . . . . . . . . . . . . . 19 10.1. Oscillation-Avoidance at the source . . . . . . . . . . . 20 10.2. Distributed Oscillation-Avoidance . . . . . . . . . . . . 20 11. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . 24 Badis & A. Agha Expires September 2006 [Page 2] INTERNET-DRAFT QoS for OLSR March 2006 12. Proposed Values for Constants . . . . . . . . . . . . . . . . 25 13. Delay metric representation in control messages . . . . . . . 25 14. TLV encoding for QoS metrics . . . . . . . . . . . . . . . . . 26 15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 16. Security Considerations . . . . . . . . . . . . . . . . . . . 26 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 27 18. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 28 19. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 28 20. Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . 28 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 [2]. 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 having direct and symmetric link. 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 by MPRs. Badis & A. Agha Expires September 2006 [Page 3] INTERNET-DRAFT QoS for OLSR March 2006 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 (section 7.5). QOLSR specification uses conventional meanings [1] for capitalized words such as MUST, SHOULD, etc., to indicate requirement levels for various protocol features. 2. Changes 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. - 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 [2] but with single interface. Additionally, this document uses the following terminology: quality of service multipoint relay (QMPR) Let X be a node and Y its symmetric 1-hop neighbour (X<--->Y). Badis & A. Agha Expires September 2006 [Page 4] INTERNET-DRAFT QoS for OLSR March 2006 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, QMS) 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. 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 composition rule. The loss probability metric can be expressed in an equivalent probability of successful transmission, like (1 - probability of successful transmission). * A problem is called NP (nondeterministic polynomial) if its solution (if one exists) can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess. If a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete. Thus, finding an efficient algorithm for any NP-complete problem implies that an efficient algorithm can be found for all such problems, since any problem belonging to this class can be recast into any other member of the class. It is not known whether any polynomial-time algorithms will ever be found for NP-complete problems, and determining whether these problems are tractable or intractable remains one of the most important questions in theoretical computer science. When an NP-complete problem must be solved, one approach is to use a polynomial algorithm to approximate the solution; the answer thus obtained will not necessarily be optimal but will be reasonably close. * 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. Badis & A. Agha Expires September 2006 [Page 5] INTERNET-DRAFT QoS for OLSR March 2006 * 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 MPR selectors and their QoS conditions, which enables the nodes to construct routes to these MPR selectors through the node. * Does the protocol support multi-constraint path QoS routing? Yes. * Does the protocol provide shortest-widest path routes for best- effort flows? Yes. See [5]. * 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,5]. * 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 be enabled through optional extensions to the protocol to provide for example reservation mechanism and admission control mechanism. Badis & A. Agha Expires September 2006 [Page 6] INTERNET-DRAFT QoS for OLSR March 2006 * Does the protocol provide support for routing through a multi- technology routing fabric? (if so, how?) No. However, provisions for multiple interfaces may easily be enabled through extensions to the protocol. * 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. * Does the protocol provide reservation mechanism? (if so, how?) No. 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. * Neighbor sensing Each node MUST detect the neighbor nodes with which it has a direct and bi-directional link. The uncertainties over radio propagation may make some links uni-directional. Consequently, all links MUST be checked in both directions in order to be Badis & A. Agha Expires September 2006 [Page 7] INTERNET-DRAFT QoS for OLSR March 2006 considered valid. To accomplish this, each node periodically broadcasts HELLO messages, containing the information about its neighbors and their link status. These control messages are transmitted in broadcast mode. These HELLO messages are received by all one hop neighbors, but they are not relayed to further nodes. * Neighbor QoS measurement Each node MUST estimate the QoS conditions (available bandwidth, delay, loss probability, cost, security, power consumption, etc.) on links to each neighbor having direct and symmetric link. Afterwards, QoS conditions in vicinity are broadcasted using additional fields in HELLO messages (See Section 7.2). Consequently, HELLO messages will permit each node to discover its neighborhood up to two hops and their QoS conditions. * 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, as described in [2]. The MPR set is re-calculated when a change in 1-hop or 2-hop neighbor sets with bi-directional link is detected. * 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 maximum bandwidth and minimum delay 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, as described in section 7. 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, 5] give an analysis and examples of QMPR selection algorithms. Badis & A. Agha Expires September 2006 [Page 8] INTERNET-DRAFT QoS for OLSR March 2006 * QMPR and QOS conditions information declaration Topology Control 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. The nodes which receive a TC message parse and store some of the connected pairs of form [node, source, bandwidth, delay, met_1, ..., met_n] where "nodes" are the addresses found in the TC message list. "source" is the QMPR selector of "node". "bandwidth", "delay", "met_1", "met_2", ... and "met_n" represent the available bandwidth, delay and 1st to Nth additional metrics values respectively on the link between "node" and "source". The routing table is built from this database using shortest- widest path algorithm for best-effort flows and a distributed algorithm based Lagrangian relaxation for QoS flows (section 9). 7. Neighbor detection and QoS measurement Through the exchange of QOLSR HELLO messages, each node accumulates information about the network. This information is stored according to the descriptions in this section. 7.1. Neighbor sensing and QoS measurement information base The neighborhood information base stores information about neighbors, 2-hop neighbors, MPRs, MPR selectors, QMPR and QMPR selectors. 7.1.1. Neighbor Set A node records a set of "neighbor tuple" (N_addr, N_status, N_Willingness, N_bandwidth, N_delay, N_met_1, ..., N_met_n, N_time) where N_addr is the address of the neighbor, N_status designates the status of the link with that neighbor (QMPR, MPR, symmetric, heard), N_Willingness is an integer between 0 and 7 (speciefies the node's Badis & A. Agha Expires September 2006 [Page 9] INTERNET-DRAFT QoS for OLSR March 2006 willingness to carry traffic on behalf of other nodes), N_bandwidth, N_delay, N_met_1, ... and N_met_n designate the available bandwidth, delay and 1st to Nth additional metrics values respectively on the link with that neighbor and N_time specifies the time at which this record expires and *MUST* be removed. 7.1.2. 2-hop Neighbor Set As only bandwidth and delay values on links to 2-hop neighbors are used for QoS multipoint relay selection, a node records a set of "2-hop tuples" (N_addr, N_2hop_addr, N_2hop_banwdwidth, N_2hop_delay, N_time), describing symmetric, MPR or QMPR links between its neighbors and the 2-hop neighborhood. N_addr is the address of a neighbor, N_2hop_addr is the address of a 2-hop neighbor, N_2hop_banwdwidth designates the bandwidth on the link between N_addr and N_2hop_addr, N_2hop_delay is the delay on the link between N_addr and N_2hop_addr, and N_time specifies the time at which a tuple expires and *MUST* be removed. In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor Set". 7.1.3. MPR Set A node maintains a set of neighbors which are selected as MPR. Their addresses are listed in the MPR Set. 7.1.4. MPR Selector Set A node records a set of MPR-selector tuples (MS_addr, MS_time), describing the neighbors which have selected this node as a MPR. MS_addr is the 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.1.5. QMPR Set A node maintains a set of neighbors which are selected as QMPR. Their addresses are listed in the QMPR Set. Badis & A. Agha Expires September 2006 [Page 10] INTERNET-DRAFT QoS for OLSR March 2006 7.1.6. QMPR Selector Set A node maintains information for each neighbor which has selected the node as a QMPR and their QoS conditions on links. It records a set of QMPR-selector tuples (QMS_addr, QMS_bandwidth, QMS_delay, QMS_met_1, ..., QMS_met_n, QMS_time). QMS_addr is the address of a node which has selected the node as QMPR, QMS_bandwidth, QMS_delay, QMS_met_1, ... and QMS_met_n designate the available bandwidth, delay and 1st to Nth additional metrics values respectively on the link between the node and its QMPR selector with address QMS_addr and QMS_time specifies the time at which a tuple expires and *MUST* be removed. In a node, the set of QMPR-selector tuples are denoted the "QMPR Selector Set". 7.2. HELLO Message Extension Format This section describes the HELLO message extension to support QoS requirements including available bandwidth, delay, etc. HELLO message extension is broadcasted to all one-hop neighbors, but are *not relayed* to further nodes. It contains: - a list of addresses of symmetric neighbors (to which there exists a symmetric link) and QoS values on links; - a list of addresses of heard neighbors and QoS values on links; - a list of MPRs and QoS values on links. - a list of QMPRs and QoS values on links. 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 Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | Badis & A. Agha Expires September 2006 [Page 11] INTERNET-DRAFT QoS for OLSR March 2006 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : . . . : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Link Code | Reserved | Link Message Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : etc. This is sent as the data-portion of the general packet format described in [2], with the "Message Type" set to HELLO_MESSAGE, the TTL field set to 1 (one). 7.2.1. Description of the fields "Reserved", "Htime", "Willingness", "Link Code", "Link Message Size" and "Neighbor Address" fields are described in [2]. 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 for MPRs 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: Badis & A. Agha Expires September 2006 [Page 12] INTERNET-DRAFT QoS for OLSR March 2006 - 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 12. - 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 13. 7.3. HELLO message extension 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 [2] for HELLO processing. Moreover, it adds and updates bandwidth, delay and the other QoS metrics values in Neighbor Set, 2-hop Neighbor, MPR Selector Set and QMPR Selector Set. 7.4. Multipoint relay (MPR) selection QOLSR applies the same heuristic used for the selection of MPRs in OLSR. MPR selection procedure is detailed in [2]. After selecting the MPRs among the neighbors, the link status of the corresponding 1-hop Badis & A. Agha Expires September 2006 [Page 13] INTERNET-DRAFT QoS for OLSR March 2006 neighbors is changed from SYM_LINK to MPR_LINK in the neighbor table. The MPR set is re-calculated when: - A change in the neighborhood is detected, i.e. either a symmetric link with a neighbor is failed, or a new neighbor with a symmetric link is added; or - A change is detected in the 2-hop neighborhood such that a symmetric link is either detected or broken between a 2-hop neighbor and a neighbour. 7.5. Quality of service multipoint relay (QMPR) selection The heuristic for the selection of multipoint relays in the standard OLSR does not take into account the bandwidth and delay information. It computes a multipoint relay set of minimal cardinality. Links with high bandwidth and low delay can be omitted. Consequently, the path calculated between two nodes using the known partial topology is not optimal (in terms of available bandwidth and delay) in the whole network. The decision of how each node selects its QMPRs is essential to determinate the optimal bandwidth and delay path in the network. In the QMPR selection, links with high bandwidth and low delay 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 maximum bandwidth and minimum delay. QMPR set allows a node to find optimal paths on the known partial topology having the same bandwidth performances that those on the whole network [4,5]. 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 neighbors. - 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. Badis & A. Agha Expires September 2006 [Page 14] INTERNET-DRAFT QoS for OLSR March 2006 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 shortest-widest path from z to x (z-->y-->x has the maximum bandwidth and minimum delay); 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). After selecting the QMPRs among the neighbors, the link status of the corresponding one-hop neighbors is changed from SYM_LINK to QMPR_LINK in the neighbor table. The QMPR set is re-calculated when: - A change in the neighborhood is detected, i.e. either a symmetric link with a neighbor is failed, or a new neighbor with a symmetric link is added; or - A change is detected in the 2-hop neighborhood such that a symmetric link is either detected or broken between a 2-hop neighbor and a neighbour; or - A change of bandwidth or delay on links of 1-hop or 2-hop neighborhood is detected. Therefore, a node measures the percentage change of previous bandwidth or delay on each link and the new values. If the bandwidth or delay percentage changes exceed BANDWIDTH_THRESHOLD or DELAY_THRESHOLD respectively [5, 6], a change is detected. Badis & A. Agha Expires September 2006 [Page 15] INTERNET-DRAFT QoS for OLSR March 2006 8. QMPR and QoS conditions information declaration 8.1. Topology information base Each node in the network maintains topological information and QoS conditions about the network. This information is acquired from TC messages and used for routing table calculations. 8.1.1. Topology Set For each destination in the network, a "Topology Tuple" (T_dest, T_last, T_bandwidth, T_delay, T_met_1, ..., T_met_n, T_seq, T_time) is recorded. T_dest is the address of a node, which may be reached in one hop from the node with the address T_last. T_bandwidth, T_delay, T_met_1, ... and T_met_n are bandwidth, delay and 1st to Nth additional metrics values respectively on the link between T_dest and T_last, 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.2. 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. 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 Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | Badis & A. Agha Expires September 2006 [Page 16] INTERNET-DRAFT QoS for OLSR March 2006 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS Multipoint Relay Selector Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : etc. 8.2.1. Description of the fields ANSN, Reserved and QoS Multipoint Relay Selector Address are described in [2]. 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 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. - 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 12. Badis & A. Agha Expires September 2006 [Page 17] INTERNET-DRAFT QoS for OLSR March 2006 - 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 13. 8.3. TC Message Extension Processing TC messages are generated by QMPRs and retransmitted by MPRs in order to diffuse the messages in the entire network. 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 on OLSR RFC3626. Moreover, it adds and updates QoS metrics values in Topology Set. 9. 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 neighbor set and the topology set. 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, R_next, R_dist, R_bandwidth, R_delay, R_met_1, ... and R_met_n which specifies that the node identified by R_dest is estimated to be R_dist hops away from the local node, and that the one hop neighbor node with address R_next is the next hop node in the route to R_dest. The bandwidth, delay and 1st to Nth additional metrics values of the selected path to R_dest 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 Badis & A. Agha Expires September 2006 [Page 18] INTERNET-DRAFT QoS for OLSR March 2006 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 [7]). 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 and topology sets. The shortest-widest path algorithm [6] 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. 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?|----------+ +--------------------------+ Badis & A. Agha Expires September 2006 [Page 23] INTERNET-DRAFT QoS for OLSR March 2006 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 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. 11. 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 Badis & A. Agha Expires September 2006 [Page 24] INTERNET-DRAFT QoS for OLSR March 2006 and message sizes (under which there is rejection) should be adjusted accordingly, considering the greater size of IPv6 addresses. 12. 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_ 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). 13. 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 Badis & A. Agha Expires September 2006 [Page 25] INTERNET-DRAFT QoS for OLSR March 2006 - 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. 14. 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 . | . | . . | . | . 15. IANA Considerations The type numbers for the extensions in section 4 are to be taken from the space of extensions to OLSR [2]. 16. 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. Badis & A. Agha Expires September 2006 [Page 26] INTERNET-DRAFT QoS for OLSR March 2006 17. References [1] 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. [2] T. Clausen and P. Jacquet. "Optimized Link State Routing Protocol". Request for Comments (Draft Standard) 3626. Internet Engineering Task Force, Oct. 2003. [3] H. Badis and K. Al Agha. "Distributed Algorithm for Multiple- metric Link State QoS Routing Problem". IEEE MWCN2003, Oct. 2003. [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 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. [6] 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. [7] Z. Wang and J. Crowcroft. "Quality of service routing for supporting multimedia applications". IEEE JSAC, vol. 14, pp. 1228-1234, Sept. 1996. [8] 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. Badis & A. Agha Expires September 2006 [Page 27] INTERNET-DRAFT QoS for OLSR March 2006 18. 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 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 19. 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. 20. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Badis & A. Agha Expires September 2006 [Page 28]