draft-ietf-manet-olsr-02.txt   draft-ietf-manet-olsr-03.txt 
INTERNET-DRAFT Philippe Jacquet INTERNET-DRAFT Philippe Jacquet
IETF MANET Working Group Paul Muhlethaler IETF MANET Working Group Paul Muhlethaler
Expiration: 18 January 2001 Amir Qayyum Expiration: 24 May 2001 Amir Qayyum
Anis Laouiti Anis Laouiti
Laurent Viennot Laurent Viennot
Thomas Clausen Thomas Clausen
INRIA Rocquencourt, France INRIA Rocquencourt, France
18 July 2000 24 November 2000
Optimized Link State Routing Protocol Optimized Link State Routing Protocol
draft-ietf-manet-olsr-02.txt draft-ietf-manet-olsr-03.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 2, line 21 skipping to change at page 2, line 21
provides optimal routes (in terms of number of hops). The protocol provides optimal routes (in terms of number of hops). The protocol
is particularly suitable for large and dense networks as the is particularly suitable for large and dense networks as the
technique of multipoint relays works well in this context. technique of multipoint relays works well in this context.
Contents Contents
Status of This Memo 1 Status of This Memo 1
Abstract 1 Abstract 1
1. Introduction 2 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 5
5. Protocol Overview 7 5. Protocol Overview 7
6. Multipoint relays 9 6. Multipoint relays 9
7. Protocol functioning 10 7. Protocol functioning 10
7.1 Packet format 10 7.1 Packet format 10
7.1.1 Packet Header 11 7.1.1 Packet Header 11
7.1.2 Extension Header 12 7.1.2 Message Header 12
7.1.3 Packet Processing 12 7.1.3 Packet Processing 12
7.2 Neighbor sensing 13 7.2 Neighbor sensing 13
7.2.1 HELLO message broadcast 13 7.2.1 HELLO message broadcast 13
7.2.2 HELLO message processing 16 7.2.2 HELLO message processing 16
7.2.3 Link Notification 18
7.3 Multipoint relay selection 19 7.3 Multipoint relay selection 19
7.4 Multipoint relay information declaration 20 7.4 Multipoint relay information declaration 20
7.4.1 TC message broadcast 20 7.4.1 TC message broadcast 20
7.4.2 TC message processing 23 7.4.2 TC message processing 23
7.5 Routing table calculation 25 7.5 Routing table calculation 25
7.6.Link layer notification 27
8. Packet Forwarding 27 8. Packet Forwarding 27
8.1 Data packet forwarding 27 8.1 Data packet forwarding 27
8.2 Topology Control (TC) packet forwarding 27 8.2 OLSR message forwarding 28
9. Proposed values for constants 27 9. Proposed values for constants 28
10. References 28 10. References 29
11. Authors' addresses 29 11. Authors' addresses 30
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
skipping to change at page 3, line 28 skipping to change at page 3, line 28
messages. The protocol uses the multipoint relays to facilitate messages. The protocol uses the multipoint relays 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 multipoint relays are used to form the route from
a given node to any destination in the network. a given node to any destination in the network.
Multipoint relays are selected by a node among its one hop Multipoint relays are selected by a node among its one hop
neighbors with "symmetric", i.e. bi-directional, link. Therefore, neighbors with "symmetric", i.e. bi-directional, link. Therefore,
selecting the route through multipoint relays automatically avoids selecting the route through multipoint relays automatically avoids
the problems associated with data packet transfer on the problems associated with data packet transfer on
uni-directional links (such as the problem of getting the uni-directional links (such as the problem of getting the
acknowledgement for the data packets at each hop) link-layer acknowledgement for the data 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 02 to version 03
- Introduction of assigned port number for use with OLSR
- The packet format now uses "message length" rather than an
offset to the next message
- Optional section describing how link-layer notifications
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
skipping to change at page 4, line 29 skipping to change at page 4, line 34
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 receive from X, "re-transmit" all the broadcast packets that it receives from X,
provided that the same packet is not already received, and the provided that the same packet is not already received, and the
hop count field of the packet is greater than zero. hop count field of the packet is greater than zero.
multipoint relay selector (MPR-S) multipoint relay selector (MPR-S)
A node which has selected its one-hop neighbor, node X, as its A node which has selected its one-hop neighbor, node X, as its
multipoint relay, will be called the multipoint relay selector 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* (not connection) between two neighbor
skipping to change at page 5, line 34 skipping to change at page 5, line 34
almost exclusively between a small specific set of nodes in the almost exclusively between a small specific set of nodes in the
network. The performance of the protocol when comparing to a network. The performance of the protocol when comparing to a
reactive protocol is even better if these [source, destination] reactive protocol is even better if these [source, destination]
pairs change with time [8]. Such changes may initiate substantial pairs change with time [8]. Such changes may initiate substantial
traffic (Query flooding) in case of reactive protocol, but nothing traffic (Query flooding) in case of reactive protocol, but nothing
in OLSR, as the routes are maintained for each known destination in OLSR, as the routes are 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 ?
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. It uses only bi-directional links (like in 802.11), but
these links may be composed of oppositely directed these links may be composed of oppositely directed
uni-directional "connections". uni-directional "connections".
* Does the protocol require the use of tunneling? (if so, how?) * Does the protocol require the use of tunneling? (if so, how?)
No. No.
* Does the protocol require using some form of source routing? (if * Does the protocol require using some form of source routing? (if
so, how?) so, how?)
No. The protocol uses hop-by-hop routing. No. The protocol uses hop-by-hop routing.
* Does the protocol require the use of periodic messaging? (if so, * Does the protocol require the use of periodic messaging? (if so,
how?) how?)
Yes. Periodically, each node in the network send a message Yes. Periodically, each node in the network 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 multipoint relay. This information enables other
nodes to build routes to that node through the multipoint nodes to build routes to that node through the multipoint
relays. relays.
* Does the protocol require the use of reliable or sequenced packet * Does the protocol require the use of reliable or sequenced packet
delivery? (if so, how?) delivery? (if so, how?)
No. As the packets are sent periodically, they need not be sent No. As the packets are sent periodically, they need not be sent
reliably. Each packet not only contains a unique Packet Sequence reliably. Each packet not only contains a unique Packet Sequence
skipping to change at page 7, line 41 skipping to change at page 7, line 41
packets while it is in sleep mode. packets while it is in sleep mode.
* Does the protocol provide some form of security? (if so, how?) * Does the protocol provide some form of security? (if so, how?)
No, not itself. It can use other protocols (like IMEP [4]) which No, not itself. It can use other protocols (like IMEP [4]) which
provide authentication and security. provide authentication and security.
* Does the protocol provide support for utilizing multi-channel, * Does the protocol provide support for utilizing multi-channel,
link-layer technologies? (if so, how?) link-layer technologies? (if so, how?)
Yes. Each interface has a unique IP address. Yes.
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 the 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 packets: rather than
skipping to change at page 9, line 29 skipping to change at page 9, line 29
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 set
is selected such that it covers (in terms of radio range) all the is selected such that it covers (in terms of radio range) all the
nodes that are two hops away. The neighborhood of any node N can be nodes that are two hops away. The neighborhood of any node N can be
defined as the set of nodes which have a symmetric link to N. The defined as the set of nodes which have a symmetric link to N. The
two hop neighborhood of N can be defined as the set of nodes which two hop neighborhood of N can be defined as the set of nodes which
don't have a symmetric link to N but have a symmetric link to the don't have a symmetric link to N but have a symmetric link to the
neighborhood of N. The multipoint relay set of N, denoted as MPR(N), neighborhood of N. The multipoint relay set of N, denoted as MPR(N),
is then an arbitrary subset of the neighborhood of N which is then an arbitrary subset of the neighborhood of N which
satisfies the following condition: every node in the two hop satisfies the following condition: every node in the two hop
neighborhood of N MUST have a symmetric link toward MPR(N). The neighborhood of N must have a symmetric link toward MPR(N). The
smaller the multipoint relay set is, the more optimal is the smaller the multipoint relay set is, the more optimal is the
routing protocol. [2] gives an analysis and example about routing protocol. [2] gives an analysis and example about
multipoint relay selection algorithms. multipoint relay selection algorithms.
Each node 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 Selectors",
which have selected the node as a MPR. A node obtain this which have selected the node as a MPR. A node obtain this
information from the periodic HELLO messages received from the information from the periodic HELLO messages received from the
neighbors. A broadcast message, intended to be diffused in the neighbors. A broadcast message, intended to be diffused in the
whole network, coming from these MPR Selector neighbor nodes is whole network, coming from these MPR Selector neighbor nodes is
skipping to change at page 10, line 27 skipping to change at page 10, line 27
at each hop. at each hop.
7. Protocol Functioning 7. Protocol Functioning
In this section we describe the details of the protocol In this section we describe the details of the protocol
functioning. This includes descriptions of the format and contents functioning. This includes descriptions of the format and contents
of the packets being exchanged by routers, the algorithms (e.g. for of the 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
Packages in OLSR are communicated using UDP. Port 698 has been
assigned by IANA for exclusive usage by the OLSR protocol.
7.1. Packet Format 7.1. 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. Inspired by the concept of "extension
headers" from IPv6, 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. network. The present draft uses IPv4 addresses. The support for
IPv6 will be described in a future draft.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Reserved for future use | | Packet Length | Reserved for future use |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Broadcast | Next Message | | Message Type | Reserved |B| Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: : : :
: MESSAGE : : MESSAGE :
: : : :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Broadcast | Next Message | | Message Type | Reserved |B| Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: : : :
: MESSAGE : : MESSAGE :
: : : :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
(etc) (etc)
7.1.1. Packet Header 7.1.1. Packet Header
Destination Address
The address of the node(s) to receive this packet. This will
often be the broadcast address (i.e. all nodes in the
neighborhood) but may also be the unicast-address of a node.
Source Address
The address of the node which is transmitting this packet. A
packet may contain messages, which originate from other nodes
(see section 7.4). In that case, the message itself MUST contain
an originator address, since the source address of the packet
will be the address of the node retransmitting the message.
Packet Length 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 information in the header of this packet is equivalent to the
information obtainable from the UDP header. information obtainable from the UDP header.
7.1.2. Extension Header 7.1.2. Message Header
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.
Broadcast B
This field indicates to a node whether the message is meant for This field indicates to a node whether the message is meant for
diffusion into the entire network. This enables a node to diffusion into the entire network. This enables a node to
forward messages correctly, even if it doesn't recognize the forward messages correctly, even if it doesn't recognize the
"Message Type". "Message Type".
Next Message Reserved
MUST be set to '0000000' to be in compliance with this
version of the draft.
This field gives the offset where the next "extension header" Message Size
can be found, allowing a node to skip through the messages.
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).
7.1.3. Packet Processing 7.1.3. Packet Processing
Upon receiving such a basic packet, the protocol parser examines Upon receiving such a basic packet, the protocol parser examines
each of the "extension headers". Based on the value of the "Message each of the "extension headers". Based on the value of the "Message
Type" field, the parser can determine the faith of the data portion Type" field, the parser can determine the faith of the data portion
of the message: of the message:
1. If the data are of a type which the receiving node can 1. If the data are of a type which the receiving node can
process, then this data is processed. process, then this data is processed.
2. Otherwise, if the "Message Type" indicates a type, unknown to 2. Otherwise, if the "Message Type" indicates a type, unknown to
the node, the "Broadcast" field MUST be examined. the node, the message SHOULD silently be dropped.
2.1 If the "Broadcast" field indicates that the message is
to be retransmitted (i.e. is set to 'BROADCAST'), and if
the recipient is a MPR of the sender, then the message
MUST be retransmitted by the node.
2.2 Otherwise, the message SHOULD silently be dropped.
By defining a set of message types, which MUST be recognized by all 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 multipoint relay
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 etc.
7.2. Neighbor sensing 7.2. Neighbor sensing
7.2.1. HELLO message broadcast 7.2.1. HELLO message broadcast
Each node MUST 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, containing
information about neighbors and their link status. The link status information about neighbors and their link status. The link status
may either be "symmetric", "heard" (asymmetric) or "MPR". may either be "symmetric", "heard" (asymmetric) or "MPR".
"Symmetric" indicates, that the link has been verified to be "Symmetric" indicates, that the link has been verified to be
bi-directional, i.e. it is possible to transmit data in both 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 is hearing from a
skipping to change at page 14, line 24 skipping to change at page 14, line 20
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 | | Message Sequence Number | MPR Sequence number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Next Link Type | | Link Type | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Address | | Neighbor Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . : : . . . :
: : : :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Type | Reserved | Next Link Type | | 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
skipping to change at page 15, line 19 skipping to change at page 15, line 19
While generating a HELLO message, the node will assign a unique While generating a HELLO message, the node will assign a unique
identification number to this message. This number is put into identification number to this message. This number is put into
the Sequence Number field. This sequence number will be the Sequence Number field. This sequence number will be
different for all the messages originated by that node. 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 multipoint relay set, calculated by the sender node.
Reserved
This field is reserved for future usage, and MUST be set to
00000000 for compliance with this draft.
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").
skipping to change at page 15, line 46 skipping to change at page 15, line 41
- 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 multipoint
relays. 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. been lost. Upon processing a HELLO message, a node silently
ignores link-types, which are unknown.
Reserved
This field is reserved for future usage, and MUST be set to
00000000 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.2.2. HELLO message processing
The HELLO messages permit each node to acquire information about The HELLO messages permit each node to acquire information about
its neighborhood up to two hops. A node maintains a Neighbor table its neighborhood up to two hops. A node maintains a Neighbor table
in which it records the information (obtained from the HELLO in which it records the information (obtained from the HELLO
messages) about its one hop neighbors, the status of the link with messages) about its one hop neighbors, the status of the link with
these neighbors, and a list of two hop neighbors that these one hop these neighbors, a list of two hop neighbors that these one hop
neighbors give access to. The information is recorded in the neighbors give access to, and an associated holding time. The
Neighbor table as a neighbor entry, which may have the following information is recorded in the Neighbor table as a neighbor entry,
format: with the following field names:
N_MPR_seq
1. N_addr N_status N_2hop_list N_time 1. N_addr N_status N_2hop_list N_time
2. N_addr N_status N_2hop_list N_time 2. N_addr N_status N_2hop_list N_time
3. ,, ,, ,, ,, 3. ,, ,, ,, ,,
Each entry in the table consists of N_addr, N_status, N_2hop_list, Each entry in the table consists of N_addr, N_status, N_2hop_list,
and N_time. This specifies that the node with address N_addr is a and N_time. This specifies that the node with address N_addr is a
one-hop neighbor to this node, the status of the link between them one-hop neighbor to this node, the status of the link between them
is N_status, and this neighbor provides access to the two hop is N_status, and this neighbor provides access to the two hop
neighbors listed in N_2hop_list. The N_status can be ASYM_LINK, neighbors listed in N_2hop_list. Each entry in N_2hop_list consists
SYM_LINK or MPR_LINK. A link status of MPR_LINK implies that the of a 2 hop neighbor address and associated holding time. The
link with the neighbor node N_addr is symmetric *AND* the node N_status can be ASYM_LINK, SYM_LINK or MPR_LINK. A link status of
N_addr is selected as a multipoint relay by this node. Each MPR_LINK implies that the link with the neighbor node N_addr is
neighbor entry has an associated holding time N_time, upon symmetric *AND* the node N_addr is selected as a multipoint relay
expiration of which it is no longer valid and hence MUST be by this node. Each neighbor entry has an associated holding time
removed. N_time, upon expiration of which it is no longer valid and hence
MUST be removed.
The neighbor table also contains a sequence number N_MPR_seq. This The node also contains a sequence number N_MPR_seq. This specifies
specifies that the node keeping this neighbor table has selected that the node has selected its most recent MPR set with the
its most recent MPR set with the sequence number N_MPR_seq. Every sequence number N_MPR_seq. Every time a node selects or updates its
time a node selects or updates its multipoint relay set, N_MPR_seq multipoint relay set, N_MPR_seq is incremented to a higher
is incremented to a higher value. This number is put into the HELLO value. This number is put into the HELLO messages as described in
messages as described in 6.2.1. 6.2.1.
Upon receiving a HELLO message, the node updates the neighbor entry Upon receiving a HELLO message, the node should update the
corresponding to the sender node address: neighbor entry corresponding to the sender node address (a node
may - e.g. for security reasons - wish to restrict updating the
neighbor-table, i.e. ignoring HELLO messages from some nodes):
1. If the entry already exists: 1. If the entry already exists:
1.1 the holding time of the entry is refreshed to 1.1 if the recipient of the HELLO has recorded the sender as
NEIGHB_HOLD_TIME asymetric:
1.2 if the node finds its own address among the addresses
listed in the HELLO message, it updates the status of the
link to the sender node as SYM_LINK if it was ASYM_LINK
before.
1.3 the N_2hop_list of the entry is updated to reflect the 1.1.1 if the node finds its own address among the
contents of the HELLO-message. addresses listed in the HELLO message (with Link
Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates
the status of the link to the sender node as
SYM_LINK and refreshes the N_time to
NEIGHB_HOLDING_TIME.
1.1.2 otherwise, if the node does not find its own
address among the addresses listed in the HELLO
message, it refreshes the N_time to
NEIGHB_HOLDING_TIME.
1.2 otherwise, if the recipient of the HELLO has recorded
the sender as symetric (or MPR):
1.2.1 if the node finds its own address among the addresses
listed in the HELLO message (with Link Type
ASYM_LINK, SYM_LINK or MPR_LINK), it refreshes the
N_time to NEIGHB_HOLDING_TIME.
2. Otherwise, a new entry is recorded in the Neighbor table with: 2. Otherwise, a new entry is recorded in the Neighbor table with:
2.1 N_addr is set to the address of the sender node - N_addr is set to the address of the sender node,
2.2 N_status is set to the value of ASYM_LINK (asymmetric - N_status is set to the value of SYM_LINK if the node
link) finds its own address (with Link Type ASYM_LINK, SYM_LINK
or MPR_LINK) among the addresses listed in the HELLO
message, and to the value of ASYM_LINK otherwise
2.3 N_2hop_list is filled with the list of addresses - N_time is set to the value of NEIGHB_HOLD_TIME
contained in the HELLO message which have a link type of
SYM_LINK or MPR_LINK, and which are not already present
in the Neighbor table (i.e., they are not one-hop
neighbors).
If a node finds its own address in a HELLO message with a The N_2hop_list of the entry of the sender is updated, as
link type of ASYM_LINK, SYM_LINK or MPR_LINK, it does not follows. For each address listed in the HELLO message with Link
register itself in the N_2hop_list. Rather, it changes Type SYM_LINK or MPR_LINK:
the link status to the sender of the HELLO from ASYM_LINK
to SYM_LINK.
2.4 N_time is set to the value of NEIGHB_HOLD_TIME 1. if an entry with this address exists in the N_2hop_list, then
the associated holding time is refreshed to NEIGHB_HOLD_TIME
2. otherwise an entry with this address and holding time
NEIGHB_HOLD_TIME is added to the N_2hop_list.
Based on the information obtained from the HELLO messages, each Based on the information obtained from the HELLO messages, each
node construct its MPR Selector table. In this table, the node node construct its MPR Selector table. In this table, the node
registers the addresses of those one hop neighbor nodes which have registers the addresses of those one hop neighbor nodes which have
selected the node as a multipoint relay. The MPR Selector table may selected the node as a multipoint relay. The MPR Selector table may
have the following format: have the following format:
MSSN
1. MS_addr MS_seq_num MS_time 1. MS_addr MS_seq_num MS_time
2. MS_addr MS_seq_num MS_time 2. MS_addr MS_seq_num MS_time
3. ,, ,, ,, 3. ,, ,, ,,
Each entry in the table consists of MS_addr, MS_seq_num and Each entry in the table consists of MS_addr, MS_seq_num and
MS_time, which specifies that the node with address MS_addr has MS_time, which specifies that the node with address MS_addr has
selected this node as its multipoint relay with the MPR sequence selected this node as its multipoint relay with the MPR sequence
number equal to MS_seq_num. Each entry has an associated holding number equal to MS_seq_num. Each entry has an associated holding
time MS_time, upon expiation of which it is no longer valid and time MS_time, upon expiation of which it is no longer valid and
hence removed. hence removed.
A sequence number, MSSN, is associated with this table. This number A sequence number, MSSN, is associated with this table. This number
specifies that the multipoint relay selector set of the node specifies that the multipoint relay selector set of the node
keeping this MPR Selector table is most recently modified with the keeping this MPR Selector table is most recently modified with the
sequence number MSSN. The node modifies its MPR Selector set sequence number MSSN. The node modifies its MPR Selector set
according to the information it receives in the HELLO messages, and according to the information it receives in the HELLO messages, and
increment this sequence number upon each modification. increment this sequence number upon each modification.
Upon receiving a HELLO message, if a node finds its own address in Upon receiving a HELLO message, if a node finds its own address in
the the address list with a link type of "MPR", it MUST update the the address list with a link type of "MPR", it MUST update the
entry corresponding to the sender node's address in the MPR entry corresponding to the sender node's address in the MPR
Selector table: Selector table:
1. If the entry already exists: 1. If the entry already exists:
1.1 if the MPR Sequence Number field of the HELLO message is 1.1 if the MPR Sequence Number field of the HELLO message is
greater than or equal to the MS_seq_num field of the greater than or equal to the MS_seq_num field of the
entry in the table, then the MS_time is refreshed to entry in the table, then the MS_time is refreshed to
NEIGHB_HOLD_TIME. NEIGHB_HOLD_TIME.
skipping to change at page 18, line 40 skipping to change at page 18, line 40
with: with:
2.1 MS_addr is set to the address of sender of the HELLO 2.1 MS_addr is set to the address of sender of the HELLO
message message
2.2 MS_seq_num is set to the MPR Sequence Number field of the 2.2 MS_seq_num is set to the MPR Sequence Number field of the
HELLO message HELLO message
2.3 MS_time is set to the value of NEIGHB_HOLD_TIME 2.3 MS_time is set to the value of NEIGHB_HOLD_TIME
7.2.3. Link Notification 2.4 MSSN is incremented 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 SHOULD 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.
7.3. Multipoint relay selection 7.3. 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 multipoint relays. Multipoint relays are used to flood the control
messages of that node into the network. The MPR set is calculated messages of that node into the network. The MPR set is calculated
in a way such that it contains a subset of one hop neighbors which in a way such that it contains a subset of one hop neighbors which
covers all the two hop neighbors. This means, that the union of the covers all the two hop neighbors. This means, that the union of the
neighbor sets of all MPRs contains the entire two hop neighbor neighbor sets of all MPRs contains the entire two hop neighbor
set. In order to build the list of the two hop nodes from a given set. In order to build the list of the two hop nodes, make the
node, it suffices to track the list of symmetric link nodes found union of N_2hop_lists of all neighbors (with Link Type SYM_LINK or
in the HELLO messages received by this node (this two-hop neighbor MPR_LINK), then remove from this union the one-hop neighbors (with
information is recorded in the neighbor table as Link Type SYM_LINK or MPR_LINK), and finally remove the node
N_2hop_list). Multipoint relays of a given node are declared in the itself. Multipoint relays of a given node are declared in the
subsequent HELLOs transmitted by this node, so that the information subsequent HELLOs transmitted by this node, so that the information
reaches the multipoint relays themselves. These selected multipoint reaches the multipoint relays themselves. These selected multipoint
relays are indicated in the HELLO messages with a link status of relays are indicated in the HELLO messages with a link status of
"MPR". The multipoint relay set is re-calculated when: "MPR". The multipoint relay set is re-calculated when:
- a change in the neighborhood is detected, i.e. either a - a change in the neighborhood is detected, i.e. either a
symmetric link with a neighbor is failed, or a new neighbor symmetric link with a neighbor is failed, or a new neighbor
with a symmetric link is added; or with a symmetric link is added; or
- a change is detected in the two-hop neighborhood such that - a change is detected in the two-hop neighborhood such that
a symmetric link is either detected or broken between a a symmetric link is either detected or broken between a
skipping to change at page 20, line 12 skipping to change at page 20, line 12
N(x): One hop neighbor set of node x (containing only symmetric N(x): One hop neighbor set of node x (containing only symmetric
neighbors) neighbors)
N2(x): Two hop neighbor set of node x (containing only symmetric N2(x): Two hop neighbor set of node x (containing only symmetric
neighbors of nodes in N(x) ). The two hop neighbor set neighbors of nodes in N(x) ). The two hop neighbor set
N2(x) of node x does not contain any one hop neighbor of N2(x) of node x does not contain any one hop neighbor of
node x node x
D(x,y): Degree of one hop neighbor node y (where y is a member D(x,y): Degree of one hop neighbor node y (where y is a member
of N(x) ), is defined as the number of symmetric one hop of N(x) ), is defined as the number of symmetric one hop
neighbors of node y EXCLUDING the node x and all the neighbors of node y EXCLUDING the node x and all the
symmetric one hop neighbors of node x which exit also symmetric one hop neighbors of node x, i.e.,
in N(y), i.e., D(x,y) = number of elements of N(y) - {x} - N(x)
D(x,y) = N(y) - x - N(x)
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(x)
2. Calculate D(x,y), where y is a member of N(x), for all nodes 2. Calculate D(x,y), where y is a member of N(x), for all nodes
in N(x) in N(x)
3. First select as MPRs those nodes in N(x) which provide the 3. First select as MPRs those nodes in N(x) which provide the
"only path" to reach some nodes in N2(x) "only path" to reach some nodes in N2(x)
4. While there still exist some nodes in N2(x) that are not 4. While there still exist some nodes in N2(x) that are not
covered by MPR(x): 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(x), calculate the number of nodes in
N2(x) which are not yet covered by MPR(x) and are N2(x) which are not yet covered by MPR(x) and are
reachable through this one hop neighbor; reachable through this one hop neighbor;
4.2 Select as a MPR that node of N(x) which reaches the 4.2 Select as a MPR that node of N(x) which reaches the
maximum number of uncovered nodes in N2(x). In case of a maximum number of uncovered nodes in N2(x). In case of a
tie, select that node as MPR whose D(x,y) is greater. tie, select that node as MPR whose D(x,y) is greater.
5. To optimize, remove each node in MPR(x), one at a time, and 5. To optimize, process each node y in MPR(x), one at a time, and
check if MPR(x) still covers all nodes in N2(x) if MPR(x) - {y} still covers all nodes in N2(x) then remove y from
MPR(x)
After selecting the multipoint relays among the neighbors, the link After selecting the multipoint relays among the neighbors, the link
status of the corresponding one hop neighbors is changed from status of the corresponding one hop neighbors is changed from
SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in
the Neighbor table is also incremented by one. the Neighbor table is also incremented by one.
7.4. Multipoint relay information declaration 7.4. Multipoint relay information declaration
7.4.1. TC Message Broadcast 7.4.1. TC Message Broadcast
skipping to change at page 21, line 26 skipping to change at page 21, line 26
messages describing a nodes MPR selector set MUST be complete messages describing a nodes MPR selector set MUST be complete
within a certain refreshing period (TC_INTERVAL). The information within a certain refreshing period (TC_INTERVAL). The information
diffused in the network by these TC messages will help each node to diffused in the network by these TC messages will help each node to
calculate its routing table. A node which has an empty MPR Selector calculate its routing table. A node which has an empty MPR Selector
set, i.e. nobody has selected it as a multipoint relay, MUST NOT set, i.e. nobody has selected it as a multipoint relay, 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 MAY 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 | | Message Sequence Number | MSSN |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Count | Unused | | Hop Count | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Multipoint Relay Selector Address | | Multipoint Relay Selector Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... | | ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 22, line 35 skipping to change at page 22, line 35
the multipoint relay selectors of the originator node is more the multipoint relay selectors of the originator node is more
recent than what it already has. recent than what it already has.
Hop Count Hop Count
This field will contain the maximum number of hops a TC message This field will contain the maximum number of hops a TC message
can attain. Every time a TC message is re-transmitted, this can attain. Every time a TC message is re-transmitted, this
field is decremented by 1. When this field reaches zero, the TC field is decremented by 1. When this field reaches zero, the TC
message is no more re-transmitted and is discarded. message is no more re-transmitted and is discarded.
Reserved
This field is reserved for future usage, and MUST be set to
'000000000000000000000000' for compliance with this draft.
Originator Address Originator Address
This field contains the address of the node, which has This field contains the address of the node, which has
originally generated this TC message. This field MUST not be originally generated this TC message. This field MUST not be
confused with the Source Address field, which is changed each confused with the source read in the UDP header, which is
time to the address of the intermediate node which is changed each time to the address of the intermediate node which
"re-transmitting" this TC message. The Originator Address field is "re-transmitting" this TC message. The Originator Address
is *never* changed in the retransmissions. field is *never* changed in the retransmissions.
Multipoint Relay Selector Address (MPR-S) Multipoint Relay Selector Address (MPR-S)
This field contains the address of a node, which has selected This field contains the address of a node, which has selected
the Originator node (of the TC message) as a multipoint relay. the Originator node (of the TC message) as a multipoint relay.
All addresses of the multipoint relay selectors of the All addresses of the multipoint relay selectors of the
Originator node are put in the TC message. If the maximum Originator node are put in the TC message. If the maximum
allowed message size (as imposed by the network) is reached allowed message size (as imposed by the network) is reached
while there are still multipoint relay selector addresses which while there are still multipoint relay selector addresses which
which have not been inserted into the TC-message, more TC which have not been inserted into the TC-message, more TC
skipping to change at page 23, line 28 skipping to change at page 23, line 28
information is recorded in the Duplicate table as Duplicate information is recorded in the Duplicate table as Duplicate
entries. entries.
The table may have the following format: The table may have the following format:
1. D_addr D_seq_num D_time 1. D_addr D_seq_num D_time
2. D_addr D_seq_num D_time 2. D_addr D_seq_num D_time
3. ,, ,, ,, 3. ,, ,, ,,
Each entry in the table consists of D_addr, D_seq_num and D_time, Each entry in the table consists of D_addr, D_seq_num and D_time,
which specifies that a TC message was received from the node with which specifies that a TC message was received, originating from
address D_addr, having the message sequence number as D-seq_num. the node with address D_addr, having the message sequence number
Each Duplicate entry also has an associated holding time D_time, as D-seq_num. Each Duplicate entry also has an associated holding
upon expiration of which it is no longer valid and hence MUST be time D_time, upon expiration of which it is no longer valid and
removed. hence MUST be removed.
Upon receiving a TC message, a node checks in its Duplicate table Upon receiving a TC message, a node checks in its Duplicate table
to see if it has already received the same message. If it finds a to see if it has already received the same message. If it finds a
corresponding entry, the message is discarded. Otherwise, a new corresponding entry, the message is discarded. Otherwise, a new
entry is recorded in the Duplicate table for this newly received TC entry is recorded in the Duplicate table for this newly received TC
message, and the message is processed. When a node receives a 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 message from a neighbor node with which it has an asymmetric (or
uni-directional) link, it neither registers the message in the uni-directional) link, it neither registers the message in the
Duplicate table nor it processes the message. Duplicate table nor it processes the message.
skipping to change at page 24, line 21 skipping to change at page 24, line 21
T_last as a multipoint relay and that the node T_last has announced T_last as a multipoint relay and that the node T_last has announced
this information of its multipoint relay selector set with the this information of its multipoint relay selector set with the
sequence number T_seq. Therefore, the node T_dest can be reached in sequence number T_seq. Therefore, the node T_dest can be reached in
the last hop through the node T_last. Each topology entry has an the last hop through the node T_last. Each topology entry has an
associated holding time T_time, upon expiration of which it is no associated holding time T_time, upon expiration of which it is no
longer valid and hence MUST be removed. longer valid and hence MUST be removed.
The entries in the topology table are recorded with the topology The entries in the topology table are recorded with the topology
information that is exchanged through TC messages. information that is exchanged through TC messages.
Upon receiving After registering a TC message in the duplicate table, the following
a TC message, the following procedure is executed to record the procedure is executed to record the information in the topology
information in the topology table: table:
1. If there exist some entry in the topology table whose T_last 1. If there exist some entry in the topology table whose T_last
corresponds to the originator address of the TC message and corresponds to the originator address of the TC message and
whose T_seq is greater in value than the MSSN in the received whose T_seq is greater in value than the MSSN in the received
message, then no further processing of this TC message is message, then no further processing of this TC message is
performed and it is silently discarded (case: message performed and it is silently discarded (case: message
received out of order). received out of order).
2. If there exist some entry in the topology table whose T_last 2. All entries in the topology table with T_last corresponding
corresponds to the originator address of the TC message and to the originator address of the TC message and whose T_seq
whose T_seq is lesser in value than the MSSN in the received is lesser in value than the MSSN in the received message,
message, then that topology entry is removed. are removed.
3. For each of the MPR Selector address received in the TC 3. For each of the MPR Selector address received in the TC
message: message:
3.1 If there exist some entry in the topology table whose 3.1 If there exist some entry in the topology table whose
T_dest corresponds to the MPR Selector address and the T_dest corresponds to the MPR Selector address and the
T_last corresponds to the originator address of the TC T_last corresponds to the originator address of the TC
message, then the holding time T_time of that topology message, then the holding time T_time of that topology
entry is refreshed to TOP_HOLD_TIME. entry is refreshed to TOP_HOLD_TIME.
3.2 Otherwise, a new topology entry is recorded in the 3.2 Otherwise, a new topology entry is recorded in the
topology table whereas: topology table where:
- T_dest is set to the MPR Selector address, - T_dest is set to this MPR Selector address,
- T_last is set to the originator address of the TC - T_last is set to the originator address of the TC
message, message,
- T_seq is set to the value of MSSN received in the TC - T_seq is set to the value of MSSN received in the TC
message, message,
- T_time is set to the value of TOP_HOLD_TIME. - T_time is set to the value of TOP_HOLD_TIME.
7.5. Routing table calculation 7.5. Routing table calculation
Each node maintains a routing table which allows it to route the Each node maintains a routing table which allows it to route the
messages for the other destinations in the network. The nodes which messages for the other destinations in the network. The routing
receive TC messages parse and store some of the connected pairs of table is based on the information contained in the neighbor table
form [node, source] where "nodes" are identified with the addresses and the topology table. Therefore, if any of these tables is
found in the TC message. The routing table is built from this changed, the routing table is re-calculated to update the route
database by tracking the connected pairs in a descending order. To information about each destination in the network. The route
find a path from a given origin to a remote node R, one has to find
a connected pair (R,X), then a connected pair (X,Y), and so forth
until one finds a node Y in the neighbor set of the origin. In
order to restrict to optimal paths, the relay nodes will consider
only the connected pairs on the minimal path. This selection can be
done dynamically and with minimal storage facilities. The sequence
numbers are used to detect connected pairs which have been
invalidated by further topology changes. The information contained
in the topology database, which has not been refreshed is
discarded.
The routing table is based on the information contained in the
neighbor table and the topology table. Therefore, if any of these
tables is changed, the routing table is re-calculated to update the
route information about each destination in the network. The route
entries are recorded in the routing table in the following format: 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 This routing table information is updated when a change is detected
- a change in the neighborhood is detected concerning a in the neighbor table, or the topology table. The update
symmetric link; of this routing table does not generate or trigger any messages to
- a route to any destination is expired (because the be transmitted, neither in the network, nor in the one-hop
corresponding topology entry is expired) or neighborhood.
- a better (e.g. shorter) route is found for a destination.
Therefore, the routing table is re-calculated locally each time the To construct the routing table of node X, a shortest path algorithm
neighbor table or the topology table (or both) are changed. The is run on the directed graph containing the arcs X -> Y where Y is any
update of this routing table does not generate or trigger any one hop neighbor of X (with Link Type SYM_LINK or MPR_LINK) and the
messages to be transmitted, neither in the network, nor in the arcs U -> V where there exists an entry in the topology table with
one-hop neighborhood. V as T_dest and U as T_last.
The following procedure is executed to calculate (or re-calculate) The following procedure is given as an example to calculate (or
the routing table : re-calculate) the routing table :
1. All the entries of the routing table are removed. 1. All the entries of the routing table are removed.
2. The new entries are recorded in the table starting with the one 2. The new entries are recorded in the table starting with the one
hop neighbors (h=1) as the destination nodes. For each neighbor hop neighbors (h=1) as the destination nodes. For each neighbor
entry in the neighbor table, whose link status is not entry in the neighbor table, whose Link Type is SYM_LINK or
asymmetric, a new route entry is recorded in the routing table MPR_LINK, a new route 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. Then 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.
4. After calculating the routing table, the topology table entries 7.6 Link layer notification
which are not used in calculating the routes MUST be removed, if
there is a need to save memory space. Otherwise, these entries OLSR is designed to operate entirely alone, i.e. does not impose or
may provide multiple routes. expect any specific information from the link layer. However, if
information from the link-layer is available, a node MAY use this
as described in this section.
If link layer information describing connectivity to neighboring
nodes is available (i.e. loss of connectivity such as through
absence of a link layer acknowledgment), this information is
used in addition to the information from the HELLO-messages to
maintain the neighbor table and the MPR selector
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
between a node and any neighbor is broken, the following actions
are taken:
1. if the link is broken to either a symetric or asymetric
neighbor, the entry for that neighbor is removed from the
neighbor table,
2. if the link is broken to a neighbor, which is selected as MPR,
the entry for that neighbor is removed from the neighbor
table and the MPR set is recalculated,
3. if the link is broken to a neighbor, which has selected this
node as MPR, the Multipoint Selector Set is updated and a
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 Data packets are relayed on a hop by hop basis. In the source
router and in any intermediate router, the next hop router is router and in any intermediate router, the next hop router is
identified by the entry of the destination in the host routing identified by the entry of the destination in the host routing
table. table.
Whenever a data packet is received to route to a destination and Whenever a data packet is received to route to a destination and
its TTL field (in IP header) is greater than zero, the node MUST its TTL field (in IP header) is greater than zero, the node MUST
examine the final destination field in the packet. If the route is examine the final destination field in the packet. If the route is
known, i.e. an entry is found in the routing table in which R_dest known, i.e. an entry is found in the routing table in which R_dest
corresponds to the final destination, then the packet is corresponds to the final destination, then the packet is
transmitted to the next hop node. While forwarding a unicast transmitted to the next hop node.
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 (TC) packet forwarding 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.
TC packets are relayed by the multipoint relays via the following 8.2. Topology Control message forwarding
rule:
A node retransmits a TC packet only when it receives its first TC messages are relayed by the multipoint relays via the
copy from a node which is its multipoint relay selector. following rule:
When a TC packet is received with a hop count is greater than zero, A node retransmits a TC message only when it is received from
then it is retransmitted by the multipoint relays of the sender one of its multipoint relay selector AND it is registered in the
node. Before retransmitting, the hop count is decremented by one. duplicate table for the first time AND the hop count is greater
than zero.
Before retransmitting, the hop count 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 TC_MIN_INTERVAL = 2 seconds
NEIGHB_HOLD_TIME = 6 seconds NEIGHB_HOLD_TIME = 6 seconds
TOP_HOLD_TIME = 15 seconds TOP_HOLD_TIME = 15 seconds
D_TIME = 30 seconds
HELLO_PACKET = 1 HELLO_PACKET = 1
TC_PACKET = 2 TC_PACKET = 2
ASYM_LINK = 1 ASYM_LINK = 1
SYM_LINK = 2 SYM_LINK = 2
MPR_LINK = 3 MPR_LINK = 3
10. References 10. References
1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing
 End of changes. 

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