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]
