draft-ietf-manet-olsr-03.txt   draft-ietf-manet-olsr-04.txt 
INTERNET-DRAFT Philippe Jacquet INTERNET-DRAFT Philippe Jacquet
IETF MANET Working Group Paul Muhlethaler IETF MANET Working Group Paul Muhlethaler
Expiration: 24 May 2001 Amir Qayyum Expiration: 02 September 2001 Amir Qayyum
Anis Laouiti Anis Laouiti
Laurent Viennot Laurent Viennot
Thomas Clausen Thomas Clausen
INRIA Rocquencourt, France INRIA Rocquencourt, France
24 November 2000 2 March 2001
Optimized Link State Routing Protocol Optimized Link State Routing Protocol
draft-ietf-manet-olsr-03.txt draft-ietf-manet-olsr-04.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 45 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
selected nodes which forward broadcast packets during the flooding selected nodes which forward broadcast messages during the
process. This technique substantially reduces the packet overhead flooding process. This technique substantially reduces the message
as compared to pure flooding mechanism where every node retransmits overhead as compared to pure flooding mechanism where every node
the packet when it receives the first copy of the packet. In OLSR retransmits each message when it receives the first copy of the
protocol, the information flooded in the network "through" these packet. In OLSR, information flooded in the network "through"
multipoint relays is also "about" the multipoint relays. Thus a these MPRs is also "about" the MPRs. Thus a
second optimization is achieved by minimizing the "contents" of the second optimization is achieved by minimizing the "contents" of
control packets flooded in the network. Hence, as contrary to the the control messages flooded in the network. Hence, as contrary to
classic link state algorithm, only a small subset of links with the the classic link state algorithm, only a small subset of links
neighbor nodes are declared instead of all the links. This with the neighbor nodes are declared instead of all the
information is then used by the OLSR protocol for route links. This information is then used by the OLSR protocol for
calculation. As a consequence hereof, the routes contain only the route calculation. As a consequence hereof, the routes contain
MPRs as intermediate nodes from a Source to a Destination. OLSR only the MPRs as intermediate nodes from a Source to a
provides optimal routes (in terms of number of hops). The protocol Destination. OLSR provides optimal routes (in terms of number of
is particularly suitable for large and dense networks as the hops). The protocol is particularly suitable for large and dense
technique of multipoint relays works well in this context. networks as the technique of MPRs works well in this context.
Contents Contents
Status of This Memo 1 Status of This Memo 1
Abstract 1 Abstract 1
1. Introduction 3 1. Introduction 3
2. Changes 3 2. Changes 3
3. OLSR terminology 4 3. OLSR terminology 4
4. Applicability Section 5 4. Applicability Section 5
4.1 Networking Context 5 4.1 Networking Context 5
4.2 Protocol Characteristics and Mechanisms 5 4.2 Protocol Characteristics and Mechanisms 6
5. Protocol Overview 7 5. Protocol Overview 8
6. Multipoint relays 9 6. Multipoint relays 9
7. Protocol functioning 10 7. Protocol functioning 10
7.1 Packet format 10 7.1 Protocol and port number 10
7.1.1 Packet Header 11 7.2 Packet format 10
7.1.2 Message Header 12 7.2.1 Packet Header 12
7.1.3 Packet Processing 12 7.2.2 Message Header 12
7.2 Neighbor sensing 13 7.2.3 Packet Processing 13
7.2.1 HELLO message broadcast 13 7.3 Neighbor sensing 15
7.2.2 HELLO message processing 16 7.3.1 Neighbor sensing information base 15
7.3 Multipoint relay selection 19 7.3.2 HELLO message broadcast 16
7.4 Multipoint relay information declaration 20 7.3.3 HELLO message processing 19
7.4.1 TC message broadcast 20 7.4 Multipoint relay selection 21
7.4.2 TC message processing 23 7.5 Multipoint relay information declaration 22
7.5 Routing table calculation 25 7.5.1 Topology information base 22
7.6.Link layer notification 27 7.5.2 TC message broadcast 23
8. Packet Forwarding 27 7.5.3 TC message processing 24
8.1 Data packet forwarding 27 7.6 Routing table calculation 26
8.2 OLSR message forwarding 28 7.7.Link layer notification 27
9. Proposed values for constants 28 8. Packet Forwarding 28
10. References 29 8.1 Data packet forwarding 28
11. Authors' addresses 30 8.2 Control message forwarding 28
9. Proposed values for constants 29
10. Sequence numbers 29
11. References 30
12. Authors' addresses 31
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]. The 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 mobile ad hoc networks. It operates This protocol is developed for mobile ad hoc networks. It operates
as a table driven or proactive protocol and exchanges topology as a table driven and proactive protocol and exchanges topology
information with other nodes of the network at regular intervals. information with other nodes of the network at regular intervals.
The nodes which are selected as a multipoint relay by some neighbor The nodes which are selected as a multipoint relay by some
nodes announce this information periodically in their control neighbor nodes announce this information periodically in their
messages. The protocol uses the multipoint relays to facilitate control messages. The protocol uses the MPRs to facilitate
efficient flooding of control messages in the network. In route efficient flooding of control messages in the network. In route
calculation, the multipoint relays are used to form the route from calculation, the MPRs are used to form the route from a given node
a given node to any destination in the network. to any destination in the network.
Multipoint relays are selected by a node among its one hop MPRs are selected by a node among its one hop neighbors with
neighbors with "symmetric", i.e. bi-directional, link. Therefore, "symmetric", i.e. bi-directional, link. Therefore, selecting the
selecting the route through multipoint relays automatically avoids route through MPRs automatically avoids the problems associated
the problems associated with data packet transfer on with data packet transfer on uni-directional links (such as the
uni-directional links (such as the problem of getting the problem of not getting link-layer acknowledgments for the data
link-layer acknowledgement for the data packets at each hop) packets at each hop)
The OLSR protocol is developed to work independently from other The OLSR protocol is developed to work independently from other
protocols. But it can be adapted to operate with a protocol (like protocols. But it can be adapted to operate with a protocol (like
IMEP [4]) which could provide common functionalities such as IMEP [4]) which could provide common functionalities such as
neighbor sensing, multipoint relaying, security authentication, neighbor sensing, multipoint relaying, security authentication,
etc. etc.
2. Changes 2. Changes
Major changes from version 03 to version 04
- Finalized the generic packet/message format to
include features for scope-limited (diameter-bound)
flooding of messages and to handle duplicate messages.
- Editorial changes towards language consistency.
Major changes from version 02 to version 03 Major changes from version 02 to version 03
- Introduction of assigned port number for use with OLSR - Introduction of assigned port number for use with OLSR.
- The packet format now uses "message length" rather than an - The packet format now uses "message length" rather than an
offset to the next message offset to the next message.
- Optional section describing how link-layer notifications - Optional section describing how link-layer notifications
can be utilized included. can be utilized included.
Major changes from version 01 to version 02 Major changes from version 01 to version 02
- Introduction of a unified packet format for encapsulation of - Introduction of a unified packet format for encapsulation of
all messages being exchanged between nodes. This also serves all messages being exchanged between nodes. This also serves
to facilitate extensions in future versions of the protocol to facilitate extensions in future versions of the protocol
(i.e. introduction of new protocol messages) without breaking (i.e. introduction of new protocol messages) without breaking
backwards compatibility. backwards compatibility.
- Removal of "Power Conservation" from this draft. Power - Removal of "Power Conservation" from this draft. Power
Conservation may be considered as an extension to the basic Conservation may be considered as an extension to the basic
routing capabilities, and the information is therefore moved routing capabilities, and the information is therefore moved
to draft-ietf-manet-olsr-extensions-00.txt. to draft-ietf-manet-olsr-extensions-00.txt.
3. OLSR Terminology 3. OLSR Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECCOMENDED", "MAY", and "OPTIONAL" in "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in RFC2119 [9]. this document are to be interpreted as described in RFC2119 [9].
The OLSR protocol uses the following terminology, in addition to The OLSR protocol uses the following terminology, in addition to
the terms defined in [5]. 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 with an entry in any table. An entry is The lifetime associated with an entry in any table. An entry is
kept in the table for a period of time, equal to its holding kept in the table for a period of time, equal to its holding
time. If the entry is not refreshed during this period, it is time. If the entry is not refreshed during this period, it is
removed from the table when the 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 receives from X, "re-transmit" all the broadcast messages that it receives from
provided that the same packet is not already received, and the X, provided that the same message is not already received, and
hop count field of the packet is greater than zero. the time to live field of the message is greater than zero.
multipoint relay selector (MPR-S) multipoint relay selector (MPR selector, MS)
A node which has selected its one-hop neighbor, node X, as its A node which has selected its one-hop neighbor, node X, as its
multipoint relay, will be called a multipoint relay selector multipoint relay, will be called a multipoint relay selector
of node X. of node X.
node node
A MANET router which implements this Optimized Link State A MANET router which implements this Optimized Link State
Routing protocol. Routing protocol.
symmetric link symmetric link
A bi-directional *link* (not connection) between two neighbor A bi-directional *link* between two neighbor nodes, i.e. node X
nodes, i.e. node X and node Y where both can hear each and node Y where both can hear each other.
other. This bi-directional link can be a union of two
oppositely-directed uni-directional connections using different
interfaces.
4. 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].
4.1. Networking Context 4.1. Networking Context
The protocol is best suited to large and dense networks, as the OLSR is well suited to large and dense mobile networks, as the
optimization achieved using the multipoint relays works well in optimi- zation achieved using the MPRs works well in this
this context. The larger and more dense a network, the more context. The larger and more dense a network, the more
optimization can be achieved as compared to the normal link state optimization can be achieved as compared to the normal link state
algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its
most recent information to route packets. Thus when a node is local information to route packets.
moving, its speed should be such that its movement could be
followed in *at least* its neighborhood, in order to correctly
route packets to the destination.
This protocol is best suited for networks where the traffic is OLSR is well suited for networks, where the traffic is random and
random and sporadic between "several" nodes rather than being sporadic between "several" nodes rather than being almost
almost exclusively between a small specific set of nodes in the exclusively between a small specific set of nodes. The performance
network. The performance of the protocol when comparing to a of the protocol, compared to a reactive protocol, is even better
reactive protocol is even better if these [source, destination] if these [source, destination] pairs change with time [8]. Such
pairs change with time [8]. Such changes may initiate substantial changes may initiate substantial traffic (Query flooding) in case
traffic (Query flooding) in case of reactive protocol, but nothing of reactive protocol, but nothing in OLSR, as the routes are
in OLSR, as the routes are maintained for each known destination maintained for each known destination all the time.
all the time.
4.2. Protocol Characteristics and Mechanisms 4.2. Protocol Characteristics and Mechanisms
* Does the protocol provide shortest path routes ? * Does the protocol provide shortest path routes ?
Yes. Yes.
* Does the protocol provide support for unidirectional links? (if * Does the protocol provide support for unidirectional links? (if
so, how?) so, how?)
No. It uses only bi-directional links (like in 802.11), but No. However, the use of uni-directional links may easily be
these links may be composed of oppositely directed enabled through optional extensions to the protocol.
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.
* 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 sends a message Yes. Periodically, each node in the network sends a message
containing the addresses of the neighbors which have selected containing the addresses of the neighbors which have selected
that node as a multipoint relay. This information enables other that node as a MPR. This information enables other nodes to
nodes to build routes to that node through the multipoint build routes to that node through the MPRs.
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.
reliably. Each packet not only contains a unique Packet Sequence
Number, but it also contains the sequence number for the most
recent information (for example "MPR Sequence Number" in the TC
packet), so un-sequenced delivery of packets will also not
create any problem.
* Does the protocol provide support for routing through a multi- * Does the protocol provide support for routing through a multi-
technology routing fabric? (if so, how?) technology routing fabric? (if so, how?)
Yes. Each network interface is assigned a unique IP address. No. However, provisions for multiple interfaces may easily be
enabled through extensions to the protocol.
* Does the protocol provide support for multiple hosts per router? * Does the protocol provide support for multiple hosts per router?
(if so, how?) (if so, how?)
Yes. The concept of RID [4] may be used to associate to a single Yes. The hosts are added to the MPR selector set of the node
RID (which can also be a unique IP address) more than one IP (router), which will then announce that the hosts can be
addresses which represent different hosts associated to the reached through that node.
router.
* Does the protocol support the IP addressing architecture? (if so, * Does the protocol support the IP addressing architecture? (if so,
how?) how?)
Yes. Yes. Nodes are assigned and addressed by regular IP-addresses.
* 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 link status sensing. This service is
is provided by sending/receiving periodic HELLO messages to/from provided by sending/receiving periodic HELLO messages to/from
one hop neighbors. one hop neighbors.
* Does the protocol depend on a central entity? (if so, how?) * Does the protocol depend on a central entity? (if so, how?)
No. All the routers in the network have their own routing tables No.
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.
limits) of sending the TC packet periodically, depending upon
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. Each node periodically sends information about its MPR
relay selectors, which helps other nodes to build routes to it. selectors, which enables the nodes to construct routes to these
MPR selectors through the node.
* Does the protocol provide loop-free routing? (if so, how?) * Does the protocol provide loop-free routing? (if so, how?)
As the protocol uses a link state algorithm, the routing is Yes. As the protocol uses a link state algorithm, routing is
loop-free when 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, OLSR can provide support for sleep period operation. To No. However, provisions for sleep-operation may easily be
enable this feature, a node should select its multipoint relays enabled through extensions to the protocol.
from among those neighbors which can (or agree to) store its
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.
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. Yes. OLSR makes no assumptions on the underlying link-layer
other, than that local broadcast must be available.
5. Protocol Overview 5. Protocol Overview
OLSR is a proactive routing protocol for mobile ad hoc networks. OLSR is a proactive routing protocol for mobile ad hoc 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 routes immediately available when
needed due to its proactive nature. OLSR is an optimization over needed due to its proactive nature. OLSR is an optimization over
the pure link state protocol, tailored for mobile ad hoc networks. the pure link state protocol, tailored for mobile ad hoc networks.
Firstly, it reduces the size of the control packets: rather than Firstly, it reduces the size of the control messages: rather than
declaring all links, a node declares only a subset of links with declaring all links, a node declares only a subset of links with
its neighbors, namely the links to those nodes which are its its neighbors, namely the links to those nodes which are its MPR
multipoint relay selectors (see section 6 on Multipoint Relays). selectors (see section 6 on MPRs). Secondly, OLSR minimizes
Secondly, OLSR minimizes flooding of control traffic by using only flooding of control traffic by using only selected nodes, called
selected nodes, called multipoint relays, to diffuse its messages. MPRs, to diffuse its messages. This technique significantly
This technique significantly reduces the number of retransmissions reduces the number of retransmissions in a flooding or broadcast
in a flooding or broadcast procedure. procedure.
The protocol MAY optimize the reactivity to topological changes by OLSR MAY optimize the reactivity to topological changes by
reducing the time interval for periodic control message reducing the time interval for periodic control message
transmission. Furthermore, as OLSR protocol keeps the routes for transmission. Furthermore, as OLSR keeps the routes for all
all destinations in the network, the protocol is beneficial for destinations in the network, the protocol is beneficial for
traffic patterns where a large subset of nodes are communicating traffic patterns where a large subset of nodes are communicating
with another large subset of nodes, and where the with another large subset of nodes, and where the
[source,destination] pairs are changing over time. The protocol is [source,destination] pairs are changing over time. The protocol is
particularly suited for large and dense networks, as the particularly suited for large and dense networks, as the
optimization done using the multipoint relays works well in this optimization done using the MPRs works well in this context. The
context. The larger and more dense a network, the more optimization larger and more dense a network, the more optimization can be
can be achieved as compared to the normal link state algorithm. achieved as compared to the normal link state algorithm.
The protocol is designed to work in a completely distributed manner OLSR is designed to work in a completely distributed manner and
and thus does not depend on any central entity. The protocol does does thus not depend on any central entity. The protocol does NOT
NOT REQUIRE reliable transmission for control messages: each node REQUIRE reliable transmission for control messages: each node
sends control messages periodically, and can therefore sustain an sends control messages periodically, and can therefore sustain an
occasional loss of some packets. Such losses occur very often in occasional loss of some such messages. Such losses occur frequent
the radio networks due to collisions or other transmission in radio networks due to collisions or other transmission problems.
problems. Also, the protocol does NOT REQUIRE sequenced delivery of
messages. Each control message contains a sequence number which is Also, OLSR does NOT REQUIRE sequenced delivery of messages. Each
incremented for each message. Thus the recipient of a control control message contains a sequence number which is incremented
packet can easily identify which information is newer - even if for each message. Thus the recipient of a control message can
messages have been re-ordered while in transmission. easily identify which information is newer - even if messages have
been re-ordered while in transmission.
Furthermore, OLSR provides support for protocol extensions such as Furthermore, OLSR provides support for protocol extensions such as
sleep mode operation, multicast-routing etc. Such extensions may be sleep mode operation, multicast-routing etc. Such extensions may be
introduced as additions to the protocol without breaking backwards introduced as additions to the protocol without breaking backwards
compatibility with earlier versions. compatibility with earlier versions.
OLSR performs hop by hop routing, i.e. each node uses its most OLSR performs hop by hop routing, i.e. each node uses its most
recent information to route the packet. Hence for OLSR to be able recent local information to route a packet. Hence for OLSR to be
to route packets, the speed of mobile nodes should be limited such able to route packets, the frequency of control messages should be
that their movements can be tracked, at least by their neighborhood. tuned to the speed of the mobile nodes such that their movements
can be tracked by their neighborhood.
OLSR does NOT REQUIRE any changes to the format of IP packets. Thus 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 any existing IP stack can be used as it is: the protocol only
interacts with routing table management. interacts with routing table management.
6. Multipoint Relays 6. Multipoint Relays
The idea of multipoint relays is to minimize flooding of broadcast The idea of multipoint relays is to minimize the overhead of
messages in the network by reducing duplicate retransmissions in flooding messages in the network by reducing duplicate
the same region. Each node in the network selects a set of nodes in retransmissions in the same region. Each node in the network
its neighborhood which may retransmit its packets. This set of selects a set of nodes in its neighborhood which may retransmit
selected neighbor nodes is called the multipoint relay (MPR) set of its messages. This set of selected neighbor nodes is called the
that node. The neighbors of node N which are *NOT* in its MPR set, "Multipoint Relay" (MPR) set of that node. The neighbors of node N
receive and process broadcast messages but do not retransmit which are *NOT* in its MPR set, receive and process broadcast
broadcast messages received from node N. messages but do not retransmit broadcast messages received from
node N.
Each node selects its MPR set among its one hop neighbors. This set Each node selects its MPR set among its one hop neighbors. This
is selected such that it covers (in terms of radio range) all the set is selected such that it covers (in terms of radio range) all
nodes that are two hops away. The neighborhood of any node N can be nodes that are two hops away. The neighborhood of any node N can
defined as the set of nodes which have a symmetric link to N. The be defined as the set of nodes which have a symmetric link to
two hop neighborhood of N can be defined as the set of nodes which N. The 2-hop neighborhood of N can be defined as the set of nodes
don't have a symmetric link to N but have a symmetric link to the which don't have a symmetric link to N but have a symmetric link
neighborhood of N. The multipoint relay set of N, denoted as MPR(N), to the neighborhood of N. The MPR set of N, denoted as MPR(N), is
is then an arbitrary subset of the neighborhood of N which then an arbitrary subset of the neighborhood of N which satisfies
satisfies the following condition: every node in the two hop the following condition: every node in the 2-hop neighborhood of N
neighborhood of N must have a symmetric link toward MPR(N). The must have a symmetric link toward MPR(N). The smaller the MPR set
smaller the multipoint relay set is, the more optimal is the is, the more optimal is the routing protocol. [2] gives an
routing protocol. [2] gives an analysis and example about analysis and example about MPR selection algorithms.
multipoint relay selection algorithms.
Each node maintains information about a set of its neighbors. This Each node maintains information about a set of its neighbors. This
is the set of neighbors, called the "Multipoint Relay Selectors", is the set of neighbors, called the "Multipoint Relay Selector
which have selected the node as a MPR. A node obtain this set" (MPR selector set), which have selected the node as a MPR. A
information from the periodic HELLO messages received from the node obtains this information from the periodic HELLO messages
neighbors. A broadcast message, intended to be diffused in the received from the neighbors. A broadcast message, intended to be
whole network, coming from these MPR Selector neighbor nodes is diffused in the whole network, coming from these MPR selector
assumed to be retransmitted by the node. This set can change over neighbor nodes is assumed to be retransmitted by the node. This
time (i.e. when a node selects another MPR-set) and is indicated by set can change over time (i.e. when a node selects another
the selector nodes in their HELLO messages. Each node has a MPR-set) and is indicated by the selector nodes in their HELLO
specific Multipoint relay Selector Sequence Number (MSSN) messages. Each node has a specific "Multipoint relay Selector
associated with this set. Whenever its MPR selector set is updated, Sequence Number" (MSSN) associated with this set. Whenever its MPR
the node also increments its MSSN. selector set is updated, the node also increments its MSSN.
OLSR relies on selection of multipoint relays, and calculates the OLSR relies on selection of MPRs, and calculates routes through
routes to a destination through these nodes. I.e. MPR nodes are these nodes. I.e. MPR nodes are selected as intermediate nodes in
selected as intermediate nodes in the path between a source and a the path between a source and a destination. To enable this, each
destination. To implement this, each node in the network node in the network periodically broadcast the information
periodically broadcast the information describing which neighbors describing which neighbors have selected it as a MPR. Upon
have selected it as a multipoint relay. Upon receipt of this "MPR receipt of this "MPR Selector" information, each node calculates
Selectors" information, each node calculates or updates the route or updates the route to each known destination. So principally,
to each known destination. So principally, the route is a sequence the route is a sequence of hops through the MPRs from source to
of hops through the multipoint relays from source to the the destination.
destination.
Multipoint relays are selected among the one hop neighbors with MPRs are selected among the one hop neighbors with "symmetric"
"symmetric" i.e. bi-directional link. Therefore, selecting the i.e. bi-directional link. Therefore, selecting the route through
route through multipoint relays automatically avoids the problems MPRs automatically avoids the problems associated with data packet
associated with data packet transfer on uni-directional links such transfer on uni-directional links such as the problem of not
as the problem of getting an acknowledgement for the data packets getting an acknowledgment for the data packets at each hop.
at each hop.
7. Protocol Functioning 7. Protocol Functioning
In this section we describe the details of the protocol This section describes the details of the protocol functioning.
functioning. This includes descriptions of the format and contents This includes descriptions of the format and contents of the
of the packets being exchanged by routers, the algorithms (e.g. for packets being exchanged by routers, the algorithms (e.g. for
packet handling and routing table calculation) and suggested data packet handling and routing table calculation) and suggested data
structures internally in each router. structures internally in each router.
7.1. Protocol and Port Number 7.1. Protocol and Port Number
Packages in OLSR are communicated using UDP. Port 698 has been Packages in OLSR are communicated using UDP. Port 698 has been
assigned by IANA for exclusive usage by the OLSR protocol. assigned by IANA for exclusive usage by the OLSR protocol.
7.1. Packet Format 7.2. Packet Format
OLSR communicates using an unified packet format for all data OLSR communicates using an unified packet format for all data
related to the protocol. Inspired by the concept of "extension related to the protocol. The purpose of this is to facilitate
headers" from IPv6, the purpose of this is to facilitate
extensibility of the protocol without breaking backwards extensibility of the protocol without breaking backwards
compatibility as well as to provide an easy way of piggybacking compatibility as well as to provide an easy way of piggybacking
different "types" of information into a single transmission. These different "types" of information into a single transmission. These
packets are embedded in UDP datagrams for transmission over the packets are embedded in UDP datagrams for transmission over the
network. The present draft uses IPv4 addresses. The support for network. The present draft uses IPv4 addresses. Support for IPv6
IPv6 will be described in a future draft. will be included in a future draft.
Each package encapsulates one or more messages. The messages share
a common header format, which enables nodes to correctly accept
and (if applicable) retransmit messages of an unknown type.
Messages can be flooded onto the entire network, or flooding can
be limited to nodes within a diameter (in terms of number of hops)
from the originator of the message. Thus, broadcasting a message
to a nodes neighborhood is just a special case of flooding. When
flooding any control message, duplicate retransmissions will be
eliminated locally (i.e. each node maintains a duplicate table to
prevent transmitting the same message twice) and minimized in the
entire network through the usage of MPRs as described in section 5
and 6.
Furthermore, a node can examine the header of a message to obtain
information on the distance (in terms of number of hops) to the
originator of the message. This feature may be useful in
situations where, e.g., the time information from a recieved
control messages is stored in a node depends on the distance to
the originator.
The basic layout of any packet in OLSR will be as follows: The basic layout of any packet in OLSR will be as follows:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Reserved for future use | | Packet Length | Reserved for future use |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved |B| Message Size | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Size | Time To Live | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: :
: MESSAGE : : MESSAGE :
: :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Reserved |B| Message Size | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Size | Time To Live | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: :
: MESSAGE : : MESSAGE :
: :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
(etc) (etc)
7.1.1. Packet Header 7.2.1. Packet Header
Packet Length Packet Length
The length (in bytes) of the packet The length (in bytes) of the packet
Reserved for future use Reserved for future use
MUST be set to '0000000000000000' to be in compliance with this MUST be set to '0000000000000000' to be in compliance with this
version of the draft. version of the draft.
The information in the header of this packet is equivalent to the The sender information for a packet is obtainable from the UDP
information obtainable from the UDP header. header.
7.1.2. Message Header 7.2.2. Message Header
Originator Address
This field contains the address of the node, which has
originally generated this message. This field SHOULD NOT be
confused with the source address from the UDP header, which is
changed each time to the address of the intermediate node which
is "re-transmitting" this message. The Originator Address field
MUST *NEVER* be changed in the retransmissions.
Message Sequence Number
While generating the TC message, the "originator" node will
assign a unique identification number to each message. This
number is inserted into the Sequence Number field of the
message. The sequence number is increased by 1 (one) for each
message originating from the node - "wrap-arounds" are handled
as described in section 10.
Message Size
This field gives the size of this message, measured from the
beginning of the "Message Type" field and until the beginning
of the next "Message Type" field (or - if there are no
following messages - the end of the packet).
Message Type Message Type
This field indicates which type of message are to be found in This field indicates which type of message are to be found in
the "MESSAGE" partition. Message types in the range of 0-127 are the "MESSAGE" partition. Message types in the range of 0-127 are
reserved for messages in this draft and in reserved for messages in this draft and in
draft-ietf-manet-olsr-extensions-00.txt. draft-ietf-manet-olsr-extensions-00.txt.
B Time To Live
This field indicates to a node whether the message is meant for This field contains the maximum number of hops a message will
diffusion into the entire network. This enables a node to be retransmitted. Before a message is transmitted, the Time To
forward messages correctly, even if it doesn't recognize the Live MUST be decremented by 1. When a node receives a message
"Message Type". with a Time To Live equal to 0, the message MUST NOT be
retransmitted under any circumstances.
Thus, by setting this field, the originator of a message can
limit the flooding radius.
Hop Count
This field will contain the number of hops a message has
attained. Before a message is (re-) transmitted, the Hop Count
MUST be incremented by 1.
Initially, this is set to '0' by the originator of the message.
Reserved Reserved
MUST be set to '0000000' to be in compliance with this
version of the draft.
Message Size This field is reserved for future usage, and MUST be set to
'00000000' for compliance with this draft.
This field gives the size of this message, measured from the 7.2.3. Packet Processing
beginning of the "Message Type" field and until the beginning
of the next "Message Type" field (or - if there are no
following messages - the end of the packet).
7.1.3. Packet Processing Upon receiving a basic packet, the protocol parser examines each
of the "message headers". Based on the value of the "Message Type"
field, the parser can determine the faith of the message. A node
may receive the same message in several packets. This can happen
only if the message is retransmitted by two nodes in the receivers
neighborhood, i.e. the "Time To Live" and the "Hop Count" fields
in the message satisfies the following condition:
Upon receiving such a basic packet, the protocol parser examines Time To Live + Hop Count > 1
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 Thus, to avoid re-processing of a message which was already
process, then this data is processed. received and processed, each node maintains a Duplicate table. In
this table, the node records information about the most recently
received messages where the above condition holds. For each
message, satisfying the above condition, a node records a
"Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr is the
originator address of the message, D_seq_num is the message
sequence number of the message and D_time specifies the time at
which a tuple expires and *MUST* be removed.
2. Otherwise, if the "Message Type" indicates a type, unknown to In a node, the set of Duplicate Tuples are denoted the "Duplicate
the node, the message SHOULD silently be dropped. set".
Thus, upon receiving a basic packet, a node performs the following
tasks for each encapsulated message:
1. If there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND
D_seq_num == Message Sequence Number
then the message has already been completely processed
and MUST silently be ignored.
2. Otherwise, if the Message Type of the message is known to
the node, the message MUST be processed according to the
specifications of such message type.
3. Otherwise, If the Message Type of the message is not known
to the node, the message MUST be processed according to the
following algorithm:
3.1 If the sender of the message is not in the MPR selector
set of the node, the message MUST silently be dropped.
3.2 If the time to live of the message is less than or equal
to '0' (zero), the message MUST silently be dropped.
3.3 Otherwise, if the sender of the message is an MPR
selector of this node and if the time to live of the
message is greater than '0' (zero), the message MUST be
forwarded according to the following algorithm:
3.3.1 The time to live of the message is reduced by one.
3.3.2 The hop-count of the message is increased by one
3.3.3 An entry in the duplicate set is recorded with:
D_addr = originator address
D_seq_num = Message Sequence Number
D_time = current time + D_HOLD_TIME.
3.3.4 The message is retransmitted (Notice: The
remaining fields of the message header SHOULD
be left unmodified.)
Notice: known message types are *not* forwarded "blindly" by this
algorithm. Forwarding (and setting the correct message header in
the forwarded, known, message) is the responsibility of the
algorithm specifying how the message is to be handled. This
enables, e.g., a message type to be specified such that the
message can be modified while in transit (e.g. to reflect the
route the message has taken). Further, it enables that the
optimization through the MPRs can be bypassed: if for some reason
pure flooding of a message type is required (e.g. to transmit
control information over unidirectional links), the algorithm
specifying handling of these messages will simply rebroadcast
the message, regardless of MPR selectors.
Finally, notice that a message, which is to be broadcast in the
neighborhood, but not flooded into the entire network, (e.g. a
HELLO-message) is simply specified by setting the time to live to
'0' (zero), and that no duplicate entries are recorded for such
messages.
By defining a set of message types, which MUST be recognized by all By defining a set of message types, which MUST be recognized by all
implementations of OLSR, it will be possible to extend the protocol implementations of OLSR, it will be possible to extend the protocol
through introduction of additional message types, while still be through introduction of additional message types, while still be
able to maintain compatibility with older implementations. The two able to maintain compatibility with older implementations. The two
REQUIRED message types for OLSR are: REQUIRED message types for OLSR are:
- HELLO-messages, performing the task of neighbor sensing. - HELLO-messages, performing the task of neighbor sensing.
- TC-messages, performing the task of multipoint relay - TC-messages, performing the task of MPR information declaration.
information declaration.
Extensions may e.g. be PC-messages for enabling power conservation Extensions may e.g. be PC-messages for enabling power conservation
/ sleep mode, multicast routing, gateway announcements etc. / sleep mode, multicast routing, gateway announcements,
auto-configuration/address assignment etc.
7.2. Neighbor sensing 7.3. Neighbor sensing
7.2.1. HELLO message broadcast 7.3.1. Neighbor sensing information base
7.3.1.1 Neighbor information
A node maintains information (obtained from the HELLO messages)
about its one hop neighbors, the status of the link with these
neighbors, a list of 2-hop neighbors that these one hop neighbors
give access to, and an associated holding time.
Thus, for each neighbor, a node records a "Neighbor Tuple"
(N_addr, N_status, N_time) where N_addr is the address of the
neighbor, N_status designates the status of the link with that
neighbor (MPR, symmetric, heard) and N_time specifies the time at
which this record expires and *MUST* be removed.
Likewise, a node records a set of "2-hop tuples" (N_addr,
N_2hop_addr, N_time), describing symmetric or MPR links between
its neighbors and the 2-hop neighborhood. N_addr is the address of
a neighbor, N_2hop_addr is the address of a 2-hop neighbor and
N_time specifies the time at which a tuple expires and *MUST*
be removed.
In a node, the set of Neighbor Tuples are denoted the "Neighbor
Set" and the set of 2-hop tuples are denoted the "2-hop neighbor
set".
7.3.1.2 MPR Selector information
A node maintains information (obtained from the HELLO messages)
about the neighbors which have selected the node as a MPR.
Thus, a node records a MPR-selector tuple (MS_addr, MS_time), for
each neighbor which has selected the node as MPR. MS_addr is the
address of a node which has selected the node as MPR, and MS_time
specifies the time at which a tuple expires and *MUST* be
removed.
In a node, the set of MPR-tuples are denoted the "MPR selector
set" A sequence number, MSSN, is associated with this
set. Whenever a tuple is added or removed to this set, the MSSN is
incremented by 1.
7.3.2. HELLO message broadcast
Each node should detect the neighbor nodes with which it has a direct Each node should 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 broadcasts HELLO messages, containing To accomplish this, each node broadcasts HELLO messages,
information about neighbors and their link status. The link status containing information about neighbors and their link status. The
may either be "symmetric", "heard" (asymmetric) or "MPR". link status may either be "symmetric", "heard" (asymmetric) or
"Symmetric" indicates, that the link has been verified to be "MPR". "Symmetric" indicates, that the link has been verified to
bi-directional, i.e. it is possible to transmit data in both be bi-directional, i.e. it is possible to transmit data in both
directions. "Heard" indicates that the node is hearing from a directions. "Heard" indicates that the node can hear HELLO
neighbor, but it is not confirmed that this neighbor is also messages from a neighbor, but it is not confirmed that this
hearing from the node. "MPR" indicates, that a node is selected by neighbor is also able to receive messages from the node. "MPR"
the sender as multipoint relay. MPR status implies that the link is indicates, that a node is selected by the sender as a MPR. A
symmetric too. status of MPR further implies that the link is symmetric.
These control messages are broadcast to all one-hop neighbors, but These control messages are broadcast to all one-hop neighbors, but
are *not relayed* to further nodes. A HELLO-message contains at a are *not relayed* to further nodes. A HELLO-message contains:
minimum:
- a list of addresses of neighbors, to which there exists a - a list of addresses of neighbors, to which there exists a
symmetric link; symmetric link;
- a list of addresses of neighbors, which have been "heard"; - a list of addresses of neighbors, which have been "heard";
- a list of neighbors, which have been selected as multipoint - a list of neighbors, which have been selected as MPRs.
relays.
The list of neighbors in a HELLO message can be partial (e.g. due The list of neighbors in a HELLO message can be partial (e.g. due
to message size limitations, imposed by the network), the rule 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).
To accommodate for the above constraints, as well as to accommodate To accommodate for the above constraints, as well as to accommodate
for future extensions, an approach similar to the overall packet for future extensions, an approach similar to the overall packet
format (see section 6.1) is taken. Thus the proposed format of a format (see section 6.1) is taken. Thus the proposed format of a
HELLO message is: 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Sequence Number | MPR Sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Link Message Size | | Link Type | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . : : . . . :
: : : :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Link Message Size | | Link Type | Reserved | Link Message Size |
skipping to change at page 14, line 38 skipping to change at page 18, line 4
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Link Message Size | | Link Type | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
: : : :
(etc) (etc)
This is sent as the data-portion of the general packet format This is sent as the data-portion of the general packet format
described in 6.1, with the "Message Type" set to HELLO_MESSAGE and described in 6.1, with the "Message Type" set to HELLO_MESSAGE and
the broadcast field set to NO_BROADCAST. the TTL field set to 0.
7.2.1.1. Description of the fields
Message Sequence Number
While generating a HELLO message, the node will assign a unique 7.3.2.1. Description of the fields
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.
MPR Sequence Number MPR Sequence Number
This field indicates the sequence number corresponding to the This field indicates the sequence number corresponding to the
most recent multipoint relay set, calculated by the sender node. most recent MPR set, calculated by the sender node.
Link Message Size
The size of the link message, measured from the beginning of
the "Link Type" field and until the next "Link Type" field (or
- if there are no more link types - the end of the message).
Link Type Link Type
This field specifies the type of link the sending node has to This field specifies the type of link the sending node has to
the following list of neighbors. As a minimum, the following the following list of neighbors. As a minimum, the following
three link types are REQUIRED by OLSR: three link types are REQUIRED by OLSR:
- ASYM_LINK - indicating that the links between the sender - ASYM_LINK - indicating that the links between the sender
and the neighbors in the following list are asymmetric and the neighbors in the following list are asymmetric
(i.e. the neighbor is "heard"). (i.e. the neighbor is "heard").
- SYM_LINK - indicating that the links between the sender - SYM_LINK - indicating that the links between the sender
and the neighbors in the following list are symmetric. and the neighbors in the following list are symmetric.
- MPR_LINK - indicating, that the nodes in the following - MPR_LINK - indicating, that the nodes in the following
list have been selected by the sender as multipoint list have been selected by the sender as MPR.
relays.
(Notice: this implies, that the links from the sender (Notice: this implies, that the links from the sender
of the HELLO and to the nodes in the list are symmetric). of the HELLO and to the nodes in the list are symmetric).
It is possible to provide additional information by specifying It is possible to provide additional information by specifying
additional link-types, e.g. LOST_LINK - indicating that the link additional link-types, e.g. LOST_LINK - indicating that the link
between the sender and the neighbors in the following list has between the sender and the neighbors in the following list has
been lost. Upon processing a HELLO message, a node silently been lost. Upon processing a HELLO message, a node silently
ignores link-types, which are unknown. ignores link-types, which are unknown.
Reserved Reserved
This field is reserved for future usage, and MUST be set to This field is reserved for future usage, and MUST be set to
00000000 for compliance with this draft. 000000000000000000000000 for compliance with this draft.
Link Message Size
The size of the link message, measured from the beginning of
the "Link Type" field and until the next "Link Type" field (or
- if there are no more link types - the end of the message).
Neighbor Address Neighbor Address
The address of a neighbor. The address of a neighbor.
7.2.2. HELLO message processing 7.3.3. HELLO message processing
The HELLO messages permit each node to acquire information about
its neighborhood up to two hops. A node maintains a Neighbor table
in which it records the information (obtained from the HELLO
messages) about its one hop neighbors, the status of the link with
these neighbors, a list of two hop neighbors that these one hop
neighbors give access to, and an associated holding time. The
information is recorded in the Neighbor table as a neighbor entry,
with the following field names:
1. N_addr N_status N_2hop_list N_time
2. N_addr N_status N_2hop_list N_time
3. ,, ,, ,, ,,
Each entry in the table consists of N_addr, N_status, N_2hop_list,
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
is N_status, and this neighbor provides access to the two hop
neighbors listed in N_2hop_list. Each entry in N_2hop_list consists
of a 2 hop neighbor address and associated holding time. The
N_status can be ASYM_LINK, 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 N_addr is selected as a multipoint relay
by this node. Each neighbor entry has an associated holding time
N_time, upon expiration of which it is no longer valid and hence
MUST be removed.
The node also contains a sequence number N_MPR_seq. This specifies Upon receiving a HELLO message, the node SHOULD update the
that the node has selected its most recent MPR set with the neighbor information corresponding to the sender node address (a
sequence number N_MPR_seq. Every time a node selects or updates its node may - e.g. for security reasons - wish to restrict updating
multipoint relay set, N_MPR_seq is incremented to a higher the neighbor-table, i.e. ignoring HELLO messages from some nodes).
value. This number is put into the HELLO messages as described in
6.2.1.
Upon receiving a HELLO message, the node should update the In this section, the term "Originator Address" will be used for
neighbor entry corresponding to the sender node address (a node the address of the node which sent the HELLO-message.
may - e.g. for security reasons - wish to restrict updating the
neighbor-table, i.e. ignoring HELLO messages from some nodes):
1. If the entry already exists: 1. If there exists a neighbor tuple with N_addr = Originator
Address:
1.1 if the recipient of the HELLO has recorded the sender as 1.1 if for that tuple N_status == ASYM_LINK:
asymetric:
1.1.1 if the node finds its own address among the 1.1.1 if the node finds its own address among the
addresses listed in the HELLO message (with Link addresses listed in the HELLO message (with Link
Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates
the status of the link to the sender node as the N_status of the tuple to SYM_LINK and sets
SYM_LINK and refreshes the N_time to N_time = current time + NEIGHB_HOLDING_TIME.
NEIGHB_HOLDING_TIME.
1.1.2 otherwise, if the node does not find its own 1.1.2 otherwise, if the node does not find its own
address among the addresses listed in the HELLO address among the addresses listed in the HELLO
message, it refreshes the N_time to message, it sets N_time = current time +
NEIGHB_HOLDING_TIME. NEIGHB_HOLDING_TIME.
1.2 otherwise, if the recipient of the HELLO has recorded 1.2 otherwise, if for that tuple:
the sender as symetric (or MPR):
N_status == SYM_LINK OR
N_status == MPR_LINK
then:
1.2.1 if the node finds its own address among the addresses 1.2.1 if the node finds its own address among the addresses
listed in the HELLO message (with Link Type listed in the HELLO message (with Link Type
ASYM_LINK, SYM_LINK or MPR_LINK), it refreshes the ASYM_LINK, SYM_LINK or MPR_LINK), it sets N_time =
N_time to NEIGHB_HOLDING_TIME. current time NEIGHB_HOLDING_TIME.
2. Otherwise, a new entry is recorded in the Neighbor table with: 2. Otherwise, a new neighbor tuple is created with:
- N_addr is set to the address of the sender node, N_addr = Originator Address
- N_status is set to the value of SYM_LINK if the node N_status with the value of SYM_LINK if the node
finds its own address (with Link Type ASYM_LINK, SYM_LINK finds its own address (with Link Type ASYM_LINK, SYM_LINK
or MPR_LINK) among the addresses listed in the HELLO or MPR_LINK) among the addresses listed in the HELLO
message, and to the value of ASYM_LINK otherwise message, and to the value of ASYM_LINK otherwise
- N_time is set to the value of NEIGHB_HOLD_TIME N_time = current time + NEIGHB_HOLD_TIME
The N_2hop_list of the entry of the sender is updated, as The 2-hop neighbor set is updated as follows: for each 2-hop
follows. For each address listed in the HELLO message with Link neighbor address listed in the HELLO message with Link Type
Type SYM_LINK or MPR_LINK: SYM_LINK or MPR_LINK:
1. if an entry with this address exists in the N_2hop_list, then 1. if a 2-hop tuple exists with:
the associated holding time is refreshed to NEIGHB_HOLD_TIME
2. otherwise an entry with this address and holding time N_addr == Originator Address AND
NEIGHB_HOLD_TIME is added to the N_2hop_list. N_2hop_address == the address of the 2-hop neighbor,
Based on the information obtained from the HELLO messages, each then the N_time of that tuple is set to:
node construct its MPR Selector table. In this table, the node
registers the addresses of those one hop neighbor nodes which have
selected the node as a multipoint relay. The MPR Selector table may
have the following format:
1. MS_addr MS_seq_num MS_time N_time = current time + NEIGHB_HOLD_TIME
2. MS_addr MS_seq_num MS_time
3. ,, ,, ,,
Each entry in the table consists of MS_addr, MS_seq_num and 2. otherwise a new 2-hop tuple is created with:
MS_time, which specifies that the node with address MS_addr has
selected this node as its multipoint relay with the MPR sequence
number equal to MS_seq_num. Each entry has an associated holding
time MS_time, upon expiation of which it is no longer valid and
hence removed.
A sequence number, MSSN, is associated with this table. This number N_addr = Originator Address,
specifies that the multipoint relay selector set of the node
keeping this MPR Selector table is most recently modified with the
sequence number MSSN. The node modifies its MPR Selector set
according to the information it receives in the HELLO messages, and
increment this sequence number upon each modification.
Upon receiving a HELLO message, if a node finds its own address in N_2hop_address = the address of the 2-hop neighbor,
the address list with a link type of "MPR", it MUST update the
entry corresponding to the sender node's address in the MPR
Selector table:
1. If the entry already exists: N_time = current time + NEIGHB_HOLD_TIME.
1.1 if the MPR Sequence Number field of the HELLO message is Based on the information obtained from the HELLO messages, each
greater than or equal to the MS_seq_num field of the node construct its MPR selector set.
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 Thus, upon receiving a HELLO message, if a node finds its own
greater than the MS_seq_num field of that entry, the address in the address list with a link type of "MPR", it MUST
MS_seq_num field is updated to the value of MPR Sequence update the MPR selector set to contain updated information about
Number field of the HELLO message. the sender of the HELLO message:
2. Otherwise, a new entry is recorded in the MPR Selector table, 1. If a MPR selector tuple exists with:
with:
2.1 MS_addr is set to the address of sender of the HELLO MS_addr == Originator Address
message
2.2 MS_seq_num is set to the MPR Sequence Number field of the then the expiration time of that tuple is set to:
HELLO message
2.3 MS_time is set to the value of NEIGHB_HOLD_TIME MS_time = current time + NEIGHB_HOLD_TIME.
2.4 MSSN is incremented to indicate that the MPR Selector 2. Otherwise, a new MPR selector tuple is created with:
table has been changed.
MS_addr = Originator Address
MS_time = current time + NEIGHB_HOLD_TIME
2.1 MSSN is incremented by one to indicate that the MPR
selector table has been changed.
If link layer information describing connectivity to neighboring If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through nodes is available (i.e. loss of connectivity such as through
absence of an acknowledgment), this MAY be used in addition to absence of an acknowledgment), this MAY be used in addition to
the information from the HELLO-messages to maintain the neighbor the information from the HELLO-messages to maintain the neighbor
table and the MPR selector table. table and the MPR selector table as described in section 7.7.
7.3. Multipoint relay selection 7.4. Multipoint relay selection
Each node in the network selects independently its own set of Each node in the network selects independently its own set of
multipoint relays. Multipoint relays are used to flood the control MPRs. MPRs are used to flood control messages from that node into
messages of that node into the network. The MPR set is calculated the network while reducing the number of retransmissions that will
in a way such that it contains a subset of one hop neighbors which occur in a region. Thus, the concept of MPRs is an optimization
covers all the two hop neighbors. This means, that the union of the of a pure flooding mechanism.
neighbor sets of all MPRs contains the entire two hop neighbor
set. In order to build the list of the two hop nodes, make the
union of N_2hop_lists of all neighbors (with Link Type SYM_LINK or
MPR_LINK), then remove from this union the one-hop neighbors (with
Link Type SYM_LINK or MPR_LINK), and finally remove the node
itself. Multipoint relays of a given node are declared in the
subsequent HELLOs transmitted by this node, so that the information
reaches the multipoint relays themselves. These selected multipoint
relays are indicated in the HELLO messages with a link status of
"MPR". The multipoint relay set is re-calculated when:
- a change in the neighborhood is detected, i.e. either a The MPR set must be calculated by a node in a way such that it,
symmetric link with a neighbor is failed, or a new neighbor through the neighbors in the MPR-set, can reach all 2-hop
with a symmetric link is added; or neighbors. This means that the union of the neighbor sets the MPR
- a change is detected in the two-hop neighborhood such that nodes contains the entire 2-hop neighbor set. While it is not
a symmetric link is either detected or broken between a essential that the MPR set is minimal, it is essential that all
two-hop neighbor and a neighbor. 2-hop neighbors can be reached through the selected MPR nodes. The
smaller a MPR-set, however, the more optimizations are achieved.
The MPR set needs not be optimal. However it SHOULD be small enough By default, the MPR set can coincide with the entire neighbor
to achieve the benefit of the multipoint relays. The concept of set. This will be the case at network initialization.
multipoint relays is an optimization of a pure flooding mechanism.
It is not essential that the multipoint relay set be minimal or
optimal. But it is essential that all two-hop neighbors can be
reached through the selected MPR's. By default, the multipoint
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
multipoint relay set. This sequence number will also appear, along
with the MPR list, in the HELLO messages.
We propose a heuristic for the selection of multipoint relays The following specifies a proposed heuristic for selection of MPRs
[2]. We use the following terminology in describing this algorithm: [2]. The following terminology will be used in describing this
algorithm:
MPR(x): Multipoint relay set of node x which is running this N: The net of neighbors with which there exists a
algorithm symmetric link.
N(x): One hop neighbor set of node x (containing only symmetric
neighbors)
N2(x): Two hop neighbor set of node x (containing only symmetric
neighbors of nodes in N(x) ). The two hop neighbor set
N2(x) of node x does not contain any one hop neighbor of
node x
D(x,y): Degree of one hop neighbor node y (where y is a member N2: The set of 2-hop neighbors. This set does not contain
of N(x) ), is defined as the number of symmetric one hop any one hop neighbors.
neighbors of node y EXCLUDING the node x and all the
symmetric one hop neighbors of node x, i.e., D(y): Degree of one hop neighbor node y (where y is a member
D(x,y) = number of elements of N(y) - {x} - N(x) of N), is defined as the number of symmetric one hop
neighbors of node y, EXCLUDING the node performing the
computation and all its direct neighbors.
The proposed heuristic is as follows: The proposed heuristic is as follows:
1. Start with an empty MPR(x) 1. Start with an empty MPR set
2. Calculate D(x,y), where y is a member of N(x), for all nodes 2. Calculate D(y), where y is a member of N, for all nodes
in N(x) in N.
3. First select as MPRs those nodes in N(x) which provide the 3. Select as MPRs those nodes in N which provide the
"only path" to reach some nodes in N2(x) "only path" to some nodes in N2
4. While there still exist some nodes in N2(x) that are not 4. While there exist nodes in N2 which are not covered by MPR:
covered by MPR(x):
4.1 For each node in N(x), calculate the number of nodes in 4.1 For each node in N, calculate the number of nodes in
N2(x) which are not yet covered by MPR(x) and are N2 which are not yet covered by MPR 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 which reaches the
maximum number of uncovered nodes in N2(x). In case of a maximum number of uncovered nodes in N2. In case of a
tie, select that node as MPR whose D(x,y) is greater. tie, select that node as MPR whose D(y) is greater.
5. To optimize, process each node y in MPR(x), one at a time, and 5. As an optimization, process each node y in MPR.
if MPR(x) - {y} still covers all nodes in N2(x) then remove y from If MPR\{y} still covers all nodes in N2, Y SHOULD be
MPR(x) removed from the MPR set.
After selecting the multipoint relays among the neighbors, the link After selecting the MPRs among the neighbors, the link status of
status of the corresponding one hop neighbors is changed from the corresponding one hop neighbors is changed from SYM_LINK to
SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in MPR_LINK in the neighbor table. MPR_Seq_Num value in the Neighbor
the Neighbor table is also incremented by one. table is also incremented by one.
The MPR set is re-calculated when:
7.4. Multipoint relay information declaration - a change in the neighborhood is detected, i.e. either a
symmetric link with a neighbor is failed, or a new neighbor
with a symmetric link is added; or
- a change is detected in the 2-hop neighborhood such that
a symmetric link is either detected or broken between a
2-hop neighbor and a neighbor.
7.4.1. TC Message Broadcast 7.5. Multipoint relay information declaration
In order to build the topology information database needed for 7.5.1 Topology information base
routing the packets, each relay node broadcasts specific service
messages called Topology Control (TC) messages. TC messages are Each node in the network maintains topological information about
forwarded, like usual broadcast messages, to all nodes in the the network. This information is acquired from TC-messages and
network and take advantage of multipoint relays. Multipoint relays used for routing table calculations.
enable a better scalability in the distribution of topology
information [1]. Thus, for each destination in the network, a "Topology Tuple"
(T_dest, T_last, T_seq, T_time) is recorded. T_dest is the address
of a node, which may be reached in one hop from the node with the
address T_last. T_seq is a sequence number, and T_time specifies
the time at which this tuple expires and *MUST* be removed.
In a node, the set of Topology Tuples are denoted the "Topology
Set".
7.5.2. TC Message Broadcast
In order to build the topology information base needed, each node,
which has been selected as MPR, broadcasts Topology Control (TC)
messages. TC messages are flooded to all nodes in the network and
take advantage of MPRs. MPRs enable a better scalability in the
distribution of topology information [1].
A TC message is sent by a node in the network to declare its MPR A TC message is sent by a node in the network to declare its MPR
Selector set. I.e., the TC message contains the list of neighbors Selector set. I.e., the TC message contains the list of neighbors
which have selected the sender node as a multipoint relay. The which have selected the sender node as a MPR. The sequence number
sequence number (MSSN) associated with this multipoint relay (MSSN) associated with this MPR selector set is also sent with the
selector set is also sent with the list. The list of addresses can list. The list of addresses can be partial in each TC message
be partial in each TC message (e.g. due to message size (e.g. due to message size limitations, imposed by the network),
limitations, imposed by the network), but parsing of all TC but parsing of all TC messages describing a nodes MPR selector set
messages describing a nodes MPR selector set MUST be complete MUST be complete within a certain refreshing period
within a certain refreshing period (TC_INTERVAL). The information (TC_INTERVAL). The information diffused in the network by these TC
diffused in the network by these TC messages will help each node to messages will help each node to calculate its routing table. A
calculate its routing table. A node which has an empty MPR Selector node which has an empty MPR selector set, i.e. nobody has selected
set, i.e. nobody has selected it as a multipoint relay, MUST NOT it as a MPR, MUST NOT generate any TC message.
generate any TC message.
A node MAY transmit additional TC-messages to increase its A node MAY transmit additional TC-messages to increase its
reactiveness to link failures. I.e. when a change to the MPR reactiveness to link failures. I.e. when a change to the MPR
selector set is detected and this change can be attributed to a selector set is detected and this change can be attributed to a
link failure, a TC-message SHOULD be transmitted after a shorter link failure, a TC-message SHOULD be transmitted after a shorter
interval than TC_INTERVAL. interval than TC_INTERVAL.
The proposed format of a TC message is The proposed format of a TC message is
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Sequence Number | MSSN | | MSSN | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Count | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This is sent as the data-portion of the general message format 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 described in 6.1, with the "Message Type" set to TC_MESSAGE. The
the broadcast field set to BROADCAST. time to live SHOULD be set to 255 (maximum value) to diffuse the
message into the entire network.
7.4.1.1. Description of the fields
Message Sequence Number
While generating the TC message, the "originator" node will 7.5.2.1. Description of the fields
assign a unique identification number to this message, and will
put this number in the Sequence Number field. This sequence
number will be different for all messages originated by that
node, and will be used to recognize duplicate reception of
messages.
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 MPR selector
selector set. Every time a node detects a change in its set. Every time a node detects a change in its MPR selector
multipoint relay selector set, it increments this sequence set, it increments this sequence number. This number is sent in
number. This number is sent in this MSSN field of the TC message this MSSN field of the TC message to keep track of the most
to keep track of the most recent information. When a node recent information. When a node receives a TC message, it can
receives a TC message, it can decide on the basis of this MPR decide on the basis of this MPR Sequence Number, whether or not
Sequence Number, whether or not the received information about the received information about the MPR selectors of the
the multipoint relay selectors of the originator node is more originator node is more recent than what it already has.
recent than what it already has.
Hop Count Multipoint Relay Selector Address (MPR-S)
This field will contain the maximum number of hops a TC message This field contains the address of a node, which has selected
can attain. Every time a TC message is re-transmitted, this the Originator node (of the TC message) as a MPR. All
field is decremented by 1. When this field reaches zero, the TC addresses of the MPR selectors of the Originator node are put
message is no more re-transmitted and is discarded. in the TC message. If the maximum allowed message size (as
imposed by the network) is reached while there are still MPR
selector addresses which which have not been inserted into the
TC-message, more TC messages will be generated until the entire
MPR selector set has been sent.
Reserved Reserved
This field is reserved for future usage, and MUST be set to This field is reserved for future usage, and MUST be set to
'000000000000000000000000' for compliance with this draft. '0000000000000000' for compliance with this draft.
Originator Address 7.5.3. TC Message Processing
This field contains the address of the node, which has TC messages are broadcasted and retransmitted by the MPRs in order
originally generated this TC message. This field MUST not be to diffuse the messages in the entire network.
confused with the source read in the UDP header, which is
changed each time to the address of the intermediate node which
is "re-transmitting" this TC message. The Originator Address
field is *never* changed in the retransmissions.
Multipoint Relay Selector Address (MPR-S) In this section, the term "originator" is used to designate the
node from which the message originally originated, while the term
"sender" is used to designate the node from which the message was
received (i.e. the "last hop" of the message).
This field contains the address of a node, which has selected The tuples in the topology set are recorded with the topology
the Originator node (of the TC message) as a multipoint relay. information that is exchanged through TC messages, following the
All addresses of the multipoint relay selectors of the following algorithm:
Originator node are put in the TC message. If the maximum
allowed message size (as imposed by the network) is reached
while there are still multipoint relay selector addresses which
which have not been inserted into the TC-message, more TC
messages will be generated until the entire MPR selector set has
been sent.
7.4.2. TC Message Processing 1. If the sender (NB: not originator) of this message is not in
the neighbor set of this node, the message is discarded.
In the OLSR protocol, TC messages are broadcasted and are 2. A tuple is inserted into the duplicate table to prevent
retransmitted by the multipoint relays in order to diffuse the being processed again with:
messages in the entire network. In this process, a node MAY receive
the same TC message more than once. To avoid re-processing of a TC
message which was already received and processed, each node
maintains a Duplicate table. In this table, the node records
information about the most recently received TC messages. The
information is recorded in the Duplicate table as Duplicate
entries.
The table may have the following format: D_addr = originator address
1. D_addr D_seq_num D_time D_seq_num = Message Sequence
2. D_addr D_seq_num D_time
3. ,, ,, ,,
Each entry in the table consists of D_addr, D_seq_num and D_time, D_time = current time + D_HOLD_TIME.
which specifies that a TC message was received, originating from
the node with address D_addr, having the message sequence number
as D-seq_num. Each Duplicate entry also has an associated holding
time D_time, upon expiration of which it is no longer valid and
hence MUST be removed.
Upon receiving a TC message, a node checks in its Duplicate table 3. If there exist some tuple in the topology set where:
to see if it has already received the same message. If it finds a
corresponding entry, the message is discarded. Otherwise, a new
entry is recorded in the Duplicate table for this newly received TC
message, and the message is processed. When a node receives a TC
message from a neighbor node with which it has an asymmetric (or
uni-directional) link, it neither registers the message in the
Duplicate table nor it processes the message.
Each node in the network maintains a topology table, in which it T_last == originator address AND
records the information about the topology of the network as T_seq > MSSN,
obtained from the TC messages. Based on this information, the
routing table is calculated. A node records information about the
multipoint relays of other nodes in the network in its topology
table as a topology entry, which may have the following format:
1. T_dest T_last T_seq T_time then no further processing of this TC message is performed
2. T_dest T_last T_seq T_time and the message is silently discarded (case: message
3. ,, ,, ,, ,, received out of order).
Each entry in the table consists of T_dest, T_last, T_seq, and 4. All tuples in the topology set where:
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
this information of its multipoint relay selector set with the
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
associated holding time T_time, upon expiration of which it is no
longer valid and hence MUST be removed.
The entries in the topology table are recorded with the topology T_last == originator address AND
information that is exchanged through TC messages. T_seq < MSSN
After registering a TC message in the duplicate table, the following are removed from the topology set.
procedure is executed to record the information in the topology
table:
1. If there exist some entry in the topology table whose T_last 5. For each of the MPR selector address received in the TC
corresponds to the originator address of the TC message and message:
whose T_seq is greater in value than the MSSN in the received
message, then no further processing of this TC message is
performed and it is silently discarded (case: message
received out of order).
2. All entries in the topology table with T_last corresponding 5.1 If there exist some tuple in the topology set where:
to the originator address of the TC message and whose T_seq
is lesser in value than the MSSN in the received message,
are removed.
3. For each of the MPR Selector address received in the TC T_dest == MPR selector address, AND
message: T_last == originator address,
3.1 If there exist some entry in the topology table whose then the holding time of that tuple is set to:
T_dest corresponds to the MPR Selector address and the
T_last corresponds to the originator address of the TC
message, then the holding time T_time of that topology
entry is refreshed to TOP_HOLD_TIME.
3.2 Otherwise, a new topology entry is recorded in the T_time = current time + TOP_HOLD_TIME.
topology table where:
- T_dest is set to this MPR Selector address, 5.2 Otherwise, a new tuple is recorded in the topology set
- T_last is set to the originator address of the TC where:
message,
- T_seq is set to the value of MSSN received in the TC
message,
- T_time is set to the value of TOP_HOLD_TIME.
7.5. Routing table calculation T_dest = MPR selector address,
T_last = originator address,
T_seq = MSSN,
T_time = current time + TOP_HOLD_TIME.
7.6. 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
messages for the other destinations in the network. The routing messages for the other destinations in the network. The routing
table is based on the information contained in the neighbor table table is based on the information contained in the neighbor set
and the topology table. Therefore, if any of these tables is and the topology set. Therefore, if any of these tables is
changed, the routing table is re-calculated to update the route changed, the routing table is re-calculated to update the route
information about each destination in the network. The 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. ,, ,, ,,
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 a change is detected This routing table is updated when a change is detected in
in the neighbor table, or the topology table. The update the neighbor set, or the topology set. The update of this routing
of this routing table does not generate or trigger any messages to information does not generate or trigger any messages to be
be transmitted, neither in the network, nor in the one-hop transmitted, neither in the network, nor in the one-hop
neighborhood. neighborhood.
To construct the routing table of node X, a shortest path algorithm To construct the routing table of node X, a shortest path
is run on the directed graph containing the arcs X -> Y where Y is any algorithm is run on the directed graph containing the arcs X -> Y
one hop neighbor of X (with Link Type SYM_LINK or MPR_LINK) and the where Y is any one hop neighbor of X (with Link Type SYM_LINK or
arcs U -> V where there exists an entry in the topology table with MPR_LINK) and the arcs U -> V where there exists an entry in the
V as T_dest and U as T_last. topology set with V as T_dest and U as T_last.
The following procedure is given as an example to calculate (or The following procedure is given as an example to calculate (or
re-calculate) the routing table : re-calculate) the routing table :
1. All the entries of the routing table are removed. 1. All the entries from the routing table are removed.
2. The new entries are recorded in the table starting with the one 2. The new routing entries are added 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 Type is SYM_LINK or entry in the neighbor table, whose Link Type is SYM_LINK or
MPR_LINK, a new route entry is recorded in the routing table MPR_LINK, a new routing entry is recorded in the routing table
where R_dest and R_next are both set to the address of the where R_dest and R_next are both set to the address of the
neighbor and R_dist is set to 1. neighbor and R_dist is set to 1.
3. Then the new route entries for the destination nodes h+1 hops 3. The new route entries for the destination nodes h+1 hops
away are recorded in the routing table. The following procedure away are recorded in the routing table. The following procedure
is executed for each value of h, starting with h=1 and is executed for each value of h, starting with h=1 and
incrementing it by 1 each time. The execution will stop if no incrementing it by 1 each time. The execution will stop if no
new entry is recorded in an iteration. new entry is recorded in an iteration.
3.1 For each topology entry in the topology table, if its 3.1 For each topology entry in the topology table, if its
T_dest does not correspond to R_dest of any route entry T_dest does not correspond to R_dest of any route entry
in the routing table AND its T_last corresponds to R_dest in the routing table AND its T_last corresponds to R_dest
of a route entry whose R_dist is equal to h, then a new of a route entry whose R_dist is equal to h, then a new
route entry is recorded in the routing table where : route entry is recorded in the routing table 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.
7.6 Link layer notification 7.7 Link layer notification
OLSR is designed to operate entirely alone, i.e. does not impose or OLSR is designed not to impose or expect any specific information
expect any specific information from the link layer. However, if from the link layer. However, if information from the link-layer
information from the link-layer is available, a node MAY use this is available, a node MAY use this as described in this section.
as described in this section.
If link layer information describing connectivity to neighboring If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through nodes is available (i.e. loss of connectivity such as through
absence of a link layer acknowledgment), this information is absence of a link layer acknowledgment), this information is
used in addition to the information from the HELLO-messages to used in addition to the information from the HELLO-messages to
maintain the neighbor table and the MPR selector maintain the neighbor set and the MPR selector set.
table. Subsequently, detection of a link failure through a
link-layer notification may trigger additional TC-messages to
increase the protocols reactiveness to link failures. I.e. when a
change to the MPR selector set is detected and this change can be
attributed to a link failure, a TC-message SHOULD be transmitted.
Thus, upon recieving a link-layer notification that the link Subsequently, detection of a link failure through a link-layer
notification may trigger additional TC-messages to increase the
protocols reactiveness to link failures. I.e. when a change to the
MPR selector set is detected and this change can be attributed to
a link failure, a TC-message SHOULD be transmitted.
Thus, upon receiving a link-layer notification that the link
between a node and any neighbor is broken, the following actions between a node and any neighbor is broken, the following actions
are taken: are taken:
1. if the link is broken to either a symetric or asymetric 1. if the link is broken to either a symmetric or asymmetric
neighbor, the entry for that neighbor is removed from the neighbor, the tuple for that neighbor is removed from the
neighbor table, neighbor set,
2. if the link is broken to a neighbor, which is selected as MPR, 2. if the link is broken to a neighbor, which is selected as MPR,
the entry for that neighbor is removed from the neighbor the tuple for that neighbor is removed from the neighbor
table and the MPR set is recalculated, set and the MPR set is recalculated,
3. if the link is broken to a neighbor, which has selected this 3. if the link is broken to a neighbor, which has selected this
node as MPR, the Multipoint Selector Set is updated and a node as MPR, the MPR selector set is updated and a
TC message SHOULD be generated. TC message SHOULD be generated.
8. Packet forwarding 8. Packet forwarding
8.1. Data packet forwarding 8.1. Data packet forwarding
Data packets are relayed on a hop by hop basis. In the source OLSR itself does not perform packet forwarding. Rather, it
router and in any intermediate router, the next hop router is maintains the routing table in the underlying operating system,
identified by the entry of the destination in the host routing which is assumed to be forwarding packets as specified in RFC1812.
table.
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
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
corresponds to the final destination, then the packet is
transmitted to the next hop node.
While forwarding a unicast packet, the originator address, and the
final destination address of the packets are not changed. The
packet traverses the intermediate source and destination pairs,
hop by hop, until it reaches its final destination.
8.2. Topology Control message forwarding 8.2. Control message forwarding
TC messages are relayed by the multipoint relays via the Control messages, destined for flooding into the entire network,
following rule: SHOULD be relayed by the MPR via the following rule:
A node retransmits a TC message only when it is received from A node retransmits a message only when it is received from one
one of its multipoint relay selector AND it is registered in the of its MPR selector AND it is not before registered in the
duplicate table for the first time AND the hop count is greater duplicate table AND the time to live is greater than zero.
than zero.
Before retransmitting, the hop count is decremented by one. Before retransmitting, the hop count is incremented by one and the
time to live is decremented by one.
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
NEIGHB_HOLD_TIME = 6 seconds NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL
TOP_HOLD_TIME = 15 seconds TOP_HOLD_TIME = 3 x TC_INTERVAL
D_TIME = 30 seconds D_TIME = 30 seconds
HELLO_PACKET = 1 HELLO_MESSAGE = 1
TC_PACKET = 2 TC_MESSAGE = 2
ASYM_LINK = 1 ASYM_LINK = 1
SYM_LINK = 2 SYM_LINK = 2
MPR_LINK = 3 MPR_LINK = 3
10. References 10. Sequence Numbers
Sequence numbers are used in OLSR with the purpose of discarding
"old" information, i.e. messages received out of order. However
with a limited number of bits for representing sequence numbers,
wrap-arounds (that the sequence number is incremented from the
maximum possible value to zero) will occur. To prevent this from
interfering with the operation of the protocol, the following
MUST be observed.
The term MAXVALUE designates in the following the largest possible
value for a sequence number.
The sequence number S1 is said to be "greater than" the sequence
number S2 iff:
S1-S2 < MAXVALUE/2 OR
S1 < MAXVALUE/2 AND S2 > S1 + MAXVALUE/2
Thus when comparing two messages, it is possible - even in the
presence of wrap-around - to determine which message contains the
most recent information.
11. 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 RR-3898, 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
skipping to change at page 30, line 28 skipping to change at page 31, line 28
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
Anis Laouiti 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 508832
Email: Anis.Laouiti@inria.fr Email: Anis.Laouiti@inria.fr
Laurent Viennot Laurent Viennot
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 5225
Email: Laurent.Viennot@inria.fr Email: Laurent.Viennot@inria.fr
Thomas Clausen Paul Muhlethaler
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: Thomas.Clausen@inria.fr
Thomas Clausen
Project HIPERCOM
INRIA Rocquencourt
BP 105
78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5133
Email: Thomas.Clausen@inria.fr 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/