IETF MANET Working Group Hakim Badis INTERNET-DRAFT Khaldoun A. Agha Expires: September 2005 LRI Laboratory, Orsay, France Project Hipercom, INRIA, France April 2005 Quality of Service for Ad hoc Optimized Link State Routing Protocol (QOLSR) Status of this Memo By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, and any of which I become aware will be disclosed, in accordance with RFC3668. This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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 April 14, 2005. Copyright Notice Copyright (C) The Internet Society (2004). All Rights Reserved. Abstract The Optimized Link State Routing (OLSR) protocol for mobile ad hoc networks is an optimization of the classical link state algorithm tailored to the requirements of a mobile wireless LAN. It reduces the message overhead as compared to a classical flooding mechanism and offers distributed partial link state information in the network using MPRs. Badis & A. Agha Expires September 2005 [Page 1] INTERNET-DRAFT QoS for OLSR April 2005 OLSR provides optimal routes in terms of number of hops. In order to provide and fulfill quality of service (QoS) requirements, extensions can be added to OLSR functioning and control messages format (HELLO and TC). These extensions specify metrics like available bandwidth, delay, jitter, loss probability, power consumption, etc., which must be used for Multipoint relay (MPR) selection and routing table calculation. This memo describes the QOLSR protocol, which is an enhancement of OLSR to support multiple-metric. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. QOLSR Terminology . . . . . . . . . . . . . . . . . . . . . . 4 4. Useful Definitions. . . . . . . . . . . . . . . . . . . . . . 4 5. QOLSR Characteristics . . . . . . . . . . . . . . . . . . . . 5 6. QOLSR Functioning . . . . . . . . . . . . . . . . . . . . . . 6 7. Neighbor sensing and QoS measurement. . . . . . . . . . . . . 8 7.1. Neighbor sensing and QoS measurement information base. . 8 7.1.1. Neighbor Set . . . . . . . . . . . . . . . . . . 8 7.1.2. 2-hop Neighbor Set. . . . . . . . . . . . . . . . 9 7.1.3. MPR Selector Set . . . . . . . . . . . . . . . . 9 7.2. HELLO Message extension Format . . . . . . . . . . . . . 9 7.2.1. Description of the fields . . . . . . . . . . . . 10 7.3. HELLO Message extension processing . . . . . . . . . . . 11 7.4. Multipoint relay selection . . . . 12 8. Multipoint relay information and QoS conditions declaration . 14 8.1. Topology information base. . . . . . . . . . . . . . . . 14 8.1.1. Topology Set . . . . . . . . . . . . . . . . . . 14 8.2. TC Message Extension Format. . . . . . . . . . . . . . . 14 8.2.1. Description of the fields . . . . . . . . . . . . 15 8.3. TC Message Extension Processing . . . . . . . . . . . . 16 9. Routing table calculation . . . . . . . . . . . . . . . . . . 16 10. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . 17 11. Proposed Values for Constants . . . . . . . . . . . . . . . 18 12. Delay metric representation in control messages . . . . . . 18 13. TLV encoding for QoS metrics . . . . . . . . . . . . . . . . 19 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . 19 15. Security Considerations . . . . . . . . . . . . . . . . . . 19 16. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 17. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 20 18. Full Copyright Statement . . . . . . . . . . . . . . . . . . 21 19. Acknowledgment . . . . . . . . . . . . . . . . . . . . . . 21 Badis & A. Agha Expires September 2005 [Page 2] INTERNET-DRAFT QoS for OLSR April 2005 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 quality of service is taken into account. For more details, please see the OLSR base specification [1]. 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 MPRs and then flooded in the network by TC messages to calculate routing tables. The heuristic for the selection of MPRs in OLSR limits its number in the network and ensures that the overhead is as low as possible. With this heuristic, good quality links may be hidden to other nodes in the network. Optimal paths found by QOLSR using MPR selection of OLSR heuristic in the known partial topology are not optimal in the whole topology [4]. A new heuristic is used by QOLSR to ensure this problem. This protocol 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 00 to version 01 Badis & A. Agha Expires September 2005 [Page 3] INTERNET-DRAFT QoS for OLSR April 2005 - Generalization for all possible QoS metrics. Available bandwidth and delay metrics are default QoS parameters for QOLSR. All other metrics are optional parameters and used according to QoS flows requirements or network scenarios. - Introduction of an efficient QoS routing algorithm based on Lagrange relaxation [3], which provides a polynomial heuristic solution to multiple-metric constraints. 3. QOLSR Terminology The QOLSR protocol uses the same terminology defined in [2] but with single interface. 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. Badis & A. Agha Expires September 2005 [Page 4] INTERNET-DRAFT QoS for OLSR April 2005 * 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 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? 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?) Badis & A. Agha Expires September 2005 [Page 5] INTERNET-DRAFT QoS for OLSR April 2005 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. * 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 available bandwidth and delay) 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. As in OLSR, all nodes, selected as MPRs, MUST declare the links QoS information to their MPR selectors using TC messages. QOLSR carried out different functions which are required to perform the task of routing. Badis & A. Agha Expires September 2005 [Page 6] INTERNET-DRAFT QoS for OLSR April 2005 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 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 of the network independently selects its own set of MPRs. The MPR set is calculated to contain a subset of the 1-hop neighbors which provides maximum bandwidth and minimum delay to each 2-hop neighbor. The MPR set needs not to be optimal, however it SHOULD be small enough to minimize the flooding of broadcast 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. MPRs of a given node are declared in the subsequent HELLOs transmitted by this node, so that the information reaches the MPRs themselves. The MPR 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. * MPR and QOS conditions information declaration Topology Control extension messages are sent by each MPR node in the network at regular intervals to declare its MPR selector set and QoS conditions. The information diffused in the network by these TC messages will help each node to calculate its routing table. Badis & A. Agha Expires September 2005 [Page 7] INTERNET-DRAFT QoS for OLSR April 2005 * 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 MPR 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 bandwidth and delay metrics or a distributed algorithm based Lagrangian relaxation for multiple metrics (See 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 and MPR 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 (MPR, symmetric, heard), N_Willingness is an integer between 0 and 7 (speciefies 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 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. Badis & A. Agha Expires September 2005 [Page 8] INTERNET-DRAFT QoS for OLSR April 2005 7.1.2. 2-hop Neighbor Set As only bandwidth and delay values on links to 2-hop neighbors are used for 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 or MPR 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 2-hop Neighbor Set, only bandwidth and delay are recorded 7.1.3. MPR Selector Set A node maintains information for each neighbor which has selected the node as a MPR and their QoS conditions on links. It records a set of MPR-selector tuples (MS_addr, MS_bandwidth, MS_delay, MS_met_1, ..., MS_met_n, MS_time). MS_addr is the address of a node which has selected the node as MPR, MS_bandwidth, MS_delay, MS_met_1 , ... and MS_met_n designate the available bandwidth, delay and 1st to Nth additional metrics values respectively on the link between the node and its MPR selector with address MS_addr and MS_time specifies the time at which a tuple expires and *MUST* be removed. 7.2. HELLO Message Extension Format This section describes the HELLO message extension to support QoS requirements including available bandwidth and delay. HELLO message extension is broadcast 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 to those neighbors; - a list of addresses of heard neighbors and QoS values on links to those neighbors; - a list of MPRs and QoS values on links to those MPR neighbors. Badis & A. Agha Expires September 2005 [Page 9] INTERNET-DRAFT QoS for OLSR April 2005 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) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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]. Badis & A. Agha Expires September 2005 [Page 10] INTERNET-DRAFT QoS for OLSR April 2005 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: - 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 Badis & A. Agha Expires September 2005 [Page 11] INTERNET-DRAFT QoS for OLSR April 2005 adds and updates bandwidth, delay and the other QoS metrics values in Neighbor Set, 2-hop Neighbor Set and MPR Selector Set. 7.4. Multipoint relay 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 MPRs is essential to determinate the optimal bandwidth and delay path in the network. In the MPR selection, links with high bandwidth and low delay SHOULD not be omitted. With QOLSR, each node in the network selects independently its own set of MPRs. 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 2-hop neighbors with maximum bandwidth and minimum delay. The following specifies a proposed heuristic for selection of MPRs. 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. - D(x,y): Degree of one hop neighbor node y (where y is a member of N(x)), is defined as the number of symmetric 1-hop neighbors of node y excluding the node x and all the symmetric 1-hop neighbors of node x, i.e., D(x,y)= number of elements of N(y) - {x} - N(x). - MPR(x): The multipoint relay set of node x which is running this algorithm. The proposed heuristic is as follows: Badis & A. Agha Expires September 2005 [Page 12] INTERNET-DRAFT QoS for OLSR April 2005 1. Start with an empty MPR set MPR(x); 2. Calculate D(x,y), for all nodes y in N(x); 3. While there still exist nodes in N2(x) that are not covered by MPR(x): 3.1. Let z be one of those nodes; 3.2. Select that node in N(x) as MPR which provide the shortest-widest path (path with maximum bandwidth and minimum delay) to reach z; 3.3. In case of a tie in the above step, select that node which reaches the maximum number of uncovered nodes in N2(x); 3.4. Mark z as covered; 3.5. For each node in N(x) which is not in MPR(x), calculate the number of nodes that are reachable through it among the nodes in N2(x) and which are not yet covered by MPR(x); After selecting the MPRs among the neighbors, the link status of the corresponding one-hop 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; 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], a change is detected and the MPR set is re-calculated. Badis & A. Agha Expires September 2005 [Page 13] INTERNET-DRAFT QoS for OLSR April 2005 8. Multipoint relay information and QoS conditions 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 node in the network to declare its MPR Selector set and its QoS conditions. I.e., the TC message contains the list of neighbors which have selected the sender node as a MPR and their QoS constraints (bandwidth, delay and 1st to Nth additional metrics values). The sequence number (MSSN) associated with this MPR 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Multipoint Relay Selector Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (bandwidth and delay) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | QoS fields values (other QoS metrics) | Badis & A. Agha Expires September 2005 [Page 14] INTERNET-DRAFT QoS for OLSR April 2005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 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 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 MPRs 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. - The remaining 32-bits represent the other QoS parameters on link between the MPR node and its MPR selector. Badis & A. Agha Expires September 2005 [Page 15] INTERNET-DRAFT QoS for OLSR April 2005 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 broadcasted and retransmitted by the 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 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 [6]). So, the combination of any two or more additive (delay, delay jitter, hop-count, cost, Badis & A. Agha Expires September 2005 [Page 16] INTERNET-DRAFT QoS for OLSR April 2005 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 QoS flows that need to maximize the available bandwidth and minimize the delay, a shortest-widest path algorithm is run on the graph generated by neighbor and topology sets. The shortest-widest path algorithm [5] 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= 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 Badis & A. Agha Expires September 2005 [Page 18] INTERNET-DRAFT QoS for OLSR April 2005 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. 13. 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 . | . | . . | . | . 14. IANA Considerations The type numbers for the extensions in section 4 are to be taken from the space of extensions to OLSR [2]. 15. 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. 16. 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. Badis & A. Agha Expires September 2005 [Page 19] INTERNET-DRAFT QoS for OLSR April 2005 [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, A. Munaretto, K. Al Agha, and G. Pujolle. "QoS for Ad hoc Networking Based on Multiple Metrics: Bandwidth and Delay". IEEE MWCN2003, Oct. 2003. [6] Z. Wang and J. Crowcroft. "Quality of service routing for supporting multimedia applications". IEEE JSAC, vol. 14, pp. 1228-1234, Sept. 1996. 17. Authors' Addresses Hakim Badis LRI Laboratory Paris-sud University, 91405 Orsay, France Phone: +33 1 6915 6591 EMail: Badis@lri.fr 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 Badis & A. Agha Expires September 2005 [Page 20] INTERNET-DRAFT QoS for OLSR April 2005 18. Full Copyright Statement Copyright (C) The Internet Society (2004). 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. 19. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Badis & A. Agha Expires September 2005 [Page 21]