Internet DRAFT - draft-badis-manet-qolsr

draft-badis-manet-qolsr



IETF MANET Working Group                                     Hakim Badis
INTERNET-DRAFT           Institut Gaspard-Monge, Marne-la-Vallée, France 
Expires: August 9, 2007                                 Khaldoun A. Agha 
                                           LRI Laboratory, Orsay, France 
                                         Project Hipercom, INRIA, France  
                                                              March 2007

            Quality of Service for Ad hoc Optimized Link State
                        Routing Protocol (QOLSR)

                    draft-badis-manet-qolsr-05.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 August 9, 2007.

Copyright Notice

   Copyright (C) The Internet Society (2007).

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 August 2007                [Page 1]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


   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 August 2007                [Page 2]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


      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 August 2007                [Page 3]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
 

   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 04 to version 05

   - Restructured draft in order to improve readability and modularity.
 
   - Enhancement of oscillation-Avoidance at the source.


   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.



Badis & A. Agha              Expires August 2007                [Page 4]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
 

   - 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 August 2007                [Page 5]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


     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 August 2007                [Page 6]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
 

     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 August 2007                [Page 7]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


       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 August 2007                [Page 8]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
    

     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 August 2007                [Page 9]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
    

     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 August 2007               [Page 10]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   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 August 2007               [Page 11]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


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 August 2007               [Page 12]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


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 August 2007               [Page 13]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   
   
   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 August 2007               [Page 14]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   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 August 2007               [Page 15]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


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 August 2007               [Page 16]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


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 August 2007               [Page 17]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
 

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 August 2007               [Page 18]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
     

     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 August 2007               [Page 19]

INTERNET-DRAFT                   QoS for OLSR                 March 2007 


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 August 2007               [Page 20]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   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 August 2007               [Page 21]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
         

          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 August 2007               [Page 22]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   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 August 2007               [Page 23]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   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 August 2007               [Page 24]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


   - 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 August 2007               [Page 25]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   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 August 2007               [Page 26]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
 

     - 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 August 2007               [Page 27]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


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 August 2007               [Page 28]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
  

   For QoS flows that need to satisfy a number of QoS constraints like 
   badnwidth>Threshold_bandwidth and/or delay<Threshold_delay, etc.,
   an efficient scalable heuristic based on Lagrangian relaxation is 
   applied [3]. This heuristic can treat two, three and four-metrics and 
   provides a polynomial solution with a good approximation bound that
   yields high performance in finding feasible paths.


15.  Oscillation problem

   QOLSR protocol suffers from some defects related to QoS information
   diffused in TC messages. There are cases in which a source node
   continuously changes a flow's next hop (oscillation problem) 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. 

  To avoid it we have proposed two solutions (See [11]):


15.1.  Oscillation-Avoidance at the source

   If a node keeps information about the next hop alone, it loses the
   ability to distinguish the part of used capacity that is induced by
   the given flow from other ones.

   For oscillation-avoidance at the source, each source node MUST
   remember not only the next hop but also all the subsequent hops on
   the path towards the destination. This information can be stored in
   the topology tuples, however, for performance considerations, it
   would be much better to keep it on a separate topology graph. This
   graph is maintained along with the topology tuples and is much more
   useful for routes calculation.

   When a source node detects a change in network conditions (via HELLO
   and TC messages), it checks for each generated QoS flow, if the 
   respective paths can be kept without breaking the flows' QoS 
   requirements. In other words, for each generated QoS flow it adds its
   corresponding rate to every arc on the respective path. Then it 
   checks whether the path is still satisfying the QoS requirement; if
   not, a new one is calculated using QOLSR.









Badis & A. Agha              Expires August 2007               [Page 29]

INTERNET-DRAFT                   QoS for OLSR                 March 2007 


15.2.  Distributed Oscillation-Avoidance

   When a node detects a change in network conditions (via HELLO and TC
   messages), it checks for each QoS flow, either generated locally or

   forwarded from another node, if the respective next hops can be kept
   without breaking the flows' QoS requirements. This is achieved by
   applying the following distributed rule (Oscillation-Avoidance 1:
   OA1): each node accounts the amount of traffic sent for each flow and
   adds the resulting rate to every arc on each feasible path starting
   from the current next hop towards the destination.  Then it checks if
   at least one of the paths is satisfying the QoS requirements; if such
   a path does not exist, a new one is calculated starting from the 
   current node and the next hop is changed, otherwise the next hop is
   kept the same.

   If two distinct nodes initiate some QoS traffic based on the same
   knowledge of the network, they might choose paths that share common
   arcs, possibly overflowing the arcs' capacity. We call the phenomenon
   flow collision. 

  The next Figure shows a simple case of flow collision between Source1-
  Destination1 and Source2-Destination2 QoS flows.

                   Source1      a       Source2

                       X---------X---------X
                                 |
                                 |
                                 |
                       X---------X---------X         
                 Destination1    b    Destination2


   The use of the oscillation-avoidance rule does not help, as each node
   would keep sending traffic along the same paths, since they cannot
   see by what amount the capacity is overflowed. 

   To estimate the amount of overflow of the arcs' capacities, we have

   proposed to take into account the packet loss ratio on each arc. As a
   source node can block the transmitting process when too much traffic
   is sent, an intermediate node has no other choice than to drop excess
   traffic when its buffers are full. Thus, the excess bandwidth of an
   arc could be estimated using the proportion of lost data. This
   information is accounted for each link by the forwarding nodes and is




Badis & A. Agha              Expires August 2007               [Page 30]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
 

   diffused in the TC messages. This way, the amount of overflow is
   known to each node in the network and enables then to take turns to
   find alternative paths (OA2 rule: OA1 rule plus taking into account
   the lost packet ratio).

   Nevertheless, the new rule alone is not enough to prevent flows from

   colliding: there is no way that nodes of two colliding flows behave
   differently in response to arc overflow.

   Therefore, some asymmetry has to be introduced to enable nodes of

   colliding flows to take different decisions regarding route change.
   This asymmetry can be achieved with the use of our proposed backoff-
   based solution. The idea is that the first node in the flow's current
   path that precedes an overflowed arc and that has an alternate route
   satisfying the flow's QoS requirement should be considered for route
   switching. This node should initialize a random backoff timer and
   maintain the current next hop as long as the timer has not expired.
   At timer expiration, the node applies OA2 again and if the flow keeps
   colliding, then the node calculates a new path using standard QOLSR,
   instead of keeping the next hop. The node responsible for the switch
   is chosen using the following method: each node applies the OA2 rule
   and notifies the next hop if it is determined to have an alternate
   route, otherwise it waits for a notification from its preceding node.   

   On reception of a notification, a node applies the OA2 rule if it has
   not done so already and notifies its next hop if it is determined to
   have an alternate route and so on. If the application of OA2 gives a
   negative answer regarding alternate routes from the next hop, the
   current node is the one that should switch the flow. It then extracts
   the source address of the notification message which is the address
   of the preceding node on the current path and removes this node from

   the topology for alternate path calculation. Removal of the preceding
   node from the topology avoids finding paths that would route the flow
   back to it.












Badis & A. Agha              Expires August 2007               [Page 31]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   The proposed QoS model is as follows:
       
               +----------+  
   +---------->| 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 August 2007               [Page 32]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   

   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 August 2007               [Page 33]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
  

   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 August 2007               [Page 34]

INTERNET-DRAFT                   QoS for OLSR                 March 2007


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 August 2007               [Page 35]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
  

   [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
   Institut Gaspard-Monge
   Computer science research laboratory
   University of Marne-la-Vallée
   F-77454 Marne-la-Vallée cedex 2, France
   Phone: +33 1 60 95 77 49
   EMail: Hakim.Badis@univ-mlv.fr

   Khaldoun Al Agha
   LRI Laboratory
   Paris-sud University, 
   91405 Orsay, France
   Phone: +33 1 6915 6617
   


Badis & A. Agha              Expires August 2007               [Page 36]

INTERNET-DRAFT                   QoS for OLSR                 March 2007
   
   
   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 IETF Trust (2007).

   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, THE IETF TRUST 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 provided by the IETF
   Administrative Support Activity (IASA).






















Badis & A. Agha             Expires August 2007                [Page 37]