draft-ietf-manet-olsrv2-00.txt   draft-ietf-manet-olsrv2-01.txt 
Mobile Ad hoc Networking (MANET) T. Clausen Mobile Ad hoc Networking (MANET) T. Clausen
Internet-Draft LIX, Ecole Polytechnique, France Internet-Draft LIX, Ecole Polytechnique, France
Expires: February 2, 2006 August 2005 Expires: September 7, 2006 C. Dearlove
BAE Systems Advanced Technology
Centre
The OLSRv2 Design Team
MANET Working Group
March 6, 2006
The Optimized Link-State Routing Protocol version 2 The Optimized Link-State Routing Protocol version 2
draft-ietf-manet-olsrv2-00 draft-ietf-manet-olsrv2-01
Status of this Memo Status of this Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
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
skipping to change at page 1, line 33 skipping to change at page 1, line 38
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on February 2, 2006. This Internet-Draft will expire on September 7, 2006.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2005). Copyright (C) The Internet Society (2006).
Abstract Abstract
This document describes version 2 of the Optimized Link State Routing This document describes version 2 of the Optimized Link State Routing
(OLSRv2) protocol for mobile ad hoc networks. The protocol is an (OLSRv2) protocol for mobile ad hoc networks. The protocol is an
optimization of the classical link state algorithm tailored to the optimization of the classical link state algorithm tailored to the
requirements of a mobile wireless LAN. requirements of a mobile wireless LAN.
The key optimization of OLSRv2 is that of multipoint relays, The key optimization of OLSRv2 is that of multipoint relays,
providing an efficient mechanism for network-wide broadcast of link- providing an efficient mechanism for network-wide broadcast of link-
skipping to change at page 3, line 10 skipping to change at page 3, line 10
management. management.
OLSRv2 is particularly suitable for large and dense networks as the OLSRv2 is particularly suitable for large and dense networks as the
technique of MPRs works well in this context. technique of MPRs works well in this context.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Applicability Statement . . . . . . . . . . . . . . . . . 7 1.2 Applicability Statement . . . . . . . . . . . . . . . . . 7
2. Protocol Overview and Functioning . . . . . . . . . . . . . . 8 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 9
3. OLSRv2 Signaling Framework . . . . . . . . . . . . . . . . . . 11 2.1 Protocol Extensibility . . . . . . . . . . . . . . . . . . 11
3.1 OLSRv2 Packet Format . . . . . . . . . . . . . . . . . . . 11 3. Processing and Forwarding Repositories . . . . . . . . . . . . 13
3.2 OLSR Messages . . . . . . . . . . . . . . . . . . . . . . 12 3.1 Received Message Set . . . . . . . . . . . . . . . . . . . 13
3.2.1 Address Blocks . . . . . . . . . . . . . . . . . . . . 13 3.2 Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.2 TLVs . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Processed Set . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Message Content Fragmentation . . . . . . . . . . . . . . 15 3.4 Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 14
4. Packet Processing and Message Forwarding . . . . . . . . . . . 17 3.5 Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 14
4.1 Processing and Forwarding Repositories . . . . . . . . . . 17 4. Packet Processing and Message Forwarding . . . . . . . . . . . 16
4.1.1 Received Message Set . . . . . . . . . . . . . . . . . 17 4.1 Actions when Receiving an OLSRv2 Packet . . . . . . . . . 16
4.1.2 Processed Set . . . . . . . . . . . . . . . . . . . . 17 4.2 Actions when Receiving an OLSRv2 Message . . . . . . . . . 16
4.1.3 Forwarded Set . . . . . . . . . . . . . . . . . . . . 18 4.3 Message Considered for Processing . . . . . . . . . . . . 16
4.1.4 Relay Set . . . . . . . . . . . . . . . . . . . . . . 18 4.4 Message Considered for Forwarding . . . . . . . . . . . . 18
4.2 Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 18 5. Information Repositories . . . . . . . . . . . . . . . . . . . 21
4.3 Actions when Receiving an OLSRv2-Packet . . . . . . . . . 19 5.1 Neighborhood Information Base . . . . . . . . . . . . . . 21
4.4 Actions when Receiving an OLSRv2-Message . . . . . . . . . 19 5.1.1 Link Set . . . . . . . . . . . . . . . . . . . . . . . 21
4.5 Message Considered for Processing . . . . . . . . . . . . 20 5.1.2 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . 22
4.6 Message Considered for Forwarding . . . . . . . . . . . . 21 5.1.3 Neighborhood Address Association Set . . . . . . . . . 23
5. Information Repositories . . . . . . . . . . . . . . . . . . . 23 5.1.4 MPR Set . . . . . . . . . . . . . . . . . . . . . . . 23
5.1 Local Link Information Base . . . . . . . . . . . . . . . 23 5.1.5 MPR Selector Set . . . . . . . . . . . . . . . . . . . 23
5.1.1 Link Set . . . . . . . . . . . . . . . . . . . . . . . 23 5.1.6 Advertised Neighbor Set . . . . . . . . . . . . . . . 23
5.1.2 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 24 5.2 Topology Information Base . . . . . . . . . . . . . . . . 24
5.1.3 Neighborhood Address Association Set . . . . . . . . . 24 5.2.1 Topology Set . . . . . . . . . . . . . . . . . . . . . 24
5.1.4 MPR Set . . . . . . . . . . . . . . . . . . . . . . . 24 5.2.2 Attached Network Set . . . . . . . . . . . . . . . . . 24
5.1.5 Advertised Neighbor Set . . . . . . . . . . . . . . . 25 5.2.3 Routing Set . . . . . . . . . . . . . . . . . . . . . 25
5.2 Topology Information Base . . . . . . . . . . . . . . . . 25 6. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 26
6. OLSRv2 Control Messages . . . . . . . . . . . . . . . . . . . 26 6.1 General OLSRv2 Message TLVs . . . . . . . . . . . . . . . 26
6.1 HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 26 6.1.1 VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 26
6.2 TC Messages . . . . . . . . . . . . . . . . . . . . . . . 26 6.1.2 INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 27
6.3 MA Messages . . . . . . . . . . . . . . . . . . . . . . . 26 6.2 Local Interface Blocks . . . . . . . . . . . . . . . . . . 28
7. Populating the MPR Set . . . . . . . . . . . . . . . . . . . . 27 6.3 HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 28
8. Populating the Advertised Neighbor Set . . . . . . . . . . . . 28 6.3.1 HELLO Message: Message TLVs . . . . . . . . . . . . . 29
9. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 29 6.3.2 HELLO Message: Address Blocks TLVs . . . . . . . . . . 29
9.1 HELLO Message: Message TLVs . . . . . . . . . . . . . . . 29 6.4 TC Messages . . . . . . . . . . . . . . . . . . . . . . . 30
9.2 HELLO Message: Address Blocks and Address TLVs . . . . . . 29 7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 31
10. HELLO Message Processing . . . . . . . . . . . . . . . . . . 31 7.1 HELLO Message: Transmission . . . . . . . . . . . . . . . 33
10.1 Populating the Link Set . . . . . . . . . . . . . . . . . 31 8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 34
10.2 Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 33 8.1 Populating the Link Set . . . . . . . . . . . . . . . . . 34
10.3 Populating the Relay Set . . . . . . . . . . . . . . . . . 34 8.2 Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 36
10.4 Neighborhood and 2-hop Neighborhood Changes . . . . . . . 34 8.3 Populating the MPR Selector Set . . . . . . . . . . . . . 37
11. TC Message Generation . . . . . . . . . . . . . . . . . . . 36 8.4 Neighborhood and 2-Hop Neighborhood Changes . . . . . . . 38
11.1 TC Message: Message TLVs . . . . . . . . . . . . . . . . . 36 9. TC Message Generation . . . . . . . . . . . . . . . . . . . . 40
11.2 TC Message: Address Blocks and Address TLVs . . . . . . . 36 9.1 TC Message: Transmission . . . . . . . . . . . . . . . . . 41
12. TC Message Processing . . . . . . . . . . . . . . . . . . . 37 10. TC Message Processing . . . . . . . . . . . . . . . . . . . 42
13. MA Message Generation . . . . . . . . . . . . . . . . . . . 39 10.1 Checking Freshness & Validity of a TC message . . . . . . 42
14. MA Message Processing . . . . . . . . . . . . . . . . . . . 40 10.2 Updating the Topology Set . . . . . . . . . . . . . . . . 43
15. Routing Table Calculation . . . . . . . . . . . . . . . . . 41 10.3 Purging Old Entries from the Topology Set . . . . . . . . 44
16. Proposed Values for Constants . . . . . . . . . . . . . . . 44 10.4 Updating the Attached Networks Set . . . . . . . . . . . . 44
16.1 Message Types . . . . . . . . . . . . . . . . . . . . . . 44 10.5 Purging Old Entries from the Attached Network Set . . . . 45
16.2 Message Intervals . . . . . . . . . . . . . . . . . . . . 44 10.6 Processing Unfragmented TC Messages . . . . . . . . . . . 45
16.3 Holding Times . . . . . . . . . . . . . . . . . . . . . . 44 10.7 Processing Partially or Wholly Self-Contained
16.4 Willingness . . . . . . . . . . . . . . . . . . . . . . . 44 Fragmented TC Messagess . . . . . . . . . . . . . . . . . 45
17. Representing Time . . . . . . . . . . . . . . . . . . . . . 45 11. Populating the MPR Set . . . . . . . . . . . . . . . . . . . 47
18. IANA Considerations . . . . . . . . . . . . . . . . . . . . 46 12. Populating Derived Sets . . . . . . . . . . . . . . . . . . 48
A. Example Heuristic for Calculating MPRs . . . . . . . . . . . . 47 12.1 Populating the Relay Set . . . . . . . . . . . . . . . . . 48
B. Example Algorithms for Generating Control Traffic . . . . . . 50 12.2 Populating the Advertised Neighbor Set . . . . . . . . . . 48
B.1 Example Algorithm for Generating HELLO messages . . . . . 50 13. Populating the Neighborhood Address Association Set . . . . 49
B.2 Example Algorithm for Generating TC messages . . . . . . . 51 14. Routing Table Calculation . . . . . . . . . . . . . . . . . 50
C. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 53 15. Proposed Values for Constants . . . . . . . . . . . . . . . 53
D. OLSRv2 Packet and Message Layout . . . . . . . . . . . . . . . 54 15.1 Message Intervals . . . . . . . . . . . . . . . . . . . . 53
D.1 General OLSR Packet Format . . . . . . . . . . . . . . . . 54 15.2 Holding Times . . . . . . . . . . . . . . . . . . . . . . 53
D.1.1 Message TLVs . . . . . . . . . . . . . . . . . . . . . 55 15.3 Willingness . . . . . . . . . . . . . . . . . . . . . . . 53
D.1.2 Address Block . . . . . . . . . . . . . . . . . . . . 55 15.4 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
D.1.3 Address Block TLV . . . . . . . . . . . . . . . . . . 57 16. Representing Time . . . . . . . . . . . . . . . . . . . . . 55
D.2 Layout of OLSRv2 Specified Messages . . . . . . . . . . . 57 17. IANA Considerations . . . . . . . . . . . . . . . . . . . . 56
D.2.1 Layout of HELLO Messages . . . . . . . . . . . . . . . 58 17.1 Multicast Addresses . . . . . . . . . . . . . . . . . . . 56
D.2.2 Layout of TC messages . . . . . . . . . . . . . . . . 58 17.2 Message Types . . . . . . . . . . . . . . . . . . . . . . 56
E. Node Configuration . . . . . . . . . . . . . . . . . . . . . . 60 17.3 TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 56
E.1 IPv6 Specific Considerations . . . . . . . . . . . . . . . 60 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 57
F. Security Considerations . . . . . . . . . . . . . . . . . . . 61 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 58
F.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . 61 A. Example Heuristic for Calculating MPRs . . . . . . . . . . . . 59
F.2 Integrity . . . . . . . . . . . . . . . . . . . . . . . . 61 B. Example Algorithms for Generating Control Traffic . . . . . . 62
F.3 Interaction with External Routing Domains . . . . . . . . 62 B.1 Example Algorithm for Generating HELLO messages . . . . . 62
F.4 Node Identity . . . . . . . . . . . . . . . . . . . . . . 63 B.2 Example Algorithm for Generating TC messages . . . . . . . 63
G. Flow and Congestion Control . . . . . . . . . . . . . . . . . 64 C. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 65
H. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 65 D. Packet and Message Layout . . . . . . . . . . . . . . . . . . 66
I. References . . . . . . . . . . . . . . . . . . . . . . . . . . 66 D.1 OLSRv2 Packet Format . . . . . . . . . . . . . . . . . . . 66
J. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 67 E. Node Configuration . . . . . . . . . . . . . . . . . . . . . . 73
K. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 68 F. Security Considerations . . . . . . . . . . . . . . . . . . . 74
Author's Address . . . . . . . . . . . . . . . . . . . . . . . 68 F.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . 74
Intellectual Property and Copyright Statements . . . . . . . . 69 F.2 Integrity . . . . . . . . . . . . . . . . . . . . . . . . 74
F.3 Interaction with External Routing Domains . . . . . . . . 75
F.4 Node Identity . . . . . . . . . . . . . . . . . . . . . . 76
G. Flow and Congestion Control . . . . . . . . . . . . . . . . . 77
H. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 78
I. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 79
J. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 80
Intellectual Property and Copyright Statements . . . . . . . . 81
1. Introduction 1. Introduction
The Optimized Link State Routing Protocol version 2 (OLSRv2) is an The Optimized Link State Routing Protocol version 2 (OLSRv2) is an
update to OLSRv1 as published in RFC3626 [11]. Compared to RFC3626, update to OLSRv1 as published in RFC3626 [1]. Compared to RFC3626,
OLSRv2 retains the same basic mechanisms and algorithms, while OLSRv2 retains the same basic mechanisms and algorithms, while
providing an even more flexible signaling framework and some providing an even more flexible signaling framework and some
simplification of the messages being exchanged. Also, OLSRv2 takes simplification of the messages being exchanged. Also, OLSRv2 takes
care to accomodate both IPv4 and IPv6 addresses in a compact fashion. care to accomodate both IPv4 and IPv6 addresses in a compact fashion.
OLSRv2 is developed for mobile ad hoc networks. It operates as a OLSRv2 is developed for mobile ad hoc networks. It operates as a
table driven, proactive protocol, i.e., exchanges topology table driven, proactive protocol, i.e. it exchanges topology
information with other nodes of the network regularly. Each node information with other nodes of the network regularly. Each node
selects a set of its neighbor nodes as "multipoint relays" (MPR). In selects a set of its neighbor nodes as "MultiPoint Relays" (MPRs).
OLSRv2, only nodes that are selected as such MPRs are then In OLSRv2, only nodes that are selected as such MPRs are then
responsible for forwarding control traffic intended for diffusion responsible for forwarding control traffic intended for diffusion
into the entire network. MPRs provide an efficient mechanism for into the entire network. MPRs provide an efficient mechanism for
flooding control traffic by reducing the number of transmissions flooding control traffic by reducing the number of transmissions
required. required.
Nodes, selected as MPRs, also have a special responsibility when Nodes selected as MPRs also have a special responsibility when
declaring link state information in the network. Indeed, the only declaring link state information in the network. Indeed, the only
requirement for OLSRv2 to provide shortest path routes to all requirement for OLSRv2 to provide shortest path routes to all
destinations is that MPR nodes declare link-state information for destinations is that MPR nodes declare link-state information for
their MPR selectors. Additional available link-state information may their MPR selectors. Additional available link-state information may
be utilized, e.g., for redundancy. be utilized, e.g., for redundancy.
Nodes which have been selected as multipoint relays by some neighbor Nodes which have been selected as multipoint relays by some neighbor
node(s) announce this information periodically in their control node(s) announce this information periodically in their control
messages. Thereby a node announces to the network, that it has messages. Thereby a node announces to the network that it has
reachability to the nodes which have selected it as an MPR. Then, reachability to the nodes which have selected it as an MPR. Thus, as
aside from being used to facilitate efficient flooding, MPRs are also well as being used to facilitate efficient flooding, MPRs are also
used for route calculation from any given node to any destination in used for route calculation from any given node to any destination in
the network. the network.
A node selects MPRs from among its one hop neighbors with A node selects MPRs from among its one hop neighbors with
"symmetric", i.e., bi-directional, linkages. Therefore, selecting "symmetric", i.e., bi-directional, linkages. Therefore, selecting
the route through MPRs automatically avoids the problems associated the route through MPRs automatically avoids the problems associated
with data packet transfer over uni-directional links (such as the with data packet transfer over uni-directional links (such as the
problem of not getting link-layer acknowledgments for data packets at problem of not getting link-layer acknowledgments for data packets at
each hop, for link-layers employing this technique for unicast each hop, for link-layers employing this technique for unicast
traffic). traffic).
OLSRv2 is developed to work independently from other protocols. OLSRv2 is developed to work independently from other protocols.
Likewise, OLSRv2 makes no assumptions about the underlying link- Likewise, OLSRv2 makes no assumptions about the underlying link-
layer. However, OLSRv2 may use link-layer information and layer. However, OLSRv2 may use link-layer information and
notifications when available and applicable. notifications when available and applicable.
OLSRv2, as OLSRv1, inherits the concept of forwarding and relaying OLSRv2, as OLSRv1, inherits the concept of forwarding and relaying
from HIPERLAN (a MAC layer protocol) which is standardized by ETSI from HIPERLAN (a MAC layer protocol) which is standardized by ETSI
[3]. [5].
1.1 Terminology 1.1 Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC2119 [5]. document are to be interpreted as described in RFC2119 [2].
Additionally, this document uses the following terminology: Additionally, this document uses the following terminology:
node - a MANET router which implements the Optimized Link State node - a MANET router which implements the Optimized Link State
Routing protocol as specified in this document. Routing protocol as specified in this document.
OLSRv2 interface - A network device participating in a MANET running OLSRv2 interface - A network device participating in a MANET running
OLSRv2. A node may have several OLSRv2 interfaces, each interface OLSRv2. A node may have several OLSRv2 interfaces, each interface
assigned an unique IP address. assigned one or more IP addresses.
neighbor - A node X is a neighbor of node Y if node Y can hear node X neighbor - A node X is a neighbor of node Y if node Y can hear node X
(i.e., a link exists from an OLSRv2 interface on node X to an (i.e., a link exists from an OLSRv2 interface on node X to an
OLSRv2 interface on node Y). A neighbor may also be called a OLSRv2 interface on node Y). A neighbor may also be called a
1-hop neighbor. 1-hop neighbor.
2-hop neighbor - A node X is a 2-hop neighbor of node Y if node X is 2-hop neighbor - A node X is a 2-hop neighbor of node Y if node X is
a neighbor of a neighbor of node Y. a neighbor of a neighbor of node Y, but is not node Y itself.
strict 2-hop neighbor - a 2-hop neighbor which is (i) not the node strict 2-hop neighbor - a 2-hop neighbor which is not a neighbor of
itself, (ii) not a neighbor of the node, and (iii) not a 2-hop the node, and is not a 2-hop neighbor only through a neighbor with
neighbor only through a neighbor with willingness WILL_NEVER. willingness WILL_NEVER.
multipoint relay (MPR) - A node which is selected by its 1-hop multipoint relay (MPR) - A node which is selected by its 1-hop
neighbor, node X, to "re-transmit" all the broadcast messages that neighbor, node X, to "re-transmit" all the broadcast messages that
it receives from node X, provided that the message is not a it receives from node X, provided that the message is not a
duplicate, and that the time to live field of the message is duplicate, and that the time to live field of the message is
greater than one. greater than one.
multipoint relay selector (MPR selector, MS) - A node which has multipoint relay selector (MPR selector, MS) - A node which has
selected its 1-hop neighbor, node X, as its multipoint relay, will selected its 1-hop neighbor, node X, as one of its multipoint
be called an MPR selector of node X. relays, will be called an MPR selector of node X.
link - A link is a pair of OLSRv2 interfaces from two different link - A link is a pair of OLSRv2 interfaces from two different
nodes, where at least one interface is able to hear (i.e. receive nodes, where at least one interface is able to hear (i.e. receive
traffic from) the other. A node is said to have a link to another traffic from) the other.
node when one of its interfaces has a link to one of the
interfaces of the other node.
symmetric link - A link where both interfaces have verified they are symmetric link - A link where both interfaces are able to hear (i.e.
able to hear the other. receive messages from) the other.
asymmetric link - A link which is not symmetric. asymmetric link - A link which is not symmetric.
symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of
any node X is the set of nodes which have at least one symmetric any node X is the set of nodes which have at least one symmetric
link to node X. link to node X.
symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of
node X is the set of nodes, excluding node X itself, which have a node X is the set of nodes, excluding node X itself, which have a
symmetric link to the symmetric 1-hop neighborhood of X. symmetric link to the symmetric 1-hop neighborhood of X.
symmetric strict 2-hop neighborhood - The symmetric strict 2-hop symmetric strict 2-hop neighborhood - The symmetric strict 2-hop
neighborhood of node X is the set of nodes in its symmetric 2-hop neighborhood of node X is the set of nodes in its symmetric 2-hop
neighborhood that are neither in its symmetric 1-hop neighborhood neighborhood that are neither in its symmetric 1-hop neighborhood
nor reachable only through a symmetric 1-hop neighbor of node X nor reachable only through a symmetric 1-hop neighbor of node X
with willingness WILL_NEVER. with willingness WILL_NEVER.
1.2 Applicability Statement 1.2 Applicability Statement
OLSRv2 is a proactive routing protocol for mobile ad hoc networks OLSRv2 is a proactive routing protocol for mobile ad hoc networks
(MANETs) [1], [2]. It is well suited to large and dense networks of (MANETs) [6], [7]. It is well suited to large and dense networks of
mobile nodes, as the optimization achieved using the MPRs works well mobile nodes, as the optimization achieved using the MPRs works well
in this context. The larger and more dense a network, the more in this context. The larger and more dense a network, the more
optimization can be achieved as compared to the classic link state optimization can be achieved as compared to the classic link state
algorithm. OLSRv2 uses hop-by-hop routing, i.e., each node uses its algorithm. OLSRv2 uses hop-by-hop routing, i.e., each node uses its
local information to route packets. local information to route packets.
As OLSRv2 continuously maintains routes to all destinations in the As OLSRv2 continuously maintains routes to all destinations in the
network, the protocol is beneficial for traffic patterns where the network, the protocol is beneficial for traffic patterns where the
traffic is random and sporadic between a large subset of nodes, and traffic is random and sporadic between a large subset of nodes, and
where the [source, destination] pairs are changing over time: no where the [source, destination] pairs are changing over time: no
additional control traffic is generated in this situation since additional control traffic need be generated in this situation since
routes are maintained for all known destinations at all times. Also, routes are maintained for all known destinations at all times. Also,
since routes are maintained continously, traffic is subject to no since routes are maintained continously, traffic is subject to no
delays due to buffering/route-discovery. delays due to buffering/route-discovery. This continued route
maintenance may be done using periodic message exchange, as detailed
in this specification, or triggered by external events if available.
OLSRv2 supports nodes which have multiple interfaces which
participate in the MANET. OLSRv2, additionally, supports nodes which
have non-MANET interfaces which can serve as (if configured to do so)
gateways towards other networks.
The message exchange format, contained in previous versions of this
specification, has been factored out to an independant specification
[4], which is used for carrying OLSRv2 control signals. OLSRv2 is
thereby able to accommodate for extensions via "external" and
"internal" extensibility. External extensibility implies that a
protocol extension may specify and exchange new message types which
can be forwarded and delivered correctly according to [4]. Internal
extensibility implies, that a protocol extension may define
additional attributes to be carried embedded in the OLSRv2 control
messages, detailed in this specification, while these OLSRv2 control
messages with additional attributes can still be correctly understood
by all OLSRv2 nodes.
2. Protocol Overview and Functioning 2. Protocol Overview and Functioning
OLSRv2 is a proactive routing protocol for mobile ad hoc networks. OLSRv2 is a proactive routing protocol for mobile ad hoc networks.
The protocol inherits the stability of a link state algorithm and has The protocol inherits the stability of a link state algorithm and has
the advantage of having routes immediately available when needed due the advantage of having routes immediately available when needed due
to its proactive nature. OLSRv2 is an optimization over the to its proactive nature. OLSRv2 is an optimization over the
classical link state protocol, tailored for mobile ad hoc networks. classical link state protocol, tailored for mobile ad hoc networks.
The main tailoring and optimizations of OLSRv2 are: The main tailoring and optimizations of OLSRv2 are:
skipping to change at page 8, line 48 skipping to change at page 9, line 48
* signal MPR selection. * signal MPR selection.
HELLO messages are emitted periodically, thereby allowing nodes to HELLO messages are emitted periodically, thereby allowing nodes to
continuously track changes in their local neighborhoods. continuously track changes in their local neighborhoods.
o A specification of global signaling, denoted TC messages. TC o A specification of global signaling, denoted TC messages. TC
messages in OLSRv2 serve to: messages in OLSRv2 serve to:
* inject link-state information into the entire network. * inject link-state information into the entire network.
* inject addresses of hosts and networks for which they may serve
as a gateway into the entire network.
* allow nodes with multiple interface addresses to ensure that
nodes within two hops can associate these addresses with a
single node for efficient MPR Set determination.
TC messages are emitted periodically, thereby allowing nodes to TC messages are emitted periodically, thereby allowing nodes to
continuously track global changes in the network. continuously track global changes in the network.
Thus, through periodic exchange of HELLO messages, a node is able to Thus, through periodic exchange of HELLO messages, a node is able to
acquire and maintain information about its immediate neighborhood. acquire and maintain information about its immediate neighborhood.
This includes information about immediate neighbors, as well as nodes This includes information about immediate neighbors, as well as nodes
which are two hops away. By HELLO messages being exchanged which are two hops away. By HELLO messages being exchanged
periodically, a node learns about changes in the neighborhood (new periodically, a node learns about changes in the neighborhood (new
nodes emerging, old nodes disappearing) without requiring explicit nodes emerging, old nodes disappearing) without requiring explicit
mechanisms for doing so. mechanisms for doing so.
Based on the local topology information, acquired through the Based on the local topology information, acquired through the
periodic exchange of HELLO messages, an OLSRv2 node is able to make periodic exchange of HELLO messages, an OLSRv2 node is able to make
provisions for ensuring optimized flooding, denoted "MPR flooding", provisions for ensuring optimized flooding, denoted "MPR flooding",
as well as injection of link-state information into the network. as well as injection of link-state information into the network.
skipping to change at page 9, line 24 skipping to change at page 10, line 30
as well as injection of link-state information into the network. as well as injection of link-state information into the network.
This is done through the notion of Multipoint Relays. This is done through the notion of Multipoint Relays.
The idea of multipoint relays is to minimize the overhead of flooding The idea of multipoint relays is to minimize the overhead of flooding
messages in the network by reducing redundant retransmissions in the messages in the network by reducing redundant retransmissions in the
same region. Each node in the network selects a set of nodes in its same region. Each node in the network selects a set of nodes in its
symmetric 1-hop neighborhood which may retransmit its messages. This symmetric 1-hop neighborhood which may retransmit its messages. This
set of selected neighbor nodes is called the "Multipoint Relay" (MPR) set of selected neighbor nodes is called the "Multipoint Relay" (MPR)
Set of that node. The neighbors of node N which are *NOT* in its MPR Set of that node. The neighbors of node N which are *NOT* in its MPR
set, receive and process broadcast messages but do not retransmit set, receive and process broadcast messages but do not retransmit
broadcast messages received from node N. The MPR set of a node is broadcast messages received from node N. The MPR Set of a node is
selected such that it covers (in terms of radio range) all symmetric selected such that it covers (in terms of radio range) all symmetric
strict 2-hop nodes. The MPR set of N, denoted as MPR(N), is then an strict 2-hop nodes. The MPR Set of N, denoted as MPR(N), is then an
arbitrary subset of the symmetric 1-hop neighborhood of N which arbitrary subset of the symmetric 1-hop neighborhood of N which
satisfies the following condition: every node in the symmetric strict satisfies the following condition: every node in the symmetric strict
2-hop neighborhood of N MUST have a symmetric link towards MPR(N). 2-hop neighborhood of N MUST have a symmetric link towards MPR(N).
The smaller a MPR set, the less control traffic overhead results from The smaller a MPR Set, the less control traffic overhead results from
the routing protocol. [2] gives an analysis and example of MPR the routing protocol. [7] gives an analysis and example of MPR
selection algorithms. Notice, that as long as the condition above is selection algorithms. Notice, that as long as the condition above is
satisfied, any algorithm selecting MPR sets is acceptable in terms of satisfied, any algorithm selecting MPR Sets is acceptable in terms of
implementation interoperability. implementation interoperability.
Each node maintains information about the set of neighbors that have Each node maintains information about the set of neighbors that have
selected it as MPR. This set is called the "Multipoint Relay selected it as MPR. This set is called the "Multipoint Relay
Selector set" (MPR Selector Set) of a node. A node obtains this Selector Set" (MPR Selector Set) of a node. A node obtains this
information from periodic HELLO messages received from the neighbors. information from periodic HELLO messages received from the neighbors.
Each node also maintains a Relay Set, which is the set of nodes for
which a node is to relay broadcast traffic. The Relay Set is derived
from the MPR Selector Set in that the Relay Set MUST contain all the
nodes in the MPR Selector set and MAY contain additional nodes.
A broadcast message, intended to be diffused in the whole network, A broadcast message, intended to be diffused in the whole network,
coming from any of the MPR selectors of node N is assumed to be coming from any of the nodes in the Relay Set of node N is assumed to
retransmitted by node N, if N has not received it yet. This set can be retransmitted by node N, if N has not received it yet. This set
change over time (i.e., when a node selects another MPR Set) and is can change over time (e.g., when a node selects another MPR Set) and
indicated by the selector nodes in their HELLO messages. is indicated by the selector nodes in their HELLO messages.
Using the MPR flooding mechanism, link-state information can be Using the MPR flooding mechanism, link-state information can be
injected into the network using TC messages: a node evaluates injected into the network. For this purpose, a node maintains an
periodically if it is required to generate TC messages and, if so, Advertised Neighbor Set which MUST contain all the nodes in the MPR
which information is to be included in these TC messages. selector set and MAY contain additional nodes. If the Advertised
Neighbor Set of a node is non-empty, TC messages, containing the
links between the node and the nodes in the Advertised Neighbor Set,
are not generated, unless needed for gateway reporting or multiple
interface address association (if the latter case only, with minimal
scope).
OLSRv2 is designed to work in a completely distributed manner and OLSRv2 is designed to work in a completely distributed manner and
does not depend on any central entity. The protocol does NOT REQUIRE does not depend on any central entity. The protocol does not require
reliable transmission of control messages: each node sends control reliable transmission of control messages: each node sends control
messages periodically, and can therefore sustain a reasonable loss of messages periodically, and can therefore sustain a reasonable loss of
some such messages. Such losses occur frequently in radio networks some such messages. Such losses occur frequently in radio networks
due to collisions or other transmission problems. due to collisions or other transmission problems.
Also, OLSRv2 does NOT REQUIRE sequenced delivery of messages. Each Also, OLSRv2 does not require sequenced delivery of messages. Each
control message contains a sequence number which is incremented for control message contains a sequence number which is incremented for
each message. Thus the recipient of a control message can, if each message. Thus the recipient of a control message can, if
required, easily identify which information is more recent - even if required, easily identify which information is more recent - even if
messages have been re-ordered while in transmission. Furthermore, messages have been re-ordered while in transmission. Furthermore,
OLSRv2 provides support for protocol extensions such as sleep mode OLSRv2 provides support for protocol extensions such as sleep mode
operation, multicast-routing etc. Such extensions may be introduced operation, multicast-routing etc. Such extensions may be introduced
as additions to the protocol without breaking backwards compatibility as additions to the protocol without breaking backwards compatibility
with earlier versions. with earlier versions.
OLSRv2 does NOT REQUIRE any changes to the format of IP packets. OLSRv2 does not require any changes to the format of IP packets.
Thus any existing IP stack can be used as is: OLSRv2 only interacts Thus any existing IP stack can be used as is: OLSRv2 only interacts
with routing table management. with routing table management. OLSR sends its own control messages
using UDP.
3. OLSRv2 Signaling Framework
In OLSRv2, signaling serves as a way for a node to express its
relationships with other nodes -- or more precisely, a control-
message in OLSRv2 states that "the address X has the following
special relationship with addresses W, Y and Z". This "special
relationship" may be advertisement of an adjacency between interface
X and interfaces WYZ, advertisement of an associated cost,
advertisement of selection as designated router etc.
In an OLSRv2 MANET, signaling may be either "local", intended only
for nodes adjacent to the originator of the signal or "global",
intended for all nodes in the OLSRv2 MANET.
In this section, the general mechanism employed for all OLSRv2
signaling is described.
This section provides abstract descriptions of message- and packet
formats. In the complementary Appendix D, a graphical representation
of OLSRv2 control messages and packets can be found.
3.1 OLSRv2 Packet Format
OLSRv2 messages are carried in a general packet format, allowing:
o piggybacking of several independent messages (originated or
forwarded) in a single transmission;
o external extensibility -- i.e. new message types can be introduced
for auxiliary functions, while still being delivered and forwarded
correctly even by nodes not capable of interpreting the message;
o controlled-scope diffusion of messages.
The packet format is inherited directly from OLSRv1 [11] and conforms
to the following specification:
packet = <packet-length><packet seq. number>{<message>}+
with the usual notion of "+" indicating "one or more" occurrences of
the preceding element, and the elements defined thus:
<packet-length> is an 16 bit field, which specifies the length (in
octets) of the packet;
<packet seq. number> is an 16 bit field, which specifies the packet
sequence number (PSN), which MUST be be incremented by one each
time a new OLSRv2 packet is transmitted. "Wrap-around" is handled
as described in Appendix H. A separate Packet Sequence Number is
maintained for each OLSRv2 interface such that packets transmitted
over an interface are sequentially enumerated.
<message> is the message as defined in Section 3.2.
3.2 OLSR Messages
Signals in OLSRv2 are carried through "messages". The primary
content of a message is a set of addresses about which the
originating node wishes to convey information. These addresses may
be divided into one or more address blocks. Each address SHALL
appear only once in a message. Each address block is followed by
zero or more TLVs, explained with more details in Section 3.2.2,
which convey information (e.g. cost, link-status, ...) about the
addresses in that address block. A message MAY also contain zero or
more TLVs, associated with the whole message.
Message content MAY (e.g. due to size limitations) be fragmented.
Each fragment is transmitted such that it makes up a syntactically
correct message (i.e. all headers are set as if each fragment is a
message in its own right, and each message contains all message
TLVs). Content fragmentation is detailed in Section 3.3.
A message has the following general layout
message = <msg-header><tlv-block>{<addr-block><tlv-block>}*
msg-header = <type><vtime><msg-size><originator-address>
<ttl><hopcount><msg-seq-number>
<tlv-block> = <tlv-length><tlv>*
with the usual notion of "*" indicating "zero or more" occurrences of
the preceding element, and the elements defined thus:
<tlv-length> is a 16 bit field, which contains the total length (in
octets) of the immediately following TLV(s). If no TLV follows,
this field contains zero;
<tlv> is a TLV, providing information regarding the entire message or
the address block which it follows. TLVs are specified in
Section 3.2.2;
<addr-block> is a block of addresses, with which the originator of
the message has a special relationship. Address blocks are
specified in Section 3.2.1;
<type> is an 8 bit field, which specifies the type of message;
<vtime> is an 8 bit field, which specifies for how long time after
reception a node MUST consider the information contained in the
message as valid, unless a more recent update to the information
is received. The encoding of vtime is as specified in Section 17;
<msg-size> is an 16 bit field, which specifies the size of the <msg-
header> and the following <msg-body>, counted in octets;
<originator-address> is the address of an interface of the node,
which originated the message. Each node SHOULD select one
interface address and MUST utilize this address consistently as
"originator address" for all messages it generates;
<ttl> is an 8 bit field, which contains the maximum number of hops a
message will be transmitted. Before a message is retransmitted,
the Time To Live MUST be decremented by 1. When a node receives a
message with a Time To Live equal to 0 or 1, the message MUST NOT
be retransmitted under any circumstances. Normally, a node would
not receive a message with a TTL of zero.
<hopcount> is an 8 bit field, which contains the number of hops a
message has attained. Before a message is retransmitted, the Hop
Count MUST be incremented by 1. Initially, this is set to '0' by
the originator of the message;
<msg-seq-number> is a 16 bit field, which contains a unique number,
generated by the originator node to uniquely identify each message
in the network. "Wrap-around" is handled as described in
Appendix H.
TLVs associated with a message or an address block SHALL be included
in numerically ascending order within each TLV block. Note that this
means that all TLVs defined in this document appear before all other
TLVs in that TLV block.
3.2.1 Address Blocks
An address block represents a set of addresses in a compact form.
Assuming that an address can be specified as a sequence of bits of
the form 'head:tail', then an address-block is a set of addresses
sharing the same 'head' and having different 'tails'. Specifically,
an address block conforms to the following specification:
address-block = {<head-length><head><nb tails>{<tail>*}}
with the usual notion of "*" indicating "zero or more" occurrences of
the preceding element, and the elements defined thus:
<head-length> is the number of "common leftmost bits" in a set of
addresses, akin to a "prefix", however with the only restriction
on the head-length that 0 <= head-length <= the length of the
address;
<head> is the longest sequence of leftmost bits, which the addresses
in the address block have in common. Akin to a prefix;
<nb tails> is the number of tails which follows;
<tail> is the sequence of bits which, when concatenated to the head,
makes up a single, complete, unique address.
This representation aims at providing a flexible, yet compact, way of
representing sets of interface addresses.
3.2.2 TLVs
A TLV is a carrier of information, relative to a message or to
addresses in an address block. A TLV, associated to an address-
block, specifies some attribute(s), which associate with address(ses)
in the address-block. In order to provide the largest amount of
flexibility to benefit from address aggregation as described in
Section 3.2.1, a TLV associated to an address block can apply to:
o a single address in the address block;
o all addresses in the address block;
o any continuous sequence of addresses in the address block;
Specifically, a TLV conforms to the following specification:
tlv = <type><length><index-start><index-stop><value>
where the elements are defined thus:
<type> is an 8 bit field, which specifies the type of the TLV. The
two most significant bits are allocated with the following
semantics:
bit 7 is the "user" bit. Types with this bit unset are defined in
this specification or can be allocated via standards action.
Types with this bit set are reserved for private/local use.
bit 6 is the "multivalue" bit. TLVs with types with this bit unset 2.1 Protocol Extensibility
include a single value, which applies to each of the addresses
defined by <index-start> and <index-stop>. TLVs with types with
this bit set include separate values for each of the addresses in
the interval defined by <index-start> and <index-stop>;
<length> is an 8 bit field which specifies the length, counted in This specification defines and uses two OLSRv2 message types, HELLO
octets, of the data contained in <value>. If the multivalue bit and TC. As for OLSRv1 [1] extensions to OLSRv2 may define new
is set, this MUST be an integral multiple of (<index-stop>-<index- message types to carry additional information. This may be
start>+1); considered as "external" extensibility. New message types are
divided into two ranges, those which may be added by standards
actions (with types up to 127) and those made available for private/
local use (with types 128 to 255).
<index-start> is an 8 bit field. For a TLV associated with an All new messages must be syntactically OLSRv2 messages, as defined in
address block, specifies the index of the first address in the [4]. (Some additional constraints to that specification are added
address-block (starting at zero), for which this TLV applies. For for OLSRv2 packets and messages, requiring full packet and message
a TLV associated with a message, this field SHALL be set to zero; headers.) Note that if it is required to include one or more blocks
of unstructured data in such a message (possibly as its only content)
this may be achieved by including each block as a single message TLV
block, with an appropriately defined message TLV. (Like message
types, TLV types are divided into those up to 127 which may be added
by standards action, and those from 128 to 255 available for private/
local use.)
<index-stop> is an 8 bit field. For a TLV associated with an address A network may contain nodes both aware of, and unaware of, any new
block, specifies the index of the last address in the address- message types. The originator of a message can control whether a
block (starting at zero) for which this TLV applies. For a TLV message flooded through the network is forwarded by nodes which are
associated with a message, this field SHALL be set to zero; unaware of the message type, thus reaching all nodes in the network,
or is only flooded by nodes which recognise the message type.
<value> contains a payload, of the length specified in <length>, OLSRv2 also supports an alternative, and more powerful, extension
which is to be processed according to the specification indexed by mechanism which was not supported by OLSRv1, that of adding new
the <type> field. If this is a TLV for an address block and the information to an already defined message type, whilst still leaving
multivalue bit is set, this field is divided into (<index-stop>- the predefined information unchanged and usable, including by a node
<index-start>+1) equal-sized fields which are applied in turn to which does not recognise the new information. This may be considered
each address described by <index-start> and <index-stop> to be "internal" extensibility of a message.
Two or more TLVs of the same type SHALL NOT apply to the same The mechanism for this extensibility is the use of TLV (type-length-
address. value) structures in the message format defined in [4] to carry
information associated with either the message as a whole, or with
one or more addresses carried in the message. The messages defined
in this specification carry two types of addresses, those of the
originating node's own interfaces participating in OLSRv2, and those
of neighbouring nodes or networks to which it has a route. (New
message types may define other relationships to addresses which they
carry.) All information associated with these addresses, or the
message as a whole, in messages defined in this specification is in
TLV format; additional TLVs may be defined and added to these
messages.
3.3 Message Content Fragmentation Those nodes which do not recognise newly defined TLV types ignore the
added TLVs. (This is facilitated by that the TLVs defined in this
specification, or in [4], have the lowest type numbers and that TLVs
must be included in type order, as specified in [4].) It is
important that newly defined TLV types permit this behaviour.
An OLSRv2 message MAY be larger than is desirable to include, with 3. Processing and Forwarding Repositories
the OLSR packet and other headers (UDP, IP) in a MAC frame. In this
case the message SHOULD be fragmented.
An OLSRv2 message may be fragmented by dividing the address blocks The following data-structures are employed in order to ensure that a
plus following TLVs among its fragments. It MAY be necessary to use message is processed at most once and is forwarded at most once per
more address blocks than might otherwise be chosen without interface of a node, and that fragmented content is treated
fragmentation. Each message fragment may carry any number of these correctly.
address blocks plus following TLVs.
All message TLVs MUST be included identically in each fragment. 3.1 Received Message Set
All TLVs pertaining to an address block MUST be included in the same Each node maintains, for each OLSRv2 interface it possesses, a set of
fragment as the address block. signatures of messages, which have been received over that interface,
in the form of "Received Tuples":
When transmitting fragmented content, each message containing a (RX_type, RX_addr, RX_seq_number, RX_time)
fragment MUST include a message TLV of type Content Sequence Number.
The value of this Content Sequence Number TLV is a 16 bit field
uniquely identifying the "version" of the content of the message. If
the content does not have an inherent sequence number or version
number, the value of the Content Sequence Number TLV SHOULD be set to
the message sequence number of the message containing the first
fragment.
A message containing a fragment MUST include a message TLV of type where:
Fragmentation. The value of this Fragmentation TLV is a 16 bit field
consisting of two 8 bit sub-fields describing the number of
fragments, and the fragment number (counting from zero).
If the same content with the same Content Sequence Number is sent RX_type is the received message type, or zero if the received message
more than once by a node, the content MUST be fragmented and sequence number is not type-specific.
transmitted identically each time it is sent.
4. Packet Processing and Message Forwarding RX_addr is the originator address of the received message;
Upon receiving a basic packet, a node examines each of the "message RX_seq_number is the message sequence number of the received message;
headers". If the "message type" is known to the node, the message is
processed locally according to the specifications for that message
type -- forwarding of known messages is considered part of the
message processing. Otherwise, the message is treated as "unknown",
and is only evaluated for forwarding.
4.1 Processing and Forwarding Repositories RX_time specifies the time at which this record expires and *MUST* be
removed.
The following data-structures are employed in order to ensure that a In a node, this is denoted the "Received Message Set" for that
message is processed at most once and is forwarded at most once per interface.
interface of a node, and that fragmented content is treated
correctly.
4.1.1 Received Message Set 3.2 Fragment Set
Each node maintains, for each OLSRv2 interface it possesses, a set of Each node stores messages containing fragmented content until all
signatures of messages received over that interface: fragments are received and the message processing can be completed,
in the form of "Fragment Tuples":
(R_addr, R_seq_number, R_time) (FG_message, FG_time)
where: where:
R_addr is the originator address of the received message; FG_message is the message containing fragmented content;
R_seq_number is the message sequence number of the received message;
R_time specifies the time at which this record expires and *MUST* be FG_time specifies the time at which this record expires and MUST be
removed. removed.
In a node, this is denoted the "Received Message Set". In a node, this is denoted the "Fragment Set".
4.1.2 Processed Set 3.3 Processed Set
Each node maintains a set of messages, which have been processed by Each node maintains a set of signatures of messages which have been
the node: processed by the node, in the form of "Processed Tuples":
(P_addr, P_seq_number, P_time) (P_type, P_addr, P_seq_number, P_time)
where: where:
P_addr is the originator address of the received message; P_type is the processed message type, or zero if the processed
P_seq_number is the message sequence number of the received message; message sequence number is not type-specific.
P_addr is the originator address of the processed message;
P_seq_number is the message sequence number of the processed message;
P_time specifies the time at which this record expires and *MUST* be P_time specifies the time at which this record expires and *MUST* be
removed. removed.
In a node, this is denoted the "Processed Set". In a node, this is denoted the "Processed Set".
4.1.3 Forwarded Set 3.4 Forwarded Set
Each node maintains a set of messages, which have been retransmitted/ Each node maintains a set of signatures of messages which have been
forwarded by the node: retransmitted/forwarded by the node, in the form of "Forwarded
Tuples":
(F_addr, F_seq_number, F_time) (FW_type, FW_addr, FW_seq_number, FW_time)
where: where:
F_addr is the originator address of the received message; FW_type is the forwarded message type, or zero if the forwarded
message sequence number is not type-specific.
F_seq_number is the message sequence number of the received message; FW_addr is the originator address of the forwarded message;
F_time specifies the time at which this record expires and *MUST* be FW_seq_number is the message sequence number of the forwarded
message;
FW_time specifies the time at which this record expires and *MUST* be
removed. removed.
In a node, this is denoted the "Forwarded Set". In a node, this is denoted the "Forwarded Set".
4.1.4 Relay Set 3.5 Relay Set
A node maintains a set of neighbor interfaces, in the form of "relay Each node maintains a set of neighbor interface addresses for which
tuples", for which it is to relay flooded messages: it is to relay flooded messages, in the form of "Relay Tuples":
(RS_if_addr, Rs_if_time) (RY_if_addr)
where: where:
RS_if_addr is the address of the neighbor interface, for which a node RY_if_addr is the address of a neighbor interface for which the node
SHOULD relay flooded messages; SHOULD relay flooded messages.
RS_if_time specifies the time at which this record expires and *MUST*
be removed.
In a node, this is denoted the "Relay Set". In a node, this is denoted the "Relay Set".
4.2 Fragment Set 4. Packet Processing and Message Forwarding
A node stores messages containing fragmented content in form of Upon receiving a basic packet, a node examines each of the message
"fragment tuples" until all fragments are received and the messages headers. If the message type is known to the node, the message is
can be processed: processed locally according to the specifications for that message
type. The message is also independently evaluated for forwarding.
(F_message, F_time) 4.1 Actions when Receiving an OLSRv2 Packet
where: Upon receiving a packet, a node MUST perform the following task:
F_message is the message containing a fragment; 1. If the packet contains no messages (i.e. the packet length is
less than or equal to the size of the packet header) or if the
packet cannot be parsed into messages, the packet MUST be
silently discarded.
F_time specifies the time at which this record expires and MUST be 2. Otherwise, each message in the packet is treated according to
removed. Section 4.2.
In a node, this is denoted the "Fragment Set". 4.2 Actions when Receiving an OLSRv2 Message
4.3 Actions when Receiving an OLSRv2-Packet A node MUST perform the following tasks for each received OLSRv2
message:
Upon receiving a basic packet, a node MUST perform the following 1. If the received OLSRv2 message header cannot be correctly parsed
task: according to the specification in [4], or if the originator
address of the message is an interface address of the receiving
node then the message MUST be silently discarded;
1. If the packet contains no messages (i.e., the Packet Length is 2. Otherwise:
less than or equal to the size of the packet header), the packet
MUST silently be discarded.
2. Otherwise, each encapsulated message is treated according to 1. If the message is of a known type then the message is
considered for processing according to Section 4.3;
2. If for the received message TTL > 0, and if either the
message is of a known type, or bit 3 of the message semantics
octet in the message header is clear, as indicated in [4],
then the message is considered for forwarding according to
Section 4.4. Section 4.4.
4.4 Actions when Receiving an OLSRv2-Message 4.3 Message Considered for Processing
A node MUST perform the following tasks for a received OLSRv2- If a message is considered for processing, the following tasks MUST
message: be performed:
If for the message TTL <= 0 or if the Originator Address of the 1. If an entry exists in the Processed Set where:
message is an interface address of the receiving node, then the
message MUST silently be dropped.
If an entry exists in the received set for the receiving * P_type == the message type, or 0 if bit 2 of the message
interface, where: semantics octet (in the message header) is clear, AND;
* R_addr == the originator of the received message, AND; * P_addr == the originator address of the message, AND;
* R_seq_number == the sequence number of the received message. * P_seq_number == the sequence number of the message.
then the message MUST be discarded then the message MUST NOT be processed.
Otherwise: 2. Otherwise:
1. Create an entry in the Received Set for the receiving 1. Create an entry in the Processed Set with:
interface with:
+ R_addr = originator address of the received message; + P_type = the message type, or 0 if bit 2 of the message
semantics octet (in the message header) is clear;
+ R_seq_number = sequence number of the received message; + P_addr = originator address of the message;
+ R_time = current time + R_HOLD_TIME. + P_seq_number = sequence number of the message;
2. If the message type is known to the receiving node, then: + P_time = current time + P_HOLD_TIME.
1. if the message contains a message TLV of type Fragment: 2. If the message does not contain a message TLV of type
Fragment (or if it does and the indicated number of fragments
is one) then process the message fully according to its type.
1. if the Fragment Set contains all remaining fragments 3. Otherwise:
necessary to reconstitute the content, the messages
containing these fragments MUST be removed from the
fragment set and received message MUST be considered
for processing according to Section 4.5;
2. otherwise, the message is added to the Fragment Set 1. If the message is "wholly or partially self-contained" as
with a F_time of XXXX (possibly replacing an identical indicated by its Fragment TLV then process the current
and previous received instance of the same fragment of message as far as possible according to its type;
the same content).
2. Otherwise, if the message does not contain a message TLV 2. If the Fragment Set includes any messages with the same
of type Fragment,the message is considered for processing originator address and content sequence number as the
according to Section 4.5; current message, and either the same fragment number or a
different number of fragments, then remove these messages
are from the Fragment Set;
Otherwise, if the message type is unknown to the receiving 3. If the Fragment Set includes messages containing all the
node, the message is considered for forwarding according to remaining fragments of the same overall message as the
Section 4.6. current message (i.e. if the number of messages in the
Fragment Set with the same originator address and content
sequence number as the current message is equal to the
current message's number of fragments, less one) then all
of these messages are removed from the Fragment Set and
processed according to their type (taking account of any
previous processing if any or all were wholly or
partially self-contained);
Notice that known message types are not automatically considered for 4. Otherwise, the current message is added to the Fragment
forwarding. Forwarding of known message types MUST be specified as a Set with a FG_time of FG_HOLD_TIME (possibly replacing an
property of processing of that message type. identical and previous received instance of the same
fragment of the same content).
4.5 Message Considered for Processing 4.4 Message Considered for Forwarding
If a message is considered for processing, the following tasks MUST If a message is considered for forwarding then if it is either of a
be performed: message type defined in this document, or of an unknown message type
it MUST use the following algorithm. A message type not defined in
this document may specify the use of this, or another algorithm.
(Such an other algorithm MAY use the Received Set for the receiving
interface, it SHOULD use the Forwarded Set similarly to the following
algorithm.)
1. If an entry exists in the Processed Set where: If a message is considered for forwarding according to this
algorithm, the following tasks MUST be performed:
* P_addr == the originator address of the received message, AND; 1. If there is no symmetric link in the Link Set between the
receiving interface and the sending interface (as indicated by
the source interface of the IP datagram containing the message)
then the message MUST be silently discarded.
* P_seq_number == the sequence number of the received message. 2. Otherwise:
the message MUST be discarded. 1. If an entry exists in the Received Set for the receiving
interface, where:
2. Otherwise: + RX_type == the message type, or 0 if bit 2 of the message
semantics octet (in the message header) is clear, AND;
1. Create an entry in the Processed Set with: + RX_addr == the originator address of the received message,
AND;
+ P_addr = originator address of the received message; + RX_seq_number == the sequence number of the received
message.
+ P_seq_number = sequence number of the received message; then the message MUST be silently discarded.
+ P_time = current time + P_HOLD_TIME. 2. Otherwise:
2. Process message locally, according to the specification for 1. Create an entry in the Received Set for the receiving
the received message type. interface with:
3. If a message of a known message type is to be forwarded, the - RX_type = the message type, or 0 if bit 2 of the
algorithm in Section 4.6 MAY be performed. All forwardable message semantics octet (in the message header) is
messages defined in this specification (TC, MA) do use the clear;
algorithm in Section 4.6.
4.6 Message Considered for Forwarding - RX_addr = originator address of the message;
If a message is considered for forwarding, the following tasks MUST - RX_seq_number = sequence number of the message;
be performed:
1. If an entry exists in the Forwarded Set where: - RX_time = current time + RX_HOLD_TIME.
* F_addr == the originator address of the received message, AND; 2. If an entry exists in the Forwarded Set where:
* F_seq_number == the sequence number of the received message. - FW_type == the message type, or 0 if bit 2 of the
message semantics octet (in the message header) is
clear;
then the message MUST be discarded - FW_addr == the originator address of the received
message, AND;
2. Otherwise: - FW_seq_number == the sequence number of the received
message.
1. If an entry exists in the Relay Set, where: then the message MUST be silently discarded.
+ RS_if_addr == message source address of the received 3. Otherwise if an entry exists in the Relay Set, where
message RY_if_addr == source address of the message (as indicated
by the source interface of the IP datagram containing the
message):
2. Create an entry in the Forwarded Set with: 1. Create an entry in the Forwarded Set with:
- F_addr = originator address of the received message; o FW_type = the message type, or 0 if bit 2 of the
message semantics octet (in the message header) is
clear;
- F_seq_number = sequence number of the received o FW_addr = originator address of the message;
message;
- F_time = current time + F_HOLD_TIME. o FW_seq_number = sequence number of the message;
3. The message header is modified as follows: o FW_time = current time + FW_HOLD_TIME.
- decrement the message TTL by 1; 2. The message header is modified as follows:
- increment the message hop count by 1; o Decrement the message TTL by 1;
4. If the message TTL > 0: o Increment the message hop count by 1;
3. Transmit the message on all OLSRv2 interfaces of the
node.
- Transmit the message on all OLSRv2 interfaces of the Messages are retransmitted in the format specified by [4] with the
node All-OLSRv2-Multicast address (see Section 17.1) as destination IP
address.
5. Information Repositories 5. Information Repositories
The signaling of OLSRv2 populates a set of information repositories, The purpose of OLSRv2 is to determine the Routing Set, which may be
specified in this section. used to update IP's Routing Table, providing "next hop" routing
information for IP datagrams. In order to accomplish this, OLSRv2
maintains a number of protocol sets, the information repository of
the protocol. These sets are updated, directly or indirectly, by the
exchange of messages between nodes in the network. In turn the
contents of these messages are largely determined by the contents of
a part of the information repositories, the Neighbourhood Information
Base, which contains information about the 1- and 2- hop
neighbourhoods of the node. The remaining part of the information
repository, the Topology Information Base (including the Routing Set)
contains information about the network which is not constrained to
the node's neighbourhood. The Topology Information Base is updated
by the OLSRv2 messages defined in this document, it is not used to
define their contents. The process of information exchange which
leads to the population of the Neighbourhood Information Base and the
Topology Information Base is started using only the node's own OLSRv2
interface addresses and host and network associated addresses. These
are not affected by the exchange of the OLSRv2 messages defined in
this document.
5.1 Local Link Information Base 5.1 Neighborhood Information Base
The local link information base stores information about links The neighborhood information base stores information about links
between local interfaces and interfaces on adjacent nodes. between local interfaces and interfaces on adjacent nodes.
5.1.1 Link Set 5.1.1 Link Set
A node records a set of "Link Tuples": A node records a set of "Link Tuples":
(L_local_iface_addr, L_neighbor_iface_addr, (L_local_iface_addr, L_neighbor_iface_addr,
L_SYM_time, L_ASYM_time, L_willingness, L_time). L_SYM_time, L_ASYM_time, L_willingness, L_time).
where: where:
skipping to change at page 24, line 5 skipping to change at page 22, line 25
| Not Expired | Not Expired | SYMMETRIC | | Not Expired | Not Expired | SYMMETRIC |
| | | | | | | |
| Expired | Not Expired | ASYMMETRIC | | Expired | Not Expired | ASYMMETRIC |
+-------------+-------------+--------------+ +-------------+-------------+--------------+
Table 1 Table 1
The status of the link, denoted L_STATUS, can be derived based on the The status of the link, denoted L_STATUS, can be derived based on the
fields L_SYM_time and L_ASYM_time as defined in Table 1. fields L_SYM_time and L_ASYM_time as defined in Table 1.
In a node, the set of Link Tuples are denoted the "Link Set". In a node, the set of Link Tuples is denoted the "Link Set".
5.1.2 2-hop Neighbor Set 5.1.2 2-Hop Neighbor Set
A node records a set of "2-hop tuples" A node records a set of "2-Hop Neighbor Tuples"
(N_local_iface_addr, N_neighbor_iface_addr, N_2hop_iface_addr, N_time) (N2_local_iface_addr, N2_neighbor_iface_addr, N2_2hop_iface_addr, N2_time)
describing symmetric links between its neighbors and the symmetric describing symmetric links between its neighbors and the symmetric
2-hop neighborhood. 2-hop neighborhood.
N_local_iface_addr is the address of the local interface over which N2_local_iface_addr is the address of the local interface over which
the information was received; the information was received;
N_neighbor_iface_addr is the interface address of a neighbor; N2_neighbor_iface_addr is the interface address of a neighbor;
N_2hop_iface_addr is the interface address of a 2-hop neighbor with a N2_2hop_iface_addr is the interface address of a 2-hop neighbor with
symmetric link to N_neighbor_iface_addr; a symmetric link to the node with interface address
N_neighbor_iface_addr;
specifies the time at which the tuple expires and *MUST* be N2_time specifies the time at which the tuple expires and *MUST* be
removed. removed.
In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor In a node, the set of 2-Hop Neighbor Tuples is denoted the "2-Hop
Set". Neighbor Set".
5.1.3 Neighborhood Address Association Set 5.1.3 Neighborhood Address Association Set
A node maintains, for each 1-hop and 2-hop neighbor with multiple A node maintains, for each 1-hop and 2-hop neighbor with multiple
addresses participating in the OLSRv2 network, a "Neighborhood addresses participating in the OLSRv2 network, a "Neighborhood
Address Association Tuple", representing that "these n addresses Address Association Tuple", representing that "these addresses belong
belong to the same node". to the same node".
(I_neighbor_addr_list, I_time) (NA_neighbor_addr_list, NA_time)
I_neighbor_iface_addr_list is the list of addresses of the 1-hop or NA_neighbor_iface_addr_list is the list of interface addresses of the
2-hop neighbor node; 1-hop or 2-hop neighbor node;
I_time specifies the time at which the tuple expires and *MUST* be NA_time specifies the time at which the tuple expires and *MUST* be
removed. removed.
In a node, the set of Neighborhood Address Association Tuples is In a node, the set of Neighborhood Address Association Tuples is
denoted the "Neighborhood Address Association Set". denoted the "Neighborhood Address Association Set".
5.1.4 MPR Set 5.1.4 MPR Set
A node maintains a set of neighbors which are selected as MPR. Their A node maintains a set of neighbors which are selected as MPRs.
interface addresses are listed in the MPR Set. Their interface addresses are listed in the MPR Set.
5.1.5 Advertised Neighbor Set 5.1.5 MPR Selector Set
A node maintains, for each interface of an 1-hop neighbor which has
selected it as MPR, an "MPR Selector Tuple", representing the an
interface of the neighbor node which have selected it as an MPR.
(MS_neighbor_if_addr, MS_time)
MS_neighbor_if_addr specifies the interface address of a 1-hop
neighbor, which has selected the node as MPR;
MS_time specifies the time at which the tuple expires and *MUST* be
removed.
Notice that if a MPR selector node has multiple interface addresses,
the MPR Selector Set will contain one tuple for each interface
address of the MPR selector.
5.1.6 Advertised Neighbor Set
A node maintains a set of neighbor interface addresses, which are to A node maintains a set of neighbor interface addresses, which are to
be advertised through TC messages: be advertised through TC messages:
(A_neighbor_iface_addr) (A_neighbor_iface_addr)
For this set, an Advertised Neighbor Set Sequence Number (ASSN) is For this set, an Advertised Neighbor Set Sequence Number (ASSN) is
maintained. Each time the Advertised Neighbor Set is updated, the maintained. Each time the Advertised Neighbor Set is updated, the
ASSN MUST be incremented. ASSN MUST be incremented.
5.2 Topology Information Base 5.2 Topology Information Base
The Topology Information Base stores topological information
describing the network beyond the nodes neighborhood (i.e. beyond the
Neighborhood Information Base of the node).
5.2.1 Topology Set
Each node in the network maintains topology information about the Each node in the network maintains topology information about the
network. network.
For each destination in the network, at least one "Topology Tuple" For each destination in the network, at least one "Topology Tuple"
(T_dest_iface_addr, T_last_iface_addr, T_seq, T_time) (T_dest_iface_addr, T_last_iface_addr, T_seq, T_time)
is recorded. is recorded.
T_dest_iface_addr is the interface address of a node, which may be T_dest_iface_addr is the interface address of a node, which may be
reached in one hop from the node with the interface address reached in one hop from the node with the interface address
T_last_iface_addr; T_last_iface_addr;
T_last_iface_addr is, conversely, the last hop towards T_last_iface_addr is, conversely, the last hop towards
T_dest_iface_addr. Typically, T_last_iface_addr is a MPR of T_dest_iface_addr. Typically, T_last_iface_addr is a MPR of
T_dest_iface_addr; T_dest_iface_addr;
T_seq is a sequence number, and T_time specifies the time at which T_seq is a sequence number, and
this tuple expires and *MUST* be removed.
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". In a node, the set of Topology Tuples are denoted the "Topology Set".
6. OLSRv2 Control Messages 5.2.2 Attached Network Set
OLSRv2 employs two different message types for exchanging protocol Each node in the network maintains information about attached
information. Those are HELLO messages, which are locally scoped, and networks.
TC messages, which are globally scoped.
6.1 HELLO Messages For each attached network, at least one "Attached Network Tuple"
HELLO messages are, in OLSRv2, exchanged between neighbor nodes with (AN_net_addr, AN_prefix_lenght, AN_gw_addr, AN_seq_no, AN_time)
the purpose of populating the local link information base:
o Link Sensing: detecting new and lost adjacent interfaces and is recorded.
performing bidirectionality check of links;
o 2-hop Neighbor Discovery: detecting the 2-hop symmetric AN_net_addr is the network address (prefix) of a network, which may
neighborhood of a node; be reached via the node with the OLSRv2 interface address
AN_gw_addr;
o MPR Signaling: signal MPR selection to neighbor nodes and detect AN_prefix_length is the length of the prefix of the network address
selection of MPRs AN_net_addr;
HELLO messages are exchanged between neighbor nodes only, i.e. they AN_gw_addr is the address of an OLSRv2 interface of a node which can
are never forwarded by any node. act as gateway to the network identified by the AD_net_addr/
AD_prefix_length;
6.2 TC Messages AN_seq_no is a sequence number, and;
TC messages are, in OLSRv2, transmitted to the entire network with AN_time specifies the time at which this tuple expires and *MUST* be
the purpose of populating the topology information base: removed.
o Topology Discovery: ensure that information is present in each In a node, the set of Topology Tuples are denoted the "Topology Set".
node describing all destinations and (at least) a sufficient
subset of links in order to provide least-hop paths to all
destinations.
TC messages are exchanged within the entire network, i.e. they are 5.2.3 Routing Set
forwarded according to the specification in section Section 4.6.
6.3 MA Messages A node records a set of "Routing Tuples":
MA messages are, in OLSRv2, transmitted by nodes with more than one (R_dest_iface_addr, R_next_iface_addr, R_dist, R_iface_addr)
address participating in the OLSRv2 network with the purpose of
populating the Neighborhood Address Association Set (NAAS).
MA messages are exchanged within the 2-hop neighborhood of the describing the next hop and distance of the path to each destination
originator - i.e. are transmitted with a TTL=2 and are forwarded in the network for which a route is known.
according to the specification in section Section 4.6.
7. Populating the MPR Set R_dest_iface_addr is the interface address of the destination node;
Each node MUST select, from among its one-hop neighbors, a subset of R_next_iface_addr is the interface address of the "next hop" on the
nodes as MPR. This subset MUST be selected such that a message path towards R_dest_iface_addr;
transmitted by the node, and retransmitted by all its MPR nodes, will
be received by all nodes 2 hops away.
Each node selects its MPR Set individually, utilizing the information R_dist is the number of hops on the path to R_dest_iface_addr;
in then neighbor set. Initially, a node will have an empty neighbor-
set, thus, initially the MPR set is empty. A node SHOULD recalculate
its MPR set when a change is detected to the neighbor set or 2-hop
neighbor set.
More specifically, a node MUST calculate MPRs per interface, the R_iface_addr is the address of the local interface over which a
union of the MPR sets of each interface make up the MPR set for the packet MUST be sent to reach R_next_iface_addr.
node.
MPRs are used to flood control messages from a node into the network In a node, the set of Routing Tuples is denoted the "Routing Set".
while reducing the number of retransmissions that will occur in a
region. Thus, the concept of MPR is an optimization of a classical
flooding mechanism. While it is not essential that the MPR set is
minimal, it is essential that all strict 2-hop neighbors can be
reached through the selected MPR nodes. A node MUST select an MPR
set such that any strict 2-hop neighbor is covered by at least one
MPR node. A node MAY select additional MPRs beyond the minimum set.
Keeping the MPR set small ensures that the overhead of OLSRv2 is kept
at a minimum.
Appendix A contains an example heuristic for selecting MPRs. 6. OLSRv2 Control Message Structures
8. Populating the Advertised Neighbor Set Nodes using OLSRv2 exchange information through messages. One or
more messages sent by a node at the same time are combined into a
packet. These messages may have originated at the sending node, or
have originated at another node and forwarded by the sending node.
Messages with different originators may be combined in the same
packet.
The Advertised Neighbor Set contains the set of neighbor addresses, The packet and message format used by OLSRv2 is defined in [4].
to which a node advertises links through TC messages. This set However this specification contains some options which are not used
SHOULD at least contain the addresses of the MPR Selector Set (i.e. by OLSRv2. In particular (using the syntactical elements defined in
all addresses, associated with a MPR selector through the the packet format specification):
Neighborhood Adverticed Address Set). This set MAY contain
additional neighbor addresses.
Each time an address is removed from the Advertised Neighbor Set, the o All OLSRv2 packets include a <packet-header>.
ASSN MUST be incremented. When an address is added to the Advertised
Neighbor Set, the ASSN SHOULD be incremented.
9. HELLO Message Generation o All OLSRv2 messages, not limited to those defined in this
document, include a full <msg-header> and hence have bits 0 and 1
of <msg-semantics> cleared.
An OLSRv2 HELLO message is composed as described in Section 3.2: a o All OLSRv2 message defined in this document have all remaining
set of message TLVs, describing general properties of the message and bits of <msg-semantics> cleared.
the node emitting the HELLO, and a set of address blocks (with
associated TLV sets), describing the links and their associated
properties.
OLSRv2 HELLO messages are generated and transmitted per interface, Other options defined in [4] may be freely used, in particular any
i.e. different HELLO messages are generated and transmitted per values of <tlv-semantics> consistent with its specification. An
OLSRv2 interface of a node. implementation of OLSRv2 MAY take full advantage of the features of
the message specification in [4] allowing decisions relating to
whether a message should be forwarded and/or processed to be taken
parsing only the message header (plus, if a message is to be
processed but may be fragmented, only the first octets of the message
body).
OLSRv2 HELLO messages are generated and transmitted periodically, OLSRv2 messages are sent using UDP, see Appendix C.
with a default interval between two consecutive HELLO emissions on
the same interface of HELLO_INTERVAL.
This section specifies the requirements, which HELLO message The remainder of this section defines, within the framework of [4],
generation MUST fulfill. An example algorithm is proposed in message types and TLVs specific to OLSRv2.
Appendix B.1.
9.1 HELLO Message: Message TLVs 6.1 General OLSRv2 Message TLVs
For each OLSRv2 interface a node MUST generate a HELLO message. In This document specifies two message TLVs, which can be applied to any
that HELLO message, a node MAY include a message TLV as specified in OLSRv2 control message, VALIDITY_TIME and INTERVAL_TIME, detailed in
Table 2. this section.
+-------------+-------------------------------------+---------------+ 6.1.1 VALIDITY_TIME TLV
| TLV Type | TLV Value | Default Value |
+-------------+-------------------------------------+---------------+ All OLSRv2 messages specified in this specification MUST include a
| Willingness | willingness to be selected as MPR. | WILL_DEFAULT | VALIDITY_TIME TLV, specifying for how long a node may, upon receiving
+-------------+-------------------------------------+---------------+ a message, consider the message content to be valid. The validity
time of a message MAY be specified to depend on the distance from the
originator (i.e. the <hop-count> field in the message header as
defined in [4]). Thus, the VALIDITY_TIME TLV contains a sequence of
pairs (time, hop-limit) in increasing hop-limit order, followed by a
default value.
Thus, an instance of a VALIDITY_TIME TLV could have the following
value:
<t_1><hl_1><t_2><hl_2> ... <t_i><hl_i> .... <t_n><hl_n><t_default>
Which would mean that the message, carrying this VALIDITY_TIME TLV,
would have the following validity times:
o <t_1> in the interval from 0 (exclusive) to <hl_1> (inclusive)
hops away from the originator;
o <t_i> in the interval from <hl_(i-1)> (exclusive) to <hl_i>
(inclusive) hops away from the originator; and
o <t_default> in the interval from <hl_n> (exclusive) to 255>
(inclusive) hops away from the originator.
The VALIDITY_TIME message TLV specification is given in Table 2.
VALIDITY_TIME message TLV specification overview
+----------------+--------+-------------------+---------------------+
| Name | Type | Length | Value |
+----------------+--------+-------------------+---------------------+
| VALIDITY_TIME | TBD | (2*n+1) * 8 bits | {<time><hoplimit>}* |
| | | | <t_default> |
+----------------+--------+-------------------+---------------------+
Table 2 Table 2
where <n> is the number of (time, hop_limit) pairs in the TLV, and
where <time> and <t_default> are represented as specified in section
Section 16.
6.1.2 INTERVAL_TIME TLV
OLSRv2 messages of a given type MAY include an INTERVAL_TIME message
TLV, specifying the interval at which messages of this type are being
generated by the originator node.
The INTERVAL_TIME message TLV specification is given in Table 3.
INTERVAL_TIME TLV specification overview
+----------------+--------+-------------------+---------------------+
| Name | Type | Length | Value |
+----------------+--------+-------------------+---------------------+
| INTERVAL_TIME | TBD | 8 bits | <time> |
+----------------+--------+-------------------+---------------------+
Table 3
where <time> is the time between two successive emissions of messages
of the type, represented as specified in section Section 16.
6.2 Local Interface Blocks
The first address block, plus following TLV block in a HELLO or TC
message is known as a Local Interface Block. A Local Interface Block
is not distinguished in any way other than by being the first address
block in the message.
A Local Interface Block contains the addresses of all of the
interfaces of the originating node that support OLSRv2 and
participate in the MANET, using the standard <address-block> syntax
from [4]. In a TC message this is sufficient; in a HELLO message,
those addresses, if any, which correspond to interfaces other than
that on which the HELLO message is sent must have a corresponding
OTHER_IF TLV. In this case (only) this OTHER_IF TLV SHALL NOT have a
<value> field.
Note that a Local Interface Block may include more than one address
for each interface, and hence in a HELLO message may contain more
than one address without an OTHER_IF TLV.
6.3 HELLO Messages
A HELLO message MUST contain:
o a message TLV VALIDITY_TIME Section 6.1.1
o one or more address blocks with associated address block TLVs
The first (mandatory) address block is a Local Interface Block, as
specified in Section 6.2. Other (optional) address blocks contain
1-hop neighbors' interface addresses.
A HELLO message MAY optionally contain:
o a message TLV INTERVAL_TIME as specified in Section 6.1.2
o a message TLV WILLINGNESS, as specified in Section 6.3.1
6.3.1 HELLO Message: Message TLVs
In a HELLO message, a node MAY include a message TLV as specified in
Table 4.
VALIDITY_TIME message TLV specification overview
+----------------+--------+-------------------+---------------------+
| Name | Type | Length | Value |
+----------------+--------+-------------------+---------------------+
| WILLINGNESS | TBD | 8 bits | <The node's |
| | | | willingness to be |
| | | | selected as MPR> |
+----------------+--------+-------------------+---------------------+
Table 4
A node's willingness to be selected as MPR ranges from WILL_NEVER
(indicating that a node MUST NOT be selected as MPR by any node) to
WILL_ALWAYS (indicating that a node MUST always be selected as MPR.
If a node does not advertise a Willingness TLV in HELLO messages, the If a node does not advertise a Willingness TLV in HELLO messages, the
node MUST be assumed to have a willingness of WILL_DEFAULT. node MUST be assumed to have a willingness of WILL_DEFAULT.
9.2 HELLO Message: Address Blocks and Address TLVs 6.3.2 HELLO Message: Address Blocks TLVs
For each OLSRv2 interface a node MUST generate a HELLO message with HELLO message address block TLV specification overview
address blocks and address TLVs according to Table 3.
+----------------+--------+-------------------+---------------------+
| Name | Type | Length | Value |
+----------------+--------+-------------------+---------------------+
| LINK_STATUS | TBD | 8 bits | One of HEARD, |
| | | | SYMMETRIC, LOST. |
| | | | |
| MPR | TBD | 0 bits | No value, i.e. |
| | | | novalue bit (see |
| | | | [4]) set |
| | | | |
| OTHER_IF | TBD | 0 or 8 bits | In a Local |
| | | | Interface Block |
| | | | none, otherwise |
| | | | either of SYMMETRIC |
| | | | or LOST |
+----------------+--------+-------------------+---------------------+
Table 5
6.4 TC Messages
A TC message MUST contain:
o a message TLV VALIDITY_TIME Section 6.1.1
o a message TLV CONTENT_SEQUENCE_NUMBER [4]
o one or more address blocks with associated address block TLVs.
The first (mandatory) address block is a Local Interface Block, as
specified in Section 6.2. Other (optional) address blocks contain
1-hop neighbors' interface addresses and/or host or network addresses
for which this node may act as a gateway. In the latter case they
may use PREFIX_LENGTH TLV(s) as specified in [4].
A TC message MAY optionally contain:
o a message TLV INTERVAL_TIME as specified in Section 6.1.2
7. HELLO Message Generation
An OLSRv2 HELLO message is composed of a set of message TLVs,
describing general properties of the message and the node emitting
the HELLO, and a set of address blocks (with associated TLV sets),
describing the links and their associated properties.
OLSRv2 HELLO messages are generated and transmitted per interface,
i.e. different HELLO messages are generated and transmitted per
OLSRv2 interface of a node.
OLSRv2 HELLO messages are generated and transmitted periodically,
with a default interval between two consecutive HELLO emissions on
the same interface of HELLO_INTERVAL.
This section specifies the requirements, which HELLO message
generation MUST fulfill. An example algorithm is proposed in
Appendix B.1.
For each OLSRv2 interface a node MUST generate a HELLO message with a
Local Interface Block as the first address block, as specified in
Section 6.2, followed by address blocks and address TLVs according to
Table 6.
+---------------------------+---------------------------------------+ +---------------------------+---------------------------------------+
| The set of neighbor | TLV (Type = Value) | | The set of neighbor | TLV(s) (Type = Value) |
| interfaces which are.... | | | interfaces which are ... | |
+---------------------------+---------------------------------------+ +---------------------------+---------------------------------------+
| HEARD over the interface | (Link Status=HEARD); | | HEARD, but not SYMMETRIC | LINK_STATUS=HEARD |
| over which the HELLO is | (Interface=TransmittingInterface) | | over the interface over | |
| being transmitted | | | which the HELLO message | |
| is being transmitted | |
| | | | | |
| SYMMETRIC over the | (Link Status=SYMMETRIC); | | SYMMETRIC over the | LINK_STATUS=SYMMETRIC |
| interface over which the | (Interface=TransmittingInterface) | | interface over which the | |
| HELLO is being | | | HELLO message is being | |
| transmitted | | | transmitted | |
| | | | | |
| LOST over the interface | (Link Status=LOST); | | LOST over the interface | LINK_STATUS=LOST |
| over which the HELLO is | (Interface=TransmittingInterface) | | over which the HELLO | |
| being transmitted | | | message is being | |
| transmitted | |
| | | | | |
| SYMMETRIC over ANY | (Link Status=SYMMETRIC); | | Not SYMMETRIC over the | OTHER_IF=SYMMETRIC |
| interface of the node | (Interface=Other) | | interface over which the | |
| other than the interface | | | HELLO message is being | |
| over which the HELLO is | | | transmitted, but | |
| being transmitted | | | SYMMETRIC over one or | |
| more other interfaces of | |
| the node | |
| | | | | |
| selected as MPR for the | (Link Status=SYMMETRIC); | | Not SYMMETRIC over any | OTHER_IF=LOST |
| interface over which the | (Interface=TransmittingInterface); | | interface or LOST over | |
| HELLO is transmitted | (MPR Selection=True) | | the interface over which | |
| the HELLO message is | |
| being transmitted, but | |
| previously reported as | |
| OTHER_IF=SYMMETRIC and | |
| still HEARD or LOST over | |
| one or more interfaces of | |
| the node other than the | |
| interface over which the | |
| HELLO message is being | |
| transmitted | |
| | |
| Selected as MPR for the | MPR |
| interface over which the | |
| HELLO message is | |
| transmitted | |
+---------------------------+---------------------------------------+ +---------------------------+---------------------------------------+
Table 3 Table 6
10. HELLO Message Processing In order that an address can be reported as OTHER_IF=LOST by a node
with more than one interface participating in the MANET, such a node
MAY maintain an Other Interface Set of addresses for each interface.
The Other Interface Set for an interface is updated when a HELLO
message is to be transmitted over that interface, and used to
determine which addresses are reported as OTHER_IF=LOST in that
message. The Other Interface Set of addresses is updated and used as
follows:
1. Each address that the HELLO message is to include with a
corresponding TLV with Type=LINK_STATUS and Value=SYMMETRIC is
removed from the set.
2. Each address that the HELLO message is to include with a
corresponding TLV with Type=OTHER_IF and Value=SYMMETRIC is added
to the set if not already present.
3. Each other address in the set (not included in the HELLO message
with a corresponding TLV with Type=OTHER_IF and Value=SYMMETRIC)
1. Is removed if the HELLO message is to include it with a
corresponding TLV with Type=LINK_STATUS and Value=LOST.
2. Is removed if it is not HEARD or LOST over an interface other
than the interface over which the HELLO message is to be
transmitted.
3. Otherwise is included in the HELLO message with a TLV with
Type=OTHER_IF and Value=LOST. (Note that the address may
also have a corresponding TLV with Type=LINK_STATUS and
Value=HEARD if appropriate.)
7.1 HELLO Message: Transmission
Messages are retransmitted in the packet/message format specified by
[4] with the All-OLSRv2-Multicast address as destination IP address
and with a TTL=1.
8. HELLO Message Processing
Upon receiving a HELLO message, a node will update its local link Upon receiving a HELLO message, a node will update its local link
information base according to the specification given in this information base according to the specification given in this
section. section.
For the purpose of this section, please notice the following: For the purpose of this section, please notice the following:
o the "validity time" of a message is calculated from the Vtime o the "validity time" of a message is calculated from the VALIDITY-
field of the message header as specified in Section 17; TIME TLV of the message as specified in Section 6.1.1;
o the "originator address" refers to the address, contained in the o the "Source Address" is the source address as indicated by the
"originator address" field of the OLSRv2 message header specified source interface of the IP datagram containing the message;
in Section 3.1;
o a HELLO message MUST neither be forwarded nor be recorded in the o a HELLO message MUST neither be forwarded nor be recorded in the
duplicate set; Processing and Forwarding Repositories;
o the address blocks considered exclude the originator address o the address blocks considered exclude the Local Interface Block,
block, unless explicitly specified; unless explicitly specified;
o a HELLO message is valid when, for each address listed in the o a HELLO message is only valid when, for each address listed in the
address blocks: address blocks:
* the address is associated with at least one TLV with Type=Link * the address is associated with a TLV with Type=Link Status OR a
Status, AND TLV with Type=Other Interface Status OR both, the latter either
when the TLV with Type=Link Status has Value=HEARD, or when the
* the address is associated with at least one TLV with the TLV with Type=Link Status has Value=LOST and the TLV with
Type=Interface, AND Type=Other Interface Status has Value=SYMMETRIC, AND
* all the TLVs with identical type, that the address is
associated with, have identical values (e.g.
Interface=TransmittingInterface is not compatible with
Interface=Other for instance), AND
* if the address is associated with one TLV "MPR Selection=True", * if the address is associated with a TLV with Type=MPR, then it
then it MUST be associated also with one TLV "Link MUST also be associated with a TLV with Type=Link Status and
Status=SYMMETRIC". Value=SYMMETRIC.
Invalid HELLO messages are not processed. Invalid HELLO messages are not processed.
10.1 Populating the Link Set 8.1 Populating the Link Set
Upon receiving a HELLO message, a node SHOULD update its Link Set Upon receiving a HELLO message, a node SHOULD update its Link Set
with the information contained in the HELLO. Thus, for each address, with the information contained in the HELLO. Thus, for the Local
listed in the HELLO message address blocks (see Section 6): Interface Block (see Section 6.2) the Neighbor Address Association
Set is updated as specified by Section 13. For each address, listed
in the subsequent HELLO message address blocks (see Section 6):
1. if there exists no link tuple with 1. if there exists no link tuple with:
* L_neighbor_iface_addr == Source Address * L_neighbor_iface_addr == Source Address
a new tuple is created with a new tuple is created with
* L_neighbor_iface_addr = Source Address; * L_neighbor_iface_addr = Source Address;
* L_local_iface_addr = Address of the interface which * L_local_iface_addr = Address of the interface which
received the HELLO message; received the HELLO message;
* L_SYM_time = current time - 1 (expired); * L_SYM_time = current time - 1 (expired);
* L_time = current time + validity time. * L_time = current time + validity time.
skipping to change at page 32, line 20 skipping to change at page 35, line 15
* L_neighbor_iface_addr = Source Address; * L_neighbor_iface_addr = Source Address;
* L_local_iface_addr = Address of the interface which * L_local_iface_addr = Address of the interface which
received the HELLO message; received the HELLO message;
* L_SYM_time = current time - 1 (expired); * L_SYM_time = current time - 1 (expired);
* L_time = current time + validity time. * L_time = current time + validity time.
2. The tuple (existing or new) with: 2. The tuple (existing or new) with L_neighbor_iface_addr == Source
Address is then modified as follows:
* L_neighbor_iface_addr == Source Address
is then modified as follows:
2. if the node finds the address of the interface, which 1. if the node finds the address of the interface, which
received the HELLO message, in one of the address blocks received the HELLO message, in one of the address blocks
included in message, then the tuple is modified as follows: included in message, then the tuple is modified as follows:
1. if the occurrence of L_local_iface_addr in the HELLO 1. if the occurrence of L_local_iface_addr in the HELLO
message is associated with a TLV with Type="Link Status" message is:
and value=LOST, and it is also associated with an TLV
with Type="Interface" and Value="TransmittingInterface" - associated with a TLV with (Type == "LINK_STATUS",
Value == LOST)
then then
- L_SYM_time = current time - 1 (i.e., expired) - L_SYM_time = current time - 1 (i.e., expired)
2. else if the occurrence of L_local_iface_addr in the HELLO 2. else if the occurrence of L_local_iface_addr in the HELLO
message is associated with a TLV with Type="Link Status" message:
and value=SYMMETRIC or HEARD, and it is also associated
with an TLV with Type="Interface" and - is associated with:
Value="TransmittingInterface" then
o a TLV with (Type == "LINK_STATUS", Value ==
SYMMETRIC);
OR;
o a TLV with (Type == "LINK_STATUS", Value == HEARD);
then
- L_SYM_time = current time + validity time, - L_SYM_time = current time + validity time,
- L_time = L_SYM_time + NEIGHB_HOLD_TIME. - L_time = L_SYM_time + L_HOLD_TIME.
3. L_ASYM_time = current time + validity time; 2. L_ASYM_time = current time + validity time;
3. L_time = max(L_time, L_ASYM_time)
4. L_time = max(L_time, L_ASYM_time)
3. Additionally, the willingness field is updated as follows: 3. Additionally, the willingness field is updated as follows:
If a TLV with Type="Willingness" is present in the message If a TLV with Type=="WILLINGNESS" is present in the message
TLVs, then TLVs, then:
+ L_willingness = Value of the TLV + L_willingness = Value of the TLV
otherwise: otherwise:
+ L_willingness = WILL_DEFAULT + L_willingness = WILL_DEFAULT
The rule for setting L_time is the following: a link losing its The rule for setting L_time is the following: a link losing its
symmetry SHOULD still be advertised in HELLOs (with the remaining symmetry SHOULD still be advertised in HELLOs (with the remaining
status as defined by Table 1) during at least the duration of the status as defined by Table 1) during at least the duration of the
"validity time". This allows neighbors to detect the link breakage. "validity time". This allows neighbors to detect the link breakage.
Thus, the Local Link Set must maintain information, also about LOST
links, until the link would otherwise expire.
10.2 Populating the 2-Hop Neighbor Set 8.2 Populating the 2-Hop Neighbor Set
Upon receiving a HELLO message from a symmetric neighbor interface, a Upon receiving a HELLO message from a symmetric neighbor interface, a
node SHOULD update its 2-hop Neighbor Set. node SHOULD update its 2-hop Neighbor Set.
If the Originator Address is the L_local_iface_addr from a link tuple If the Source Address is the L_local_iface_addr from a link tuple
included in the Link Set with L_STATUS equal to SYMMETRIC (in other included in the Link Set with L_STATUS equal to SYMMETRIC (in other
words: if the Originator Address is a symmetric neighbor interface) words: if the Source Address is a symmetric neighbor interface) then
then the 2-hop Neighbor Set SHOULD be updated as follows: the 2-hop Neighbor Set SHOULD be updated as follows:
1. for each address (henceforth: 2-hop neighbor address), listed in 1. for each address (henceforth: 2-hop neighbor address), listed in
the HELLO message with a Link Status TLV equal to SYMMETRIC: the HELLO message:
1. if the 2-hop neighbor address is an address of the receiving 1. if the 2-hop neighbor address is an interface address of the
node: receiving node silently discard the 2-hop neighbor address
(in other words: a node is not its own 2-hop neighbor).
silently discard the 2-hop neighbor address. 2. else if the 2-hop neighbor address has a TLV with:
(in other words: a node is not its own 2-hop neighbor). + (Type=LINK_STATUS, Value == SYMMETRIC); OR
2. Otherwise, a 2-hop tuple is created with: + (Type=OTHER_IF, Value=SYMMETRIC);
+ N_local_iface_addr = address of the interface over a 2-hop tuple is created with:
+ N2_local_iface_addr = address of the interface over
which the HELLO message was received; which the HELLO message was received;
+ N_neighbor_iface_addr = Originator Address of the message; + N2_neighbor_iface_addr = source address of the message;
+ N_2hop_iface_addr = 2-hop neighbor address; + N2_2hop_iface_addr = 2-hop neighbor address;
+ N_time = current time + validity time. + N2_time = current time + validity time.
This tuple may replace an older similar tuple with same This tuple may replace an older similar tuple with the same
N_local_iface_addr, N_neighbor_iface_addr and N2_local_iface_addr, N2_neighbor_iface_addr and
N_2hop_iface_addr values. N2_2hop_iface_addr values.
10.3 Populating the Relay Set 3. else if the 2-hop neighbor address has a TLV with:
+ (Type == LINK_STATUS, Value == LOST); OR
+ (Type == OTHER_IF, Value == LOST),
then any 2-hop tuple with:
+ N2_local_iface_addr equal to the address of the interface
over which the HELLO message was received; AND
+ N2_neighbor_iface_addr equal to the source address of the
message; AND
+ and N2_2hop_iface_addr equal to the 2-hop neighbour
address
MUST be deleted.
8.3 Populating the MPR Selector Set
Upon receiving a HELLO message, if a node finds one of its own Upon receiving a HELLO message, if a node finds one of its own
interface addresses, listed with an MPR TLV (indicating that the interface addresses, listed with an MPR TLV (indicating that the
originator node has selected one of the receiving nodes interfaces as originator node has selected one of the receiving node's interfaces
MPR), the Relay Set SHOULD be updated as follows: as MPR), the MPR Selector Set SHOULD be updated as follows:
For each address in the originator address block: For each address in the Local Interface Block of the received
message:
1. If there exists no Relay tuple with: 1. If there exists no MPR Selector tuple with:
* RS_if_addr == that address * MS_if_addr == that address
then a new tuple is created with: then a new tuple is created with:
* RS_if_addr = that address * MS_if_addr = that address
2. The tuple (new or otherwise) with 2. The tuple (new or otherwise) with:
* RS_if_addr == that address * MS_if_addr == that address
is then modified as follows: is then modified as follows:
* RS_time = current time + validity time. * MS_time = current time + validity time.
Relay tuples are removed upon expiration of RS_time, or upon link MPR Selector tuples are removed upon expiration of MS_time, or upon
breakage as described in Section 10.4. link breakage as described in Section 8.4.
10.4 Neighborhood and 2-hop Neighborhood Changes 8.4 Neighborhood and 2-Hop Neighborhood Changes
A change in the neighborhood is detected when: A change in the neighborhood is detected when:
o The L_SYM_time field of a link tuple expires. This is considered o Link Loss: the L_SYM_time field of a link tuple expires (either
as a link loss. due to time out, or as a result of processing a TLV (Type ==
LINK_STATUS, Value == LOST)).
o A new link tuple is inserted in the Link Set with a non expired o Link Acquisition: a new link tuple is inserted in the Link Set
L_SYM_time or a tuple with expired L_SYM_time is modified so that with a non expired L_SYM_time or a tuple with expired L_SYM_time
L_SYM_time becomes non-expired. This is considered as a link is modified so that L_SYM_time becomes non-expired. This is
appearance if there was previously no such link tuple. considered as a link acquisition if there was previously no such
link tuple.
A change in the 2-hop neighborhood is detected when a 2-hop neighbor o Neighbor Loss: all links to a neighbor node have have been lost.
tuple expires or is deleted according to section Section 10.2.
A change in the 2-hop neighborhood is detected when a 2-Hop Neighbor
Tuple expires or is deleted according to section Section 8.2.
The following processing occurs when changes in the neighborhood or The following processing occurs when changes in the neighborhood or
the 2-hop neighborhood are detected: the 2-hop neighborhood are detected:
o In case of link loss, all 2-hop tuples with o In case of link loss, all 2-Hop Neighbor Tuples with
* N_local_iface_addr == interface address of the node where the * N2_local_iface_addr == interface address of the node where the
link was lost link was lost
* N_neighbor_iface_addr == interface address of the neighbor * N2_neighbor_iface_addr == interface address of the neighbor
MUST be deleted. MUST be deleted.
o In case of neighbor interface loss, if there exists no link left o In case of neighbor loss, all MPR Selector tuples associated with
to this neighbor node, all MPR selector tuples associated with
that neighbor are deleted. More precisely: that neighbor are deleted. More precisely:
* If there exists an entry in the neighbor address iface * all MPR selector tuples with MS_iface_addr == interface address
association set where of the neighbor MUST be deleted, along with any interface
addresses associated in the Neighbor Address Association Set.
+ I_neighbor_iface_addr_list includes the
N_neighbor_iface_addr of the lost link tuple
AND such has there exists a link tuple such has
+ L_neighbor_iface_addr is one of the addresses in
I_neighbor_iface_addr_list
then a link to the neighbor interface was lost, but the
neighbor node itself is still a neighbor (with another link),
and the mpr selector set is not changed,
* otherwise, the neighbor node is lost, and all MPR selector
tuples with MS_iface_addr == interface address of the neighbor
MUST be deleted, along with any interface address associated in
the neighbor address iface association set.
o The MPR set MUST be re-calculated when a link appearance or loss o The MPR Set MUST be re-calculated when a link acquisition or loss
is detected, or when a change in the 2-hop neighborhood is is detected, or when a change in the 2-hop neighborhood is
detected. detected.
o An additional HELLO message MAY be sent when the MPR set changes. o An additional HELLO message MAY be sent when the MPR Set or the
neighborhood changes.
Additionally, proper update of the sets describing local topology Additionally, proper update of the sets describing local topology
should be made when a neighbor association address tuple has a list should be made when a Neighbor Association Address Tuple has a list
of addresses which is modified. of addresses which is modified.
11. TC Message Generation 9. TC Message Generation
An OLSRv2 TC message is composed as described in Section 3.2: a set TC messages are, in OLSRv2, transmitted with the purpose of
of message TLVs, describing general properties of the message and the populating the Topology Set, the Attached Network Set and the
node emitting the TC, and a set of address blocks (with associated Neighborhood Address Association Set:
TLV sets), describing the links and their associated properties.
OLSRv2 TC messages are generated and transmitted per node, i.e. the o Topology Discovery: ensure that information is present in each
same TC messages are generated and transmitted on all OLSRv2 node describing all destinations and a sufficient subset of links
interfaces of a node. in order to provide least-hop paths to all destinations.
OLSRv2 TC messages are generated and transmitted periodically, with a o Multiple Interface Declaration: ensure that nodes, up to two hops
default interval between two consecutive TC emissions by the same away from the originator, are aware of the interface configuration
node of TC_INTERVAL. of the originator node.
11.1 TC Message: Message TLVs Thus, nodes with a non-empty Advertised Neighbor Set, or which are
specifically reporting an empty Advertised Neighbor Set (for a period
of T_HOLD_TIME following reporting a non-empty Advertised Neighbor
Set) or with more than one interface which supports OLSRv2 and
participates in the MANET, MUST generate TC messages, according to
the following:
Each OLSRv2 node, selected as MPR (i.e. a node with a non-empty MPR 1. The node includes, in its first address block of the TC message,
Selector Set) MUST generate TC messages with message TLVs according a Local Interface Block as specified in Section 6.2
to the following table:
+----------------------+----------------------+---------------------+ 2. If the node has a non-empty Advertised Neighbor Set or is
| TLV Type | TLV Value | Default Value | specifically reporting an empty Advertised Neighbor Set, or it
+----------------------+----------------------+---------------------+ has a one or more attached non-OLSRv2 networks, to which it
| Content Seq. no | <the current value | N/A | wishes to advertise routes to the network, it furthermore:
| | of the ASSN of the | |
| | node> | |
+----------------------+----------------------+---------------------+
Table 4 1. includes a message TLV (Type = CONTENT_SEQ_NUMBER TLV, Value
= the Advertised Neighbor Set Sequence Number);
11.2 TC Message: Address Blocks and Address TLVs 2. includes address blocks, containing its Advertised Neighbor
Set (if non-empty);
Each OLSRv2 node, selected as MPR (i.e. a node with a non-empty MPR 3. includes address blocks and PREFIX_LENGTH TLVs, describing
Selector Set) MUST generate TC messages with address blocks and attached non-OLSRv2 networks;
address TLVs according to the following table:
+---------------------------------+---------------------------------+ 4. sets the TTL of the message to the network diameter.
| Addresses | TLVs |
+---------------------------------+---------------------------------+
| The set of neighbor interfaces, | |
| which have selected the node as | |
| MPR | |
+---------------------------------+---------------------------------+
Table 5 3. Otherwise, the node:
12. TC Message Processing 1. sets the TTL of the message to 2.
Upon receiving a TC message, a node will update its topology OLSRv2 TC messages are generated and transmitted periodically, with a
default interval between two consecutive TC emissions by the same
node of TC_INTERVAL.
9.1 TC Message: Transmission
Messages are retransmitted in the packet/message format specified by
[4] with the All-OLSRv2-Multicast address as destination IP address
and is forwarded according to the specification in section
Section 4.4. If fragmentation is necessary, a FRAGMENTATION TLV MUST
be included, and each fragment SHOULD be flagged as partially or
wholly self contained as specified in [4].
10. TC Message Processing
Upon receiving a TC message, a node MUST update its topology
information base according to the specification given in this information base according to the specification given in this
section. section.
For the purpose of this section, please notice the following: For the purpose of this section, note the following:
o the "validity time" of a message is calculated from the Vtime o the "validity time" of a message is calculated from the
field of the message header as specified in Section 17; VALIDITY_TIME message TLV according to the specification in
Section 16;
o the "originator address" refers to the address, contained in the o the "originator address" refers to the address, contained in the
"originator address" field of the OLSRv2 message header specified "originator address" field of the OLSRv2 message header specified
in Section 3.1; in [4];
o the ASSN of the node, originating the TC message, is recovered as o the ASSN of the node, originating the TC message, is recovered as
the value of the Content Seq. no message TLV in the TC message; the value of the CONTENT_SEQ_NO message TLV in the TC message, if
any.
Upon receiving a TC message, a node SHOULD update its topology set as 10.1 Checking Freshness & Validity of a TC message
follows:
1. If the sender interface (NB: not originator) address of this In order to be able to ensure that only valid and fresh information
message is not in the symmetric 1-hop neighborhood of this node, is recorded in the Topology Set, each node maintains an ASSN History
the message MUST be discarded; Set, recording the highest ASSN received from each node in the
network, in the form of a "ASSN History Tuples":
2. otherwise, if the TC message does not contain a message-TLV of (AS_Address, AS_seq, AS_time)
type Content Seq. no., the message SHOULD be discarded;
3. otherwise, if there exist some tuple in the topology set where: AS_Address is the originator address of a received TC message;
T_last_iface_addr == originator address in the message AND AS_seq is the highest received ASSN seen in a TC message from
AS_Address;
T_seq > ASSN; AS_time is the time at which this tuple expires and MUST be removed.
then the TC message SHOULD be discarded. Upon receiving a TC message, a node MUST check if the TC message is
fresh and valid as follows:
4. The topology set is then updated in two steps: 1. If the TC message has more than one address block (i.e. not just
a Local Interface Block) and does not contain a message-TLV of
type CONTENT_SEQ_NO. then the message MUST be discarded;
1. any topology tuple where: 2. otherwise, if the ASSN History Set contains a tuple where:
T_last_iface_addr == originator address in the message AND * AS_Address == Originator Address of the TC message; AND
* AS_seq > the ASSN recovered from the TC message,
then the TC message MUST be discarded;
3. otherwise a tuple is inserted in the ASSN History Set with:
* AS_Address = Originator Address in the message;
* AS_seq = The ASSN, extracted from the message;
* AS_time = current time + AS_HOLD_TIME.
possibly replacing an existing tuple with the same AS_Address.
10.2 Updating the Topology Set
A node SHOULD update its Topology Set as follows:
1. For each address, LocAddr, from the Local Interface Block in the
TC message:
1. For each advertised neighbor address, listed in an address
block other than the Local Interface Block in the TC message,
which does NOT have an associated PREFIX_LENGTH TLV:
1. if there exists a tuple in the Topology Set where:
T_dest_iface_addr == advertised neighbor address; AND
T_last_iface_addr == LocAddr.
then the tuple is updated as follows:
T_time = current time + validity time
T_seq = ASSN
2. Otherwise, a new topology tuple is created with:
T_dest_iface_addr = advertised neighbor address, AND
T_last_iface_addr = LocAddr; AND
T_seq = ASSN.
10.3 Purging Old Entries from the Topology Set
Old entries from the Topology Set MUST be purged as follows:
1. For each address, LocAddr, from the Local Interface Block in the
TC message:
1. all tuples in the Topology Set where:
T_last_iface_addr == LocAddr AND
T_seq < ASSN T_seq < ASSN
SHOULD be removed. MUST be removed.
2. For each address, listed in the TC message: 10.4 Updating the Attached Networks Set
1. if there exists a tuple in the topology set where: A node SHOULD update its Attached Networks Set as follows:
T_dest_iface_addr == advertised neighbor address, AND 1. For each address, LocAddr, from the Local Interface Block in the
TC message:
T_last_iface_addr == originator address; 1. For each advertised neighbor address, listed in an address
block other than the Local Interface Block in the TC message,
which does have an associated PREFIX_LENGTH TLV:
1. if there exists a tuple in the Attached Networks Set
where:
AN_net_addr == advertised neighbor address; AND
AN_prefix_length == the prefix length as recoveredf from
the PREFIX_LENGTH TLV; AND
AN_gw_addr == LocAddr.
then the tuple is updated as follows: then the tuple is updated as follows:
T_time = current time + validity time. AN_time = current time + validity time
(Note that necessarily: T_seq == ASSN). AN_seq = ASSN
2. Otherwise, a new topology tuple is created with: 2. Otherwise, a new topology tuple is created with:
T_dest_iface_addr == advertised neighbor main address, AN_net_addr == advertised neighbor address; AND
AND
T_last_iface_addr == originator address in the message AN_prefix_length == the prefix length as recoveredf from
AND the PREFIX_LENGTH TLV; AND
T_seq == ASSN; AN_gw_addr == LocAddr.
13. MA Message Generation AN_time = current time + validity time
An OLSRv2 MA message is composed as described in Section 3.2: a set AN_seq = ASSN
of message TLVs, describing general properties of the message and the
node emitting the MA, and a set of address blocks (with associated
TLV sets). These address blocks MUST list all addresses of the node
which are participating in the OLSRv2 network. Other addresses of
the node MAY also be included.
An OLSRv2 MA message describes the set of addresses, associated to a 10.5 Purging Old Entries from the Attached Network Set
given node. Nodes with a single address SHOULD NOT generate MA
messages. Nodes with multiple addresses, participating in the OLSRv2
network SHOULD generate MA messages.
OLSRv2 MA messages are generated and transmitted per node, i.e. the TBD
same MA messages are generated and transmitted on all OLSRv2
interfaces of a node.
OLSRv2 TC messages are generated and transmitted periodically, with a 10.6 Processing Unfragmented TC Messages
default interval between two consecutive MA emissions by the same
node of TC_INTERVAL.
14. MA Message Processing If an unfragmented TC message, i.e. a TC message without a
FRAGMENTATION message TLV, is received, it MUST be processed as
follows:
Upon receiving a MA message the node SHOULD update its Neighborhood 1. Verify freshness and validity of the TC message (see
Address Association Set as follows: Section 10.1). If the message is not discarded, then continue;
1. All neighborhood address association tuples where 2. Update the Topology Set (see Section 10.2);
* I_neighbor_addr_list contains at least one address which is 3. Purge old entries from the Topology Set (see Section 10.3);
listed in the received MA message,
SHOULD be removed, and a new neighborhood address association 4. Update the Attached Networks Set (see Section 10.4;
tuple SHOULD be created with:
* I_neighbor_addr_list = list of all addresses contained in the 5. Purge old entries from the Attached Networks Set (see
received MA message; Section 10.5);
* I_time = current time + validity time. 6. Update the Neighborhood Address Association Set (see Section 13).
15. Routing Table Calculation 10.7 Processing Partially or Wholly Self-Contained Fragmented TC
Messagess
A node records a set of "routing tuples": If a TC message contains a FRAGMENTATION message TLV which indicates
that the fragment is a partially or wholly self-contained message,
then the following processing SHOULD be carried out immediately upon
receipt of each received fragment (if not then it MUST be carried out
for each fragment once all fragments have been received):
(R_dest_iface_addr, R_next_iface_addr, R_dist, R_iface_addr) 1. Verify freshness and validity of the TC message (see
Section 10.1). If the message is not discarded, then continue;
2. Update the Topology Set (see Section 10.2);
describing the next hop and distance of the path to each destination 3. Update the Neighborhood Address Association Set (see Section 13).
in the network for which a route is known.
R_dest_iface_addr is the interface address of the destination node; 4. Update the Attached Networks Set (see Section 10.4;
R_next_iface_addr is the interface address of the "next hop" on the Once all fragments have been received, the following processing MUST
path towards R_dest_iface_addr; be carried out once:
R_dist is the number of hops on the path to R_dest_iface_addr; 1. Purge old entries from the Topology Set (see Section 10.3);
R_iface_addr is the address of the local interface over which a 2. Purge old entries from the Attached Networks Set (see
packet MUST be sent to reach R_next_iface_addr. Section 10.5);
In a node, the set of routing tuples is denoted the "routing set". 11. Populating the MPR Set
The routing set is updated when a change (an entry appearing/ Each node MUST select, from among its one-hop neighbors, a subset of
nodes as MPRs. This subset MUST be selected such that a message
transmitted by the node, and retransmitted by all its MPR nodes, will
be received by all nodes 2 hops away.
Each node selects its MPR Set individually, utilizing the information
in the Link Set, 2-Hop Neighbor Set and Neighborhood Address
Association Set. Initially these sets will be empty, as will be the
MPR Set. A node SHOULD recalculate its MPR Set when a relevant change
is made to the Link Set, 2-Hop Neighbor Set or Neighborhood Address
Association Set.
More specifically, a node MUST calculate MPRs per interface, the
union of the MPR Sets of each interface make up the MPR Set for the
node.
MPRs are used to flood control messages from a node into the network
while reducing the number of retransmissions that will occur in a
region. Thus, the concept of MPR is an optimization of a classical
flooding mechanism. While it is not essential that the MPR Set is
minimal, it is essential that all strict 2-hop neighbors can be
reached through the selected MPR nodes. A node MUST select an MPR
Set such that any strict 2-hop neighbor is covered by at least one
MPR node. A node MAY select additional MPRs beyond the minimum set.
Keeping the MPR Set small ensures that the overhead of OLSRv2 is kept
at a minimum.
Appendix A contains an example heuristic for selecting MPRs.
12. Populating Derived Sets
The Relay Set and the Advertised Neighbor Set of OLSRv2 are denoted
derived sets, since updates to these sets are not directly a function
of message exchanges, but rather are derived from updates to other
sets, in particular the MPR Selector Set.
12.1 Populating the Relay Set
The Relay Set contains the set of neighbor addresses, for which a
node is supposed to relay broadcast traffic. This set SHOULD at
least contain the addresses of the MPR Selector set (i.e. all
addresses, associated with a MPR selector through the Neighborhood
Address Association Set). This set MAY contain additional neighbor
addresses.
12.2 Populating the Advertised Neighbor Set
The Advertised Neighbor Set contains the set of neighbor addresses,
to which a node advertises links through TC messages. This set
SHOULD at least contain the addresses of the MPR Selector Set (i.e.
all addresses, associated with a MPR selector through the
Neighborhood Address Association Set). This set MAY contain
additional neighbor addresses.
Each time an address is removed from the Advertised Neighbor Set, the
ASSN MUST be incremented. When an address is added to the Advertised
Neighbor Set, the ASSN MUST be incremented.
13. Populating the Neighborhood Address Association Set
All OLSRv2 messages containing a Local Interface Block (including
HELLO and TC messages) SHOULD be used to update the Neighborhood
Address Association Set as follows:
1. If there is a Neighborhood Address Association Tuple, any of
whose addresses are in the Local Interface Block being processed,
then discard that tuple.
2. A tuple is added to the Neighborhood Address Association Set,
where:
* NA_neighbor_addr_list = all addresses from the Local Interface
Block;
* NA_time = current time + NA_HOLD_TIME.
14. Routing Table Calculation
The Routing Set is updated when a change (an entry appearing/
disappearing) is detected in: disappearing) is detected in:
o the link set, o the Link Set,
o the neighbor address association set, o the Neighbor Address Association Set,
o the 2-hop neighbor set, o the 2-hop Neighbor Set,
o the topology set, o the Topology Set,
Updates to the routing set does not generate or trigger any messages Updates to the Routing Set does not generate or trigger any messages
to be transmitted. The state of the routing set SHOULD, however, be to be transmitted. The state of the Routing Set SHOULD, however, be
reflected in the IP routing table by adding and removing entries from reflected in the IP routing table by adding and removing entries from
the routing table as appropriate. the routing table as appropriate.
To construct the routing set of node X, a shortest path algorithm is To construct the Routing Set of node X, a shortest path algorithm is
run on the directed graph containing the arcs X -> Y where Y is any run on the directed graph containing the arcs X -> Y where Y is any
symmetric neighbor of X (with Link Type equal to SYM), the arcs Y -> symmetric neighbor of X (with Link Type equal to SYM), the arcs Y ->
Z where Y is a neighbor node with willingness different of WILL_NEVER Z where Y is a neighbor node with willingness different of WILL_NEVER
and there exists an entry in the 2-hop Neighbor set with Y as and there exists an entry in the 2-hop Neighbor Set with Y as
N_neighbor_iface_addr and Z as N_2hop_iface_addr, and the arcs U -> N2_neighbor_iface_addr and Z as N2_2hop_iface_addr, and the arcs U ->
V, where there exists an entry in the topology set with V as V, where there exists an entry in the Topology Set with V as
T_dest_iface_addr and U as T_last_iface_addr. The graph is T_dest_iface_addr and U as T_last_iface_addr. The graph is
complemented with the arcs W0 -> W1 where W0 and W1 are two addresses complemented with the arcs W0 -> W1 where W0 and W1 are two addresses
of interfaces of a same neighbor (in a neighbor address association of interfaces of a same neighbor (in a neighbor address association
tuple). tuple).
The following procedure is given as an example for (re-)calculating The following procedure is given as an example for (re-)calculating
the routing set (with a breadth-first algorithm): the Routing Set (with a breadth-first algorithm):
1. All the tuples from the routing set are removed. 1. All the tuples from the Routing Set are removed.
2. The new routing tuples are added starting with the symmetric 2. The new routing tuples are added starting with the symmetric
neighbors (h=1) as the destinations. Thus, for each tuple in the neighbors (h=1) as the destinations. Thus, for each tuple in the
link set where: Link Set where:
* L_STATUS = SYMMETRIC * L_STATUS == SYMMETRIC (L_STATUS is calculated as
indicated in Table 1)
a new routing tuple is recorded in the routing set with: a new routing tuple is recorded in the Routing Set with:
* R_dest_iface_addr = L_neighbor_iface_addr, of the link tuple; * R_dest_iface_addr = L_neighbor_iface_addr, of the link tuple;
* R_next_iface_addr = L_neighbor_iface_addr, of the link tuple; * R_next_iface_addr = L_neighbor_iface_addr, of the link tuple;
* R_dist = 1; * R_dist = 1;
* R_iface_addr = L_local_iface_addr of the link tuple. * R_iface_addr = L_local_iface_addr of the link tuple.
3. for each neighbor address association tuple, for which two 3. for each neighbor address association tuple, for which two
addresses A1 and A2 exist in I_neighbor_iface_addr_list where: addresses A1 and A2 exist in I_neighbor_iface_addr_list where:
* there exists a routing tuple with: * there exists a routing tuple with:
+ R_dest_iface_addr = A1 + R_dest_iface_addr == A1
* there is no routing tuple with: * there is no routing tuple with:
+ R_dest_iface_addr = A2 + R_dest_iface_addr == A2
then a tuple in the routing set is created with: then a tuple in the Routing Set is created with:
* R_dest_iface_addr = A2; * R_dest_iface_addr = A2;
* R_next_iface_addr = R_next_iface_addr of the route tuple of * R_next_iface_addr = R_next_iface_addr of the route tuple of
A1; A1;
* R_dist = R_dist of the route tuple of A1 (e.g. 1); * R_dist = R_dist of the route tuple of A1 (e.g. 1);
* R_iface_addr = R_iface_addr of the route tuple of A1. * R_iface_addr = R_iface_addr of the route tuple of A1.
4. for each symmetric strict 2-hop neighbor where the 4. for each symmetric strict 2-hop neighbor where the
N_neighbor_iface_addr has a willingness different from WILL_NEVER N2_neighbor_iface_addr has a willingness different from
a tuple in the routing set is created with: WILL_NEVER a tuple in the Routing Set is created with:
* R_dest_iface_addr = N_2hop_iface_addr of the 2-hop neighbor; * R_dest_iface_addr = N2_2hop_iface_addr of the 2-hop neighbor;
* R_next_iface_addr = the R_next_iface_addr of the route tuple * R_next_iface_addr = the R_next_iface_addr of the route tuple
with: with:
+ R_dest_iface_addr == N_neighbor_iface_addr of the 2-hop + R_dest_iface_addr == N2_neighbor_iface_addr of the 2-hop
tuple; tuple;
* R_dist = 2; * R_dist = 2;
* R_iface_addr = the R_iface_addr of the route tuple with: * R_iface_addr = the R_iface_addr of the route tuple with:
+ R_dest_iface_addr == N_neighbor_iface_addr of the 2-hop + R_dest_iface_addr == N2_neighbor_iface_addr of the 2-hop
tuple; tuple;
5. The new route tuples for the destination nodes h+1 hops away are 5. The new route tuples for the destination nodes h+1 hops away are
recorded in the routing table. The following procedure MUST be recorded in the routing table. The following procedure MUST be
executed for each value of h, starting with h=2 and incrementing executed for each value of h, starting with h=2 and incrementing
by 1 for each iteration. The execution will stop if no new tuple by 1 for each iteration. The execution will stop if no new tuple
is recorded in an iteration. is recorded in an iteration.
1. For each topology tuple in the topology set, if its 1. For each topology tuple in the Topology Set, if its
T_dest_iface_addr does not correspond to R_dest_iface_addr of T_dest_iface_addr does not correspond to R_dest_iface_addr of
any route tuple in the routing set AND its T_last_iface_addr any route tuple in the Routing Set AND its T_last_iface_addr
corresponds to R_dest_iface_addr of a route tuple whose corresponds to R_dest_iface_addr of a route tuple whose
R_dist is equal to h, then a new route tuple MUST be recorded R_dist is equal to h, then a new route tuple MUST be recorded
in the routing set (if it does not already exist) where: in the Routing Set (if it does not already exist) where:
+ R_dest_iface_addr = T_dest_iface_addr; + R_dest_iface_addr = T_dest_iface_addr;
+ R_next_iface_addr = R_next_iface_addr of the route tuple + R_next_iface_addr = R_next_iface_addr of the route tuple
where: where:
- R_dest_iface_addr == T_last_iface_addr - R_dest_iface_addr == T_last_iface_addr
+ R_dist = h+1; and + R_dist = h+1; and
+ R_iface_addr = R_iface_addr of the route tuple where: + R_iface_addr = R_iface_addr of the route tuple where:
- R_dest_iface_addr == T_last_iface_addr. - R_dest_iface_addr == T_last_iface_addr.
2. Several topology tuples may be used to select a next hop 2. Several topology tuples may be used to select a next hop
R_next_iface_addr for reaching the node R_dest_iface_addr. R_next_iface_addr for reaching the node R_dest_iface_addr.
When h=1, ties should be broken such that nodes with highest When h==1, ties should be broken such that nodes with highest
willingness and MPR selectors are preferred as next hop. willingness and MPR selectors are preferred as next hop.
16. Proposed Values for Constants 15. Proposed Values for 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.
16.1 Message Types 15.1 Message Intervals
o HELLOv2 = 5
o TCv2 = 6
16.2 Message Intervals
o HELLO_INTERVAL = 2 seconds o HELLO_INTERVAL = 2 seconds
o REFRESH_INTERVAL = 2 seconds o REFRESH_INTERVAL = 2 seconds
o TC_INTERVAL = 5 seconds o TC_INTERVAL = 5 seconds
16.3 Holding Times 15.2 Holding Times
o NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL o L_HOLD_TIME = 3 x HELLO_INTERVAL
o TOP_HOLD_TIME = 3 x TC_INTERVAL o N2_HOLD_TIME = 3 x REFRESH_INTERVAL
o DUP_HOLD_TIME = 30 seconds o NA_HOLD_TIME = 3 x TC_INTERVAL
16.4 Willingness o T_HOLD_TIME = 3 x TC_INTERVAL
o RX_HOLD_TIME = 30 seconds
o FW_HOLD_TIME = 30 seconds
o P_HOLD_TIME = 30 seconds
o FG_HOLD_TIME = 30 seconds
15.3 Willingness
o WILL_NEVER = 0 o WILL_NEVER = 0
o WILL_LOW = 1 o WILL_LOW = 1
o WILL_DEFAULT = 3 o WILL_DEFAULT = 3
o WILL_HIGH = 6 o WILL_HIGH = 6
o WILL_ALWAYS = 7 o WILL_ALWAYS = 7
17. Representing Time 15.4 Time
In HELLO messages, the 4 highest bits of the value of the TLV with o C = 0.0625 seconds (1/16 second)
Type="Htime" (see Appendix D.2.1) represent the mantissa (a) and the
four lowest bits the exponent (b), yielding that the HELLO interval
is expressed thus: C*(1+a/16)*2^b [in seconds]
Similarily, the validity time is represented by its mantissa (four 16. Representing Time
highest bits of Vtime field) and by its exponent (four lowest bits of
Vtime field). In other words:
o validity time = C*(1+a/16)* 2^b [in seconds] OLSRv2 specifies several TLVs, where time, in seconds, is to be
represented via an 8 bit field.
where a is the integer represented by the four highest bits of Vtime Of these 8 bits, the highest four bits represent the mantissa (a) and
field and b the integer represented by the four lowest bits of Vtime the four lowest bits represent the exponent (b), yielding that:
field. The proposed value of the scaling factor C is specified in
Section 16
18. IANA Considerations o time = C*(1+a/16)* 2^b [in seconds]
OLSRv2 defines a TLV "Type" field for message TLVs and address block where a is the integer represented by the four highest bits of the
TLVs respectively. Two new registries MUST be created for values for time field and b the integer represented by the four lowest bits of
this TLV type field, with initial assignments as specified in Table 6 the time field. The proposed value of the scaling factor C is
and Table 7 specified in Section 15. All nodes in the network MUST use the same
value of C.
Assigned message TLV Types 17. IANA Considerations
17.1 Multicast Addresses
A well-known multicast address, All-OLSRv2-Multicast, must be
registered and defined for both IPv6 and IPv4. The addressing scope
is link-local, i.e. this address is similar to the all nodes/routers
multicast address of IPv6 in that it targets all OLSRv2 capable nodes
adjacent to the originator of an IP datagram.
17.2 Message Types
OLSRv2 defines two message types, which must be allocated from the
"Assigned Message Types" repository of [4]
+--------------------+--------+-------------------------------------+ +--------------------+--------+-------------------------------------+
| Mnemonic | Value | Description | | Mnemonic | Value | Description |
+--------------------+--------+-------------------------------------+ +--------------------+--------+-------------------------------------+
| Fragmentation | 0 | Specifies behavior in case of | | HELLOv2 | TBD | Local Signaling |
| | | content fragmentation |
| | | |
| Content Sequence | 1 | A sequence number, associated with |
| Number | | the content of the message |
| | | | | | | |
| Willingness | 2 | Specifies a nodes willingness [0-7] | | TCv2 | TBD | Global Signaling |
| | | to act as a relay and to parttake |
| | | in network formation |
+--------------------+--------+-------------------------------------+ +--------------------+--------+-------------------------------------+
Table 6 Table 7
Assigned address block TLV Types 17.3 TLV Types
OLSRv2 defines three Message TLV types, which must be allocated from
the "Assigned message TLV Types" repository of [4]
+--------------------+--------+-------------------------------------+ +--------------------+--------+-------------------------------------+
| Mnemonic | Value | Description | | Mnemonic | Value | Description |
+--------------------+--------+-------------------------------------+ +--------------------+--------+-------------------------------------+
| Link Status | 0 | Specifies a given link's status | | VALIDITY_TIME | TBD | The time (in seconds) from receipt |
| | | of the message during which the |
| | | information contained in a message |
| | | is to be valid |
| | | |
| INTERVAL_TIME | TBD | The time (in seconds) between two |
| | | successive transmissions of |
| | | messages of a given type |
| | | |
| WILLINGNESS | TBD | Specifies a node's willingness |
| | | [0-7] to act as a relay and to |
| | | partake in network formation |
+--------------------+--------+-------------------------------------+
Table 8
OLSRv2 defines three Address Block TLV types, which must be allocated
from the "Assigned address block TLV Types" repository of [4]
+--------------------+--------+-------------------------------------+
| Mnemonic | Value | Description |
+--------------------+--------+-------------------------------------+
| OTHER_IF | TBD | Specifies that an address is |
| | | associated to an interface other |
| | | than the one where the message is |
| | | transmitted, and may specify its |
| | | status (verified bidirectional or |
| | | lost) |
| | | |
| LINK_STATUS | TBD | Specifies a given link's status |
| | | (asymmetric, verified | | | | (asymmetric, verified |
| | | bidirectional, lost) | | | | bidirectional, lost) |
| | | | | | | |
| MPR | 1 | Specifies that a given address is | | MPR | TBD | Specifies that a given address is |
| | | selected as MPR | | | | selected as MPR |
+--------------------+--------+-------------------------------------+ +--------------------+--------+-------------------------------------+
Table 7 Table 9
OLSRv2 message types MUST be assigned from the OLSRv2 repository 18. References
(HELLOv2, TCv2)
[1] Clausen, T., "The Optimized Link State Routing Protocol",
RFC 3626, October 2003.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, BCP 14, March 1997.
[3] Atkins, D., Stallings, W., and P. Zimmermann, "PGP Message
Exchange Formats", RFC 1991, August 1996.
[4] Clausen, T., Dean, J., and C. Dearlove, "Generalized MANET
Packet/Message Format", Work In
Progress draft-ietf-manet-packetbb-00.txt, February 2006.
[5] ETSI, "ETSI STC-RES10 Committee. Radio equipment and systems:
HIPERLAN type 1, functional specifications ETS 300-652",
June 1996.
[6] Jacquet, P., Minet, P., Muhlethaler, P., and N. Rivierre,
"Increasing reliability in cable free radio LANs: Low level
forwarding in HIPERLAN.", 1996.
[7] Qayuum, A., Viennot, L., and A. Laouiti, "Multipoint relaying:
An efficient technique for flooding in mobile wireless
networks.", 2001.
Authors' Addresses
Thomas Heide Clausen
LIX, Ecole Polytechnique, France
Phone: +33 6 6058 9349
Email: T.Clausen@computer.org
URI: http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/
Christopher M. Dearlove
BAE Systems Advanced Technology Centre
Phone: +44 1245 242194
Email: chris.dearlove@baesystems.com
The OLSRv2 Design Team
MANET Working Group
Appendix A. Example Heuristic for Calculating MPRs Appendix A. Example Heuristic for Calculating MPRs
The following specifies a proposed heuristic for selection of MPRs. The following specifies a proposed heuristic for selection of MPRs.
In graph theory terms, MPR computation is a "set cover" problem, In graph theory terms, MPR computation is a "set cover" problem,
which is a difficult optimization problem, but for which an easy and which is a difficult optimization problem, but for which an easy and
efficient heuristics exist: the so-called "Greedy Heuristic", a efficient heuristics exist: the so-called "Greedy Heuristic", a
variant of which is described here. In simple terms, MPR computation variant of which is described here. In simple terms, MPR computation
constructs an MPR Set that enables a node to reach any 2-hop constructs an MPR Set that enables a node to reach any 2-hop
interfaces through relaying by one MPR node. interfaces by relaying through an MPR node.
There are several peripheral issues that the algorithm need to There are several peripheral issues that the algorithm need to
address. The first one is that some nodes have some willingness address. The first one is that some nodes have some willingness
WILL_NEVER. The second one is that some nodes may have several WILL_NEVER. The second one is that some nodes may have several
interfaces. interfaces.
The algorithm hence need to be precised in the following way: The algorithm hence need to be precised in the following way:
o All neighbor nodes with willingness equal to WILL_NEVER MUST o All neighbor nodes with willingness equal to WILL_NEVER MUST
ignored in the following algorithm: they are not considered as ignored in the following algorithm: they are not considered as
neighbors (hence not used as MPR), nor as 2-hop neighbors (hence neighbors (hence not used as MPRs), nor as 2-hop neighbors (hence
no attempt to cover them is made). no attempt to cover them is made).
o Because link sensing is performed by interface, the local network o Because link sensing is performed by interface, the local network
topology, is best described in terms of links: hence the algorithm topology, is best described in terms of links: hence the algorithm
is considering neighbor interfaces, and 2-hop neighbor interfaces is considering neighbor interfaces, and 2-hop neighbor interfaces
(and their addresses). Additionally, asymmetric links are (and their addresses). Additionally, asymmetric links are
ignored. This is reflected in the definitions below. ignored. This is reflected in the definitions below.
o MPR computation is performed on each interface of the node: on o MPR computation is performed on each interface of the node: on
each interface I, the node MUST select some neighbor interface, so each interface I, the node MUST select some neighbor interfaces,
that all 2-hop interfaces are reached. so that all 2-hop interfaces are reached.
>From now on, MPR calculation will be described for one interface I From now on, MPR calculation will be described for one interface I on
on the node, and the following terminology will be used in describing the node, and the following terminology will be used in describing
the heuristics: the heuristics:
neighbor interface (of I) - An interface of a neighbor to which there neighbor interface (of I) - An interface of a neighbor to which there
exist a symmetrical link on interface I. exist a symmetrical link on interface I.
N - the set of such neighbor interfaces N - the set of such neighbor interfaces
2-hop neighbor interface (of I) An interface of a symmetric strict 2-hop neighbor interface (of I) An interface of a symmetric strict
2-hop neighbor and which can be reached from a neighbor interface 2-hop neighbor and which can be reached from a neighbor interface
for I. for I.
N2 - the set of such 2-hop neighbor interfaces N2 - the set of such 2-hop neighbor interfaces
D(y): - the degree of a 1-hop neighbor interface y (where y is a D(y): - the degree of a 1-hop neighbor interface y (where y is a
member of N), is defined as the number of symmetric neighbor member of N), is defined as the number of symmetric neighbor
interfaces of node y which are in N2 interfaces of node y which are in N2
MPR set - the set of the neighbor interfaces selected as MPR. MPR Set - the set of the neighbor interfaces selected as MPRs.
The proposed heuristic selects iteratively some interfaces from N as The proposed heuristic selects iteratively some interfaces from N as
MPR in order to cover 2-hop neighbor interfaces from N2, as follows: MPRs in order to cover 2-hop neighbor interfaces from N2, as follows:
1. Start with an MPR set made of all members of N with N_willingness 1. Start with an MPR Set made of all members of N with N_willingness
equal to WILL_ALWAYS equal to WILL_ALWAYS
2. Calculate D(y), where y is a member of N, for all interfaces in 2. Calculate D(y), where y is a member of N, for all interfaces in
N. N.
3. Add to the MPR set those interfaces in N, which are the *only* 3. Add to the MPR Set those interfaces in N, which are the *only*
nodes to provide reachability to an interface in N2. For nodes to provide reachability to an interface in N2. For
example, if interface B in N2 can be reached only through a example, if interface B in N2 can be reached only through a
symmetric link to interface A in N, then add interface B to the symmetric link to interface A in N, then add interface B to the
MPR set. Remove the interfaces from N2 which are now covered by MPR Set. Remove the interfaces from N2 which are now covered by a
a interface in the MPR set. interface in the MPR Set.
4. While there exist interfaces in N2 which are not covered by at 4. While there exist interfaces in N2 which are not covered by at
least one interface in the MPR set: least one interface in the MPR Set:
1. For each interface in N, calculate the reachability, i.e., 1. For each interface in N, calculate the reachability, i.e.,
the number of interfaces in N2 which are not yet covered by the number of interfaces in N2 which are not yet covered by
at least one node in the MPR set, and which are reachable at least one node in the MPR Set, and which are reachable
through this neighbor interface; through this neighbor interface;
2. Select as a MPR the interface with highest N_willingness 2. Select as an MPR the interface with highest N_willingness
among the interfaces in N with non-zero reachability. In among the interfaces in N with non-zero reachability. In
case of multiple choice select the interface which provides case of multiple choice select the interface which provides
reachability to the maximum number of interfaces in N2. In reachability to the maximum number of interfaces in N2. In
case of multiple interfaces providing the same amount of case of multiple interfaces providing the same amount of
reachability, select the interface as MPR whose D(y) is reachability, select the interface as MPR whose D(y) is
greater. Remove the interfaces from N2 which are now covered greater. Remove the interfaces from N2 which are now covered
by an interface in the MPR set. by an interface in the MPR Set.
Other algorithms, as well as improvements over this algorithm, are Other algorithms, as well as improvements over this algorithm, are
possible. For example: possible. For example:
o Some 2-hop neighbors may have several interfaces. The described o Some 2-hop neighbors may have several interfaces. The described
algorithm attempts to reach every such interface of the nodes. algorithm attempts to reach every such interface of the nodes.
However, whenever information that several 2-hop interfaces are, However, whenever information that several 2-hop interfaces are,
in fact, interfaces of the same 2-hop neighbor, is available, it in fact, interfaces of the same 2-hop neighbor, is available, it
can be used: only one of the interfaces of the 2-hop neighbor can be used: only one of the interfaces of the 2-hop neighbor
needs to be covered. needs to be covered. This information is provided in the
Neighborhood Address Association Set.
o Assume that in a multiple-interface scenario there exists more o Assume that in a multiple interface scenario there exists more
than one link between nodes 'a' and 'b'. If node 'a' has selected than one link between nodes 'a' and 'b'. If node 'a' has selected
node 'b' as MPR for one of its interfaces, then node 'b' can be node 'b' as MPR for one of its interfaces, then node 'b' can be
selected as MPR with minimal performance loss by any other selected as MPR with minimal performance loss by any other
interfaces on node 'a'. interfaces on node 'a'.
o In a multiple interface scenario MPRs are selected for each
interface of the selecting node, providing full coverage of all
2-hop nodes accessible through that interface. The overall MPR
Set is then the union of these sets. These sets do not however
have to be selected independently, if a node is selected as an MPR
for one interface it may be automatically added to the MPR
selection for other interfaces.
Appendix B. Example Algorithms for Generating Control Traffic Appendix B. Example Algorithms for Generating Control Traffic
The proposed generation of the control messages proceeds in four The proposed generation of the control messages proceeds in four
steps. HELLO messages, like TC messages consist essentially in a steps. HELLO messages and TC messages both essentially consist of a
list of advertised addresses of neighbors (some part of the list of advertised addresses of neighbors (some part of the
topology). topology).
Hence, a first step is to collect the set of relevant of addresses Hence, a first step is to collect the set of relevant addresses which
which are to be advertised. Because there are a number of TLVs which are to be advertised. Because there are a number of TLVs which can
can be associated to each address (including mandatory ones), this be associated with each address (including mandatory ones), this step
steps results into a list of addresses, each associated with a results in a list of addresses, each associated with a certain number
certain number of TLVs. of TLVs.
Thus, the second step is then to regroup the addresses which share The second step is then to regroup the addresses which share exactly
exactly the same TLVs (same Type and same Value), into an address the same TLVs (same Type and same Value), into an address block which
block which will be associated with a list of TLVs. will be associated with a list of TLVs.
The third step is to pack the message header and message TLVs into a The third step is to pack the message header and message TLVs into a
string of octets. sequence of octets.
The fourth step consists in packing every address block obtained in The fourth step consists of packing every address block obtained in
the second step: by finding the longest common prefix of the the second step by finding the longest common prefix of the addresses
addresses in the address block (the head), then, packing the list of in the address block (the head), then, packing the list of the tails
the tail of the addresses into a string of octets, followed by the of the addresses into a sequence of octets, followed by the TLVs of
TLVs of the address block. the address block.
This generation method can be used for TC generation and HELLO This generation method can be used for TC generation and HELLO
generation: in each case, all what need to be specified is the generation: in each case, all what need to be specified is the
message headers, message TLVs, and the list of each address with its message headers, message TLVs, and the list of each address with its
associated TLVs. associated TLVs.
The message headers are identical to RFC 3626, and should be filled The Local Interface Block MUST include all of the participating
in the same way. The orginator address block MUST include all the interface addresses of the node (including the one of chosen as the
addresses of the node (including the one of chosen for originator node's originator address and included in the message header).
address in the message header)
Appendix B.1 Example Algorithm for Generating HELLO messages Appendix B.1 Example Algorithm for Generating HELLO messages
This section proposes an algorithm for generating HELLOs This section proposes an algorithm for generating HELLO messages.
Periodically, on every interface I, the node generates a HELLO Periodically, on each interface I, the node generates a HELLO message
message different on each interface, as follows: specific to that interface, as follows:
1. First, the list of the links of the interface is collected. It 1. First, the list of the links of the interface is collected. It
is the list of the link tuples where: is the list of the Link Tuples where:
* L_local_iface_addr == address of the interface * L_local_iface_addr == address of the interface
Each corresponding address L_neighbor_iface_addr is then Each corresponding address L_neighbor_iface_addr is then
advertized with the following TLVs: advertised with the following TLVs:
* Type="Link Status", Value=L_STATUS, status of the link (see * Type="LINK-STATUS", Value=L_STATUS, the status of the link
Section 5.1.1) (see Section 5.1.1);
* Type="Interface" Value="TransmittingInterface" * Type="OTHER_IF", if and only if as specified in Section 7);
* Type="MPR Selection", Value="True", if and only of the address * Type="MPR", if and only of the address L_neighbor_iface_addr
L_neighbor_iface_addr is one interface address in the MPR set. is an interface address in the MPR Set.
2. Second, if the node has several interfaces, for each address 2. Second, if the node has more than one interface, for each address
which was not previously advertised, and for which there exists a which was not previously advertised and for which there exists a
link tuple on another interface where: Link Tuple on another interface where:
* L_local_iface_addr is different from address of the interface * L_local_iface_addr is different from address of the interface
I I; AND
* L_STATUS == SYMMETRIC * L_STATUS == SYMMETRIC
the corresponding address L_neighbor_iface_addr is advertized the corresponding address L_neighbor_iface_addr is advertised
with the following TLVs: with the following TLV:
* Type="Link Status", Value=L_STATUS, status of the link (see * Type="OTHER_IF", Value=SYMMETRIC.
Section 5.1.1)
* Type="Interface" Value="Other" 3. Third, if the node has more than one interface, for each
interface address which is to be reported as LOST as specified in
Section 7) the interface address is advertised with the following
TLV:
3. Then a HELLO message is generated using the previous method, with * Type="OTHER_IF", Value=LOST.
the proper headers and TLVs:
* a message TLV with Type="Htime" and Value=encoding of the 4. Then a HELLO message is generated using the previous method, with
HELLO generation interval, is added the specified headers and TLVs:
* a message TLV with Type="Willingness" and Value=the * a message TLV with Type="VALIDITY_TIME" and Value=encoding of
willingness of the node. If a node has a willingness of L_HOLD_TIME, SHALL be added
WILL_DEFAULT, a node SHOULD NOT include a TLV with
type="Willingness";
* the message header including Vtime, which MUST be set to a * a message TLV with Type="INTERVAL_TIME" and Value=encoding of
value higher than this generation interval, typically 3 times HELLO_INTERVAL, SHOULD be added
the generation interval, to allow for message losses.
* a message TLV with Type="WILLINGNESS" and Value=the
willingness of the node. This SHOULD NOT be included if this
value is WILL_DEFAULT, it SHALL be included otherwise.
Appendix B.2 Example Algorithm for Generating TC messages Appendix B.2 Example Algorithm for Generating TC messages
Periodically, the node generates TC messages, broadcast on all the Periodically, the node generates TC messages, broadcast on all the
interfaces of the node, as follows: interfaces of the node, as follows:
1. Each A_iface_addr in the Advertised Neighbor set, will be 1. Each A_iface_addr in the Advertised Neighbor Set, SHALL be
included in the TC message. included in the TC message.
2. The TC message is generated using the previous method with the 2. The TC message is generated with the proper headers, and (except
proper headers, and including the mandatory TC message TLV, where the Advertised Neighbor Set is empty and the TC message is
Type="ASSN" Value=the current value of the ASSN of the node. not specifically reporting this, see Section 9) including the
message TLV, Type="CONTENT_SEQUENCE_NUMBER", Value=the current
ASSN of the node.
Appendix C. Protocol and Port Number Appendix C. Protocol and Port Number
Packets in OLSRv2 are communicated using UDP. Port 698 has been Packets in OLSRv2 are communicated using UDP. Port 698 has been
assigned by IANA for exclusive usage by the OLSR (v1 and v2) assigned by IANA for exclusive usage by the OLSR (v1 and v2)
protocol. protocol.
Appendix D. OLSRv2 Packet and Message Layout Appendix D. Packet and Message Layout
This section specifies the translation from the abstract descriptions This section specifies the translation from the abstract descriptions
of OLSRv2 control signals, employed in the protocol specification, of packets employed in the protocol specification, and the bit-layout
and the bit-layout in the control-frames actually exchanged between packets actually exchanged between the nodes.
the nodes.
Appendix D.1 General OLSR Packet Format Appendix D.1 OLSRv2 Packet Format
The basic layout of any packet in OLSRv2 is as follows (omitting IP The basic layout of an OLSRv2 packet is as described in [4]. However
and UDP headers): the following points should be noted.
OLSRv2 uses only packets with a packet header. Thus all OLSRv2
packets have the following layout.
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 | Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |0 0 0 0 0 0 0 0| Reserved | Packet Sequence Number |
| Message Type | Vtime | Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Number of Msg TLVs | Number of Address Blocks |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Msg TLV | Msg TLV | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| | | |
: ... :
| Message |
| | | |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Msg TLV | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Originator Address Block: Addr Block 1 |
: ... :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Addr Block 2 |
| Message |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: :
| |
(etc.)
The generic packet format defined in RFC3626 encapsulates messages, All reserved bits are also unset (zero).
similarly to OLSRv1. OLSRv2 messages are defined as new message
types. These messages contain the same header as OLSRv1 messages,
with address blocks and TLVs, as described below.
Appendix D.1.1 Message TLVs
The TLV format (Type-Length-Value) is used to introduce information OLSRv2 uses only packets with a complete message header. Thus all
in a flexible way. A message TLV associates some information OLSRv2 messages have the following layout.
(depending on the type) with the node/address that originated the
message.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
: Value ... :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Appendix D.1.2 Address Block | Message Type | Resv |U|N|0|0| Message Size |
An address block is a way of representing addresses, as well as +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
information associated with addresses, in a compact and flexible way.
The proposed format of an address block is as follows: | Originator Address |
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # addresses | Addr. length | Head length | #TLV |
| Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: Head :
| Message Body + Padding |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Tail | Tail | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + In standard OLSRv2 messages (HELLO and TC) the U and N bits are also
| | unset(zero). In all OLSRv2 messages the reserved bits marked Resv
: ... : above are also unset (zero).
| |
+ +-+-+-+-+-+-+-+-+-+ The layouts of the message body, address block, TLV block and TLV are
| | Tail | as in [4], allowing all options. Standard (HELLO and TC) messages
contain a first address block which contains local interface
addresses, all other address blocks contain information specific to
the message type. Except by being first, the local interface address
block is not distinguished in any way.
An example HELLO message, using IPv4 (four octet) addresses is as
follows. The overall message length is 56 octets (it does not need
padding). The message has a TTL of 1 and a hop count of 0, as sent
by its originator.
The message has a message TLV block with content length 12 octets
containing three message TLVs. These TLVs represent message validity
time, message interval time and willingness. Each uses a TLV with
semantics value 4, indicating no start and stop indexes are included,
and each has a value length of 1 octet.
The first address block contains a single local interface address,
with head length 4; thus although 1 tail is indicated, no tail octets
are included. This address block has no TLVs (TLV block content
length 0 octets).
The second, and last, address block reports 4 neighbour interface
addresses, with address head length 3 octets. The following TLV
block (content length 11 octets) includes two TLVs.
The first of these TLVs reports the link status of all four
neighbours in a single multivalue TLV, the first two addresses are
HEARD, the last two addresses are SYMMETRIC. The TLV semantics value
of 12 indicates, in addition to that this is a multivalue TLV, that
no start index and stop index are included, since values for all
addresses are included. The TLV value length of 4 octets indicates
one octet per value per address.
The second of these TLV indicates that the last address (start index
3, stop index 3) is an MPR. This TLV has no value, or value length,
fields, as indicated by its semantics octet being equal to 1.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Addr. Block TLV | Addr. Block TLV | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | HELLO |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0|
| |
: ... :
| |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Addr. Block TLV | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
# addresses - The number of addresses in the address block | Originator Address |
Addr. length - The length, in bits, of an individual address. For +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
IPv4 addresses, this field MUST be set to 32 For IPv6 addresses,
this field MUST be set to 128
Prefix length - The length of the common prefix of all the addresses |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number |
in the address block. 0 <= Prefix length < Addr. length A prefix
length of 0 indicates, that the prefix field (following) is
absent.
#TLV - The number of TLV's in the address block. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Prefix The longest sequence of bits which is common among all the |0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0| VALIDITY-TIME |0 0 0 0 0 1 0 0|
addresses, included in the address block. This field is of a
fixed length, as specified in the field "prefix length"
Host The host fields specifies the unique part of all the addresses, +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
included in the address block. Indeed, letting + denote the
concatenation operator, the expression prefix+host will yield a
unique address. This field os of a fixed length = "Addr. length"
- "Prefix length"
TLV A TLV carries the information, associated to one, or a set of,
addresses in the classic type-length-value format. This format is
explicitly given below.
Padding A variable-length field of all-zero's, to achieve 32-bit |0 0 0 0 0 0 0 1| Value | INTERVAL-TIME |0 0 0 0 0 1 0 0|
alignment of the packet.
Note that no alignments are attempted -- all alignments happen in the +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
address block listed above.
Appendix D.1.3 Address Block TLV |0 0 0 0 0 0 0 1| Value | WILLINGNESS |0 0 0 0 0 1 0 0|
Again, the TLV format (Type-Length-Value) is used to introduce +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
information in a flexible way inside Address Blocks. An Address
Block TLV associates some information with some address(s) listed in |0 0 0 0 0 0 0 1| Value |0 0 0 0 0 1 0 0| Head |
the Address Block.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Index Start | Index Stop | Length |
| Head (cont) |0 0 0 0 0 0 0 1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Value ...
+-+-+-+-+-+-+-+-+
Type This field specifies the type of the TLV. |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 1 1| Head |
Addr Start This field specifies to which address the TLV applies: the +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
addresses listed between Index Start and Index Stop.
Addr Stop This field specifies to which address the TLV applies: the | Head (cont) |0 0 0 0 0 1 0 0| Tail |
addresses listed between Index Start and Index Stop.
Length This field specifies the length of the data contained in +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
"Value"
Value This field is a field of the length specified in Length, which | Tail | Tail | Tail |0 0 0 0 0 0 0 0|
contains data -- information, which is to be interpreted according
to the specification by the "Type" field, and in the context given
by the "addr#" and "Offset" fields.
Appendix D.2 Layout of OLSRv2 Specified Messages +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The message format specified for OLSRv2 allows a great deal of |0 0 0 0 1 0 1 1| LINK-STATUS |0 0 0 0 1 1 0 0|0 0 0 0 0 1 0 0|
flexibility in how control messages are organized. For example,
while it is possible to represent a sequence of addresses as an
address-block, it is also possible -- although possibly less optimal
-- to represent the same sequence as individual addresses in an
OLSRv2 control message.
This section will, therefore, give an example of how OLSRv2 HELLO and +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
TC messages typically can be be generated. It is, however, important
to keep in mind that this section presents one possible instance of
HELLO and TC messages.
Appendix D.2.1 Layout of HELLO Messages | HEARD | HEARD | SYMMETRIC | SYMMETRIC |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
HELLO TLVs | MPR |0 0 0 0 0 0 0 1|0 0 0 0 0 0 1 1|0 0 0 0 0 0 1 1|
+-------------+---------------+------------+-------------------------+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Scope | Importance | Description |
+-------------+---------------+------------+-------------------------+
| Status | Address Block | MUST | SYM, ASYM, LOST |
| | | | |
| MPR | Address Block | MUST | Nodes selected as MPR |
| | | | |
| Willingness | Message | MAY | Willingness information |
| | | | |
| Htime | Message | MUST | Htime information |
+-------------+---------------+------------+-------------------------+
Table 8 An example TC message, using IPv4 (four octet) addresses, is as
follows. The overall message length is 67 octets, the final octet is
padding.
Appendix D.2.2 Layout of TC messages The message has a message TLV block with content length 13 octets
containing three TLVs. The first TLV is a content sequence number
TLV used to carry the 2 octet ANSN. The semantics value is 4
indicating that no index fields are included. The other two TLVs are
validity and interval times as for the HELLO message above.
TC TLVs The message has three address blocks. The first address block
contains 3 local interface addresses (with common head length 2
octets) and has a TLV block with content length 4 octets containing a
single TLV with semantics value 1, indicating that the TLV has no
value field, or length thereof. This TLV indicates that the second
and third of these addresses (indexes 1 to 2) are for other
interfaces than the one on which this TC message is transmitted.
+------+-------+------------+-------------------------------------+ The other two address blocks contain neighbour interface addresses,
| Type | Scope | Importance | Description | with head lengths 2 and 4 respectively. The first of these, with 3
+------+-------+------------+-------------------------------------+ addresses, has an empty TLV block (content length 0 octets). The
| ASSN | Msg | MUST | Advertised Neighbor Sequence Number | second, which contains 1 address, has a TLV block (content length 4
+------+-------+------------+-------------------------------------+ octets) with a single TLV (semantics value 4 indicating no indexes
needed) indicating that this is a network address with the given
prefix length (itself with length 1 octet).
Table 9
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TC Msg Type | Vtime | Message Size |
| TC |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time To Live | Hop Count | Message Sequence Number |
| Time to Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Number of Msg TLVs (1) | Number of Address Blocks (1) |
|0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1| CONT_SEQ_NUM |0 0 0 0 0 1 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ANSN (Message TLV) |
|0 0 0 0 0 0 1 0| Value (ASSN) | VALIDITY_TIME |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|# addresses(17)|Addr lgth (32) |Prefx lgth (28)| #TLV (2) |
|0 0 0 0 0 1 0 0|0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| IP Prefix | Host1 |
|0 0 0 0 0 1 0 0|0 0 0 0 0 0 0 1| Value |0 0 0 0 0 0 1 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Host2 | Host3 | Host4 | Host5 | Host6 | Host7 | Host8 | Host9 |
| Head |0 0 0 0 0 0 1 1| Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Host10| Host11| Host12| Host13| Host14| Host15| Host16| Host17|
| Tail (cont) | Tail | Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Same Node (Addr. Block TLV) |
| Tail (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0| OTHER_IF |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 1|0 0 0 0 0 0 1 0|0 0 0 0 0 0 1 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Head |0 0 0 0 0 0 1 1| Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Tail (cont) | Tail | Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Tail (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Head |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0| PREFIX-LENGTH |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 1 0 0|0 0 0 0 0 0 0 1|Value (Length) |0 0 0 0 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Appendix E. Node Configuration Appendix E. Node Configuration
OLSRv2 does not make any assumption about node addresses, other than OLSRv2 does not make any assumption about node addresses, other than
that each node is assumed to have a unique and routable IP address. that each node is assumed to have at least one a unique and routable
IP address for each interface that it has which participates in the
MANET.
When applicable, a recommended way of connecting an OLSR network to When applicable, a recommended way of connecting an OLSRv2 network to
an existing IP routing domain is to assign an IP prefix (under the an existing IP routing domain is to assign an IP prefix (under the
authority of the nodes/gateways connecting the MANET with the routing authority of the nodes/gateways connecting the MANET with the routing
domain) exclusively to the OLSR area, and to configure the gateways domain) exclusively to the OLSRv2 area, and to configure the gateways
statically to advertise routes to that IP sequence to nodes in the statically to advertise routes to that IP sequence to nodes in the
existing routing domain. existing routing domain.
Appendix E.1 IPv6 Specific Considerations
In the case of IPv6, a node's routable IP address can either be a
global address, or a manet-local address (as described in
draft-wakikawa-manet-ipv6). Typically an OLSRv2 may have several
addresses, for example: a link-local address and a routable address.
However the link-local address is only valid within the 1-hop
neighborhood. It may be used to resolve neighbor state with the
Neighbor Discovery Protocol, but routes to link-local addresses MUST
NOT be advertized and MUST NOT be inserted in routing tables. Only
routable addresses are stored in routing tables, and a routable
address MUST be used for the originator address in HELLO messages and
in TC messages.
OLSRv2 uses a specific flooding address (ff02::3) called the All-
OLSRv2-Multicast address. This address is similar to all nodes/
routers multicast address in IPv6 specification (i.e. ff02::1 or
ff02::2). The difference is that All-OLSRv2-Multicast specifies that
intended receivers are OLSRv2 nodes. Since the All-OLSRv2-Multicast
address is a link-local address, the message sent to the multicast
address can not reach further than 1 hop. Each OLSRv2 node MUST
process flooding packets and possibly re-flood the packets to the
same destination (ff02::3), if they are designated forwarders. Note
that although ff02::3 is a link-local address, each flooded message
MUST be transmitted with a routable address as originator address.
Appendix F. Security Considerations Appendix F. Security Considerations
Currently, OLSR does not specify any special security measures. As a Currently, OLSRv2 does not specify any special security measures. As
proactive routing protocol, OLSR makes a target for various attacks. a proactive routing protocol, OLSRv2 makes a target for various
The various possible vulnerabilities are discussed in this section. attacks. The various possible vulnerabilities are discussed in this
section.
Appendix F.1 Confidentiality Appendix F.1 Confidentiality
Being a proactive protocol, OLSR periodically diffuses topological Being a proactive protocol, OLSRv2 periodically diffuses topological
information. Hence, if used in an unprotected wireless network, the information. Hence, if used in an unprotected wireless network, the
network topology is revealed to anyone who listens to OLSR control network topology is revealed to anyone who listens to OLSRv2 control
messages. messages.
In situations where the confidentiality of the network topology is of In situations where the confidentiality of the network topology is of
importance, regular cryptographic techniques such as exchange of OLSR importance, regular cryptographic techniques, such as exchange of
control traffic messages encrypted by PGP [9] or encrypted by some OLSRv2 control traffic messages encrypted by PGP [3] or encrypted by
shared secret key can be applied to ensure that control traffic can some shared secret key, can be applied to ensure that control traffic
be read and interpreted by only those authorized to do so. can be read and interpreted by only those authorized to do so.
Appendix F.2 Integrity Appendix F.2 Integrity
In OLSR, each node is injecting topological information into the In OLSRv2, each node is injecting topological information into the
network through transmitting HELLO messages and, for some nodes, TC network through transmitting HELLO messages and, for some nodes, TC
messages. If some nodes for some reason, malicious or malfunction, messages. If some nodes for some reason, malicious or malfunction,
inject invalid control traffic, network integrity may be compromised. inject invalid control traffic, network integrity may be compromised.
Therefore, message authentication is recommended. Therefore, message authentication is recommended.
Different such situations may occur, for instance: Different such situations may occur, for instance:
1. a node generates TC messages, advertising links to non-neighbor 1. a node generates TC messages, advertising links to non-neighbor
nodes; nodes;
2. a node generates TC messages, pretending to be another node; 2. a node generates TC messages, pretending to be another node;
3. a node generates HELLO messages, advertising non-neighbor nodes; 3. a node generates HELLO messages, advertising non-neighbor nodes;
4. a node generates HELLO messages, pretending to be another node; 4. a node generates HELLO messages, pretending to be another node;
5. a node forwards altered control messages; 5. a node forwards altered control messages;
6. a node does not broadcast control messages; 6. a node does not forward control messages;
7. a node does not select multipoint relays correctly; 7. a node does not select multipoint relays correctly;
8. a node forwards broadcast control messages unaltered, but does 8. a node forwards broadcast control messages unaltered, but does
not forward unicast data traffic; not forward unicast data traffic;
9. a node "replays" previously recorded control traffic from another 9. a node "replays" previously recorded control traffic from another
node. node.
Authentication of the originator node for control messages (for Authentication of the originator node for control messages (for
situation 2, 4 and 5) and on the individual links announced in the situations 2, 4 and 5) and on the individual links announced in the
control messages (for situation 1 and 3) may be used as a control messages (for situations 1 and 3) may be used as a
countermeasure. However to prevent nodes from repeating old (and countermeasure. However to prevent nodes from repeating old (and
correctly authenticated) information (situation 9) temporal correctly authenticated) information (situation 9) temporal
information is required, allowing a node to positively identify such information is required, allowing a node to positively identify such
delayed messages. delayed messages.
In general, digital signatures and other required security In general, digital signatures and other required security
information may be transmitted as a separate OLSRv2 message type, information may be transmitted as a separate OLSRv2 message type,
thereby allowing that "secured" and "unsecured" nodes can coexist in thereby allowing that "secured" and "unsecured" nodes can coexist in
the same network, if desired, or signatures and security information the same network, if desired, or signatures and security information
may be transmitted within the OLSRv2 HELLO and TC messages, using the may be transmitted within the OLSRv2 HELLO and TC messages, using the
TLV mechanism. TLV mechanism.
Specifically, the authenticity of entire OLSRv2 control messages can Specifically, the authenticity of entire OLSRv2 control messages can
be established through employing IPsec authentication headers, be established through employing IPsec authentication headers,
whereas authenticity of individual links (situation 1 and 3) require whereas authenticity of individual links (situations 1 and 3) require
additional security information to be distributed. additional security information to be distributed.
An important consideration is, that all control messages in OLSR are An important consideration is, that all control messages in OLSRv2
transmitted either to all nodes in the neighborhood (HELLO messages) are transmitted either to all nodes in the neighborhood (HELLO
or broadcast to all nodes in the network (e.g., TC messages). messages) or broadcast to all nodes in the network (TC messages).
For example, a control message in OLSRv2 is always a point-to- For example, a control message in OLSRv2 is always a point-to-
multipoint transmission. It is therefore important that the multipoint transmission. It is therefore important that the
authentication mechanism employed permits that any receiving node can authentication mechanism employed permits that any receiving node can
validate the authenticity of a message. As an analogy, given a block validate the authenticity of a message. As an analogy, given a block
of text, signed by a PGP private key, then anyone with the of text, signed by a PGP private key, then anyone with the
corresponding public key can verify the authenticity of the text. corresponding public key can verify the authenticity of the text.
Appendix F.3 Interaction with External Routing Domains Appendix F.3 Interaction with External Routing Domains
OLSRv2 does, through the use of TC messages, provide a basic OLSRv2 does, through the use of TC messages, provide a basic
mechanism for injecting external routing information to the OLSRv2 mechanism for injecting external routing information to the OLSRv2
domain. Section XXX also specifies that routing information can be domain. Appendix E also specifies that routing information can be
extracted from the topology table or the routing table of OLSR and, extracted from the topology table or the routing table of OLSRv2 and,
potentially, injected into an external domain if the routing protocol potentially, injected into an external domain if the routing protocol
governing that domain permits. governing that domain permits.
Other than as described in the section XXX, when operating nodes, Other than as described in Appendix E, when operating nodes,
connecting OLSRv2 to an external routing domain, care MUST be taken connecting OLSRv2 to an external routing domain, care MUST be taken
not to allow potentially insecure and un-trustworthy information to not to allow potentially insecure and untrustworthy information to be
be injected from the OLSRv2 domain to external routing domains. Care injected from the OLSRv2 domain to external routing domains. Care
MUST be taken to validate the correctness of information prior to it MUST be taken to validate the correctness of information prior to it
being injected as to avoid polluting routing tables with invalid being injected as to avoid polluting routing tables with invalid
information. information.
A recommended way of extending connectivity from an existing routing A recommended way of extending connectivity from an existing routing
domain to an OLSRv2 routed MANET is to assign an IP prefix (under the domain to an OLSRv2 routed MANET is to assign an IP prefix (under the
authority of the nodes/gateways connecting the MANET with the exiting authority of the nodes/gateways connecting the MANET with the exiting
routing domain) exclusively to the OLSRv2 MANET area, and to routing domain) exclusively to the OLSRv2 MANET area, and to
configure the gateways statically to advertise routes to that IP configure the gateways statically to advertise routes to that IP
sequence to nodes in the existing routing domain. sequence to nodes in the existing routing domain.
Appendix F.4 Node Identity Appendix F.4 Node Identity
OLSR does not make any assumption about node addresses, other than OLSRv2 does not make any assumption about node addresses, other than
that each node is assumed to have a unique IP address. that each node is assumed to have at least one a unique and routable
IP address for each interface that it has which participates in the
MANET.
Appendix G. Flow and Congestion Control Appendix G. Flow and Congestion Control
TBD TBD
Appendix H. Sequence Numbers Appendix H. Sequence Numbers
Sequence numbers are used in OLSR with the purpose of discarding Sequence numbers are used in OLSR with the purpose of discarding
"old" information, i.e., messages received out of order. However "old" information, i.e., messages received out of order. However
with a limited number of bits for representing sequence numbers, with a limited number of bits for representing sequence numbers,
skipping to change at page 66, line 5 skipping to change at page 79, line 5
number S2 if: number S2 if:
o S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR o S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR
o S2 > S1 AND S2 - S1 > MAXVALUE/2 o S2 > S1 AND S2 - S1 > MAXVALUE/2
Thus when comparing two messages, it is possible - even in the Thus when comparing two messages, it is possible - even in the
presence of wrap-around - to determine which message contains the presence of wrap-around - to determine which message contains the
most recent information. most recent information.
Appendix I. References Appendix I. Contributors
o [1] P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre.
Increasing reliability in cable free radio LANs: Low level
forwarding in HIPERLAN. Wireless Personal Communications, 1996.
o [2] A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An
efficient technique for flooding in mobile wireless networks. 35th
Annual Hawaii International Conference on System Sciences
(HICSS'2001).
o [3] ETSI STC-RES10 Committee. Radio equipment and systems:
HIPERLAN type 1, functional specifications ETS 300-652, ETSI, June
1996.
o [4] P. Jacquet and L. Viennot, Overhead in Mobile Ad-hoc Network
Protocols, INRIA research report RR-3965, 2000.
o [5] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
o [6] T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The
Optimized Link State Routing Protocol, Evaluation through
Experiments and Simulation. IEEE Symposium on "Wireless Personal
Mobile Communications", September 2001.
o [7] T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A.
Qayyum and L. Viennot. Optimized Link State Routing Protocol.
IEEE INMIC Pakistan 2001. [8] Narten, T. and H. Alvestrand,
"Guidelines for Writing an IANA Considerations Section in RFCs",
BCP 26, RFC 2434, October 1998.
o [9] Atkins, D., Stallings, W. and P. Zimmermann, "PGP Message
Exchange Formats", RFC 1991, August 1996.
o [10] P. Jacquet, A. Laouiti, P. Minet, L. Viennot, "Performance
analysis of OLSR multipoint relay flooding in two ad hoc wireless
network models", INRIA research report RR-4260, 2001.
o [11] T. Clausen (ed), P. Jacquet (ed), "The Optimized Link State
Routing Protocol", RFC3626, October 2003
Appendix J. Contributors
This specification is the result of the joint efforts of the This specification is the result of the joint efforts of the
following contributers -- listed alphabetically. following contributers -- listed alphabetically.
o Cedric Adjih, INRIA, France, <Cedric.Adjih@inria.fr> o Cedric Adjih, INRIA, France, <Cedric.Adjih@inria.fr>
o Emmanuel Baccelli, INRIA, France, <Emmanuel.Baccelli@inria.fr> o Emmanuel Baccelli, Hitachi Labs Europe, France,
<Emmanuel.Baccelli@inria.fr>
o Thomas Heide Clausen, PCRI, France<T.Clausen@computer.org> o Thomas Heide Clausen, PCRI, France<T.Clausen@computer.org>
o Justin Dean, NRL, USA<jdean@itd.nrl.navy.mil> o Justin Dean, NRL, USA<jdean@itd.nrl.navy.mil>
o Christopher Dearlove, BAE Systems, UK, o Christopher Dearlove, BAE Systems, UK,
<Chris.Dearlove@baesystems.com> <Chris.Dearlove@baesystems.com>
o Satoh Hiroki, Hitachi SDL, Japan, <h-satoh@sdl.hitachi.co.jp> o Satoh Hiroki, Hitachi SDL, Japan, <h-satoh@sdl.hitachi.co.jp>
o Philippe Jacquet, INRIA, France, <Philippe.Jacquet@inria.fr> o Philippe Jacquet, INRIA, France, <Philippe.Jacquet@inria.fr>
o Monden Kazuya, Hitachi SDL, Japan, <monden@sdl.hitachi.co.jp> o Monden Kazuya, Hitachi SDL, Japan, <monden@sdl.hitachi.co.jp>
o Kenichi Mase, University, Japan, <mase@ie.niigata-u.ac.jp> o Kenichi Mase, University, Japan, <mase@ie.niigata-u.ac.jp>
o Ryuji Wakikawa, KEIO University, Japan, <ryuji@sfc.wide.ad.jp> o Ryuji Wakikawa, KEIO University, Japan, <ryuji@sfc.wide.ad.jp>
Appendix K. Acknowledgements Appendix J. Acknowledgements
The authors would like to acknowledge the team behind OLSRv1, The authors would like to acknowledge the team behind OLSRv1,
specified in RFC3626, including Paul Muhlethaler, Anis Laouiti, specified in RFC3626, including Anis Laouiti, Pascale Minet, Laurent
Pascale Minet, Laurent Viennot (all at INRIA, France), and Amir Viennot (all at INRIA, France), and Amir Qayuum (Center for Advanced
Qayuum (Center for Advanced Research in Engineering) for their Research in Engineering) for their contributions.
contributions.
The authors would like to gratefully acknowledge the following people The authors would like to gratefully acknowledge the following people
for intense technical discussions, early reviews and comments on the for intense technical discussions, early reviews and comments on the
specification and its components: Kenichi Mase (Niigata University), specification and its components: Kenichi Mase (Niigata University),
Li Li (CRC), Louise Lamont (CRC), Joe Macker (NRL), Alan Cullen (BAE Li Li (CRC), Louise Lamont (CRC), Joe Macker (NRL), Alan Cullen (BAE
Systems), Philippe Jacquet (INRIA), Khaldoun Al Agha (LRI), Richard Systems), Philippe Jacquet (INRIA), Khaldoun Al Agha (LRI), Richard
Ogier (?), Song-Yean Cho (Samsung Software Center), Shubhranshu Singh Ogier (?), Song-Yean Cho (Samsung Software Center), Shubhranshu Singh
(Samsung AIT) and the entire IETF MANET working group. (Samsung AIT) and the entire IETF MANET working group.
Author's Address
Thomas Heide Clausen
LIX, Ecole Polytechnique, France
Phone: +33 6 6058 9349
Email: T.Clausen@computer.org
URI: http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/
Intellectual Property Statement Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79. found in BCP 78 and BCP 79.
skipping to change at page 69, line 41 skipping to change at page 81, line 41
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement Copyright Statement
Copyright (C) The Internet Society (2005). This document is subject Copyright (C) The Internet Society (2006). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights. except as set forth therein, the authors retain all their rights.
Acknowledgment Acknowledgment
Funding for the RFC Editor function is currently provided by the Funding for the RFC Editor function is currently provided by the
Internet Society. Internet Society.
 End of changes. 492 change blocks. 
1274 lines changed or deleted 1667 lines changed or added

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