draft-ietf-manet-olsr-01.txt   draft-ietf-manet-olsr-02.txt 
INTERNET-DRAFT Philippe Jacquet INTERNET-DRAFT Philippe Jacquet
IETF MANET Working Group Paul Muhlethaler IETF MANET Working Group Paul Muhlethaler
Expiration: 7 August 2000 Amir Qayyum Expiration: 18 January 2001 Amir Qayyum
Anis Laouiti
Laurent Viennot
Thomas Clausen
INRIA Rocquencourt, France INRIA Rocquencourt, France
7 February 2000 18 July 2000
Optimized Link State Routing Protocol Optimized Link State Routing Protocol
draft-ietf-manet-olsr-01.txt draft-ietf-manet-olsr-02.txt
Status of this Memo Status of this Memo
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 except that the right to
produce derivative works is not granted. 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 groups may also distribute working documents as other groups may also distribute working documents as
skipping to change at page 1, line 41 skipping to change at page 1, line 45
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 of the pure link state algorithm tailored to the optimization of the pure link state algorithm tailored to the
requirements of a mobile wireless LAN. The key concept used in the requirements of a mobile wireless LAN. The key concept used in the
protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are
the selected nodes which forward the broadcast packets during the selected nodes which forward broadcast packets during the flooding
flooding process. This technique substantially reduces the packet process. This technique substantially reduces the packet overhead
overhead as compared to pure flooding mechanism where every node as compared to pure flooding mechanism where every node retransmits
retransmits the packet when it receives the first copy of the the packet when it receives the first copy of the packet. In OLSR
packet. In OLSR protocol, the information flooded in the network protocol, the information flooded in the network "through" these
"through" these multipoint relays is also "about" the multipoint multipoint relays is also "about" the multipoint relays. Thus a
relays. Hence, a second optimization is achieved here by minimizing second optimization is achieved by minimizing the "contents" of the
the "contents" of the control packet flooded in the network. Hence, control packets flooded in the network. Hence, as contrary to the
as contrary to the classic link state algorithm, only a small classic link state algorithm, only a small subset of links with the
subset of links with the neighbor nodes are declared instead of all neighbor nodes are declared instead of all the links. This
the links. This information is then used by OLSR protocol for route information is then used by the OLSR protocol for route
calculation, and therefore the routes contain only the MPRs as the calculation. As a consequence hereof, the routes contain only the
intermediate nodes from Source to Destination. It results in MPRs as intermediate nodes from a Source to a Destination. OLSR
providing the optimal routes (in terms of number of hops), and provides optimal routes (in terms of number of hops). The protocol
hence another optimization. The protocol is particularly suitable is particularly suitable for large and dense networks as the
for the large dense networks as the technique of multipoint relays technique of multipoint relays works well in this context.
works well in this context.
Contents
Status of This Memo 1
Abstract 1
1. Introduction 2
2. Changes 3
3. OLSR terminology 4
4. Applicability Section 5
4.1 Networking Context 5
4.2 Protocol Characteristics and Mechanisms 5
5. Protocol Overview 7
6. Multipoint relays 9
7. Protocol functioning 10
7.1 Packet format 10
7.1.1 Packet Header 11
7.1.2 Extension Header 12
7.1.3 Packet Processing 12
7.2 Neighbor sensing 13
7.2.1 HELLO message broadcast 13
7.2.2 HELLO message processing 16
7.2.3 Link Notification 18
7.3 Multipoint relay selection 19
7.4 Multipoint relay information declaration 20
7.4.1 TC message broadcast 20
7.4.2 TC message processing 23
7.5 Routing table calculation 25
8. Packet Forwarding 27
8.1 Data packet forwarding 27
8.2 Topology Control (TC) packet forwarding 27
9. Proposed values for constants 27
10. References 28
11. Authors' addresses 29
1. Introduction 1. Introduction
This Optimized Link State Routing protocol inherits the concept of This Optimized Link State Routing protocol inherits the concept of
forwarding and relaying from HIPERLAN (a MAC layer protocol) which forwarding and relaying from HIPERLAN (a MAC layer protocol) which
is standardized by ETSI [3]. OLSR protocol is developed in the is standardized by ETSI [3]. The OLSR protocol is developed in the
IPANEMA project (part of Euclid program) and in the PRIMA project IPANEMA project (part of Euclid program) and in the PRIMA project
(part of RNRT program). (part of RNRT program).
This protocol is developed for the mobile adhoc networks. It This protocol is developed for mobile ad hoc networks. It operates
functions as a table driven or proactive protocol and exchanges as a table driven or proactive protocol and exchanges topology
topology information with other nodes of the network at regular information with other nodes of the network at regular intervals.
intervals. The nodes which are selected as a multipoint relay by The nodes which are selected as a multipoint relay by some neighbor
some neighbor nodes announce this information periodically in their nodes announce this information periodically in their control
control messages. The protocol uses the multipoint relays to do messages. The protocol uses the multipoint relays to facilitate
efficient flooding of its control messages in the network. In route efficient flooding of control messages in the network. In route
calculation, these are the multipoint relays which are used to form calculation, the multipoint relays are used to form the route from
the route towards any destination in the network. a given node to any destination in the network.
Multipoint relays are selected among the one hop neighbors with Multipoint relays are selected by a node among its one hop
"symmetric" i.e. bi-directional link. Therefore, selecting the neighbors with "symmetric", i.e. bi-directional, link. Therefore,
route through multipoint relays automatically avoids the problems selecting the route through multipoint relays automatically avoids
associated with data packet transfer on uni-directional links; like the problems associated with data packet transfer on
the problem of getting the acknowledgement for the data packets at uni-directional links (such as the problem of getting the
each hop, which cannot be received if there is a uni-directional acknowledgement for the data packets at each hop)
link in the selected route.
OLSR protocol is developed to work independently. But it can be The OLSR protocol is developed to work independently from other
modified to work with a protocol (like IMEP protocol [4]) which protocols. But it can be adapted to operate with a protocol (like
could provide common functionalities such as neighbor sensing, IMEP [4]) which could provide common functionalities such as
multipoint relaying, security authentication, etc. neighbor sensing, multipoint relaying, security authentication,
etc.
2. OLSR terminology 2. Changes
OLSR protocol uses the following terminology, in addition to the Major changes from version 01 to version 02
terms defined in [5].
- Introduction of a unified packet format for encapsulation of
all messages being exchanged between nodes. This also serves
to facilitate extensions in future versions of the protocol
(i.e. introduction of new protocol messages) without breaking
backwards compatibility.
- Removal of "Power Conservation" from this draft. Power
Conservation may be considered as an extension to the basic
routing capabilities, and the information is therefore moved
to draft-ietf-manet-olsr-extensions-00.txt.
3. OLSR Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECCOMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC2119 [9].
The OLSR protocol uses the following terminology, in addition to
the terms defined in [5].
connection connection
A communication channel or medium *on the same physical A communication channel or medium *on the same physical
interface*, over which the nodes can communicate with each interface*, over which the nodes can communicate with each
other. other.
holding time holding time
The lifetime associated to an entry in any table. That entry is The lifetime associated with an entry in any table. An entry is
kept in the table for a period equal to its holding time. If the kept in the table for a period of time, equal to its holding
entry is not refreshed during this period, it is removed from time. If the entry is not refreshed during this period, it is
the table when its holding time expires. 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 packets that it will receive "re-transmit" all the broadcast packets that it receive from X,
from X, provided that the same packet is not already received, provided that the same packet is not already received, and the
and the hop count field of the packet is greater than zero. hop count field of the packet is greater than zero.
multipoint relay selector (MPR-S) multipoint relay selector (MPR-S)
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 the multipoint relay selector of multipoint relay, will be called the multipoint relay selector
node X. of node X.
node node
A MANET router that implements this Optimized Link State Routing A MANET router which implements this Optimized Link State
protocol. Routing protocol.
symmetric link symmetric link
A bi-directional *link* (not connection) between two neighbor A bi-directional *link* (not connection) between two neighbor
nodes, i.e. node X and node Y, both can hear each other. This nodes, i.e. node X and node Y where both can hear each
bi-directional link can be a union of two oppositely-directed other. This bi-directional link can be a union of two
uni-directional connections using different interfaces. oppositely-directed uni-directional connections using different
interfaces.
3. Applicability Section 4. Applicability Section
This section dictates the characteristics of the OLSR protocol, as This section dictates the characteristics of the OLSR protocol as
specified in the Applicability Statement draft [6]. specified in the Applicability Statement draft [6].
3.1. Networking Context 4.1. Networking Context
The protocol is best suited to the large dense networks, as the The protocol is best suited to large and dense networks, as the
optimization done using the multipoint relays works well in this optimization achieved using the multipoint relays works well in
context. More the network is dense and large, more optimization is this context. The larger and more dense a network, the more
achieved as compared to the normal link state algorithm. OLSR uses optimization can be achieved as compared to the normal link state
the hop-by-hop routing, i.e. each node uses its most recent algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its
information to route the packet. So when a node is moving, its most recent information to route packets. Thus when a node is
speed should be such that its movement could be followed in *at moving, its speed should be such that its movement could be
least* its neighborhood, to correctly route the packets to the followed in *at least* its neighborhood, in order to correctly
destination. route packets to the destination.
This protocol is best suited for the networks where the traffic is This protocol is best suited for networks where the traffic is
random and sporadic between "several" nodes instead of being random and sporadic between "several" nodes rather than being
between a small specific set of nodes of the network. The almost exclusively between a small specific set of nodes in the
comparative performance of the protocol with a reactive protocol is network. The performance of the protocol when comparing to a
still better if these [source, destination] pairs change with reactive protocol is even better if these [source, destination]
time. These changes may initiate substantial traffic (Query flooding) pairs change with time [8]. Such changes may initiate substantial
in case of reactive protocol, but nothing in OLSR, as the routes traffic (Query flooding) in case of reactive protocol, but nothing
are maintained for each known destination all the time. in OLSR, as the routes are maintained for each known destination
all the time.
3.2. Protocol Characteristics and Mechanisms 4.2. Protocol Characteristics and Mechanisms
* Does the protocol provide support for unidirectional links? (if so, * Does the protocol provide support for unidirectional links? (if
how?) so, how?)
No. It uses only bi-directional links (like in 802.11), but No. It uses only bi-directional links (like in 802.11), but
these links may be composed of oppositely directed these links may be composed of oppositely directed
uni-directional "connections". uni-directional "connections".
* Does the protocol require the use of tunneling? (if so, how?) * Does the protocol require the use of tunneling? (if so, how?)
No. No.
* Does the protocol require using some form of source routing? (if * Does the protocol require using some form of source routing? (if
so, how?) so, how?)
No. The protocol uses hop-by-hop routing. No. The protocol uses hop-by-hop routing.
* Does the protocol require the use of periodic messaging? (if so, * Does the protocol require the use of periodic messaging? (if so,
how?) how?)
Yes. Periodically, each node in the network send a message Yes. Periodically, each node in the network send a message
containing the addresses of its neighbors who has selected that containing the addresses of the neighbors which have selected
node as a multipoint relay. This information helps other nodes that node as a multipoint relay. This information enables other
to build routes to that node through these multipoint relay nodes to build routes to that node through the multipoint
selectors. relays.
* Does the protocol require the use of reliable or sequenced packet * Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?) delivery? (if so, how?)
No. As the packets are sent periodically, they need not be sent No. As the packets are sent periodically, they need not be sent
reliably. Each packet not only contains a unique Packet Sequence reliably. Each packet not only contains a unique Packet Sequence
Number, but it also contains the sequence number for the most Number, but it also contains the sequence number for the most
recent information (for example "MPR Sequence Number" in the TC recent information (for example "MPR Sequence Number" in the TC
packet), so un-sequenced delivery of packets will also not packet), so un-sequenced delivery of packets will also not
create any problem. create any problem.
skipping to change at page 6, line 5 skipping to change at page 7, line 5
Yes. Yes.
* Does the protocol require link or neighbor status sensing (if so, * Does the protocol require link or neighbor status sensing (if so,
how?) how?)
Yes. The protocol requires the link status sensing. This service Yes. The protocol requires the link status sensing. This service
is provided by sending/receiving periodic HELLO messages to/from is provided by sending/receiving periodic HELLO messages to/from
one hop neighbors. one hop neighbors.
* Does the protocol have dependence on a central entity? (if so, * Does the protocol depend on a central entity? (if so, how?)
how?)
No. All the routers in the network have their own routing tables No. All the routers in the network have their own routing tables
and does not depend on any specific node. and do not depend on any specific node.
* Does the protocol function reactively? (if so, how?) * Does the protocol function reactively? (if so, how?)
No. But it decreases and increases the interval (within certain No. But it decreases and increases the interval (within certain
limits) of sending the TC packet periodically, depending upon limits) of sending the TC packet periodically, depending upon
the rate of link changes in its neighborhood. the rate of link changes in its neighborhood.
* Does the protocol function proactively? (if so, how?) * Does the protocol function proactively? (if so, how?)
Yes. It periodically sends the information about its multipoint Yes. It periodically sends the information about its multipoint
relay selectors, which helps other nodes to build routes to it. relay selectors, which helps other nodes to build routes to it.
* Does the protocol provide loop-free routing? (if so, how?) * Does the protocol provide loop-free routing? (if so, how?)
As the protocol uses link state algorithm, so the routing is As the protocol uses a link state algorithm, the routing is
loop-free in a stable state. loop-free when in a stable state.
* Does the protocol provide for sleep period operation? (if so, how?) * Does the protocol provide for sleep period operation? (if so, how?)
Yes, it can provide support for sleep period operation. To Yes, OLSR can provide support for sleep period operation. To
enable this feature, the protocol should select its multipoint enable this feature, a node should select its multipoint relays
relays from only among the nodes which can (or agree to) store from among those neighbors which can (or agree to) store its
its packets while it is in sleep mode. packets while it is in sleep mode.
* Does the protocol provide some form of security? (if so, how?) * Does the protocol provide some form of security? (if so, how?)
No, not itself. It can use other protocols (like IMEP [4]) which No, not itself. It can use other protocols (like IMEP [4]) which
provide authentication and security. provide authentication and security.
* Does the protocol provide support for utilizing multi-channel, * Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?) link-layer technologies? (if so, how?)
Yes. Each interface has a unique IP address. Yes. Each interface has a unique IP address.
4. Protocol Overview 5. Protocol Overview
OLSR is a proactive routing protocol for mobile adhoc networks. OLSR is a proactive routing protocol for mobile adhoc networks.
The protocol inherits the stability of a link state algorithm and The protocol inherits the stability of a link state algorithm and
has the advantage of having the routes immediately available when has the advantage of having the routes immediately available when
needed due to its proactive nature. OLSR protocol is an needed due to its proactive nature. OLSR is an optimization over
optimization of the pure link state protocol, tailored for the the pure link state protocol, tailored for mobile ad hoc networks.
mobile adhoc networks. First, it reduces the size of the control
packets: instead of all links, it declares only a subset of links
with its neighbors who are its multipoint relay selectors (see
section 5 on Multipoint Relays). Secondly, it minimizes flooding of
its control traffic by using only the selected nodes, called
multipoint relays, to diffuse its messages. This technique
significantly reduces the number of retransmissions in a flooding
or broadcast procedure.
Apart from its normal periodic control messages, the protocol does Firstly, it reduces the size of the control packets: rather than
not generate extra control traffic in response to link failures and declaring all links, a node declares only a subset of links with
additions. Thus it is suitable for networks with a high rate of its neighbors, namely the links to those nodes which are its
topological changes. As OLSR protocol keeps the routes for all the multipoint relay selectors (see section 6 on Multipoint Relays).
destinations in the network so the protocol is beneficial for the Secondly, OLSR minimizes flooding of control traffic by using only
traffic patterns where a large subset of network nodes are selected nodes, called multipoint relays, to diffuse its messages.
communicating with another large subset of nodes, and the This technique significantly reduces the number of retransmissions
[source,destination] pairs are also changing with time. The in a flooding or broadcast procedure.
protocol is particularly suited to large and dense networks, as the
The protocol MAY optimize the reactivity to topological changes by
reducing the time interval for periodic control message
transmission. Furthermore, as OLSR protocol keeps the routes for
all destinations 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 changing over time. The protocol is
particularly suited for large and dense networks, as the
optimization done using the multipoint relays works well in this optimization done using the multipoint relays works well in this
context. More dense and large a network is, more optimization is context. The larger and more dense a network, the more optimization
achieved as compared to the normal link state algorithm. can be achieved as compared to the normal link state algorithm.
The protocol is designed to work in a completely distributed manner The protocol is designed to work in a completely distributed manner
and thus does not depend upon any central entity. The protocol does and thus does not depend on any central entity. The protocol does
not require a reliable transmission for its control messages: each NOT REQUIRE reliable transmission for control messages: each node
node sends its control messages periodically, and can therefore sends control messages periodically, and can therefore sustain an
sustain a loss of some packets from time to time, which arrives occasional loss of some packets. Such losses occur very often in
very often in the radio networks due to collisions or other the radio networks due to collisions or other transmission
transmission errors and problems. The protocol also does not need a problems. Also, the protocol does NOT REQUIRE sequenced delivery of
sequenced delivery of its messages, as each control message messages. Each control message contains a sequence number which is
contains a sequence number of the most recent information. So the incremented for each message. Thus the recipient of a control
re-ordering at the receiving end can not affect the functioning of packet can easily identify which information is newer - even if
the protocol. Furthermore, it provides support for the sleep mode messages have been re-ordered while in transmission.
operation, which is quite advantageous for the battery operated
small terminals.
OLSR protocol does not do the source routing. Instead it performs Furthermore, OLSR provides support for protocol extensions such as
hop by hop routing, i.e. each node uses its most recent information sleep mode operation, multicast-routing etc. Such extensions may be
to route the packet. Hence, when a node is moving, its speed should introduced as additions to the protocol without breaking backwards
be such that its movement could be followed in at least its compatibility with earlier versions.
neighborhood, to correctly route the packets to the
destination.
The protocol does not require any change in the IP format of OLSR performs hop by hop routing, i.e. each node uses its most
packets and classical IP stack can be used as it is, since the recent information to route the packet. Hence for OLSR to be able
protocol only impacts the routing table management. to route packets, the speed of mobile nodes should be limited such
that their movements can be tracked, at least by their neighborhood.
5. Multipoint relays OLSR does NOT REQUIRE any changes to the format of IP packets. Thus
any existing IP stack can be used as it is: the protocol only
interacts with routing table management.
The idea of multipoint relays is to minimize the flooding of 6. Multipoint Relays
broadcast messages in the network by reducing duplicate
retransmissions in the same region. Each node in the network
selects a set of nodes in its neighborhood, which retransmit its
packets. This set of 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, read and process the packet but do
not retransmit the broadcast message received from node N.
Each node selects its multipoint relay set among its one hop The idea of multipoint relays is to minimize flooding of broadcast
neighbors in such a manner that it covers (in terms of radio range) messages in the network by reducing duplicate retransmissions in
all the nodes that are two hops away. We define the neighborhood of the same region. Each node in the network selects a set of nodes in
any node N as the set of nodes which have a symmetric link to N. We its neighborhood which may retransmit its packets. This set of
define the two hop neighborhood of N as the set of nodes which 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
broadcast messages received from node N.
Each node selects its MPR set among its one hop neighbors. This set
is selected such that it covers (in terms of radio range) all the
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
two 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 don't have a symmetric link to N but have a symmetric link to the
neighborhood of N. The multipoint relay set of N (we can call as neighborhood of N. The multipoint relay set of N, denoted as MPR(N),
MPR(N) ) is an arbitrary subset of the neighborhood of N which is then an arbitrary subset of the neighborhood of N which
satisfies the following condition: every node in the two hop satisfies the following condition: every node in the two hop
neighborhood of N must have a symmetric link toward MPR(N). The neighborhood of N MUST have a symmetric link toward MPR(N). The
smaller the multipoint relay set is, the more optimal is the smaller the multipoint relay set is, the more optimal is the
routing protocol. [2] gives an analysis and example about routing protocol. [2] gives an analysis and example about
multipoint relay selection algorithms. multipoint relay selection algorithms.
Each node has a set of its neighbors which are called the Each node maintains information about a set of its neighbors. This
"Multipoint Relay Selectors" of the node. A node obtain this is the set of neighbors, called the "Multipoint Relay Selectors",
information from the periodic HELLO messages of its neighbors. A which have selected the node as a MPR. A node obtain this
broadcast message intended to be diffused in the whole network information from the periodic HELLO messages received from the
coming from these MPR Selector neighbor nodes is assumed to be neighbors. A broadcast message, intended to be diffused in the
retransmitted by the node. This set can change over time, which is whole network, coming from these MPR Selector neighbor nodes is
indicated by the selector nodes in their HELLO messages. Each node assumed to be retransmitted by the node. This set can change over
has a specific Multipoint relay Selector Sequence Number (MSSN) 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, associated with this set. Whenever its MPR selector set is updated,
the node also increments its MSSN. the node also increments its MSSN.
OLSR protocol relies on the selection of multipoint relays, and OLSR relies on selection of multipoint relays, and calculates the
calculates the routes to a destination through these nodes, i.e. routes to a destination through these nodes. I.e. MPR nodes are
MPR nodes are selected as intermediate nodes. To implement this, selected as intermediate nodes in the path between a source and a
each node in the network periodically broadcast the information destination. To implement this, each node in the network
describing which neighbors have selected it as a multipoint relay. periodically broadcast the information describing which neighbors
Upon receipt of this "MPR Selectors" information, each node have selected it as a multipoint relay. Upon receipt of this "MPR
calculates or updates the route to each known destination. So Selectors" information, each node calculates or updates the route
principally, the route is a sequence of hops through the multipoint to each known destination. So principally, the route is a sequence
relays from source to the destination. of hops through the multipoint relays from source to the
destination.
Multipoint relays are selected among the one hop neighbors with Multipoint relays are selected among the one hop neighbors with
"symmetric" i.e. bi-directional link. Therefore, selecting the "symmetric" i.e. bi-directional link. Therefore, selecting the
route through multipoint relays automatically avoids the problems route through multipoint relays automatically avoids the problems
associated with data packet transfer on uni-directional links such associated with data packet transfer on uni-directional links such
as the problem of getting an acknowledgement for the data packets as the problem of getting an acknowledgement for the data packets
at each hop which cannot be received if there is a uni-directional at each hop.
link in the selected route.
6. Protocol functioning 7. Protocol Functioning
OLSR protocol carry out different functions which are required to In this section we describe the details of the protocol
perform the task of routing. Here we discuss these functionalities functioning. This includes descriptions of the format and contents
of the protocol. of the packets being exchanged by routers, the algorithms (e.g. for
packet handling and routing table calculation) and suggested data
structures internally in each router.
6.1. Neighbor sensing 7.1. Packet Format
6.1.1. HELLO message broadcast OLSR communicates using an unified packet format for all data
related to the protocol. Inspired by the concept of "extension
headers" from IPv6, 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.
Each node must detect the neighbor nodes with which it has a direct The basic layout of any packet in OLSR will be as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Reserved for future use |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Broadcast | Next Message |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: :
: MESSAGE :
: :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Broadcast | Next Message |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: :
: MESSAGE :
: :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
(etc)
7.1.1. Packet Header
Destination Address
The address of the node(s) to receive this packet. This will
often be the broadcast address (i.e. all nodes in the
neighborhood) but may also be the unicast-address of a node.
Source Address
The address of the node which is transmitting this packet. A
packet may contain messages, which originate from other nodes
(see section 7.4). In that case, the message itself MUST contain
an originator address, since the source address of the packet
will be the address of the node retransmitting the message.
Packet Length
The length (in bytes) of the packet
Reserved for future use
MUST be set to '0000000000000000' to be in compliance with this
version of the draft.
The information in the header of this packet is equivalent to the
information obtainable from the UDP header.
7.1.2. Extension Header
Message Type
This field indicates which type of message are to be found in
the "MESSAGE" partition. Message types in the range of 0-127 are
reserved for messages in this draft and in
draft-ietf-manet-olsr-extensions-00.txt.
Broadcast
This field indicates to a node whether the message is meant for
diffusion into the entire network. This enables a node to
forward messages correctly, even if it doesn't recognize the
"Message Type".
Next Message
This field gives the offset where the next "extension header"
can be found, allowing a node to skip through the messages.
7.1.3. Packet Processing
Upon receiving such a basic packet, the protocol parser examines
each of the "extension headers". Based on the value of the "Message
Type" field, the parser can determine the faith of the data portion
of the message:
1. If the data are of a type which the receiving node can
process, then this data is processed.
2. Otherwise, if the "Message Type" indicates a type, unknown to
the node, the "Broadcast" field MUST be examined.
2.1 If the "Broadcast" field indicates that the message is
to be retransmitted (i.e. is set to 'BROADCAST'), and if
the recipient is a MPR of the sender, then the message
MUST be retransmitted by the node.
2.2 Otherwise, the message SHOULD silently be dropped.
By defining a set of message types, which MUST be recognized by all
implementations of OLSR, it will be possible to extend the protocol
through introduction of additional message types, while still be
able to maintain compatibility with older implementations. The two
REQUIRED message types for OLSR are:
- HELLO-messages, performing the task of neighbor sensing.
- TC-messages, performing the task of multipoint relay
information declaration.
Extensions may e.g. be PC-messages for enabling power conservation
/ sleep mode, multicast routing, gateway announcements etc.
7.2. Neighbor sensing
7.2.1. HELLO message broadcast
Each node MUST detect the neighbor nodes with which it has a direct
and symmetric link. The uncertainties over radio propagation may and symmetric link. The uncertainties over radio propagation may
make some links asymmetric. Consequently, all links must be checked make some links asymmetric. Consequently, all links MUST be checked
in both directions in order to be considered valid. in both directions in order to be considered valid.
To accomplish this, each node periodically broadcasts its HELLO To accomplish this, each node broadcasts HELLO messages, containing
messages, containing the information about its neighbors and their information about neighbors and their link status. The link status
link status. These control packets are transmitted in the broadcast may either be "symmetric", "heard" (asymmetric) or "MPR".
mode. These are received by all one-hop neighbors, but they are "Symmetric" indicates, that the link has been verified to be
*not relayed* to further nodes. A HELLO message contain: bi-directional, i.e. it is possible to transmit data in both
directions. "Heard" indicates that the node is hearing from a
neighbor, but it is not confirmed that this neighbor is also
hearing from the node. "MPR" indicates, that a node is selected by
the sender as multipoint relay. MPR status implies that the link is
symmetric too.
- list of addresses of the neighbors to which there exists a These control messages are broadcast to all one-hop neighbors, but
valid symmetric link; are *not relayed* to further nodes. A HELLO-message contains at a
- list of addresses corresponding to heard nodes, i.e., the minimum:
nodes which are heard by this node (a HELLO has been received)
but the link is not yet validated as symmetric - a list of addresses of neighbors, to which there exists a
The list of neighbors in the HELLO packet can be partial, the rule symmetric link;
- a list of addresses of neighbors, which have been "heard";
- a list of neighbors, which have been selected as multipoint
relays.
The list of neighbors in a HELLO message can be partial (e.g. due
to message size limitations, imposed by the network), the rule
being that all neighbor nodes are cited at least once within a being that all neighbor nodes are cited at least once within a
predetermined refreshing period (HELLO_INTERVAL). predetermined refreshing period (HELLO_INTERVAL).
The proposed format of a HELLO packet is To accommodate for the above constraints, as well as to accommodate
for future extensions, an approach similar to the overall packet
format (see section 6.1) 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address | | Message Sequence Number | MPR Sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Packet Sequence Number | | Link Type | Reserved | Next Link Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Type | Unused | MPR Sequence number | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Status | Neighbor : . . . :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Address | Neighbor Status | | Link Type | Reserved | Next Link Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
: :
(etc)
6.1.1.1. Description of the fields 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
Destination address the broadcast field set to NO_BROADCAST.
For all the HELLO packets, this 4-bytes address field is always 7.2.1.1. Description of the fields
set to the broadcast address of the network, so that when this
packet is transmitted, each neighbor node get this information
and hence update its neighbor table.
Source address Message Sequence Number
It is set to the address of the node transmitting this HELLO While generating a HELLO message, the node will assign a unique
packet. identification number to this message. This number is put into
the Sequence Number field. This sequence number will be
different for all the messages originated by that node.
Packet Length MPR Sequence Number
This field contains the length of the HELLO packet in bytes, This field indicates the sequence number corresponding to the
starting from the Packet Type field, i.e., length of rest of the most recent multipoint relay set, calculated by the sender node.
packet.
Packet Sequence Number Reserved
While generating the HELLO packet, the node will assign a unique This field is reserved for future usage, and MUST be set to
identification number to this packet, and will put this number 00000000 for compliance with this draft.
in the Sequence Number field. This sequence number will be
different for all the packets originated by that node.
Packet Type Link Type
The Packet Type field is set to the HELLO_PACKET value. This field specifies the type of link the sending node has to
the following list of neighbors. As a minimum, the following
three link types are REQUIRED by OLSR:
Unused - ASYM_LINK - indicating that the links between the sender
and the neighbors in the following list are asymmetric
(i.e. the neighbor is "heard").
This unused one byte field is reserved for the future use. - SYM_LINK - indicating that the links between the sender
and the neighbors in the following list are symmetric.
MPR Sequence Number - MPR_LINK - indicating, that the nodes in the following
list have been selected by the sender as multipoint
relays.
(Notice: this implies, that the links from the sender
of the HELLO and to the nodes in the list are symmetric).
This field indicates the sequence number with which the most It is possible to provide additional information by specifying
recent multipoint relay set is calculated by the sender node. additional link-types, e.g. LOST_LINK - indicating that the link
between the sender and the neighbors in the following list has
been lost.
[Neighbor Address, Neighbor Status] Neighbor Address
These pairs of fields contain, one by one, all the addresses of The address of a neighbor.
the neighbor nodes present in the neighbor table, along with
their link status.
6.1.2. HELLO message processing 7.2.2. HELLO message processing
The HELLO messages permit each node to learn the knowledge of its The HELLO messages permit each node to acquire information about
neighborhood up to two hops. A node maintains a Neighbor table in its neighborhood up to two hops. A node maintains a Neighbor table
which it records the information obtained from the HELLO messages, in which it records the information (obtained from the HELLO
about its one hop neighbors, the status of the link with these messages) about its one hop neighbors, the status of the link with
neighbors, and a list of two hop neighbors that these one hop these neighbors, and a list of two hop neighbors that these one hop
neighbors give access to. The information is recorded in the neighbors give access to. The information is recorded in the
Neighbor table as a neighbor entry, which may have the following Neighbor table as a neighbor entry, which may have the following
format to record these entries: format:
N_MPR_seq N_MPR_seq
1. N_addr N_status N_2hop_list N_time 1. N_addr N_status N_2hop_list N_time
2. N_addr N_status N_2hop_list N_time 2. N_addr N_status N_2hop_list N_time
3. ,, ,, ,, ,, 3. ,, ,, ,, ,,
Each entry in the table consists of N_addr, N_status, N_2hop_list, Each entry in the table consists of N_addr, N_status, N_2hop_list,
and N_time, which specifies that the node with address N_addr is a and N_time. This specifies that the node with address N_addr is a
one-hop neighbor to this node, the status of the link between them one-hop neighbor to this node, the status of the link between them
is N_status, and this neighbor provides access to the two hop is N_status, and this neighbor provides access to the two hop
neighbors listed in N_2hop_list. The N_status can be ASYM_LINK, neighbors listed in N_2hop_list. The N_status can be ASYM_LINK,
SYM_LINK or MPR_LINK. The link status as MPR_LINK implies that the SYM_LINK or MPR_LINK. A link status of MPR_LINK implies that the
link with the neighbor node N_addr is symmetric *AND* the node link with the neighbor node N_addr is symmetric *AND* the node
N_addr is selected as a multipoint relay by this node. Each N_addr is selected as a multipoint relay by this node. Each
neighbor entry has an associated holding time N_time, upon expiry neighbor entry has an associated holding time N_time, upon
of which it is no longer valid and hence removed. expiration of which it is no longer valid and hence MUST be
removed.
The neighbor table also contains a sequence number N_MPR_seq which The neighbor table also contains a sequence number N_MPR_seq. This
specifies that the node keeping this neighbor table has selected specifies that the node keeping this neighbor table has selected
its most recent MPR set with the sequence number N_MPR_seq. Every its most recent MPR set with the sequence number N_MPR_seq. Every
time a node selects or updates its multipoint relay set, this time a node selects or updates its multipoint relay set, N_MPR_seq
N_MPR_seq is incremented to a higher value. is incremented to a higher value. This number is put into the HELLO
messages as described in 6.2.1.
On reception of a HELLO message, the node updates the neighbor Upon receiving a HELLO message, the node updates the neighbor entry
entry corresponding to the sender node address: corresponding to the sender node address:
1. If the entry already exists: 1. If the entry already exists:
1.1 the holding time of the entry is refreshed to 1.1 the holding time of the entry is refreshed to
NEIGHB_HOLD_TIME NEIGHB_HOLD_TIME
1.2 if the node finds its own address in one of the 1.2 if the node finds its own address among the addresses
[Neighbor, Status] pairs in the HELLO message, it updates listed in the HELLO message, it updates the status of the
the status of the link to the sender node as SYM_LINK if link to the sender node as SYM_LINK if it was ASYM_LINK
it was ASYM_LINK before. before.
2. Otherwise a new entry is recorded in the Neighbor table with: 1.3 the N_2hop_list of the entry is updated to reflect the
contents of the HELLO-message.
2. Otherwise, a new entry is recorded in the Neighbor table with:
2.1 N_addr is set to the address of the sender node
2.1 N_addr is set to the sender node address
2.2 N_status is set to the value of ASYM_LINK (asymmetric 2.2 N_status is set to the value of ASYM_LINK (asymmetric
link) link)
2.3 N_2hop_list is filled with the list of addresses 2.3 N_2hop_list is filled with the list of addresses
contained in the HELLO message in the [Neighbor, Status] contained in the HELLO message which have a link type of
pairs for which the Status is *NOT* asymmetric and which SYM_LINK or MPR_LINK, and which are not already present
are not already present in the Neighbor table (i.e., they in the Neighbor table (i.e., they are not one-hop
are not one-hop neighbors). If a node finds its own neighbors).
address in the [Neighbor, Status] pair, it does not
register itself in the N_2hop_list, and it changes the If a node finds its own address in a HELLO message with a
link status to the sender node from ASYM_LINK to link type of ASYM_LINK, SYM_LINK or MPR_LINK, it does not
SYM_LINK. register itself in the N_2hop_list. Rather, it changes
the link status to the sender of the HELLO from ASYM_LINK
to SYM_LINK.
2.4 N_time is set to the value of NEIGHB_HOLD_TIME 2.4 N_time is set to the value of NEIGHB_HOLD_TIME
With information obtained from the HELLO messages, each node also
construct its MPR Selector table, in which it puts the addresses of Based on the information obtained from the HELLO messages, each
its one hop neighbor nodes which has selected it as a multipoint node construct its MPR Selector table. In this table, the node
relay. The MPR Selector table may have the following format to registers the addresses of those one hop neighbor nodes which have
record the entries: selected the node as a multipoint relay. The MPR Selector table may
have the following format:
MSSN MSSN
1. MS_addr MS_seq_num MS_time 1. MS_addr MS_seq_num MS_time
2. MS_addr MS_seq_num MS_time 2. MS_addr MS_seq_num MS_time
3. ,, ,, ,, 3. ,, ,, ,,
Each entry in the table consists of MS_addr, MS_seq_num and Each entry in the table consists of MS_addr, MS_seq_num and
MS_time, which specifies that the node with address MS_addr has MS_time, which specifies that the node with address MS_addr has
selected this node as its multipoint relay with the MPR sequence selected this node as its multipoint relay with the MPR sequence
number equal to MS_seq_num. Each entry has an associated holding number equal to MS_seq_num. Each entry has an associated holding
time MS_time, upon expiry of which it is no longer valid and hence time MS_time, upon expiation of which it is no longer valid and
removed. hence removed.
A sequence number MSSN is associated to this table which specifies A sequence number, MSSN, is associated with this table. This number
that the multipoint relay selector set of the node keeping specifies that the multipoint relay selector set of the node
this MPR Selector table is most recently modified with the sequence keeping this MPR Selector table is most recently modified with the
number MSSN. The node modifies its MPR Selector set according to sequence number MSSN. The node modifies its MPR Selector set
the information it receives in the HELLO messages, and increment according to the information it receives in the HELLO messages, and
this sequence number on each modification. increment this sequence number upon each modification.
On the reception of a HELLO message, if a node finds its own Upon receiving a HELLO message, if a node finds its own address in
address in the [Neighbor, Status] pair with the Status field equal the the address list with a link type of "MPR", it MUST update the
to "MPR", then it updates the entry corresponding to the sender entry corresponding to the sender node's address in the MPR
node's address in the MPR Selector table: Selector table:
1. If the entry exists already: 1. If the entry already exists:
1.1 if the MPR Sequence Number field of the HELLO message is 1.1 if the MPR Sequence Number field of the HELLO message is
greater than or equal to the MS_seq_num field of that greater than or equal to the MS_seq_num field of the
entry, then the MS_time is refreshed to NEIGHB_HOLD_TIME. entry in the table, then the MS_time is refreshed to
NEIGHB_HOLD_TIME.
1.2 if the MPR Sequence Number field of the HELLO message is 1.2 if the MPR Sequence Number field of the HELLO message is
greater than the MS_seq_num field of that entry, the greater than the MS_seq_num field of that entry, the
MS_seq_num field is updated to the value of MPR Sequence MS_seq_num field is updated to the value of MPR Sequence
Number field of the HELLO message. Number field of the HELLO message.
2. Otherwise, a new entry is recorded in the MPR Selector table, 2. Otherwise, a new entry is recorded in the MPR Selector table,
with: with:
2.1 MS_addr is set to the address of sender of the HELLO 2.1 MS_addr is set to the address of sender of the HELLO
message message
skipping to change at page 13, line 49 skipping to change at page 18, line 34
1.2 if the MPR Sequence Number field of the HELLO message is 1.2 if the MPR Sequence Number field of the HELLO message is
greater than the MS_seq_num field of that entry, the greater than the MS_seq_num field of that entry, the
MS_seq_num field is updated to the value of MPR Sequence MS_seq_num field is updated to the value of MPR Sequence
Number field of the HELLO message. Number field of the HELLO message.
2. Otherwise, a new entry is recorded in the MPR Selector table, 2. Otherwise, a new entry is recorded in the MPR Selector table,
with: with:
2.1 MS_addr is set to the address of sender of the HELLO 2.1 MS_addr is set to the address of sender of the HELLO
message message
2.2 MS_seq_num is set to the MPR Sequence Number field of the 2.2 MS_seq_num is set to the MPR Sequence Number field of the
HELLO message HELLO message
2.3 MS_time is set to the value of NEIGHB_HOLD_TIME 2.3 MS_time is set to the value of NEIGHB_HOLD_TIME
6.2. Multipoint relay selection 7.2.3. Link Notification
Each node of the network selects independently its own set of If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through
absence of an acknowledgment), this SHOULD be used in addition to
the information from the HELLO-messages to maintain the neighbor
table and the MPR selector table.
7.3. Multipoint relay selection
Each node in the network selects independently its own set of
multipoint relays. Multipoint relays are used to flood the control multipoint relays. Multipoint relays are used to flood the control
messages of that node. The MPR set is calculated in a manner to messages of that node into the network. The MPR set is calculated
contain a subset of one hop neighbors which covers all the two hop in a way such that it contains a subset of one hop neighbors which
neighbors. By this we mean that the union of the neighbor sets of covers all the two hop neighbors. This means, that the union of the
all MPRs contains the entire two hop neighbor set. In order to neighbor sets of all MPRs contains the entire two hop neighbor
build the list of the two hop nodes from a given node, it suffices set. In order to build the list of the two hop nodes from a given
to track the list of symmetric link nodes found in the HELLO node, it suffices to track the list of symmetric link nodes found
packets received by this node (this two-hop neighbor information is in the HELLO messages received by this node (this two-hop neighbor
recorded in the neighbor table as N_2hop_list). Multipoint relays information is recorded in the neighbor table as
of a given node are declared in the subsequent HELLOs transmitted N_2hop_list). Multipoint relays of a given node are declared in the
by this node, so that the information reaches the multipoint relays subsequent HELLOs transmitted by this node, so that the information
themselves. These selected multipoint relays are indicated in the reaches the multipoint relays themselves. These selected multipoint
HELLO messages with the link status as "MPR". The multipoint relay relays are indicated in the HELLO messages with a link status of
set is re-calculated when: "MPR". The multipoint relay set is re-calculated when:
- a change in the neighborhood is detected when either a - a change in the neighborhood is detected, i.e. either a
symmetric link with a neighbor is failed, or a new neighbor symmetric link with a neighbor is failed, or a new neighbor
with a symmetric link is added; or with a symmetric link is added; or
- a change in the two-hop neighbor set with symmetric link is - a change is detected in the two-hop neighborhood such that
detected. a symmetric link is either detected or broken between a
two-hop neighbor and a neighbor.
The MPR set need not be optimal, however it should be small enough The MPR set needs not be optimal. However it SHOULD be small enough
to achieve the benefit of the multipoint relays. Multipoint relays to achieve the benefit of the multipoint relays. The concept of
is an optimization of the pure flooding mechanism; it is not multipoint relays is an optimization of a pure flooding mechanism.
essential that the multipoint relay set be minimal or optimal. But It is not essential that the multipoint relay set be minimal or
it is essential that it covers the two hop nodes. By default, the optimal. But it is essential that all two-hop neighbors can be
multipoint relay set can coincide with the whole neighbor set. This reached through the selected MPR's. By default, the multipoint
will be the case at network initialization. Each node will manage a relay set can coincide with the entire neighbor set. This will be
the case at network initialization. Each node will manage a
dedicated sequence number in order to track the changes in its dedicated sequence number in order to track the changes in its
multipoint relay set. This sequence number will also appear, along multipoint relay set. This sequence number will also appear, along
with the MPR list, in the HELLO messages. with the MPR list, in the HELLO messages.
We propose here a heuristic for the selection of multipoint relays We propose a heuristic for the selection of multipoint relays
[2]. We use the following terminology in describing this algorithm: [2]. We use the following terminology in describing this algorithm:
MPR(x): Multipoint relay set of node x which is running this MPR(x): Multipoint relay set of node x which is running this
algorithm algorithm
N(x): One hop neighbor set of node x (containing only symmetric N(x): One hop neighbor set of node x (containing only symmetric
neighbors) neighbors)
N2(x): Two hop neighbor set of node x (containing only symmetric N2(x): Two hop neighbor set of node x (containing only symmetric
neighbors of nodes in N(x) ). The two hop neighbor set neighbors of nodes in N(x) ). The two hop neighbor set
N2(x) of node x does not contain any one hop neighbor of N2(x) of node x does not contain any one hop neighbor of
node x node x
skipping to change at page 15, line 31 skipping to change at page 20, line 36
4.1 For each node in N(x), calculate the number of nodes in 4.1 For each node in N(x), calculate the number of nodes in
N2(x) which are not yet covered by MPR(x) and are N2(x) which are not yet covered by MPR(x) and are
reachable through this one hop neighbor; reachable through this one hop neighbor;
4.2 Select as a MPR that node of N(x) which reaches the 4.2 Select as a MPR that node of N(x) which reaches the
maximum number of uncovered nodes in N2(x). In case of a maximum number of uncovered nodes in N2(x). In case of a
tie, select that node as MPR whose D(x,y) is greater. tie, select that node as MPR whose D(x,y) is greater.
5. To optimize, remove each node in MPR(x), one at a time, and 5. To optimize, remove each node in MPR(x), one at a time, and
check if MPR(x) still covers all nodes in N2(x) check if MPR(x) still covers all nodes in N2(x)
After selecting the multipoint relays from among the neighbors, the After selecting the multipoint relays among the neighbors, the link
link status of the corresponding one hop neighbors is changed from status of the corresponding one hop neighbors is changed from
SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in
the Neighbor table is also incremented by one. the Neighbor table is also incremented by one.
6.3. Multipoint relay information declaration 7.4. Multipoint relay information declaration
6.3.1. TC Packet Broadcast 7.4.1. TC Message Broadcast
In order to build the topology information database needed for In order to build the topology information database needed for
routing packets, each relay node broadcasts specific service routing the packets, each relay node broadcasts specific service
packets called Topology Control (TC) packets. TC packets are messages called Topology Control (TC) messages. TC messages are
forwarded like usual broadcast packets to all nodes in the network forwarded, like usual broadcast messages, to all nodes in the
and take advantage of multipoint relays. Multipoint relays enable a network and take advantage of multipoint relays. Multipoint relays
better scalability of topology information [1]. enable a better scalability in the distribution of topology
information [1].
A TC message is sent by a node in the network at regular intervals A TC message is sent by a node in the network to declare its MPR
to declare its MPR Selector set, i.e., the message contains the Selector set. I.e., the TC message contains the list of neighbors
list of neighbors who have selected the sender node as a multipoint which have selected the sender node as a multipoint relay. The
relay. The sequence number (MSSN) associated to this multipoint sequence number (MSSN) associated with this multipoint relay
relay selector set is also sent with the list. The list of selector set is also sent with the list. The list of addresses can
addresses can be partial in each TC packet due to maximum size be partial in each TC message (e.g. due to message size
limitation, but parsing must be complete within a certain limitations, imposed by the network), but parsing of all TC
refreshing period (TC_INTERVAL). The information diffused in the messages describing a nodes MPR selector set MUST be complete
network by these TC packets will help each node to calculate its within a certain refreshing period (TC_INTERVAL). The information
routing table. A node which has an empty MPR Selector set, i.e., diffused in the network by these TC messages will help each node to
nobody has selected it as a multipoint relay, does NOT generate the calculate its routing table. A node which has an empty MPR Selector
TC packet. set, i.e. nobody has selected it as a multipoint relay, MUST NOT
generate any TC message.
The interval between the transmission of two TC packets depends A node MAY transmit additional TC-messages to increase its
upon whether the MPR Selector set is changed or not, since the last reactiveness to link failures. I.e. when a change to the MPR
TC packet transmitted. If no change occur in the MPR Selector set, selector set is detected and this change can be attributed to a
the TC packet is sent after its normal interval (TC_INTERVAL). When link failure, a TC-message MAY be transmitted after a shorter
a change occur in the MPR Selector set, the next TC packet is sent interval than TC_INTERVAL.
after a pre-specified minimum interval (TC_MIN_INTERVAL),
starting from the time the last TC packet was sent. If this much
time has already elapsed, the next TC packet is transmitted
immediately. After sending a TC packet with that minimum interval,
the default value for the interval again becomes the normal
interval (TC_INTERVAL) for sending TC packets, until the MPR
Selector set is changed again.
The proposed format of a TC packet 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address | | Message Sequence Number | MSSN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Type | Hop Count | MSSN | | Hop Count | Unused |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
6.3.1.1. Description of the fields This is sent as the data-portion of the general message format
described in 6.1, with the "Message Type" set to TC_MESSAGE and
Destination address the broadcast field set to BROADCAST.
For all the TC packets, this 4-bytes address field is always
set to the broadcast address of the network, so that when this
packet is diffused in the network, every node get this
information and hence update its topology table.
Source address
It is set to the address of the node *transmitting*
this TC packet. This field should not be confused with the
Originator Address of the TC packet. Whenever a node
"re-transmit" the TC packet, this field is updated to that
transmitter node's address.
Packet Length
This field contains the length of the TC packet in bytes, 7.4.1.1. Description of the fields
starting from the Packet Type field, i.e., the length of rest of
the packet.
Packet Sequence Number Message Sequence Number
While generating the TC packet, the "originator" node will While generating the TC message, the "originator" node will
assign a unique identification number to this packet, and will assign a unique identification number to this message, and will
put this number in the Sequence Number field. This sequence put this number in the Sequence Number field. This sequence
number will be different for all the packets originated by that number will be different for all messages originated by that
node, which will help to recognize the duplicate reception of node, and will be used to recognize duplicate reception of
the packets. messages.
Packet Type
The Packet Type field is set to the TC_PACKET value.
Hop Count
This field will contain the maximum number of hops a TC packet
can attain. Every time a TC packet is re-transmitted, this field
is decremented by 1. When this field reaches zero, the TC packet
is no more re-transmitted and is discarded.
MPR Selector Sequence Number (MSSN) MPR Selector Sequence Number (MSSN)
A sequence number is associated with the multipoint relay A sequence number is associated with the multipoint relay
selector set and every time a node detects a change in its selector set. Every time a node detects a change in its
multipoint relay selector set, it increments this sequence multipoint relay selector set, it increments this sequence
number. This number is sent in this MSSN field of the TC packet number. This number is sent in this MSSN field of the TC message
to keep track of the most recent information. When a node to keep track of the most recent information. When a node
receives a TC packet, it can decide on the basis of this MPR receives a TC message, it can decide on the basis of this MPR
Sequence Number, whether the information about the multipoint Sequence Number, whether or not the received information about
relay selectors of the originator node is more recent than that the multipoint relay selectors of the originator node is more
it already has, or not. recent than what it already has.
Hop Count
This field will contain the maximum number of hops a TC message
can attain. Every time a TC message is re-transmitted, this
field is decremented by 1. When this field reaches zero, the TC
message is no more re-transmitted and is discarded.
Originator Address Originator Address
This field contains the address of the node which has originally This field contains the address of the node, which has
generated this TC packet to declare its multipoint relay selector's originally generated this TC message. This field MUST not be
information. This field should not be confused with the Source confused with the Source Address field, which is changed each
Address field, which is changed each time to the address of the time to the address of the intermediate node which is
intermediate node which is "re-transmitting" this TC packet, "re-transmitting" this TC message. The Originator Address field
while the Originator Address field in never changed in the is *never* changed in the retransmissions.
retransmissions.
Multipoint Relay Selector Address (MPR-S) Multipoint Relay Selector Address (MPR-S)
This field contains the address of the node which has selected This field contains the address of a node, which has selected
the Originator node (of the TC packet) as a multipoint relay. the Originator node (of the TC message) as a multipoint relay.
All the node addresses of the multipoint relay selectors of the All addresses of the multipoint relay selectors of the
Originator node are put in the TC packet, one after another. If Originator node are put in the TC message. If the maximum
the maximum allowed packet size (of IP protocol) is attained and allowed message size (as imposed by the network) is reached
there are still some multipoint relay selector addresses which while there are still multipoint relay selector addresses which
remain in the MPR Selector set, then more TC packets will be which have not been inserted into the TC-message, more TC
generated, until all addresses in the multipoint relay selector messages will be generated until the entire MPR selector set has
set are transmitted. been sent.
6.3.2. TC Packet Processing 7.4.2. TC Message Processing
In OLSR protocol, TC packets are sent in broadcast and are In the OLSR protocol, TC messages are broadcasted and are
retransmitted by the selected nodes to diffuse the packet in the retransmitted by the multipoint relays in order to diffuse the
whole network. In this process, a node may receive more than once messages in the entire network. In this process, a node MAY receive
the same TC packet. To avoid the re-processing of the TC packet the same TC message more than once. To avoid re-processing of a TC
which was already received and processed, each node maintains a message which was already received and processed, each node
Duplicate table in which it records the information about the most maintains a Duplicate table. In this table, the node records
recently received TC packets. The information is recorded in the information about the most recently received TC messages. The
Duplicate table as a Duplicate entry. The table may have information is recorded in the Duplicate table as Duplicate
the following format to record these entries: entries.
The table may have the following format:
1. D_addr D_seq_num D_time 1. D_addr D_seq_num D_time
2. D_addr D_seq_num D_time 2. D_addr D_seq_num D_time
3. ,, ,, ,, 3. ,, ,, ,,
Each entry in the table consists of D_addr, D_seq_num and D_time, Each entry in the table consists of D_addr, D_seq_num and D_time,
which specifies that a TC packet was received from the node with which specifies that a TC message was received from the node with
address D_addr, having the packet sequence number as D-seq_num. address D_addr, having the message sequence number as D-seq_num.
Each Duplicate entry has an associated holding time D_time, upon Each Duplicate entry also has an associated holding time D_time,
expiry of which it is no longer valid and hence removed. upon expiration of which it is no longer valid and hence MUST be
removed.
On reception of a TC packet, a node checks in its Duplicate table Upon receiving a TC message, a node checks in its Duplicate table
if it has already received the same packet or not. If it finds a to see if it has already received the same message. If it finds a
corresponding entry, the packet is discarded. Otherwise, a new corresponding entry, the message is discarded. Otherwise, a new
entry is recorded in the Duplicate table for this newly received TC entry is recorded in the Duplicate table for this newly received TC
packet, and the packet is then processed further. When a node message, and the message is processed. When a node receives a TC
receives a TC packet from its neighbor node with an asymmetric (or message from a neighbor node with which it has an asymmetric (or
uni-directional) link, it does not register the packet in the uni-directional) link, it neither registers the message in the
Duplicate table neither it processes the packet. Duplicate table nor it processes the message.
Each node of the network maintains a topology table, in which it Each node in the network maintains a topology table, in which it
records the information about the topology of the network obtained records the information about the topology of the network as
from the TC packets. Based on this information, the routing table obtained from the TC messages. Based on this information, the
is calculated. A node records information about the multipoint routing table is calculated. A node records information about the
relays of other nodes in the network in its topology table as a multipoint relays of other nodes in the network in its topology
topology entry, which may have the following format: table as a topology entry, which may have the following format:
1. T_dest T_last T_seq T_time 1. T_dest T_last T_seq T_time
2. T_dest T_last T_seq T_time 2. T_dest T_last T_seq T_time
3. ,, ,, ,, ,, 3. ,, ,, ,, ,,
Each entry in the table consists of T_dest, T_last, T_seq, and Each entry in the table consists of T_dest, T_last, T_seq, and
T_time which specifies that the node T_dest has selected the node T_time, which specifies that the node T_dest has selected the node
T_last as a multipoint relay and that the node T_last has announced T_last as a multipoint relay and that the node T_last has announced
this information of its multipoint relay selector set with the this information of its multipoint relay selector set with the
sequence number T_seq. Therefore, the node T_dest can be reached in sequence number T_seq. Therefore, the node T_dest can be reached in
the last hop through the node T_last. Each topology entry has an the last hop through the node T_last. Each topology entry has an
associated holding time T_time, upon expiry of which it is no associated holding time T_time, upon expiration of which it is no
longer valid and hence removed. longer valid and hence MUST be removed.
The entries in the topology table are recorded with the topology The entries in the topology table are recorded with the topology
information that is exchanged among the network nodes through TC information that is exchanged through TC messages.
packets. Upon receipt of a TC packet, the following procedure is
executed to record the information in the topology table: Upon receiving
a TC message, the following procedure is executed to record the
information in the topology table:
1. If there exist some entry in the topology table whose T_last 1. If there exist some entry in the topology table whose T_last
corresponds to the originator address of the TC packet and corresponds to the originator address of the TC message and
whose T_seq is greater in value than the MSSN in the received whose T_seq is greater in value than the MSSN in the received
packet, then no further processing of this TC packet is done message, then no further processing of this TC message is
and it is silently discarded (case: packet received out of performed and it is silently discarded (case: message
order). received out of order).
2. If there exist some entry in the topology table whose T_last 2. If there exist some entry in the topology table whose T_last
corresponds to the originator address of the TC packet and corresponds to the originator address of the TC message and
whose T_seq is lesser in value than the MSSN in the received whose T_seq is lesser in value than the MSSN in the received
packet, then that topology entry is removed. message, then that topology entry is removed.
3. For each of the MPR Selector address received in the TC 3. For each of the MPR Selector address received in the TC
packet: message:
3.1 If there exist some entry in the topology table whose 3.1 If there exist some entry in the topology table whose
T_dest corresponds to the MPR Selector address and the T_dest corresponds to the MPR Selector address and the
T_last corresponds to the originator address of the TC T_last corresponds to the originator address of the TC
packet, then the holding time T_time of that topology message, then the holding time T_time of that topology
entry is refreshed to TOP_HOLD_TIME. entry is refreshed to TOP_HOLD_TIME.
3.2 Otherwise, a new topology entry is recorded in the 3.2 Otherwise, a new topology entry is recorded in the
topology table whereas: topology table whereas:
- T_dest is set to the MPR Selector address, - T_dest is set to the MPR Selector address,
- T_last is set to the originator address of the TC - T_last is set to the originator address of the TC
packet, message,
- T_seq is set to the value of MSSN received in the TC - T_seq is set to the value of MSSN received in the TC
packet, message,
- T_time is set to the value of TOP_HOLD_TIME. - T_time is set to the value of TOP_HOLD_TIME.
6.4. Routing table calculation 7.5. Routing table calculation
Each node maintains a routing table which allows it to route the Each node maintains a routing table which allows it to route the
packets for the other destinations in the network. The nodes which messages for the other destinations in the network. The nodes which
receive the TC packet parse and store some of the connected pairs receive TC messages parse and store some of the connected pairs of
of form [node, source] where "nodes" are identified with the form [node, source] where "nodes" are identified with the addresses
addresses found in the TC packet list. The routing table is built found in the TC message. The routing table is built from this
from this database by tracking the connected pairs in a descending database by tracking the connected pairs in a descending order. To
order. To find a path from a given origin to a remote node R, one find a path from a given origin to a remote node R, one has to find
has to find a connected pair (R,X), then a connected pair (X,Y), a connected pair (R,X), then a connected pair (X,Y), and so forth
and so forth until one finds a node Y in the neighbor set of the until one finds a node Y in the neighbor set of the origin. In
origin. In order to restrict to optimal paths, the relay nodes will order to restrict to optimal paths, the relay nodes will consider
consider only the connected pairs on the minimal path. This only the connected pairs on the minimal path. This selection can be
selection can be done dynamically and with minimal storage done dynamically and with minimal storage facilities. The sequence
facilities. The sequence numbers are used to detect connected pairs numbers are used to detect connected pairs which have been
which have been invalidated by further topology changes. The invalidated by further topology changes. The information contained
information contained in the topology database, which has not been in the topology database, which has not been refreshed is
refreshed is discarded. discarded.
The routing table is based on the information contained in the The routing table is based on the information contained in the
neighbor table and the topology table. Therefore, if any of these neighbor table and the topology table. Therefore, if any of these
tables is changed, the routing table is re-calculated to update the tables is changed, the routing table is re-calculated to update the
route information about each destination in the network. The route route information about each destination in the network. The route
entries are recorded in the routing table in the following format: entries are recorded in the routing table in the following format:
1. R_dest R_next R_dist 1. R_dest R_next R_dist
2. R_dest R_next R_dist 2. R_dest R_next R_dist
3. ,, ,, ,, 3. ,, ,, ,,
skipping to change at page 21, line 25 skipping to change at page 26, line 4
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 and R_dist,
which specifies that the node identified by R_dest is estimated to which specifies that the node identified by R_dest is estimated to
be R_dist hops away from the local node, and that the one hop be R_dist hops away from the local node, and that the one hop
neighbor node with address R_next is the next hop node in the route neighbor node with address R_next is the next hop node in the route
to R_dest. Entries are recorded in the table for each destination to R_dest. Entries are recorded in the table for each destination
in the network for which the route is known. All the destinations in the network for which the route is known. All the destinations
for which the route is broken or partially known are not entered in for which the route is broken or partially known are not entered in
the table. the table.
This routing table information is updated when This routing table information is updated when
- a change in the neighborhood is detected concerning a - a change in the neighborhood is detected concerning a
symmetric link; symmetric link;
- a route to any destination is expired (because the - a route to any destination is expired (because the
corresponding topology entry is expired) or corresponding topology entry is expired) or
- a better (e.g. shorter) route is found for a destination. - a better (e.g. shorter) route is found for a destination.
Therefore, the routing table is re-calculated locally each time the Therefore, the routing table is re-calculated locally each time the
neighbor table or the topology table or both are changed. The neighbor table or the topology table (or both) are changed. The
update of this routing table does not generate or trigger any update of this routing table does not generate or trigger any
packets to be transmitted, neither in the network, nor in the messages to be transmitted, neither in the network, nor in the
one-hop neighborhood. one-hop neighborhood.
The following procedure is executed to calculate (or re-calculate) The following procedure is executed to calculate (or re-calculate)
the routing table : the routing table :
1. All the entries of the routing table are removed. 1. All the entries of the routing table are removed.
2. The new entries are recorded in the table starting with the one 2. The new entries are recorded in the table starting with the one
hop neighbors (h=1) as the destination nodes. For each neighbor hop neighbors (h=1) as the destination nodes. For each neighbor
entry in the neighbor table, whose link status is not entry in the neighbor table, whose link status is not
skipping to change at page 22, line 23 skipping to change at page 26, line 46
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 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_next is set to R_next of the route entry whose
R_dest is equal to T_last; and R_dest is equal to T_last; and
- R_dist is set to h+1. - R_dist is set to h+1.
4. After calculating the routing table, the topology table entries 4. After calculating the routing table, the topology table entries
which are not used in calculating the routes may be removed, if which are not used in calculating the routes MUST be removed, if
there is a need to save memory space. Otherwise, these entries there is a need to save memory space. Otherwise, these entries
may provide multiple routes. may provide multiple routes.
7. Packet forwarding 8. Packet forwarding
7.1. Data packet forwarding 8.1. Data packet forwarding
Data packets are relayed on a hop by hop basis. In the source Data packets are relayed on a hop by hop basis. In the source
router and in any intermediate router, the next hop router is router and in any intermediate router, the next hop router is
identified by the entry of the destination in the host routing identified by the entry of the destination in the host routing
table. table.
Whenever a data packet is received to route to a destination and Whenever a data packet is received to route to a destination and
its TTL field (in IP header) is greater than zero, the node must its TTL field (in IP header) is greater than zero, the node MUST
look at the final destination field in the packet. If the route is examine the final destination field in the packet. If the route is
known, i.e. an entry is found in the routing table in which R_dest known, i.e. an entry is found in the routing table in which R_dest
corresponds to the final destination, then the packet is corresponds to the final destination, then the packet is
transmitted to the next hop node. While forwarding a unicast transmitted to the next hop node. While forwarding a unicast
packet, the originator address, and the final destination address packet, the originator address, and the final destination address
of the packets are not changed. The packet traverses the of the packets are not changed. The packet traverses the
intermediate source and destination pair, hop by hop, until it intermediate source and destination pairs, hop by hop, until it
reaches its final destination. reaches its final destination.
7.2. Topology Control (TC) packet forwarding 8.2. Topology Control (TC) packet forwarding
TC packets are relayed by the multipoint relays via the TC packets are relayed by the multipoint relays via the following
following rule: rule:
A node retransmits a TC packet only when it receives its first A node retransmits a TC packet only when it receives its first
copy from a node which is its multipoint relay selector. copy from a node which is its multipoint relay selector.
When a TC packet is received and its hop count is greater than When a TC packet is received with a hop count is greater than zero,
zero, then it is retransmitted by the multipoint relays of the then it is retransmitted by the multipoint relays of the sender
sender node. Before retransmitting, the hop count is decremented by node. Before retransmitting, the hop count is decremented by one.
one.
8. Power Conservation or Sleep mode operation
Power conservation mode is very desirable for the low capacity,
battery operated small terminals. With the constraint on the power
consumption, nodes may wish to conserve their battery power by
going into "sleep mode". The sleep mode may simply be a pause in
the operation of a node, or it may be some intermittent sleep and
wake periods of a node to economically use its battery resources.
8.1. Sleep mode initiation
When a node plans to go in sleep mode, it has to stop sending its
periodic control messages:
- HELLO messages: so that it is no more selected as a multipoint
relay by its neighbor nodes, and
- TC messages: so that it is no more used as an intermediate
node while calculating a route.
Then it looks its MPR Selector set. If this set is not empty, it
means that some of its neighbors are using it as a multipoint
relay, and secondly, other nodes of the network may calculate the
route to some destinations using this node as an intermediate
node. In this case, the node can not go into sleep mode immediately
because it is assumed to function as a multipoint relay of some
node. The node must wait until its MPR Selector set becomes
empty. As the node is sending no more HELLOs, so it will not be
selected as a multipoint relay further more, and hence the entries
in the MPR Selector set will be expired.
After terminating the transmission of its periodic messages, the
node has to negotiate with its multipoint relays to keep its data
packets while it is in sleep mode. The node has to keep only those
MPRs in its MPR set which agree to keep its packets.
To initiate the negotiation for the power conservation mode, the
node has to transmit a power conservation (PC) message. This PC
message is broadcast to one hop neighbors only with packet type
equal to PC_PACKET. It contains the list of the MPRs of the sender
node, along with the intended duration of the sleep period (in
milliseconds). The Request/Reply field is set to 1 by the sender
node who is requesting to keep its packets while it is in sleep
mode.
The proposed format of a PC packet 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Type | Request/Reply | Sleep period (in msec) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| MPR Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| MPR Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
When a node receives a PC message with Request/Reply field equal to
1, then:
1. if its MPR set contains the sender node's address, this
address must be removed from the MPR set and the receiver
must re-calculate its MPR set;
2. if the receiver is listed as an MPR address in the PC
message, it will decide if it can keep the packets for the
sender node during the sleep period mentioned in the PC
message:
2.1 if it does not agree to keep sender node's packets,
then no further processing of PC message is done;
2.2 otherwise, if it agrees to keep the packets of the
sender node for the intended sleep mode duration,
then:
2.2.1 it will add the intended sleep period time to
the holding time of the entry in the MPR
Selector table corresponding to the sender
node's address
2.2.2 it will reply to the sender node with a PC
message in unicast, with the Request/Reply
field set to 2. The sleep period field will
be equal to that in the received PC message
and there will be no list of MPR Addresses.
When the node who intends to go in sleep mode receives a reply of
its PC message from one or more of its MPRs, it should keep only
these addresses (of the MPRs) in its neighbor table and remove all
others. It can now go in sleep mode.
If the node does not receive a reply after one HELLO_INTERVAL, it
can re-send its PC message and wait for the reply. If still no
reply is received, the node can not go in sleep mode, OR, it can go
in sleep mode with a risk to loose its own packets. A "sleeping"
node does not affect the routing of packets which are not destined
to it. In OLSR, packets are routed hop-by-hop. So the neighbor
nodes of the sleeping node will not send the packets to it, and
will route the packet towards its destination according to their
own most recent information.
8.2. Wake up procedure
8.2.1. Wake up to resume activities after sleep mode
The sleeping node must wake up before the sleep period (mentioned
in its PC message) expires. It should start its normal operation,
i.e. sending periodic HELLO and TC messages. At the same time, it
should look in its neighbor table the addresses of its MPR nodes
who agreed to keep its packets. Then it should request those
neighbors to send these kept packets, by sending a PC message to
all of them, one after another. This PC message will have the
Request/Reply field equal to zero and the sleep period equal to
zero. A node who receives a PC message containing Request/Reply
field equal to zero the sleep period equal to zero, should send all
the packets, which it has kept for the sender node.
This method of requesting its kept packets to its MPRs one by one,
when a node wakes up, may avoid the high packet flow towards a node
who wakes up.
If a node A is keeping packets for any node B, and the intended
sleep period arrives at its expiration, node A should see if the
route to node B is known, i.e. if node B is alive or not. If the
route is known, all the packets are send to the node B, otherwise,
node A will discard all packets of node B.
8.2.2. Wake up in the intermittent wake-and-sleep periods
The sleeping node must wake up before the sleep period (mentioned
in its PC message) expires. As the node intends to re-go into sleep
mode after a small wake up period, it does not resume sending HELLO
and TC packets. To collect its packets from its MPR neighbors, it
will send a PC message with the Destination address set to the
broadcast address, the Request/Reply field set to zero and the
Sleep period field set to zero. There will be no list of MPR
addresses attached to the PC packet. A node who receives this PC
message will send all the packets it has kept for the sender node
of the PC message.
To go again into sleep mode after processing (and replying to, if
necessary) the packets it receives, the node has to re-negotiate
with its MPRs as mentioned in section 8.1. (Future versions of the
draft may explain if sending an intermittent wake-and-sleep pattern
in the first negotiation could avoid the repetitive negotiations).
To end the intermittent wake-and-sleep operation, the node should
follow the procedure of section 8.2.1 when it wakes up.
9. Proposed values for the constants 9. Proposed values for the constants
This section list the values for the constants used in the This section list the values for the constants used in the
description of the protocol. description of the protocol.
HELLO_INTERVAL = 2 seconds HELLO_INTERVAL = 2 seconds
TC_INTERVAL = 5 seconds TC_INTERVAL = 5 seconds
TC_MIN_INTERVAL = 2 seconds TC_MIN_INTERVAL = 2 seconds
skipping to change at page 26, line 44 skipping to change at page 28, line 4
This section list the values for the constants used in the This section list the values for the constants used in the
description of the protocol. description of the protocol.
HELLO_INTERVAL = 2 seconds HELLO_INTERVAL = 2 seconds
TC_INTERVAL = 5 seconds TC_INTERVAL = 5 seconds
TC_MIN_INTERVAL = 2 seconds TC_MIN_INTERVAL = 2 seconds
NEIGHB_HOLD_TIME = 6 seconds NEIGHB_HOLD_TIME = 6 seconds
TOP_HOLD_TIME = 15 seconds TOP_HOLD_TIME = 15 seconds
HELLO_PACKET = 1 HELLO_PACKET = 1
TC_PACKET = 2 TC_PACKET = 2
PC_PACKET = 3
ASYM_LINK = 1 ASYM_LINK = 1
SYM_LINK = 2 SYM_LINK = 2
MPR_LINK = 3 MPR_LINK = 3
10. References 10. References
1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing
reliability in cable free radio LANs: Low level forwarding in reliability in cable free radio LANs: Low level forwarding in
HIPERLAN. Wireless Personal Communications, 1996 HIPERLAN. Wireless Personal Communications, 1996
2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An
efficient technique for flooding in mobile wireless networks. efficient technique for flooding in mobile wireless networks.
INRIA research report, 2000 INRIA research report RR-3898, 2000
3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN
type 1, functional specifications ETS 300-652, ETSI, June 1996 type 1, functional specifications ETS 300-652, ETSI, June 1996
4. Corson et al. Internet MANET Encapsulation Protocol. Internet 4. Corson et al. Internet MANET Encapsulation Protocol. Internet
draft, draft-ietf-manet-imep-spec-01.txt, Work in progress. draft, draft-ietf-manet-imep-spec-01.txt, Work in progress.
5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet 5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet
draft, draft-ietf-manet-term-00.txt, work in progress. draft, draft-ietf-manet-term-00.txt, work in progress.
6. Corson, S., MANET Routing Protocol Applicability Statement, 6. Corson, S., MANET Routing Protocol Applicability Statement,
Internet draft, draft-ietf-manet-appl-00.txt, Work in progress. Internet draft, draft-ietf-manet-appl-00.txt, Work in progress.
11. Authors' Addresses 7. S. Bradner. Key words for use in RFCs to Indicate Requirement
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
Network Protocols, INRIA research report RR-3965, 2000
12. Authors' Addresses
Amir Qayyum Amir Qayyum
Project HIPERCOM Project HIPERCOM
INRIA Rocquencourt INRIA Rocquencourt
BP 105 BP 105
78153 Le Chesnay Cedex, France 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5273 Phone: +33 1 3963 5273
Email: Amir.Qayyum@inria.fr Email: Amir.Qayyum@inria.fr
Philippe Jacquet Philippe Jacquet
Project HIPERCOM Project HIPERCOM
INRIA Rocquencourt INRIA Rocquencourt
BP 105 BP 105
78153 Le Chesnay Cedex, France 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5263 Phone: +33 1 3963 5263
Email: Philippe.Jacquet@inria.fr Email: Philippe.Jacquet@inria.fr
Paul Muhlethaler Anis Laouiti
Project HIPERCOM Project HIPERCOM
INRIA Rocquencourt INRIA Rocquencourt
BP 105 BP 105
78153 Le Chesnay Cedex, France 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278 Phone: +33 1 3963 5278
Email: Paul.Muhlethaler@inria.fr Email: Anis.Laouiti@inria.fr
Laurent Viennot
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
Email: Laurent.Viennot@inria.fr
Thomas Clausen
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278
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/