draft-ietf-manet-olsr-04.txt   draft-ietf-manet-olsr-05.txt 
INTERNET-DRAFT Philippe Jacquet INTERNET-DRAFT Thomas Clausen
IETF MANET Working Group Paul Muhlethaler IETF MANET Working Group Philippe Jacquet
Expiration: 02 September 2001 Amir Qayyum Expiration: 30 April 2002 Anis Laouiti
Anis Laouiti Pascale Minet
Paul Muhlethaler
Amir Qayyum
Laurent Viennot Laurent Viennot
Thomas Clausen
INRIA Rocquencourt, France INRIA Rocquencourt, France
2 March 2001 31 October 2001
Optimized Link State Routing Protocol Optimized Link State Routing Protocol
draft-ietf-manet-olsr-04.txt
draft-ietf-manet-olsr-05.txt
Status of this Memo Status of this Memo
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026 except that the right to all provisions of Section 10 of RFC 2026.
produce derivative works is not granted.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that other
other groups may also distribute working documents as groups may also distribute working documents as Internet-Drafts.
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six Internet-Drafts are draft documents valid for a maximum of six months
months and may be updated, replaced, or obsoleted by other and may be updated, replaced, or obsoleted by other documents at any
documents at any time. It is inappropriate to use Internet-Drafts time. It is inappropriate to use Internet-Drafts as reference
as reference material or to cite them other than as "work in material or to cite them other than as "work in progress."
progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Abstract Abstract
This document describes the Optimized Link State Routing (OLSR) This document describes the Optimized Link State Routing (OLSR)
protocol for mobile ad hoc networks. The protocol is an protocol for mobile ad hoc networks. The protocol is an optimization
optimization of the pure link state algorithm tailored to the of the pure link state algorithm tailored to the requirements of a
requirements of a mobile wireless LAN. The key concept used in the mobile wireless LAN. The key concept used in the protocol is that of
protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are multipoint relays (MPRs) [1], [2]. MPRs are selected nodes which
selected nodes which forward broadcast messages during the forward broadcast messages during the flooding process. This
flooding process. This technique substantially reduces the message technique substantially reduces the message overhead as compared to a
overhead as compared to pure flooding mechanism where every node pure flooding mechanism, where every node retransmits each message
retransmits each message when it receives the first copy of the when it receives the first copy of the message. In OLSR, information
packet. In OLSR, information flooded in the network "through" flooded in the network "through" these MPRs is also "about" the MPRs.
these MPRs is also "about" the MPRs. Thus a Thus, a second optimization is achieved by minimizing the "contents"
second optimization is achieved by minimizing the "contents" of of the control messages flooded in the network. Hence, as contrary to
the control messages flooded in the network. Hence, as contrary to the classic link state algorithm, a node declares only a small subset
the classic link state algorithm, only a small subset of links of links to its neighbor nodes, rather than all links to all
with the neighbor nodes are declared instead of all the neighbors. This information is then used by the OLSR protocol for
links. This information is then used by the OLSR protocol for route calculation. As a consequence hereof, the routes contain only
route calculation. As a consequence hereof, the routes contain the MPRs as intermediate nodes from a Source to a Destination. OLSR
only the MPRs as intermediate nodes from a Source to a provides optimal routes (in terms of number of hops). The protocol is
Destination. OLSR provides optimal routes (in terms of number of particularly suitable for large and dense networks as the technique
hops). The protocol is particularly suitable for large and dense of MPRs works well in this context.
networks as the technique of MPRs works well in this context.
Contents Table of Contents
Status of This Memo 1 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
Abstract 1 1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . 4
1. Introduction 3 1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . 5
2. Changes 3 1.3. Applicability Section . . . . . . . . . . . . . . . . . . 7
3. OLSR terminology 4 1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . 7
4. Applicability Section 5 1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . 8
4.1 Networking Context 5
4.2 Protocol Characteristics and Mechanisms 6 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 9
5. Protocol Overview 8 2.1. Packet Format and Forwarding . . . . . . . . . . . . . . . 10
6. Multipoint relays 9 2.1.1. Protocol and Port Number . . . . . . . . . . . . . . . . 11
7. Protocol functioning 10 2.1.2. Multiple Interfaces and Main Address . . . . . . . . . . 11
7.1 Protocol and port number 10 2.1.3. Packet Format . . . . . . . . . . . . . . . . . . . . . 11
7.2 Packet format 10 2.1.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . 12
7.2.1 Packet Header 12 2.1.3.2. Message Header . . . . . . . . . . . . . . . . . . . . 12
7.2.2 Message Header 12 2.1.4. Packet Processing and Message Flooding . . . . . . . . . 13
7.2.3 Packet Processing 13 2.1.5. Message Emission and Jitter . . . . . . . . . . . . . . 16
7.3 Neighbor sensing 15
7.3.1 Neighbor sensing information base 15 2.2. Neighbor Sensing . . . . . . . . . . . . . . . . . . . . . 17
7.3.2 HELLO message broadcast 16 2.2.1. HELLO Message Format . . . . . . . . . . . . . . . . . . 18
7.3.3 HELLO message processing 19 2.2.2. Neighbor Sensing Information Base . . . . . . . . . . . 20
7.4 Multipoint relay selection 21 2.2.2.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . 20
7.5 Multipoint relay information declaration 22 2.2.2.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 20
7.5.1 Topology information base 22 2.2.2.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 21
7.5.2 TC message broadcast 23 2.2.2.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . 21
7.5.3 TC message processing 24 2.2.3. HELLO Message Generation . . . . . . . . . . . . . . . . 21
7.6 Routing table calculation 26 2.2.4. HELLO Message Processing . . . . . . . . . . . . . . . . 22
7.7.Link layer notification 27 2.2.5. Multipoint Relay Selection . . . . . . . . . . . . . . . 25
8. Packet Forwarding 28 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes . . . . . 27
8.1 Data packet forwarding 28 2.2.6. Advanced Neighbor Sensing Functioning . . . . . . . . . 27
8.2 Control message forwarding 28 2.2.6.1. Link Hysteresis . . . . . . . . . . . . . . . . . . . 28
9. Proposed values for constants 29 2.2.6.2. Optional Link layer notification . . . . . . . . . . . 29
10. Sequence numbers 29 2.3. Topology Discovery . . . . . . . . . . . . . . . . . . . . 30
11. References 30 2.3.1. Multipoint Relay Information Declaration . . . . . . . . 30
12. Authors' addresses 31 2.3.1.1. Topology Information Base . . . . . . . . . . . . . . 30
2.3.1.2. TC Message Generation . . . . . . . . . . . . . . . . 31
2.3.1.3. TC Message Processing . . . . . . . . . . . . . . . . 32
2.3.2. Multiple Interface Association . . . . . . . . . . . . . 34
2.3.2.1. Interface Association Information Base . . . . . . . . 34
2.3.2.2. MID Broadcast . . . . . . . . . . . . . . . . . . . . 35
2.3.2.3. MID Message Processing . . . . . . . . . . . . . . . . 36
2.3.3. Associated Networks and Hosts . . . . . . . . . . . . . 37
2.3.3.1. Host and Network Association Information Base . . . . 38
2.3.3.2. Host and Network Association Message Broadcast . . . . 38
2.3.3.3. HNA Message Processing . . . . . . . . . . . . . . . . 39
2.3.3.4. Optional Link layer notification . . . . . . . . . . . 40
2.3.4. Routing Table Calculation . . . . . . . . . . . . . . . 41
3. Node Configuration . . . . . . . . . . . . . . . . . . . . . 43
3.1. Address Assignment . . . . . . . . . . . . . . . . . . . . 43
3.2. Routing Configuration . . . . . . . . . . . . . . . . . . 43
3.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . 44
3.4. Control Message Forwarding . . . . . . . . . . . . . . . . 44
4. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . 44
5. Proposed Values for the Constants . . . . . . . . . . . . . 44
6. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . 45
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 46
1. Introduction 1. Introduction
This Optimized Link State Routing protocol inherits the concept of The Optimized Link State Routing Protocol (OLSR) is developed for
forwarding and relaying from HIPERLAN (a MAC layer protocol) which mobile ad hoc networks. It operates as a table driven and proactive
is standardized by ETSI [3]. The OLSR protocol is developed in the protocol, thus exchanges topology information with other nodes of the
IPANEMA project (part of Euclid program) and in the PRIMA project network regularly. The nodes which are selected as a multipoint relay
(part of RNRT program). by some neighbor nodes announce this information periodically in
their control messages. Thereby, a node announces to the network,
that it has reachability to the nodes which have selected it as MPR.
In route calculation, the MPRs are used to form the route from a
given node to any destination in the network. The protocol uses the
MPRs to facilitate efficient flooding of control messages in the net-
work.
This protocol is developed for mobile ad hoc networks. It operates MPRs are selected by a node among its one hop neighbors with "symmet-
as a table driven and proactive protocol and exchanges topology ric", i.e. bi-directional, link. Therefore, selecting the route
information with other nodes of the network at regular intervals. through MPRs automatically avoids the problems associated with data
The nodes which are selected as a multipoint relay by some packet transfer over uni-directional links (such as the problem of
neighbor nodes announce this information periodically in their not getting link-layer acknowledgments for data packets at each hop)
control messages. The protocol uses the MPRs to facilitate
efficient flooding of control messages in the network. In route
calculation, the MPRs are used to form the route from a given node
to any destination in the network.
MPRs are selected by a node among its one hop neighbors with OLSR is developed to work independently from other protocols. Like-
"symmetric", i.e. bi-directional, link. Therefore, selecting the wise, OLSR makes no assumptions about the underlying link-layer.
route through MPRs automatically avoids the problems associated
with data packet transfer on uni-directional links (such as the
problem of not getting link-layer acknowledgments for the data
packets at each hop)
The OLSR protocol is developed to work independently from other OLSR inherits the concept of forwarding and relaying from HIPERLAN (a
protocols. But it can be adapted to operate with a protocol (like MAC layer protocol) which is standardized by ETSI [3]. The protocol
IMEP [4]) which could provide common functionalities such as is developed in the IPANEMA project (part of the Euclid program) and
neighbor sensing, multipoint relaying, security authentication, in the PRIMA project (part of the RNRT program).
etc.
2. Changes 1.1. Changes
Major changes from version 04 to version 05
- Introduction of support for multiple interfaces
- Introduction of support for associated hosts and networks.
- Introduction of support for advanced neighbor sensing through
hysteresis.
- Modularity between neighbor sensing and topology discovery
emphasized.
Major changes from version 03 to version 04 Major changes from version 03 to version 04
- Finalized the generic packet/message format to - Finalized the generic packet/message format to include fea-
include features for scope-limited (diameter-bound) tures for scope-limited (diameter-bound) flooding of messages
flooding of messages and to handle duplicate messages. and to handle duplicate messages.
- Editorial changes towards language consistency. - Editorial changes towards language consistency.
Major changes from version 02 to version 03 Major changes from version 02 to version 03
- Introduction of assigned port number for use with OLSR. - Introduction of assigned port number for use with OLSR.
- The packet format now uses "message length" rather than an - The packet format now uses "message length" rather than an
offset to the next message. offset to the next message.
- Optional section describing how link-layer notifications - Optional section describing how link-layer notifications can
can be utilized included. be utilized included.
Major changes from version 01 to version 02 Major changes from version 01 to version 02
- Introduction of a unified packet format for encapsulation of - Introduction of a unified packet format for encapsulation of
all messages being exchanged between nodes. This also serves all messages being exchanged between nodes. This also serves
to facilitate extensions in future versions of the protocol to facilitate extensions in future versions of the protocol
(i.e. introduction of new protocol messages) without breaking (i.e. introduction of new protocol messages) without breaking
backwards compatibility. backwards compatibility.
- Removal of "Power Conservation" from this draft. Power - Removal of "Power Conservation" from this draft. Power Conser-
Conservation may be considered as an extension to the basic vation may be considered as an extension to the basic routing
routing capabilities, and the information is therefore moved capabilities.
to draft-ietf-manet-olsr-extensions-00.txt.
3. OLSR Terminology 1.2. OLSR Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
this document are to be interpreted as described in RFC2119 [9]. document are to be interpreted as described in RFC2119 [5]. The OLSR
The OLSR protocol uses the following terminology, in addition to protocol uses the following terminology:
the terms defined in [5].
connection
A communication channel or medium *on the same physical
interface*, over which the nodes can communicate with each
other.
holding time
The lifetime associated with an entry in any table. An entry is
kept in the table for a period of time, equal to its holding
time. If the entry is not refreshed during this period, it is
removed from the table when the holding time expires.
multipoint relay (MPR) multipoint relay (MPR)
A node which is selected by its one-hop neighbor, node X, to A node which is selected by its one-hop neighbor, node X, to
"re-transmit" all the broadcast messages that it receives from "re-transmit" all the broadcast messages that it receives from
X, provided that the same message is not already received, and X, provided that the same message is not already received, and
the time to live field of the message is greater than zero. the time to live field of the message is greater than one.
multipoint relay selector (MPR selector, MS) multipoint relay selector (MPR selector, MS)
A node which has selected its one-hop neighbor, node X, as its A node which has selected its one-hop neighbor, node X, as its
multipoint relay, will be called a multipoint relay selector multipoint relay, will be called a multipoint relay selector
of node X. of node X.
node node
A MANET router which implements this Optimized Link State A MANET router which implements this Optimized Link State
Routing protocol. Routing protocol.
symmetric link interface
A bi-directional *link* between two neighbor nodes, i.e. node X
and node Y where both can hear each other.
4. Applicability Section
This section dictates the characteristics of the OLSR protocol as
specified in the Applicability Statement draft [6].
4.1. Networking Context
OLSR is well suited to large and dense mobile networks, as the
optimi- zation achieved using the MPRs works well in this
context. The larger and more dense a network, the more
optimization can be achieved as compared to the normal link state
algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its
local information to route packets.
OLSR is well suited for networks, where the traffic is random and
sporadic between "several" nodes rather than being almost
exclusively between a small specific set of nodes. The performance
of the protocol, compared to a reactive protocol, is even better
if these [source, destination] pairs change with time [8]. Such
changes may initiate substantial traffic (Query flooding) in case
of reactive protocol, but nothing in OLSR, as the routes are
maintained for each known destination all the time.
4.2. Protocol Characteristics and Mechanisms
* Does the protocol provide shortest path routes ?
Yes.
* Does the protocol provide support for unidirectional links? (if
so, how?)
No. However, the use of uni-directional links may easily be
enabled through optional extensions to the protocol.
* Does the protocol require the use of tunneling? (if so, how?)
No. A network device participating in the MANET (it is usually
wireless). A node may have several interfaces, each one pos-
sessing its own IP address.
* Does the protocol require using some form of source routing? (if link
so, how?)
No. A link is a pair of interfaces (from two different nodes) sus-
ceptible to hear one another (i.e. one may be able to receive
traffic from the other). A node is said to have a link to
another node when one of its interface has a link to one of
the interfaces of the other node.
* Does the protocol require the use of periodic messaging? (if so, neighbor interface
how?)
Yes. Periodically, each node in the network sends a message An interface I is a neighbor interface of an interface J if J
containing the addresses of the neighbors which have selected can hear I (i.e. it is possible to send traffic from I to J).
that node as a MPR. This information enables other nodes to
build routes to that node through the MPRs.
* Does the protocol require the use of reliable or sequenced packet sender interface
delivery? (if so, how?)
No. The sender interface of a control message is the neighbor
interface over which the message has been transmitted.
* Does the protocol provide support for routing through a multi- receiver interface
technology routing fabric? (if so, how?)
No. However, provisions for multiple interfaces may easily be The reciever interface of a control message is the (local)
enabled through extensions to the protocol. interface, over which a control message has been recieved.
* Does the protocol provide support for multiple hosts per router? neighbor node
(if so, how?)
Yes. The hosts are added to the MPR selector set of the node A node X is a neighbor node of node Y if node Y can hear node
(router), which will then announce that the hosts can be X (i.e. one of X interfaces is a neighbor interface of some
reached through that node. interface of Y).
* Does the protocol support the IP addressing architecture? (if so, symmetric link
how?)
Yes. Nodes are assigned and addressed by regular IP-addresses. A bi-directional link between two interfaces, i.e. interface I
and interface J where both can hear each other.
* Does the protocol require link or neighbor status sensing (if so, symmetric neighborhood
how?) The symmetric neighborhood of any node X is the set of nodes
which have at least one symmetric link to X.
Yes. The protocol requires link status sensing. This service is symmetric 2-hop neighborhood
provided by sending/receiving periodic HELLO messages to/from The symmetric 2-hop neighborhood of X is the set of nodes
one hop neighbors. which don't have a symmetric link to X but have a symmetric
link to the symmetric neighborhood of X.
* Does the protocol depend on a central entity? (if so, how?) main address
No. The main address of a node, which will be used in OLSR control
traffic as the "originator address" of all messages emitted by
this node. It is the address of one of its interfaces.
* Does the protocol function reactively? (if so, how?) 1.3. Applicability Section
No. OLSR is a proactive routing protocol for mobile ad-hoc networks
(MANETs). It is well suited to large and dense mobile networks, as
the optimization achieved using the MPRs works well in this context.
The larger and more dense a network, the more optimization can be
achieved as compared to the classic link state algorithm. OLSR uses
hop-by-hop routing, i.e. each node uses its local information to
route packets.
* Does the protocol function proactively? (if so, how?) OLSR is well suited for networks, where the traffic is random and
sporadic between "several" nodes rather than being almost exclusively
between a small specific set of nodes. The performance of the proto-
col, compared to a reactive protocol, is even better if these
[source, destination] pairs change with time [4]. Such changes may
initiate substantial traffic (query flooding) in case of a reactive
protocol, but nothing in OLSR, as the routes are maintained for each
known destination all the time.
Yes. Each node periodically sends information about its MPR 1.4. Protocol Overview
selectors, which enables the nodes to construct routes to these
MPR selectors through the node.
* Does the protocol provide loop-free routing? (if so, how?) OLSR is a proactive routing protocol for mobile ad hoc networks. The
protocol inherits the stability of a link state algorithm and has the
advantage of having routes immediately available when needed due to
its proactive nature. OLSR is an optimization over the pure link
state protocol, tailored for mobile ad hoc networks.
Yes. As the protocol uses a link state algorithm, routing is Firstly, it reduces the size of the control messages: rather than
loop-free when in a stable state. declaring all links, a node declares only a subset of links with its
neighbors, namely the links to those nodes which are its MPR selec-
tors. Secondly, OLSR minimizes flooding of control traffic by using
only selected nodes, called MPRs, to diffuse its control messages.
This technique significantly reduces the number of retransmissions in
a flooding or broadcast procedure.
* Does the protocol provide for sleep period operation? (if so, how?) OLSR MAY optimize the reactivity to topological changes by reducing
the maximum time interval for periodic control message transmission.
Furthermore, as OLSR continuously maintains routes for all destina-
tions in the network, the protocol is beneficial for traffic patterns
where a large subset of nodes are communicating with another large
subset of nodes, and where the [source,destination] pairs are chang-
ing over time. The protocol is particularly suited for large and
dense networks, as the optimization done using MPRs works well in
this context. The larger and more dense a network, the more optimiza-
tion can be achieved as compared to the classic link state algorithm.
No. However, provisions for sleep-operation may easily be OLSR is designed to work in a completely distributed manner and does
enabled through extensions to the protocol. thus not depend on any central entity. The protocol does NOT REQUIRE
reliable transmission of control messages: each node sends control
messages periodically, and can therefore sustain an occasional loss
of some such messages. Such losses occur frequently in radio networks
due to collisions or other transmission problems.
* Does the protocol provide some form of security? (if so, how?) Also, OLSR does not require sequenced delivery of messages. Each con-
trol message contains a sequence number which is incremented for each
message. Thus the recipient of a control message can easily identify
which information is newer - even if messages have been re-ordered
while in transmission.
No. Furthermore, OLSR provides support for protocol extensions such as
sleep mode operation, multicast-routing etc. Such extensions may be
introduced as additions to the protocol without breaking backwards
compatibility with earlier versions.
* Does the protocol provide support for utilizing multi-channel, OLSR performs hop by hop routing, i.e. each node uses its most recent
link-layer technologies? (if so, how?) local information to route a packet. Hence, for OLSR to be able to
route packets, the frequency of control messages should be tuned to
the speed of the mobile nodes such that their movements can be
tracked by their neighborhood.
Yes. OLSR makes no assumptions on the underlying link-layer OLSR does not require any changes to the format of IP packets. Thus
other, than that local broadcast must be available. any existing IP stack can be used as is: the protocol only interacts
with routing table management.
5. Protocol Overview 1.5. Multipoint Relays
OLSR is a proactive routing protocol for mobile ad hoc networks. The idea of multipoint relays is to minimize the overhead of flooding
The protocol inherits the stability of a link state algorithm and messages in the network by reducing duplicate retransmissions in the
has the advantage of having routes immediately available when same region. Each node in the network selects a set of nodes in its
needed due to its proactive nature. OLSR is an optimization over symmetric neighborhood which may retransmit its messages. This set of
the pure link state protocol, tailored for mobile ad hoc networks. selected neighbor nodes is called the "Multipoint Relay" (MPR) set of
that node. The neighbors of node N which are *NOT* in its MPR set,
receive and process broadcast messages but do not retransmit broad-
cast messages received from node N.
Firstly, it reduces the size of the control messages: rather than Each node selects its MPR set among its one hop symmetric neighbors.
declaring all links, a node declares only a subset of links with This set is selected such that it covers (in terms of radio range)
its neighbors, namely the links to those nodes which are its MPR all nodes that are two hops away. The MPR set of N, denoted as
selectors (see section 6 on MPRs). Secondly, OLSR minimizes MPR(N), is then an arbitrary subset of the symmetric neighborhood of
flooding of control traffic by using only selected nodes, called N which satisfies the following condition: every node in the symmet-
MPRs, to diffuse its messages. This technique significantly ric 2-hop neighborhood of N must have a symmetric link towards
reduces the number of retransmissions in a flooding or broadcast MPR(N). The smaller the MPR set is, the more optimal is the routing
procedure. protocol. [2] gives an analysis and example of MPR selection algo-
rithms.
OLSR MAY optimize the reactivity to topological changes by Each node maintains information about the neighbors that have
reducing the time interval for periodic control message selected it as MPR. This set is called the "Multipoint Relay Selector
transmission. Furthermore, as OLSR keeps the routes for all set" (MPR selector set) of a node. A node obtains this information
destinations in the network, the protocol is beneficial for from periodic HELLO messages received from the neighbors.
traffic patterns where a large subset of nodes are communicating
with another large subset of nodes, and where the
[source,destination] pairs are changing over time. The protocol is
particularly suited for large and dense networks, as the
optimization done using the MPRs works well in this context. The
larger and more dense a network, the more optimization can be
achieved as compared to the normal link state algorithm.
OLSR is designed to work in a completely distributed manner and A broadcast message, intended to be diffused in the whole network,
does thus not depend on any central entity. The protocol does NOT coming from these MPR selectors is assumed to be retransmitted by the
REQUIRE reliable transmission for control messages: each node node. This set can change over time (i.e. when a node selects another
sends control messages periodically, and can therefore sustain an MPR-set) and is indicated by the selector nodes in their HELLO mes-
occasional loss of some such messages. Such losses occur frequent sages. Each node has a specific "Multipoint relay Selector Sequence
in radio networks due to collisions or other transmission problems. Number" (MSSN) associated with this set. Whenever the MPR selector
set is updated, the node also increments its MSSN.
Also, OLSR does NOT REQUIRE sequenced delivery of messages. Each OLSR relies on selection of MPRs, and calculates routes through these
control message contains a sequence number which is incremented nodes. I.e., the path is made of links between MPR and MPR selector.
for each message. Thus the recipient of a control message can To enable this, each node in the network periodically floods informa-
easily identify which information is newer - even if messages have tion describing which neighbors have selected it as a MPR. Upon
been re-ordered while in transmission. receipt of this "MPR Selector" information, each node calculates or
updates the route to each known destination. So principally, the
route is a sequence of hops through the MPRs from source to the des-
tination.
Furthermore, OLSR provides support for protocol extensions such as MPRs are selected among the symmetric neighborhood. Therefore,
sleep mode operation, multicast-routing etc. Such extensions may be selecting the route through MPRs automatically avoids the problems
introduced as additions to the protocol without breaking backwards associated with data packet transfer over uni-directional links such
compatibility with earlier versions. as the problem of not getting an acknowledgment for the data packets
at each hop.
OLSR performs hop by hop routing, i.e. each node uses its most 2. Protocol Functioning
recent local information to route a packet. Hence for OLSR to be
able to route packets, the frequency of control messages should be
tuned to the speed of the mobile nodes such that their movements
can be tracked by their neighborhood.
OLSR does NOT REQUIRE any changes to the format of IP packets. Thus This section describes the details of the protocol functioning. This
any existing IP stack can be used as it is: the protocol only includes descriptions of the format and contents of the packets being
interacts with routing table management. exchanged by routers, the algorithms (e.g. for packet handling and
routing table calculation) and suggested data structures internally
kept in each router.
6. Multipoint Relays The "Packet Forwarding" and "Neighbor Sensing" mechanisms may be seen
as a transfer layer for the routing protocol. This provides nodes
with information about their neighbors and offer an optimized mecha-
nism for flooding messages through the concept of MPRs. It completely
relies on the exchange of HELLO messages.
The idea of multipoint relays is to minimize the overhead of The "Topoly Discovery" mechanism relies on the "Packet Forwarding"
flooding messages in the network by reducing duplicate and "Neighbor Sensing" mechanisms. Neighbor and MPR information from
retransmissions in the same region. Each node in the network the "Neighbor Sensing" mechanism is utilized by a node for diffusing
selects a set of nodes in its neighborhood which may retransmit local topology information to the whole network. Topology information
its messages. This set of selected neighbor nodes is called the is diffused through the "Packet Forwarding" mechanism, and relies on
"Multipoint Relay" (MPR) set of that node. The neighbors of node N TC, MID and HNA messages. Resulting from the "Topology Discovery"
which are *NOT* in its MPR set, receive and process broadcast mechanism is information which allows routing table calculation.
messages but do not retransmit broadcast messages received from
node N.
Each node selects its MPR set among its one hop neighbors. This The key notion in these modules is the MPR relationship.
set is selected such that it covers (in terms of radio range) all
nodes that are two hops away. The neighborhood of any node N can
be defined as the set of nodes which have a symmetric link to
N. The 2-hop neighborhood of N can be defined as the set of nodes
which don't have a symmetric link to N but have a symmetric link
to the neighborhood of N. The MPR set of N, denoted as MPR(N), is
then an arbitrary subset of the neighborhood of N which satisfies
the following condition: every node in the 2-hop neighborhood of N
must have a symmetric link toward MPR(N). The smaller the MPR set
is, the more optimal is the routing protocol. [2] gives an
analysis and example about MPR selection algorithms.
Each node maintains information about a set of its neighbors. This 2.1. Packet Format and Forwarding
is the set of neighbors, called the "Multipoint Relay Selector
set" (MPR selector set), which have selected the node as a MPR. A
node obtains this information from the periodic HELLO messages
received from the neighbors. A broadcast message, intended to be
diffused in the whole network, coming from these MPR selector
neighbor nodes is assumed to be retransmitted by the node. This
set can change over time (i.e. when a node selects another
MPR-set) and is indicated by the selector nodes in their HELLO
messages. Each node has a specific "Multipoint relay Selector
Sequence Number" (MSSN) associated with this set. Whenever its MPR
selector set is updated, the node also increments its MSSN.
OLSR relies on selection of MPRs, and calculates routes through OLSR communicates using an unified packet format for all data related
these nodes. I.e. MPR nodes are selected as intermediate nodes in to the protocol. The purpose of this is to facilitate extensibility
the path between a source and a destination. To enable this, each of the protocol without breaking backwards compatibility, as well as
node in the network periodically broadcast the information to provide an easy way of piggybacking different "types" of informa-
describing which neighbors have selected it as a MPR. Upon tion into a single transmission. These packets are embedded in UDP
receipt of this "MPR Selector" information, each node calculates datagrams for transmission over the network. The present draft is
or updates the route to each known destination. So principally, presented with IPv4 addresses. Considerations regarding IPv6 are
the route is a sequence of hops through the MPRs from source to given in section 4.
the destination.
MPRs are selected among the one hop neighbors with "symmetric" Each packet encapsulates one or more messages. The messages share a
i.e. bi-directional link. Therefore, selecting the route through common header format, which enables nodes to correctly accept and (if
MPRs automatically avoids the problems associated with data packet applicable) retransmit messages of an unknown type.
transfer on uni-directional links such as the problem of not
getting an acknowledgment for the data packets at each hop.
7. Protocol Functioning Messages can be flooded onto the entire network, or flooding can be
limited to nodes within a diameter (in terms of number of hops) from
the originator of the message. Thus, broadcasting a message to the
neighborhood of a node is just a special case of flooding. When
flooding any control message, duplicate retransmissions will be elim-
inated locally (i.e. each node maintains a duplicate table to prevent
transmitting the same message twice) and minimized in the entire net-
work through the usage of MPRs as described in later sections.
This section describes the details of the protocol functioning. Furthermore, a node can examine the header of a message to obtain
This includes descriptions of the format and contents of the information on the distance (in terms of number of hops) to the orig-
packets being exchanged by routers, the algorithms (e.g. for inator of the message. This feature may be useful in situations
packet handling and routing table calculation) and suggested data where, e.g., the time information from a received control messages
structures internally in each router. stored in a node depends on the distance to the originator.
7.1. Protocol and Port Number 2.1.1. Protocol and Port Number
Packages in OLSR are communicated using UDP. Port 698 has been Packets in OLSR are communicated using UDP. Port 698 has been
assigned by IANA for exclusive usage by the OLSR protocol. assigned by IANA for exclusive usage by the OLSR protocol.
7.2. Packet Format 2.1.2. Multiple Interfaces and Main Address
OLSR communicates using an unified packet format for all data
related to the protocol. The purpose of this is to facilitate
extensibility of the protocol without breaking backwards
compatibility as well as to provide an easy way of piggybacking
different "types" of information into a single transmission. These
packets are embedded in UDP datagrams for transmission over the
network. The present draft uses IPv4 addresses. Support for IPv6
will be included in a future draft.
Each package encapsulates one or more messages. The messages share A node may have several wireless interfaces, each of them having a
a common header format, which enables nodes to correctly accept distinct IP address. OLSR supports such nodes with multiple inter-
and (if applicable) retransmit messages of an unknown type. faces. For this reason, each node MUST choose one of its interface
addresses as its "main address". For example, the smallest interface
address may be the chosen as the main interface. The main address
MUST be used in OLSR control traffic as the "originator address" of
all messages emitted by a node.
Messages can be flooded onto the entire network, or flooding can A node must transmit and retransmit all control messages on all
be limited to nodes within a diameter (in terms of number of hops) interfaces. The source address in the IP header must contain the IP-
from the originator of the message. Thus, broadcasting a message address of the interface where the message is transmitted. This
to a nodes neighborhood is just a special case of flooding. When address will be denoted the "sender interface address".
flooding any control message, duplicate retransmissions will be
eliminated locally (i.e. each node maintains a duplicate table to
prevent transmitting the same message twice) and minimized in the
entire network through the usage of MPRs as described in section 5
and 6.
Furthermore, a node can examine the header of a message to obtain 2.1.3. Packet Format
information on the distance (in terms of number of hops) to the
originator of the message. This feature may be useful in
situations where, e.g., the time information from a recieved
control messages is stored in a node depends on the distance to
the originator.
The basic layout of any packet in OLSR will be as follows: The basic layout of any packet in OLSR is as follows (omitting the IP
and UDP headers):
0 1 2 3 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Reserved for future use | | Packet Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Message Type | Reserved | Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Size | Time To Live | Hop Count | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Message Sequence Number | | Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: MESSAGE : : MESSAGE :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Message Type | Reserved | Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Size | Time To Live | Hop Count | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Message Sequence Number | | Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: MESSAGE : : MESSAGE :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
(etc) (etc)
7.2.1. Packet Header 2.1.3.1. Packet Header
Packet Length Packet Length
The length (in bytes) of the packet The length (in bytes) of the packet
Reserved for future use Reserved
MUST be set to '0000000000000000' to be in compliance with this MUST be set to "0000000000000000" to be in compliance with
version of the draft. this version of the draft.
The sender information for a packet is obtainable from the UDP The sender information for a packet is obtainable from the UDP
header. header.
7.2.2. Message Header 2.1.3.2. Message Header
Originator Address Message Type
This field contains the address of the node, which has This field indicates which type of message are to be found in
originally generated this message. This field SHOULD NOT be the "MESSAGE" partition. Message types in the range of 0-127
confused with the source address from the UDP header, which is are reserved for messages in this draft and in extension
changed each time to the address of the intermediate node which drafts.
is "re-transmitting" this message. The Originator Address field
MUST *NEVER* be changed in the retransmissions.
Message Sequence Number Reserved
While generating the TC message, the "originator" node will MUST be set to "00000000" to be in compliance with this ver-
assign a unique identification number to each message. This sion of the draft.
number is inserted into the Sequence Number field of the
message. The sequence number is increased by 1 (one) for each
message originating from the node - "wrap-arounds" are handled
as described in section 10.
Message Size Message Size
This field gives the size of this message, measured from the This field gives the size of this message, counted in bytes
beginning of the "Message Type" field and until the beginning and measured from the beginning of the "Message Type" field
of the next "Message Type" field (or - if there are no and until the beginning of the next "Message Type" field (or -
following messages - the end of the packet). if there are no following messages - the end of the packet).
Message Type
This field indicates which type of message are to be found in Originator Address
the "MESSAGE" partition. Message types in the range of 0-127 are This field contains the main address of the node, which has
reserved for messages in this draft and in originally generated this message. This field SHOULD NOT be
draft-ietf-manet-olsr-extensions-00.txt. confused with the source address from the UDP header, which is
changed each time to the address of the intermediate interface
which is "re-transmitting" this message. The Originator
Address field MUST *NEVER* be changed in retransmissions.
Time To Live Time To Live
This field contains the maximum number of hops a message will This field contains the maximum number of hops a message will
be retransmitted. Before a message is transmitted, the Time To be transmitted. Before a message is retransmitted, the Time To
Live MUST be decremented by 1. When a node receives a message Live MUST be decremented by 1. When a node receives a message
with a Time To Live equal to 0, the message MUST NOT be with a Time To Live equal to 0 or 1, the message MUST NOT be
retransmitted under any circumstances. retransmitted under any circumstances. Normally, a node would
not receive a message with a TTL of zero.
Thus, by setting this field, the originator of a message can Thus, by setting this field, the originator of a message can
limit the flooding radius. limit the flooding radius.
Hop Count Hop Count
This field will contain the number of hops a message has This field contains the number of hops a message has attained.
attained. Before a message is (re-) transmitted, the Hop Count Before a message is retransmitted, the Hop Count MUST be
MUST be incremented by 1. incremented by 1.
Initially, this is set to '0' by the originator of the message. Initially, this is set to '0' by the originator of the mes-
sage.
Reserved Message Sequence Number
This field is reserved for future usage, and MUST be set to While generating a message, the "originator" node will assign
'00000000' for compliance with this draft. a unique identification number to each message. This number is
inserted into the Sequence Number field of the message. The
sequence number is increased by 1 (one) for each message orig-
inating from the node - "wrap-arounds" are handled as
described in a later section. Message sequence numbers are
used to ensure that a given message is not retransmitted more
than once by any node.
7.2.3. Packet Processing 2.1.4. Packet Processing and Message Flooding
Upon receiving a basic packet, the protocol parser examines each Upon receiving a basic packet, the protocol parser examines each of
of the "message headers". Based on the value of the "Message Type" the "message headers". Based on the value of the "Message Type"
field, the parser can determine the faith of the message. A node field, the parser can determine the fate of the message. A node may
may receive the same message in several packets. This can happen receive the same message several times. This can happen only if the
only if the message is retransmitted by two nodes in the receivers message is retransmitted by two interfaces in the receivers neighbor-
neighborhood, i.e. the "Time To Live" and the "Hop Count" fields hood and the "Time To Live" and the "Hop Count" fields in the message
in the message satisfies the following condition: satisfy the following condition:
Time To Live + Hop Count > 1 Time To Live + Hop Count > 1
Thus, to avoid re-processing of a message which was already Thus, to avoid re-processing of a message which was already received
received and processed, each node maintains a Duplicate table. In and processed, each node maintains a Duplicate table. In this table,
this table, the node records information about the most recently the node records information about the most recently received mes-
received messages where the above condition holds. For each sages where the above condition holds. For each message, satisfying
message, satisfying the above condition, a node records a the above condition, a node records a "Duplicate Tuple" (D_addr,
"Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr is the D_seq_num, D_time), where D_addr is the originator address of the
originator address of the message, D_seq_num is the message message, D_seq_num is the message sequence number of the message and
sequence number of the message and D_time specifies the time at D_time specifies the time at which a tuple expires and *MUST* be
which a tuple expires and *MUST* be removed. removed.
In a node, the set of Duplicate Tuples are denoted the "Duplicate In a node, the set of Duplicate Tuples are denoted the "Duplicate
set". set".
Thus, upon receiving a basic packet, a node performs the following Thus, upon receiving a basic packet, a node performs the following
tasks for each encapsulated message: tasks for each encapsulated message:
1. If there exists a tuple in the duplicate set, where: 1 If the time to live of the message is less than or equal to
'0' (zero), the message MUST silently be dropped.
2 If there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND D_addr == Originator Address, AND
D_seq_num == Message Sequence Number D_seq_num == Message Sequence Number
then the message has already been completely processed then the message has already been completely processed and
and MUST silently be ignored. MUST silently be ignored.
2. Otherwise, if the Message Type of the message is known to 3 Otherwise, if the Message Type of the message is known to the
the node, the message MUST be processed according to the node, the message MUST be processed according to the specifi-
specifications of such message type. cations of such message type.
3. Otherwise, If the Message Type of the message is not known 4 Otherwise, If the Message Type of the message is not known to
to the node, the message MUST be processed according to the the node, the message SHOULD be processed according to the
following algorithm: following algorithm:
3.1 If the sender of the message is not in the MPR selector 4.1 If the sender of the message is not detected to be in the
set of the node, the message MUST silently be dropped. symmetric neighborhood of the node, the message MUST
silently be dropped.
3.2 If the time to live of the message is less than or equal
to '0' (zero), the message MUST silently be dropped.
3.3 Otherwise, if the sender of the message is an MPR
selector of this node and if the time to live of the
message is greater than '0' (zero), the message MUST be
forwarded according to the following algorithm:
3.3.1 The time to live of the message is reduced by one.
3.3.2 The hop-count of the message is increased by one
3.3.3 An entry in the duplicate set is recorded with: 4.2 If the sender of the message is detected to be in the
symmetric neighborhood of the node, an entry in the
duplicate set is recorded with:
D_addr = originator address D_addr = originator address
D_seq_num = Message Sequence Number D_seq_num = Message Sequence Number
D_time = current time + D_HOLD_TIME. D_time = current time + D_HOLD_TIME.
3.3.4 The message is retransmitted (Notice: The 4.3 If the sender address is the link interface address of a
remaining fields of the message header SHOULD MPR selector of this node and if the time to live of the
be left unmodified.) message is greater than '1', the message MUST be for-
warded according to the following:
4.3.1
The TTL of the message is reduced by one.
4.3.2
The hop-count of the message is increased by one
4.3.3
The message is broadcasted on all interfaces
(Notice: The remaining fields of the message header
SHOULD be left unmodified.)
Notice: known message types are *not* forwarded "blindly" by this Notice: known message types are *not* forwarded "blindly" by this
algorithm. Forwarding (and setting the correct message header in algorithm. Forwarding (and setting the correct message header in the
the forwarded, known, message) is the responsibility of the forwarded, known, message) is the responsibility of the algorithm
algorithm specifying how the message is to be handled. This specifying how the message is to be handled. This enables, e.g., a
enables, e.g., a message type to be specified such that the message type to be specified such that the message can be modified
message can be modified while in transit (e.g. to reflect the while in transit (e.g. to reflect the route the message has taken).
route the message has taken). Further, it enables that the Further, it enables that the optimization through the MPRs can be
optimization through the MPRs can be bypassed: if for some reason bypassed: if for some reason pure flooding of a message type is
pure flooding of a message type is required (e.g. to transmit required (e.g. to transmit control information over unidirectional
control information over unidirectional links), the algorithm links), the algorithm which specifies how such messages should be
specifying handling of these messages will simply rebroadcast handled will simply rebroadcast the message, regardless of MPRs.
the message, regardless of MPR selectors.
Finally, notice that a message, which is to be broadcast in the Finally, notice that a message, which is to be broadcasted in the
neighborhood, but not flooded into the entire network, (e.g. a neighborhood but not flooded into the entire network, (e.g. a HELLO-
HELLO-message) is simply specified by setting the time to live to message) is simply specified by setting the time to live to 1 (one)
'0' (zero), and that no duplicate entries are recorded for such and the hop count to 0 (zero), and that no duplicate tuples are
messages. recorded for such messages.
By defining a set of message types, which MUST be recognized by all By defining a set of message types, which MUST be recognized by all
implementations of OLSR, it will be possible to extend the protocol implementations of OLSR, it will be possible to extend the protocol
through introduction of additional message types, while still be through introduction of additional message types, while still be able
able to maintain compatibility with older implementations. The two to maintain compatibility with older implementations. The REQUIRED
REQUIRED message types for OLSR are: message types for OLSR are:
- HELLO-messages, performing the task of neighbor sensing. - HELLO-messages, performing the task of neighbor sensing.
- TC-messages, performing the task of MPR information declaration.
Extensions may e.g. be PC-messages for enabling power conservation - TC-messages, performing the task of MPR information declara-
/ sleep mode, multicast routing, gateway announcements, tion (OLSR topology declaration).
auto-configuration/address assignment etc.
7.3. Neighbor sensing - MID-messages, performing the task of multiple interface decla-
ration.
7.3.1. Neighbor sensing information base - HNA-messages, performing the task of associated host and/or
network declaration
7.3.1.1 Neighbor information Extensions may for example be messages enabling power conservation /
sleep mode, multicast routing, support for unidirectional links,
auto-configuration/address assignment etc.
A node maintains information (obtained from the HELLO messages) 2.1.5. Message Emission and Jitter
about its one hop neighbors, the status of the link with these
neighbors, a list of 2-hop neighbors that these one hop neighbors
give access to, and an associated holding time.
Thus, for each neighbor, a node records a "Neighbor Tuple" As a basic implementation requirement, synchronization of control
(N_addr, N_status, N_time) where N_addr is the address of the messages SHOULD be avoided. As a consequence, periodic OLSR messages
neighbor, N_status designates the status of the link with that should be emitted such that they avoid synchronization.
neighbor (MPR, symmetric, heard) and N_time specifies the time at
which this record expires and *MUST* be removed.
Likewise, a node records a set of "2-hop tuples" (N_addr, Emission of control traffic from neighboring nodes may, for various
N_2hop_addr, N_time), describing symmetric or MPR links between reasons (mainly timer interactions with packet processing), become
its neighbors and the 2-hop neighborhood. N_addr is the address of synchronized such that several neighbor nodes attempt to transmit
a neighbor, N_2hop_addr is the address of a 2-hop neighbor and control traffic simultaneously. Depending on the nature of the under-
N_time specifies the time at which a tuple expires and *MUST* lying link-layer, this may or may not lead to collisions and hence
be removed. message loss - possibly loss of several subsequent messages of the
same type.
In a node, the set of Neighbor Tuples are denoted the "Neighbor To counter such synchronizations, the following simple strategy for
Set" and the set of 2-hop tuples are denoted the "2-hop neighbor emitting control messages is proposed. A node may add an amount of
set". jitter to the interval at which messages are generated. The jitter
must be a random value for each message generated. Thus, for a node
utilizing jitter:
7.3.1.2 MPR Selector information Actual message interval = MESSAGE_INTERVAL + jitter
A node maintains information (obtained from the HELLO messages) Where jitter is a value, randomly selected from the interval
about the neighbors which have selected the node as a MPR. [-MAXJITTER,0] and MESSAGE_INTERVAL is the value of the message
interval specified for the message being emitted (e.g. HELLO_INTERVAL
for HELLO messages, TC_INTERVAL for TC-messages etc.).
Thus, a node records a MPR-selector tuple (MS_addr, MS_time), for It should be noticed that the present draft imposes a minimal rate of
each neighbor which has selected the node as MPR. MS_addr is the control message emission. However a node MAY send control messages at
address of a node which has selected the node as MPR, and MS_time a higher rate (e.g. for better reacting to high mobility). It is an
specifies the time at which a tuple expires and *MUST* be implementation issue to optimize the rate of control packet emission.
removed. If all nodes use the same constant base rate, introducing some jitter
as described above may be desirable.
In a node, the set of MPR-tuples are denoted the "MPR selector 2.2. Neighbor Sensing
set" A sequence number, MSSN, is associated with this
set. Whenever a tuple is added or removed to this set, the MSSN is
incremented by 1.
7.3.2. HELLO message broadcast Each node should detect the neighbor interfaces with which it has a
direct and symmetric link. Uncertainties over radio propagation may
make some links unidirectional. Consequently, all links MUST be
checked in both directions in order to be considered valid.
Each node should detect the neighbor nodes with which it has a direct To perform neighbor detection, each node broadcasts HELLO messages,
and symmetric link. The uncertainties over radio propagation may containing information about heard neighbor interfaces and their link
make some links asymmetric. Consequently, all links MUST be checked status. The link status may either be "symmetric", "heard" (asymmet-
in both directions in order to be considered valid. ric), "MPR" or "lost". "Symmetric" indicates, that the link has been
verified to be bi-directional, i.e. it is possible to transmit data
in both directions. "Heard" indicates that the node can hear HELLO
messages from a neighbor interface, but it is not confirmed that this
neighbor interface is also able to receive messages from the node.
"MPR" indicates, that a node is selected by the sender as a MPR. A
status of MPR further implies that the link is symmetric. "Lost"
indicates that the link with this neighbor interface is now lost.
To accomplish this, each node broadcasts HELLO messages, HELLO messages are broadcasted to all one-hop neighbors and are emit-
containing information about neighbors and their link status. The ted on each MANET interface of the node. They are *not relayed* to
link status may either be "symmetric", "heard" (asymmetric) or further nodes.
"MPR". "Symmetric" indicates, that the link has been verified to
be bi-directional, i.e. it is possible to transmit data in both
directions. "Heard" indicates that the node can hear HELLO
messages from a neighbor, but it is not confirmed that this
neighbor is also able to receive messages from the node. "MPR"
indicates, that a node is selected by the sender as a MPR. A
status of MPR further implies that the link is symmetric.
These control messages are broadcast to all one-hop neighbors, but More precisely, a HELLO message contains for each interface I:
are *not relayed* to further nodes. A HELLO-message contains:
- a list of addresses of neighbors, to which there exists a - a list of neighbor interface addresses, having a symmetric
symmetric link; link to interface I;
- a list of addresses of neighbors, which have been "heard"; - a list of neighbor interface addresses, which are "heard" by
interface I (for historical reasons, the term "heard" is used
for "asymmetric");
- a list of neighbors, which have been selected as MPRs. - a list of neighbor interface addresses of neighbors selected
as MPRs, AND having a symmetric link to interface I;
The list of neighbors in a HELLO message can be partial (e.g. due - a list of neighbor interface addresses, which have been lost.
to message size limitations, imposed by the network), the rule
being that all neighbor nodes are cited at least once within a
predetermined refreshing period (HELLO_INTERVAL).
To accommodate for the above constraints, as well as to accommodate These lists are computed as described in the HELLO message generation
for future extensions, an approach similar to the overall packet section.
format (see section 6.1) is taken. Thus the proposed format of a
HELLO message is: 2.2.1. HELLO Message Format
To accommodate the above requirements, as well as to accommodate for
future extensions, an approach similar to the overall packet format
is taken. Thus the proposed format of a HELLO message is:
0 1 2 3 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Link Message Size | | Reserved | # Interfaces |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . : : . . . :
: : : :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Link Message Size | | Link Type | Interface # | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Interface # | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
: : : :
(etc) (etc)
This is sent as the data-portion of the general packet format This is sent as the data-portion of the general packet format
described in 6.1, with the "Message Type" set to HELLO_MESSAGE and described in the Packet Format and Forwarding section, with the "Mes-
the TTL field set to 0. sage Type" set to HELLO_MESSAGE and the TTL field set to 1 (one).
7.3.2.1. Description of the fields Description of the fields
Reserved
MPR Sequence Number This field is reserved for future usage, and MUST be set to
"000000000000000000000000" for compliance with this draft.
This field indicates the sequence number corresponding to the # Interfaces
most recent MPR set, calculated by the sender node.
This field indicates the number of additional MANET interfaces
(excluding the main interface) possessed by the node. If the
node has only one interface, this number is 0.
Interface Address
This field indicates the addresses of additional MANET inter-
faces. The first one will be referenced as interface address
number 1, the second as interface address number 2, and so on.
The main address of the node (whose address is given in the
originator field of the message header) will be referenced as
interface address number 0.
Link Message Size Link Message Size
The size of the link message, measured from the beginning of The size of the link message, counted in bytes and measured
the "Link Type" field and until the next "Link Type" field (or from the beginning of the "Link Type" field and until the next
- if there are no more link types - the end of the message). "Link Type" field (or - if there are no more link types - the
end of the message).
Interface #
This field indicates the number of the interface to which the
following list of neighbor interfaces corresponds. Number 0
indicates the main interface (whose address is the main
address).
Link Type Link Type
This field specifies the type of link the sending node has to This field specifies the type of the link between the inter-
the following list of neighbors. As a minimum, the following face of the sender, as identified by the interface number, and
three link types are REQUIRED by OLSR: the following list of neighbor interfaces. As a minimum, the
following four link types are REQUIRED by OLSR:
- ASYM_LINK - indicating that the links between the sender - ASYM_LINK - indicating that the links are asymmetric
and the neighbors in the following list are asymmetric (i.e. the neighbor interface is "heard").
(i.e. the neighbor is "heard").
- SYM_LINK - indicating that the links between the sender - SYM_LINK - indicating that the links are symmetric.
and the neighbors in the following list are symmetric.
- MPR_LINK - indicating, that the nodes in the following - MPR_LINK - indicating, that the links are symmetric AND
list have been selected by the sender as MPR. that the neighbors have been selected as MPR by the
(Notice: this implies, that the links from the sender sender.
of the HELLO and to the nodes in the list are symmetric).
It is possible to provide additional information by specifying - LOST_LINK - indicating that the links have been lost.
additional link-types, e.g. LOST_LINK - indicating that the link
between the sender and the neighbors in the following list has
been lost. Upon processing a HELLO message, a node silently
ignores link-types, which are unknown.
Reserved Neighbor Interface Address
This field is reserved for future usage, and MUST be set to An interface address of a neighbor.
000000000000000000000000 for compliance with this draft.
Neighbor Address Neighbor sensing is performed using HELLO message exchange, updating
the neighbor sensing information base in each node.
The address of a neighbor. 2.2.2. Neighbor Sensing Information Base
7.3.3. HELLO message processing The neighbor sensing information base stores information about neigh-
bor interfaces, 2-hop neighbors, MPRs and MPR selectors.
Upon receiving a HELLO message, the node SHOULD update the 2.2.2.1. Neighbor Set
neighbor information corresponding to the sender node address (a
node may - e.g. for security reasons - wish to restrict updating
the neighbor-table, i.e. ignoring HELLO messages from some nodes).
In this section, the term "Originator Address" will be used for For each of its interface I and for each neighbor interface NI, heard
the address of the node which sent the HELLO-message. by I, a node records a "Neighbor Tuple" (N_if_id, N_if_addr,
N_main_addr, N_SYM_time, N_ASYM_time, N_time) where N_if_id is the
identification number of I, N_if_addr is the address of the neighbor
interface NI, N_main_addr is the main address of the neighbor pos-
sessing NI, N_SYM_time is the time until which the link is considered
symmetric, N_ASYM_time is the time until which the neighbor interface
is considered heard, and N_time specifies the time at which this
record expires and *MUST* be removed. When N_SYM_time and
N_ASYM_time are expired, the link is considered lost.
1. If there exists a neighbor tuple with N_addr = Originator This information is used when declaring the neighbor interfaces in
Address: the HELLO messages. N_SYM_time and N_ASYM_time are used to decide the
Link Type declared for the neighbor interface. If N_SYM_time is not
expired, the link is declared symmetric. If N_SYM_time is expired but
N_ASYM_time is not, the link is declared heard. If both N_SYM_time
and N_ASYM_time are expired, the link is declared lost.
1.1 if for that tuple N_status == ASYM_LINK: In a node, the set of Neighbor Tuples are denoted the "Neighbor Set".
1.1.1 if the node finds its own address among the 2.2.2.2. 2-hop Neighbor Set
addresses listed in the HELLO message (with Link
Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates
the N_status of the tuple to SYM_LINK and sets
N_time = current time + NEIGHB_HOLDING_TIME.
1.1.2 otherwise, if the node does not find its own A node records a set of "2-hop tuples" (N_main_addr, N_if_addr,
address among the addresses listed in the HELLO N_2hop_addr, N_time), describing symmetric or MPR links between its
message, it sets N_time = current time + neighbors and the 2-hop symmetric neighborhood. N_main_addr and
NEIGHB_HOLDING_TIME. N_if_addr are the main address and an interface address of a
neighbor, N_2hop_addr is an interface address of a 2-hop neighbor
with a symmetric or MPR link to interface N_if_addr and N_time speci-
fies the time at which the tuple expires and *MUST* be removed.
1.2 otherwise, if for that tuple: This information is gathered from the HELLO messages received by a
node from its neighbor nodes.
N_status == SYM_LINK OR In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor
N_status == MPR_LINK Set".
then: 2.2.2.3. MPR Set
1.2.1 if the node finds its own address among the addresses A node maintains a set of neighbors which are elected as MPR. Their
listed in the HELLO message (with Link Type main addresses are listed in the so-called MPR Set. The Multipoint
ASYM_LINK, SYM_LINK or MPR_LINK), it sets N_time = relay selection section describes how MPRs are elected.
current time NEIGHB_HOLDING_TIME.
2. Otherwise, a new neighbor tuple is created with: 2.2.2.4. MPR Selector Set
N_addr = Originator Address A node maintains information (obtained from the HELLO messages) about
the neighbors which have selected this node as a MPR.
N_status with the value of SYM_LINK if the node Thus, a node records a MPR-selector tuple (MS_if_addr, MS_main_addr,
finds its own address (with Link Type ASYM_LINK, SYM_LINK MS_time), for interfaces of a neighbor which has selected the node as
or MPR_LINK) among the addresses listed in the HELLO MPR. MS_if_addr is the address of an interface of a node which has
message, and to the value of ASYM_LINK otherwise selected the node as MPR for that interface, MS_main_addr is the main
address of the MPR selector and MS_time specifies the time at which a
tuple expires and *MUST* be removed.
N_time = current time + NEIGHB_HOLD_TIME In a node, the set of MPR-selector tuples are denoted the "MPR Selec-
tor Set". A sequence number, MSSN, is associated with this set. When-
ever a tuple is added to or removed from this set, the MSSN is incre-
mented by 1.
The 2-hop neighbor set is updated as follows: for each 2-hop 2.2.3. HELLO Message Generation
neighbor address listed in the HELLO message with Link Type
SYM_LINK or MPR_LINK:
1. if a 2-hop tuple exists with: The lists of addresses declared in a HELLO message are computed from
the Neighbor Set as follows:
N_addr == Originator Address AND - for each tuple where N_SYM_time and N_ASYM_time are expired,
N_2hop_address == the address of the 2-hop neighbor, the N_if_addr is declared with LOST_LINK Link Type for inter-
face N_if_id;
then the N_time of that tuple is set to: - for each tuple where N_SYM_time is not expired, the N_if_addr
is declared with MPR_LINK Link Type if N_main_addr is in the
MPR set and SYM_LINK Link Type otherwise;
- for each tuple where N_SYM_time is expired but N_ASYM_time is
not expired, the N_if_addr is declared with ASYM_LINK Link
Type.
The list of neighbor interfaces in a HELLO message can be partial
(e.g. due to message size limitations, imposed by the network), the
rule being the following: for each interface a neighbor interface is
heard on, its address is cited with corresponding interface id at
least once within a predetermined refreshing period (HELLO_INTERVAL).
Notice that for limiting the impact from loss of control messages, it
is desirable that a message fits in a single MAC packet.
Each HELLO message generated is broadcasted on each MANET interface
of the node.
2.2.4. HELLO Message Processing
Upon receiving a HELLO message, the node SHOULD update the neighbor
information corresponding to the sender node address (a node may -
e.g. for security reasons - wish to restrict updating the neighbor-
table, i.e. ignoring HELLO messages from some nodes).
In this section, the term "Originator Address" will be used for the
main address of the node which sent the HELLO-message. The term
"Sender Interface Address" will be used for the sender address (given
in the IP header of the packet containing the message) of the inter-
face which sent the HELLO message. The term "Receiver Interface" will
be used for the interface which received the HELLO message. The term
"link interface addresses" will be used for the own interface
addresses of the sender listed in the HELLO message.
The Neighbor Set should be updated as follows:
1 Upon receiving a HELLO message, if there exists no neighbor
tuple with
N_if_addr == Sender Interface Address
and
N_if_id == identifier of the Receiver Interface,
a new tuple is created with
N_if_addr = Sender Interface Address
N_if_id = identifier of the Receiver Interface
N_SYM_time = current time - 1 (expired time)
N_time = current time + NEIGHB_HOLD_TIME N_time = current time + NEIGHB_HOLD_TIME
2. otherwise a new 2-hop tuple is created with: 2 The tuple is then modified as follows:
N_addr = Originator Address, 2.1 N_main_addr = Originator Address.
N_2hop_address = the address of the 2-hop neighbor, 2.3 N_time = max (N_time, current time +
NEIGHB_HOLD_TIME);
2.4 N_ASYM_time = current time + NEIGHB_HOLD_TIME;
2.5 if the node finds the receiver interface address among
the addresses listed in the HELLO with:
Link Interface Address == Sender Interface Address,
then, the tuple is modified as follows:
if Link Type == LOST_LINK then
N_SYM_time = current time - 1 (expired time)
else:
N_SYM_time = current time + NEIGHB_HOLD_TIME,
N_time = current time + 2 *
NEIGHB_HOLD_TIME.
The rule for setting N_time is the following: a link loosing its sym-
metricity should still be advertised at least NEIGHB_HOLD_TIME. This
allows neighbors to detect the link breakage.
The 2-hop Neighbor Set is updated as follows:
1 for each 2-hop interface address listed in the HELLO message
with Link Type SYM_LINK or MPR_LINK, a 2-hop tuple is created
with:
N_main_addr = Originator Address;
N_if_addr = Link Interface Address corresponding to the
2-hop interface address;
N_2hop_addr = the interface address of the 2-hop neigh-
bor;
N_time = current time + NEIGHB_HOLD_TIME. N_time = current time + NEIGHB_HOLD_TIME.
Based on the information obtained from the HELLO messages, each This tuple may replaces an older similar tuple with same
node construct its MPR selector set. N_if_addr and N_2hop_addr values.
Thus, upon receiving a HELLO message, if a node finds its own 2 For each 2-hop interface address listed in the HELLO message
address in the address list with a link type of "MPR", it MUST with Link Type LOST_LINK or ASYM_LINK, all the 2-hop tuples
update the MPR selector set to contain updated information about where:
the sender of the HELLO message:
1. If a MPR selector tuple exists with: N_if_addr == Link Interface Address corresponding to the
2-hop interface address,
MS_addr == Originator Address and
then the expiration time of that tuple is set to: N_2hop_addr == the 2-hop interface address
MS_time = current time + NEIGHB_HOLD_TIME. are deleted.
2. Otherwise, a new MPR selector tuple is created with: Based on the information obtained from the HELLO messages, each node
constructs its MPR selector set.
MS_addr = Originator Address Thus, upon receiving a HELLO message, if a node finds one of its
interface addresses in a list with a link type of "MPR", it MUST
update the MPR selector set to contain updated information about the
sender of the HELLO message:
MS_time = current time + NEIGHB_HOLD_TIME 1 If there exists no MPR selector tuple with:
2.1 MSSN is incremented by one to indicate that the MPR MS_if_addr == Link Interface Address
selector table has been changed.
If link layer information describing connectivity to neighboring and
nodes is available (i.e. loss of connectivity such as through
absence of an acknowledgment), this MAY be used in addition to
the information from the HELLO-messages to maintain the neighbor
table and the MPR selector table as described in section 7.7.
7.4. Multipoint relay selection MS_main_addr == Originator Address
Each node in the network selects independently its own set of then MSSN is incremented to indicate that the MPR selector
MPRs. MPRs are used to flood control messages from that node into table is going to change.
the network while reducing the number of retransmissions that will
occur in a region. Thus, the concept of MPRs is an optimization
of a pure flooding mechanism.
The MPR set must be calculated by a node in a way such that it, 2 If there exists no MPR selector tuple with:
through the neighbors in the MPR-set, can reach all 2-hop
neighbors. This means that the union of the neighbor sets the MPR MS_if_addr == Link Interface Address
nodes contains the entire 2-hop neighbor set. While it is not then a new tuple is created with:
essential that the MPR set is minimal, it is essential that all
MS_if_addr = Link Interface Address
3 The tuple is then modified as follows:
MS_main_addr = Originator Address,
MS_time = current time + NEIGHB_HOLD_TIME.
Deletion of MPR selector tuples occurs in case of expiration of the
timer or in case of link breakage as described in the neighborhood
and 2-hop neighborhood changes section.
2.2.5. Multipoint Relay Selection
Each node in the network selects, independently, its own set of MPRs
among its symmetric neighborhood. The symmetric links with MPRs are
advertised with Link Type MPR_LINK instead of SYM_LINK in HELLO mes-
sages.
MPRs are used to flood control messages from that node into the net-
work while reducing the number of retransmissions that will occur in
a region. Thus, the concept of MPR is an optimization of a pure
flooding mechanism.
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 2-hop
neighbors which are not at the same time symmetric neighbors of the
node. This means that the union of the symmetric neighborhoods of
the MPR nodes contains the symmetric 2-hop neighborhood. While it is
not essential that the MPR set is minimal, it is essential that all
2-hop neighbors can be reached through the selected MPR nodes. The 2-hop neighbors can be reached through the selected MPR nodes. The
smaller a MPR-set, however, the more optimizations are achieved. smaller a MPR-set, however, the more optimization is achieved.
By default, the MPR set can coincide with the entire neighbor By default, the MPR set can coincide with the entire symmetric neigh-
set. This will be the case at network initialization. bor set. This will be the case at network initialization.
The following specifies a proposed heuristic for selection of MPRs The following specifies a proposed heuristic for selection of MPRs
[2]. The following terminology will be used in describing this [2] adapted for multiple interfaces support. It constructs a MPR-set
algorithm: that allows to reach any symmetric 2-hop interface (i.e. any inter-
face of a 2-hop neighbor having a symmetric link with a neighbor).
The following terminology will be used in describing this algorithm
(neighbors are identified by their main address and 2-hop interfaces
by their address):
N: The net of neighbors with which there exists a N: The set of neighbors with which there exists a symmetric link.
symmetric link.
N2: The set of 2-hop neighbors. This set does not contain N2: The set made of the symmetric 2-hop interfaces excluding all
any one hop neighbors. the interfaces of members of N and the interfaces of the node
performing the computation.
D(y): Degree of one hop neighbor node y (where y is a member D(y):
of N), is defined as the number of symmetric one hop Degree of one hop neighbor node y (where y is a member of N),
neighbors of node y, EXCLUDING the node performing the defined as the number of symmetric neighbor interfaces of node
computation and all its direct neighbors. y, EXCLUDING all the interfaces of members of N and the inter-
faces of the node performing the computation.
The proposed heuristic is as follows: The proposed heuristic is as follows:
1. Start with an empty MPR set 1 Start with an empty MPR set
2. Calculate D(y), where y is a member of N, for all nodes
in N.
3. Select as MPRs those nodes in N which provide the
"only path" to some nodes in N2
4. While there exist nodes in N2 which are not covered by MPR:
4.1 For each node in N, calculate the number of nodes in 2 Calculate D(y), where y is a member of N, for all nodes in N.
N2 which are not yet covered by MPR and are
3 Select as MPRs those nodes in N which provide the "only path"
to some interfaces in N2.
4 While there exist interfaces in N2 which are not covered by
the MPR set:
4.1 For each node in N, calculate the number of interfaces in
N2 which are not yet covered by the MPR set and are
reachable through this one hop neighbor; reachable through this one hop neighbor;
4.2 Select as a MPR that node of N which reaches the
maximum number of uncovered nodes in N2. In case of a
tie, select that node as MPR whose D(y) is greater.
5. As an optimization, process each node y in MPR. 4.2 Select as a MPR the node from N which provides reachabil-
If MPR\{y} still covers all nodes in N2, Y SHOULD be ity to the maximum number of uncovered interfaces in N2.
removed from the MPR set. In case of a tie, select that node as MPR whose D(y) is
greater.
After selecting the MPRs among the neighbors, the link status of 5 As an optimization, process each node y in the MPR set. If the
the corresponding one hop neighbors is changed from SYM_LINK to MPR set excluding y still covers all interfaces in N2, node y
MPR_LINK in the neighbor table. MPR_Seq_Num value in the Neighbor is removed from the MPR set.
table is also incremented by one.
The MPR set is re-calculated when:
- a change in the neighborhood is detected, i.e. either a When the MPR set has been computed, all the corresponding main
symmetric link with a neighbor is failed, or a new neighbor addresses are stored in the MPR Set.
with a symmetric link is added; or
- a change is detected in the 2-hop neighborhood such that
a symmetric link is either detected or broken between a
2-hop neighbor and a neighbor.
7.5. Multipoint relay information declaration Some processing such as MPR set re-calculation should occur when
changes are detected in the neighborhood or the 2-hop neighborhood.
7.5.1 Topology information base 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes
Each node in the network maintains topological information about A change in the neighborhood is detected when:
the network. This information is acquired from TC-messages and
used for routing table calculations. - The N_SYM_time field of a neighbor tuple expires. This is con-
sidered as a neighbor loss if it was the last link with a
neighbor node (on the contrary, a link with an interface may
break while a link with another interface of the neighbor node
is still alive).
- The N_ASYM_time field of a neighbor tuple expires and
N_SYM_time is expired. The link is then considered lost.
- A new neighbor tuple is inserted in the Neighbor Set with a
valid N_SYM_time or a tuple with expired N_SYM_time is modi-
fied so that N_SYM_time becomes valid. This is considered as a
neighbor appearance if there was previously no link with the
corresponding neighbor node.
A change in the 2-hop neighborhood is detected when a 2-hop neighbor
tuple expires or is deleted according to the HELLO message processing
section.
The following processing should occur when changes in the neighbor-
hood or the 2-hop neighborhood are detected:
- In case of neighbor loss, all the 2-hop tuples with
N_main_addr == Main Address of the neighbor are deleted.
- In case of neighbor loss, all the MPR selector tuples with
MS_main_addr == Main Address of the neighbor are deleted
- The MPR set is re-calculated when a neighbor appearance or
loss is detected, or when a change in the 2-hop neighborhood
is detected.
- An additional HELLO message may be sent when the MPR set
changes.
2.2.6. Advanced Neighbor Sensing Functioning
Established links should be as reliable as possible to avoid data
packet loss. To enhance the reliability of the neighbor sensing mech-
anism, the following implementation recomendations should be consid-
ered.
Each neighbor tuple in the neighbor set SHOULD, in addition to what
is described in section 2.2.2.1, include a N_pending field, a N_qual-
ity field, and a N_LOST_time. N_pending is a boolean value specify-
ing if the link is considered pending (i.e. the link is not consid-
ered established). N_quality is a dimensionless number between 0 and
1 describing the quality of the link. N_LOST_time is a timer for
declaring a link as lost when an established link becomes pending.
HELLO message generation should consider those new fields as follows.
1 If N_LOST_time is not expired, the link is advertised with a
link type of LOST_LINK;
2 otherwise, if N_LOST_time is expired and N_pending is set to
"true", the link SHOULD NOT be advertised at all;
3 otherwise, if N_LOST_time is expired and N_pending is set to
"false", the link is advertised as described in the HELLO mes-
sage generation section.
A node considers it has a symmetric link for each neighbor tuple such
that N_LOST_time is expired, N_pending is "false" and N_SYM_time is
not expired. This should be taken as definition for computing the
symmetric neighborhood when computing the MPR set.
Apart from the above points, what has been previously describe do not
interfere with this newly introduced fields. The N_quality, N_pending
and N_LOST_time fields are updated according to the present section
and nowhere else. The other fields are not modified by the advanced
neighbor sensing functioning.
This advanced functioning is described as separately as possible to
increase readability.
2.2.6.1. Link Hysteresis
The link between a node and some of its neighbor interfaces might be
"bad", i.e. from time to time let HELLOs pass through only to fade
out immediately after. In this case, the neighbor information base
would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of
link layer notification, such a bad link would spoil routing. To cope
with such unstable links, the following hysteresis strategy SHOULD be
adopted.
For each neighbor interface NI heard by interface I, the N_quality
field of the corresponding Neighbor Tuple determines the establish-
ment of the link. Its value is compared to two thresholds
HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW which are fixed between 0 and
1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. When
N_quality becomes higher than HYST_THRESHOLD_HIGH, the N_pending
field is set to false. When N_quality goes below HYST_THRESHOLD_LOW,
the N_pending field is set to true and N_LOST_time is set to min
(N_time, current time + NEIGHB_HOLD_TIME) (the link is then consid-
ered as lost according to the Neighborhood and 2-hop neighborhood
changes section and this may produce a neighbor loss). The condition
for considering a link established is thus stricter than the condi-
tion for loosing it.
As a basic implementation requirement, an estimation of the link
quality must be maintained and stored in the N_quality field. If some
measure of the signal/noise level on a received message is available
(e.g. as a link layer notification), then it can be used as estima-
tion after normalization.
If no signal/noise information is available from the link layer, an
algorithm such the following can be utilized. The algorithm is
parametrized by a scaling parameter HYST_SCALING which is a number
fixed between 0 and 1. For each neighbor interface NI heard by inter-
face I, the first time NI is heard by I, N_quality is set to
HYST_SCALING (and N_pending is set to true).
A tuple is updated according to two rules. Every time an OLSR mes-
sage emitted by NI is received by I, the stability rule is applied:
N_quality = (1-HYST_SCALING)*N_quality + HYST_SCALING.
When an OLSR message emitted by NI is lost by I, the instability
rule is applied:
N_quality = (1-HYST_SCALING)*N_quality.
The loss of OLSR messages is detected by tracking the missing Message
Sequence Numbers and by long period of silence. If no HELLO message
has been received for a HELLO_INTERVAL period, a loss of HELLO mes-
sage is detected.
2.2.6.2. Optional Link layer notification
OLSR is designed not to impose or expect any specific information
from the link layer. However, if information from the link-layer is
available, a node MAY use this as described in this section.
If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through absence
of a link layer acknowledgment), this information is used in addition
to the information from the HELLO-messages to maintain the neighbor
information base and the MPR selector set.
Thus, upon receiving a link-layer notification that the link between
a node and a neighbor interface is broken, the following actions are
taken:
1 if the link is broken to either a symmetric or asymmetric
neighbor interface, the corresponding neighbor tuple is modi-
fied: N_LOST_time and N_time are set to current time +
NEIGHB_HOLD_TIME.
2 this is considred as a link loss and the appropriate process-
ing described in the neighborhood and 2-hop neighborhood
changes section should be performed.
2.3. Topology Discovery
The Neighbor Sensing part of the protocol basically offers to each
node a list of neighbors with which it can communicate directly and
an optimized flooding mechanism through MPRs. Based on this mecha-
nism, topology information is disseminated through the network. The
present section describes what part of the information given by the
Neighbor Sensing is disseminated and how it is used to construct
routes.
Routes are constructed through MPR-links and links with neighbors. A
node thus basically disseminates its MPR-selector set. If a node has
multiple interfaces, it must also disseminate the list of its inter-
face addresses.
2.3.1. Multipoint Relay Information Declaration
2.3.1.1. Topology Information Base
Each node in the network maintains topological 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, a "Topology Tuple" Thus, for each destination in the network, a "Topology Tuple"
(T_dest, T_last, T_seq, T_time) is recorded. T_dest is the address (T_dest, T_last, T_seq, T_time) is recorded. T_dest is the main
of a node, which may be reached in one hop from the node with the address of a node, which may be reached in one hop from the node with
address T_last. T_seq is a sequence number, and T_time specifies the main address T_last. Typically, T_last is a MPR of T_dest. T_seq
the time at which this tuple expires and *MUST* be removed. 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 In a node, the set of Topology Tuples are denoted the "Topology Set".
Set".
7.5.2. TC Message Broadcast 2.3.1.2. TC Message Generation
In order to build the topology information base needed, each node, In order to build the topology information base needed, each node,
which has been selected as MPR, broadcasts Topology Control (TC) which has been selected as MPR, broadcasts Topology Control (TC) mes-
messages. TC messages are flooded to all nodes in the network and sages. TC messages are flooded to all nodes in the network and take
take advantage of MPRs. MPRs enable a better scalability in the advantage of MPRs. MPRs enable a better scalability in the distribu-
distribution of topology information [1]. tion of topology information [1].
A TC message is sent by a node in the network to declare its MPR A TC message is sent by a node in the network to declare its MPR
Selector set. I.e., the TC message contains the list of neighbors Selector set. I.e., the TC message contains the list of neighbors
which have selected the sender node as a MPR. The sequence number which have selected the sender node as a MPR. The sequence number
(MSSN) associated with this MPR selector set is also sent with the (MSSN) associated with this MPR selector set is also sent with the
list. The list of addresses can be partial in each TC message list. The list of addresses can be partial in each TC message (e.g.
(e.g. due to message size limitations, imposed by the network), due to message size limitations, imposed by the network), but parsing
but parsing of all TC messages describing a nodes MPR selector set of all TC messages describing the MPR selector set of a node MUST be
MUST be complete within a certain refreshing period complete within a certain refreshing period (TC_INTERVAL). The infor-
(TC_INTERVAL). The information diffused in the network by these TC mation diffused in the network by these TC messages will help each
messages will help each node to calculate its routing table. A node calculate its routing table. A node which has an empty MPR
node which has an empty MPR selector set, i.e. nobody has selected selector set, i.e. nobody has selected it as a MPR, SHOULD NOT gener-
it as a MPR, MUST NOT generate any TC message. ate any TC message.
A node MAY transmit additional TC-messages to increase its A node MAY transmit additional TC-messages to increase its reactive-
reactiveness to link failures. I.e. when a change to the MPR ness to link failures. I.e. when a change to the MPR selector set is
selector set is detected and this change can be attributed to a detected and this change can be attributed to a link failure, a TC-
link failure, a TC-message SHOULD be transmitted after a shorter message SHOULD be transmitted after a shorter interval than TC_INTER-
interval than TC_INTERVAL. VAL.
The proposed format of a TC message is The proposed format of a TC message is
0 1 2 3 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 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| MSSN | Reserved | | MSSN | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format with
the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set
to 255 (maximum value) to diffuse the message into the entire net-
work.
This is sent as the data-portion of the general message format Description of the fields
described in 6.1, with the "Message Type" set to TC_MESSAGE. The
time to live SHOULD be set to 255 (maximum value) to diffuse the
message into the entire network.
7.5.2.1. Description of the fields
MPR Selector Sequence Number (MSSN) MPR Selector Sequence Number (MSSN)
A sequence number is associated with the MPR selector A sequence number is associated with the MPR selector set.
set. Every time a node detects a change in its MPR selector Every time a node detects a change in its MPR selector set, it
set, it increments this sequence number. This number is sent in increments this sequence number. This number is sent in this
this MSSN field of the TC message to keep track of the most MSSN field of the TC message to keep track of the most recent
recent information. When a node receives a TC message, it can information. When a node receives a TC message, it can decide
decide on the basis of this MPR Sequence Number, whether or not on the basis of this MPR Sequence Number, whether or not the
the received information about the MPR selectors of the received information about the MPR selectors of the originator
originator node is more recent than what it already has. node is more recent than what it already has.
Multipoint Relay Selector Address (MPR-S) Multipoint Relay Selector Main Address
This field contains the address of a node, which has selected This field contains the main address of a node, which has
the Originator node (of the TC message) as a MPR. All selected the Originator node (of the TC message) as a MPR.
addresses of the MPR selectors of the Originator node are put All addresses of the MPR selectors of the Originator node are
in the TC message. If the maximum allowed message size (as put in the TC message. If the maximum allowed message size (as
imposed by the network) is reached while there are still MPR imposed by the network) is reached while there are still MPR
selector addresses which which have not been inserted into the selector addresses which which have not been inserted into the
TC-message, more TC messages will be generated until the entire TC-message, more TC messages will be generated until the
MPR selector set has been sent. entire MPR selector set has been sent.
Reserved Reserved
This field is reserved for future usage, and MUST be set to This field is reserved for future usage, and MUST be set to
'0000000000000000' for compliance with this draft. "0000000000000000" for compliance with this draft.
7.5.3. TC Message Processing 2.3.1.3. TC Message Processing
TC messages are broadcasted and retransmitted by the MPRs in order TC messages are broadcasted and retransmitted by the MPRs in order to
to diffuse the messages in the entire network. diffuse the messages in the entire network.
In this section, the term "originator" is used to designate the In this section, the term "originator" is used to designate the node
node from which the message originally originated, while the term from which the message originally originated, while the term "sender"
"sender" is used to designate the node from which the message was is used to designate the node from which the message was received
received (i.e. the "last hop" of the message). (i.e. the "last hop" of the message).
The tuples in the topology set are recorded with the topology The tuples in the topology set are recorded with the topology infor-
information that is exchanged through TC messages, following the mation that is exchanged through TC messages, according to the
following algorithm: following algorithm:
1. If the sender (NB: not originator) of this message is not in 1 If the sender interface (NB: not originator) of this message
the neighbor set of this node, the message is discarded. is not in the symmetric neighborhood of this node, the message
is discarded.
2. A tuple is inserted into the duplicate table to prevent 2 A tuple is inserted into the duplicate table to prevent it
being processed again with: from being processed again with:
D_addr = originator address D_addr = originator address
D_seq_num = Message Sequence D_seq_num = Message Sequence
D_time = current time + D_HOLD_TIME. D_time = current time + D_HOLD_TIME.
3. If there exist some tuple in the topology set where: 3 If there exist some tuple in the topology set where:
T_last == originator address AND T_last == originator address AND
T_seq > MSSN, T_seq > MSSN,
then no further processing of this TC message is performed then no further processing of this TC message is performed and
and the message is silently discarded (case: message the message is silently discarded (case: message received out
received out of order). of order).
4. All tuples in the topology set where: 4 All tuples in the topology set where:
T_last == originator address AND T_last == originator address AND
T_seq < MSSN T_seq < MSSN
are removed from the topology set. are removed from the topology set.
5. For each of the MPR selector address received in the TC 5 For each of the MPR selector address received in the TC mes-
message: sage:
5.1 If there exist some tuple in the topology set where: 5.1 If there exist some tuple in the topology set where:
T_dest == MPR selector address, AND T_dest == MPR selector address, AND
T_last == originator address, T_last == originator address,
then the holding time of that tuple is set to: then the holding time of that tuple is set to:
T_time = current time + TOP_HOLD_TIME. T_time = current time + TOP_HOLD_TIME.
5.2 Otherwise, a new tuple is recorded in the topology set 5.2 Otherwise, a new tuple is recorded in the topology set
where: where:
T_dest = MPR selector address, T_dest = MPR selector address,
skipping to change at page 26, line 16 skipping to change at page 34, line 18
where: where:
T_dest = MPR selector address, T_dest = MPR selector address,
T_last = originator address, T_last = originator address,
T_seq = MSSN, T_seq = MSSN,
T_time = current time + TOP_HOLD_TIME. T_time = current time + TOP_HOLD_TIME.
7.6. Routing table calculation 6 If the sender address is the link interface address of a MPR
selector of this node and if the time to live of the message
is greater than '1', the message MUST be forwarded according
to the following:
Each node maintains a routing table which allows it to route the 6.1 The TTL of the message is reduced by one.
messages for the other destinations in the network. The routing
table is based on the information contained in the neighbor set
and the topology set. Therefore, if any of these tables is
changed, the routing table is re-calculated to update the route
information about each destination in the network. The route
entries are recorded in the routing table in the following format:
1. R_dest R_next R_dist 6.2 The hop-count of the message is increased by one
2. R_dest R_next R_dist
6.3 The message is broadcasted on all interfaces (Notice: The
remaining fields of the message header SHOULD be left
unmodified.)
2.3.2. Multiple Interface Association
Each node in the network maintains interface information about the other
nodes in the network. This information acquired from MID-messages, emit-
ted by nodes with multiple interfaces participating in the MANET, and is
used for routing table calculations.
2.3.2.1. Interface Association Information Base
For each destination in the network, "Interface association Tuples"
(I_if_addr, I_main_addr, I_time) are recorded. I_if_addr is an inter-
face 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.
In a node, the set of Interface association Tuples is denoted the
"Interface association Set".
2.3.2.2. MID Message Broadcast
In order to build the interface association information base, each
node with multiple interfaces broadcast Multiple Interface Declara-
tion (MID) messages. MID messages are flooded to all nodes in the
network and take advantage of MPRs.
A MID message is sent by a node in the network to declare its multi-
ple interfaces (if any). I.e., the MID message contains the list of
interface addresses which are associated to its main address. The
list of addresses can be partial in each TC message (e.g. due to mes-
sage size limitations, imposed by the network), but parsing of all
MID messages describing a nodes interface set MUST be complete within
a certain refreshing period (MID_INTERVAL). The information diffused
in the network by these MID messages will help each node to calculate
its routing table. A node which has only a single interface address
participating in the MANET (i.e. running OLSR), MUST NOT generate any
MID message.
A node with more interfaces, where only one is participating in the
MANET and running OLSR (e.g. a node is connected to a wired network
as well as to a MANET) MUST NOT generate any MID messages.
The proposed format of a MID message is
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format with
the "Message Type" set to MID_MESSAGE. The time to live SHOULD be
set to 255 (maximum value) to diffuse the message into the entire
network.
Description of the fields
Interface Address
This field contains the address of an interface of the node
other than its main address (already indicated in the origina-
tor address). All interface addresses other than the main
address of the Originator node are put in the MID message. If
the maximum allowed message size (as imposed by the network)
is reached while there are still interface addresses which
have not been inserted into the MID-message, more MID messages
are generated until the entire interface addresses set has
been sent.
2.3.2.3. MID Message Processing
MID messages are broadcasted and retransmitted by the MPRs in order
to diffuse the messages in the entire network.
In this section, the term "originator" is used to designate the node
from which the message originally originated, while the term "sender"
is used to designate the node from which the message was received
(i.e. the "last hop" of the message).
The tuples in the multiple interface association set are recorded
with the information that is exchanged through MID messages, follow-
ing the following algorithm:
1 If the sender (NB: not originator) of this message is not in
the symmetric neighborhood of this node, the message is dis-
carded.
2 A tuple is inserted into the duplicate table to prevent it
from being processed again with:
D_addr = originator address
D_seq_num = Message Sequence
D_time = current time + D_HOLD_TIME.
3 For each of the interface address received in the MID message:
3.1 If there exist some tuple in the interface association
set where:
I_if_addr == interface address, AND
I_main_addr == originator address,
then the holding time of that tuple is set to:
I_time = current time + MID_HOLD_TIME.
3.2 Otherwise, a new tuple is recorded in the interface asso-
ciation set where:
I_if_addr = interface address,
I_main_addr = originator address,
I_time = current time + MID_HOLD_TIME.
4 If the sender address is the link interface address of a MPR
selector of this node and if the time to live of the message
is greater than '1', the message MUST be forwarded according
to the following:
4.1 The TTL of the message is reduced by one.
4.2 The hop-count of the message is increased by one
4.3 The message is broadcasted on all interfaces (Notice: The
remaining fields of the message header SHOULD be left
unmodified.)
2.3.3. Associated Networks and Hosts
A node MAY provide access to a set of associated hosts. I.e., a node
may act as a "gateway" between the MANET and a number of associated
hosts and/or subnets, not running OLSR and thus not participating in
the MANET. Thus, a node SHOULD be able to inject routing information
describing these associated hosts or networks into MANET, as SHOULD
all nodes be capable of interpreting such information.
Notice, that this is a different case from that of "multiple inter-
faces", described previously. Where, in the "Multiple Interface Asso-
ciations", all the described interfaces were participating in the
MANET through running the OLSR protocol, this section addresses the
interfaces which do not participate. This is, e.g., the case where a
node has both a wireless interface (participating in the MANET) and a
wired interface, through which a number of hosts statically connect
(to the nodes in the MANET).
To accomplish this, a node, to which there are associated hosts
and/or networks, periodically issues an Host and Network Association
(HNA) message, containing sufficient information for the recipients
to construct an appropriate routing table.
2.3.3.1. Host and Network Association Information Base
Each node maintains information concerning which nodes may act as
"gateways" to associated hosts and networks by recording "association
tuples" (GW_main_addr, NET_addr, NET_mask, GS_time), where
GW_main_addr is the main address of the gateway, NET_addr and
NET_mask specifies the network address and netmask of a network,
reachable through this gateway, and GS_time specifies the time at
which this tuple expires and hence *MUST* be removed.
The set of all association tuples in a node is called the "associa-
tion set".
2.3.3.2. Host and Network Association Message Broadcast
A node with associated hosts and/or networks SHOULD periodically gen-
erate a Host and Network Association (HNA) message, containing pairs
of (network address, netmask) corresponding to the connected hosts and
networks. HNA-messages SHOULD be transmitted periodically every
HNA_INTERVAL.
A node without any associated hosts and/or networks SHOULD NOT gener-
ate HNA-messages.
The proposed format of an HNA-message is:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data part of the general packet format with the
"Message Type" set to HNA and the TTL field set to 255.
It should be noticed, that the HNA-message can be considered as a
"generalized version" of the TC-message: the originator of both the
HNA and TC messages announce "reachability" to some other host(s). In
the TC-message, no netmask is required, since all reachability is
announced on a per-host basis. In HNA-messages, announcing reachabil-
ity to an address sequence through a network- and netmask address is
typically preferred over announcing reachability to individual host
addresses.
Description of the fields
Network Address
The network address of the associated network
Netmask
The netmask, corresponding to the network address immediately
above.
2.3.3.3. HNA Message Processing
In this section, the term "originator address" is used to designate
the main address of the node which originally issued the HNA-message.
Upon receiving a HNA-message, the node performs the following:
1 An entry in the duplicate set is recorded for this message
with:
D_addr = originator address
D_seq_num = Message Sequence Number
D_time = current time + D_HOLD_TIME.
2 For each (network address, netmask) pair in the message:
2.1 if an entry in the association set already exists, where:
GW_main_addr == originator address
NET_addr == network address
NET_mask == netmask
then the holding time for that tuple is set to:
GW_time = current time + GW_HOLDING_TIME
2.2 otherwise, a new tuple is recorded with:
GW_main_addr == originator address
NET_addr == network address
NET_mask == netmask
GW_time = current time + GW_HOLDING_TIME
3 If the sender address is the link interface address of a MPR
selector of this node and if the time to live of the message
is greater than '1', the message MUST be forwarded according
to the following:
3.1 The TTL of the message is reduced by one.
3.2 The hop-count of the message is increased by one
3.3 The message is broadcasted on all interfaces (Notice: The
remaining fields of the message header SHOULD be left
unmodified.)
2.3.3.4. Optional Link layer notification
Detection of a link failure between a node and one of its MPR selec-
tors through a link-layer notification may trigger additional TC-mes-
sages to increase the protocols reactiveness to link failures. I.e.
when a change to the MPR selector set is detected and this change can
be attributed to a link failure, an additional TC-message SHOULD be
transmitted.
Thus, if a link failure appears to be a neighbor loss with a neigh-
bor, which has selected this node as MPR, the MPR selector set is
updated (MSSN is thus incremented) and a TC message SHOULD be gener-
ated.
2.3.4. Routing Table Calculation
Each node maintains a routing table which allows it to route data,
destined for the other nodes in the network. The routing table is
based on the information contained in the neighbor sensing informa-
tion base, the interface association set and the topology set. There-
fore, if any of these tables are changed, the routing table is re-
calculated to update the route information about each destination in
the network. The route entries are recorded in the routing table in
the following format:
1. R_dest R_next R_dist R_if_id
2. R_dest R_next R_dist R_if_id
3. ,, ,, ,, 3. ,, ,, ,,
Each entry in the table consists of R_dest, R_next and R_dist, Each entry in the table consists of R_dest, R_next, R_dist, and
which specifies that the node identified by R_dest is estimated to R_if_id which specifies that the node identified by R_dest is esti-
be R_dist hops away from the local node, and that the one hop mated to be R_dist hops away from the local node, and that the sym-
neighbor node with address R_next is the next hop node in the route metric neighbor node with interface address R_next is the next hop
to R_dest. Entries are recorded in the table for each destination node in the route to R_dest, and this one hop is reachable through
in the network for which the route is known. All the destinations the local interface
for which the route is broken or partially known are not entered in R_if_id. Entries are recorded in the table for each destination in
the table. 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.
This routing table is updated when a change is detected in This routing table is updated when a change is detected in the neigh-
the neighbor set, or the topology set. The update of this routing bor information base, or the topology set. More precisely, it is re-
information does not generate or trigger any messages to be calculated in case of neighbor appearance or loss, or when a topology
transmitted, neither in the network, nor in the one-hop tuple is created or removed. The update of this routing information
neighborhood. does not generate or trigger any messages to be transmitted, neither
in the network, nor in the one-hop neighborhood.
To construct the routing table of node X, a shortest path To construct the routing table of node X, a shortest path algorithm
algorithm is run on the directed graph containing the arcs X -> Y is run on the directed graph containing the arcs X -> Y where Y is
where Y is any one hop neighbor of X (with Link Type SYM_LINK or any symmetric neighbor of X (with Link Type SYM_LINK or MPR_LINK) and
MPR_LINK) and the arcs U -> V where there exists an entry in the the arcs U -> V where there exists an entry in the topology set with
topology set with V as T_dest and U as T_last. V as T_dest and U as T_last.
The following procedure is given as an example to calculate (or The following procedure is given as an example to calculate (or re-
re-calculate) the routing table : calculate) the routing table :
1. All the entries from the routing table are removed. 1 All the entries from the routing table are removed.
2. The new routing entries are added starting with the one 2 The new routing entries are added starting with the symmetric
hop neighbors (h=1) as the destination nodes. For each neighbor neighbors (h=1) as the destination nodes. For each neighbor
entry in the neighbor table, whose Link Type is SYM_LINK or tuple in the neighbor set, corresponding to a symmetric link
MPR_LINK, a new routing entry is recorded in the routing table (i.e. N_LOST_time is expired, N_pending == false and
where R_dest and R_next are both set to the address of the N_SYM_time is not expired),
neighbor and R_dist is set to 1. a new routing entry is recorded in the routing table where
R_dest is set to the main address N_main_addr of the neighbor,
R_next is set to the interface address N_if_addr of the neigh-
bor interface, R_dist is set to 1, and R_if_id is set to the
value field N_if_id of the entry. If N_if_addr is distinct of
N_main_addr, another new routing entry with R_dest =
N_main_addr, R_next = N_if_addr, R_if_id = N_if_id and R_dist
= 1 is added.
3. The new route entries for the destination nodes h+1 hops 3 The new route entries for the destination nodes h+1 hops away
away are recorded in the routing table. The following procedure are recorded in the routing table. The following procedure is
is executed for each value of h, starting with h=1 and executed for each value of h, starting with h=1 and increment-
incrementing it by 1 each time. The execution will stop if no ing it by 1 each time. The execution will stop if no new entry
new entry is recorded in an iteration. is recorded in an iteration.
3.1 For each topology entry in the topology table, if its 3.1 For each topology entry in the topology table, if its
T_dest does not correspond to R_dest of any route entry T_dest does not correspond to R_dest of any route entry
in the routing table AND its T_last corresponds to R_dest in the routing table AND its T_last corresponds to R_dest
of a route entry whose R_dist is equal to h, then a new of a route entry whose R_dist is equal to h, then a new
route entry is recorded in the routing table where : route entry is recorded in the routing table (if it does
not already exist) where:
- R_dest is set to T_dest; R_dest is set to T_dest;
- R_next is set to R_next of the route entry whose
R_dest is equal to T_last; and
- R_dist is set to h+1.
7.7 Link layer notification R_next is set to R_next of the recorded route entry
whose R_dest is equal to T_last
OLSR is designed not to impose or expect any specific information R_dist is set to h+1; and
from the link layer. However, if information from the link-layer
is available, a node MAY use this as described in this section.
If link layer information describing connectivity to neighboring R_if_id is set to the value of the R_if_id of the
nodes is available (i.e. loss of connectivity such as through recorded route entry whose R_dest is equal to
absence of a link layer acknowledgment), this information is T_last.
used in addition to the information from the HELLO-messages to
maintain the neighbor set and the MPR selector set.
Subsequently, detection of a link failure through a link-layer The routing table is further completed by using the multiple inter-
notification may trigger additional TC-messages to increase the face association set:
protocols reactiveness to link failures. I.e. when a change to the
MPR selector set is detected and this change can be attributed to
a link failure, a TC-message SHOULD be transmitted.
Thus, upon receiving a link-layer notification that the link 1 For each entry in the multiple interface association where
between a node and any neighbor is broken, the following actions there exists a routing entry such that:
are taken:
1. if the link is broken to either a symmetric or asymmetric R_dest == I_main_addr (of the multiple interface inter-
neighbor, the tuple for that neighbor is removed from the face association entry)
neighbor set, a route entry is created in the routing table with:
2. if the link is broken to a neighbor, which is selected as MPR, R_dest = I_if_addr (of the multiple interface associa-
the tuple for that neighbor is removed from the neighbor tion entry)
set and the MPR set is recalculated,
3. if the link is broken to a neighbor, which has selected this R_next = R_next (of the recorded route entry)
node as MPR, the MPR selector set is updated and a
TC message SHOULD be generated.
8. Packet forwarding R_dist = R_dist (of the recorded route entry)
8.1. Data packet forwarding R_if_id = R_if_id (of the recorded route entry).
OLSR itself does not perform packet forwarding. Rather, it The routing table is finally completed by using the host and network
maintains the routing table in the underlying operating system, association set:
which is assumed to be forwarding packets as specified in RFC1812.
8.2. Control message forwarding 1 For each tuple in the routing set, record an entry in the
routing table, with:
R_dest = NET_addr/NET_mask
R_next = the next hop on the path from the node to
GW_main_addr
R_dist = dist to GW_main_addr
R_next and R_if_id are set to the same values as the
tuple from the routing set with R_dest == GW_main_addr.
3. Node Configuration
3.1. Address Assignment
The nodes in the MANET network SHOULD be assigned addresses within a
defined address sequence. I.e., the nodes in the MANET SHOULD be
addressable through a network address and a netmask.
Likewise, the nodes in each associated network SHOULD be assigned
addresses from a defined address sequence, distinct from that being
used in the MANET.
3.2. Routing Configuration
MANET nodes MUST be configured such that they have a network route
set up on one of the interfaces participating in the MANET. I.e., in
lack of other routing information, any incoming datagrams, destined
for a node in the MANET address sequence, is transmitted onto this
interface (efficiently: incoming data to a MANET node, which the node
cannot find an exact match for, is broadcast to all neighbors)
Any node with associated networks or hosts SHOULD, in addition to the
configuration described above, be configured such that it has routes
set up to the interfaces with associated hosts or network.
3.3. Data Packet Forwarding
OLSR itself does not perform packet forwarding. Rather, it maintains
the routing table in the underlying operating system, which is
assumed to be forwarding packets as specified in RFC1812.
3.4. Control Message Forwarding
Control messages, destined for flooding into the entire network, Control messages, destined for flooding into the entire network,
SHOULD be relayed by the MPR via the following rule: SHOULD be relayed by the MPR via the following rule:
A node retransmits a message only when it is received from one A node retransmits a message only when it is received from one
of its MPR selector AND it is not before registered in the of its MPR selector AND it is not before registered in the
duplicate table AND the time to live is greater than zero. duplicate table AND the time to live is greater than 1 (one).
Before retransmitting, the hop count is incremented by one and the Before retransmitting, the hop count is incremented by one and the
time to live is decremented by one. time to live is decremented by one.
9. Proposed values for the constants 4. IPv6 Considerations
This section list the values for the constants used in the All the operations and parameters described in this document used by
description of the protocol. OLSR for IP version 4 are the same as those used by OLSR for IP ver-
sion 6. However, with IP version 6, we only need to replace all the
4 bytes Ipv4 address field in different messages with 16 bytes Ipv6
address format.
5. Proposed Values for the Constants
This section list the values for the constants used in the descrip-
tion of the protocol.
HELLO_INTERVAL = 2 seconds HELLO_INTERVAL = 2 seconds
TC_INTERVAL = 5 seconds TC_INTERVAL = 5 seconds
MID_INTERVAL = TC_INTERVAL
HNA_INTERVAL = TC_INTERVAL
NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL
TOP_HOLD_TIME = 3 x TC_INTERVAL TOP_HOLD_TIME = 3 x TC_INTERVAL
D_TIME = 30 seconds D_TIME = 30 seconds
I_TIME = 3 x MID_INTERVAL
GW_TIME = 3 x HNA_INTERVAL
HELLO_MESSAGE = 1 HELLO_MESSAGE = 1
TC_MESSAGE = 2 TC_MESSAGE = 2
ASYM_LINK = 1 MID_MESSAGE = 3
SYM_LINK = 2
MPR_LINK = 3
10. Sequence Numbers HNA_MESSAGE = 4
Sequence numbers are used in OLSR with the purpose of discarding ASYM_LINK = 1
"old" information, i.e. messages received out of order. However
with a limited number of bits for representing sequence numbers,
wrap-arounds (that the sequence number is incremented from the
maximum possible value to zero) will occur. To prevent this from
interfering with the operation of the protocol, the following
MUST be observed.
The term MAXVALUE designates in the following the largest possible SYM_LINK = 2
value for a sequence number.
The sequence number S1 is said to be "greater than" the sequence MPR_LINK = 3
number S2 iff:
S1-S2 < MAXVALUE/2 OR LOST_LINK = 4
S1 < MAXVALUE/2 AND S2 > S1 + MAXVALUE/2
Thus when comparing two messages, it is possible - even in the HYST_THRESHOLD_HIGH = 0.8
presence of wrap-around - to determine which message contains the
most recent information.
11. References HYST_THRESHOLD_LOW = 0.3
1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing HYST_SCALING = 0.5
reliability in cable free radio LANs: Low level forwarding in
HIPERLAN. Wireless Personal Communications, 1996
2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An MAXJITTER = 0.5
efficient technique for flooding in mobile wireless networks.
INRIA research report RR-3898, 2000
3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN 6. Sequence Numbers
type 1, functional specifications ETS 300-652, ETSI, June 1996
4. Corson et al. Internet MANET Encapsulation Protocol. Internet Sequence numbers are used in OLSR with the purpose of discarding
draft, draft-ietf-manet-imep-spec-01.txt, Work in progress. "old" information, i.e. messages received out of order. However with
a limited number of bits for representing sequence numbers, wrap-
arounds (that the sequence number is incremented from the maximum
possible value to zero) will occur. To prevent this from interfering
with the operation of the protocol, the following MUST be observed.
5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet The term MAXVALUE designates in the following the largest possible
draft, draft-ietf-manet-term-00.txt, work in progress. value for a sequence number.
6. Corson, S., MANET Routing Protocol Applicability Statement, The sequence number S1 is said to be "greater than" the sequence num-
Internet draft, draft-ietf-manet-appl-00.txt, Work in progress. ber S2 iff:
7. S. Bradner. Key words for use in RFCs to Indicate Requirement S1-S2 < MAXVALUE/2 OR
Levels. Request for Comments (Best Current Practice) 2119,
Internet Engineering Task Force, March 1997.
8. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc S1 < MAXVALUE/2 AND S2 > S1 + MAXVALUE/2
Network Protocols, INRIA research report RR-3965, 2000
12. Authors' Addresses Thus when comparing two messages, it is possible - even in the pres-
ence of wrap-around - to determine which message contains the most
recent information.
Amir Qayyum 7. Acknowledgments
Project HIPERCOM The authors would like to thank Joseph Macker and his team
INRIA Rocquencourt <macker@itd.nrl.navy.mil> for their valuable suggestions on the
BP 105 advanced neighbor sensing mechanism.
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5273
Email: Amir.Qayyum@inria.fr
Philippe Jacquet 8. References
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5263
Email: Philippe.Jacquet@inria.fr
Anis Laouiti 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia-
Project HIPERCOM bility in cable free radio LANs: Low level forwarding in HIPERLAN.
INRIA Rocquencourt Wireless Personal Communications, 1996
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 508832
Email: Anis.Laouiti@inria.fr
Laurent Viennot 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient
Project HIPERCOM technique for flooding in mobile wireless networks. INRIA research
INRIA Rocquencourt report RR-3898, 2000
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5225
Email: Laurent.Viennot@inria.fr
Paul Muhlethaler 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type
Project HIPERCOM 1, functional specifications ETS 300-652, ETSI, June 1996
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
Email: Thomas.Clausen@inria.fr
Thomas Clausen 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net-
Project HIPERCOM work Protocols, INRIA research report RR-3965, 2000
INRIA Rocquencourt
BP 105 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev-
78153 Le Chesnay Cedex, France els. Request for Comments (Best Current Practice) 2119, Internet
Phone: +33 1 3963 5133 Engineering Task Force, March 1997.
Email: Thomas.Clausen@inria.fr
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/