draft-ietf-manet-olsrv2-01.txt   draft-ietf-manet-olsrv2-02.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: September 7, 2006 C. Dearlove Expires: December 28, 2006 C. Dearlove
BAE Systems Advanced Technology BAE Systems Advanced Technology
Centre Centre
P. Jacquet
Project Hipercom, INRIA
The OLSRv2 Design Team The OLSRv2 Design Team
MANET Working Group MANET Working Group
March 6, 2006 June 26, 2006
The Optimized Link-State Routing Protocol version 2 The Optimized Link-State Routing Protocol version 2
draft-ietf-manet-olsrv2-01 draft-ietf-manet-olsrv2-02
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 38 skipping to change at page 1, line 40
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 September 7, 2006. This Internet-Draft will expire on December 28, 2006.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2006). 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 embodies
optimization of the classical link state algorithm tailored to the an 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-
state information. A secondary optimization is, that OLSRv2 employs state information (i.e. reducing the cost of performing a network-
partial link-state information: each node maintains information of wide link-state broadcast). A secondary optimization is that OLSRv2
all destinations, but only a subset of links. This allows that only employs partial link-state information: each node maintains
select nodes diffuse link-state advertisements (i.e. reduces the information about all destinations, but only a subset of links. This
number of network-wide broadcasts) and that these advertisements allows that only select nodes diffuse link-state advertisements (i.e.
contain only a subset of links (i.e. reduces the size of each reduces the number of network-wide link-state broadcasts) and that
network-wide broadcast). The partial link-state information thus these advertisements contain only a subset of links (i.e. reduces the
obtained allows each OLSRv2 node to at all times maintain optimal (in size of each network-wide link-state broadcast). The partial link-
terms of number of hops) routes to all destinations in the network. state information thus obtained still allows each OLSRv2 node to at
all times maintain optimal (in terms of number of hops) routes to all
destinations in the network.
OLSRv2 imposes minimum requirements to the network by not requiring OLSRv2 imposes minimum requirements to the network by not requiring
sequenced or reliable transmission of control traffic. Furthermore, sequenced or reliable transmission of control traffic. Furthermore,
the only interaction between OLSRv2 and the IP stack is routing table the only interaction between OLSRv2 and the IP stack is routing table
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 . . . . . . . . . . . . . . . . . 6
2. Protocol Overview and Functioning . . . . . . . . . . . . . . 9 2. Protocol Overview and Functioning . . . . . . . . . . . . . . 8
2.1 Protocol Extensibility . . . . . . . . . . . . . . . . . . 11 2.1. Protocol Extensibility . . . . . . . . . . . . . . . . . . 10
3. Processing and Forwarding Repositories . . . . . . . . . . . . 13 3. Processing and Forwarding Repositories . . . . . . . . . . . . 11
3.1 Received Message Set . . . . . . . . . . . . . . . . . . . 13 3.1. Received Set . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 13 3.2. Fragment Set . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Processed Set . . . . . . . . . . . . . . . . . . . . . . 14 3.3. Processed Set . . . . . . . . . . . . . . . . . . . . . . 12
3.4 Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 14 3.4. Forwarded Set . . . . . . . . . . . . . . . . . . . . . . 12
3.5 Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5. Relay Set . . . . . . . . . . . . . . . . . . . . . . . . 12
4. Packet Processing and Message Forwarding . . . . . . . . . . . 16 4. Packet Processing and Message Forwarding . . . . . . . . . . . 14
4.1 Actions when Receiving an OLSRv2 Packet . . . . . . . . . 16 4.1. Actions when Receiving an OLSRv2 Packet . . . . . . . . . 14
4.2 Actions when Receiving an OLSRv2 Message . . . . . . . . . 16 4.2. Actions when Receiving an OLSRv2 Message . . . . . . . . . 14
4.3 Message Considered for Processing . . . . . . . . . . . . 16 4.3. Message Considered for Processing . . . . . . . . . . . . 15
4.4 Message Considered for Forwarding . . . . . . . . . . . . 18 4.4. Message Considered for Forwarding . . . . . . . . . . . . 17
5. Information Repositories . . . . . . . . . . . . . . . . . . . 21 5. Information Repositories . . . . . . . . . . . . . . . . . . . 20
5.1 Neighborhood Information Base . . . . . . . . . . . . . . 21 5.1. Neighborhood Information Base . . . . . . . . . . . . . . 20
5.1.1 Link Set . . . . . . . . . . . . . . . . . . . . . . . 21 5.1.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . 20
5.1.2 2-Hop Neighbor Set . . . . . . . . . . . . . . . . . . 22 5.1.2. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 21
5.1.3 Neighborhood Address Association Set . . . . . . . . . 23 5.1.3. MPR Selector Set . . . . . . . . . . . . . . . . . . . 21
5.1.4 MPR Set . . . . . . . . . . . . . . . . . . . . . . . 23 5.2. Topology Information Base . . . . . . . . . . . . . . . . 21
5.1.5 MPR Selector Set . . . . . . . . . . . . . . . . . . . 23 5.2.1. Advertised Neighbor Set . . . . . . . . . . . . . . . 21
5.1.6 Advertised Neighbor Set . . . . . . . . . . . . . . . 23 5.2.2. ANSN History Set . . . . . . . . . . . . . . . . . . . 22
5.2 Topology Information Base . . . . . . . . . . . . . . . . 24 5.2.3. Topology Set . . . . . . . . . . . . . . . . . . . . . 22
5.2.1 Topology Set . . . . . . . . . . . . . . . . . . . . . 24 5.2.4. Attached Network Set . . . . . . . . . . . . . . . . . 23
5.2.2 Attached Network Set . . . . . . . . . . . . . . . . . 24 5.2.5. Routing Set . . . . . . . . . . . . . . . . . . . . . 23
5.2.3 Routing Set . . . . . . . . . . . . . . . . . . . . . 25 6. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 24
6. OLSRv2 Control Message Structures . . . . . . . . . . . . . . 26 6.1. General OLSRv2 Message TLVs . . . . . . . . . . . . . . . 24
6.1 General OLSRv2 Message TLVs . . . . . . . . . . . . . . . 26 6.1.1. VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 24
6.1.1 VALIDITY_TIME TLV . . . . . . . . . . . . . . . . . . 26 6.2. HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 25
6.1.2 INTERVAL_TIME TLV . . . . . . . . . . . . . . . . . . 27 6.2.1. HELLO Message OLSRv2 Message TLVs . . . . . . . . . . 26
6.2 Local Interface Blocks . . . . . . . . . . . . . . . . . . 28 6.2.2. HELLO Message OLSRv2 Address Block TLVs . . . . . . . 26
6.3 HELLO Messages . . . . . . . . . . . . . . . . . . . . . . 28 6.3. TC Messages . . . . . . . . . . . . . . . . . . . . . . . 27
6.3.1 HELLO Message: Message TLVs . . . . . . . . . . . . . 29 6.4. TC Message: OLSRv2 Address Block TLVs . . . . . . . . . . 27
6.3.2 HELLO Message: Address Blocks TLVs . . . . . . . . . . 29 7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 29
6.4 TC Messages . . . . . . . . . . . . . . . . . . . . . . . 30 7.1. HELLO Message: Transmission . . . . . . . . . . . . . . . 29
7. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 31 8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 30
7.1 HELLO Message: Transmission . . . . . . . . . . . . . . . 33 8.1. Populating the MPR Selector Set . . . . . . . . . . . . . 30
8. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 34 8.2. Symmetric Neighborhood and 2-Hop Neighborhood Changes . . 31
8.1 Populating the Link Set . . . . . . . . . . . . . . . . . 34 9. TC Message Generation . . . . . . . . . . . . . . . . . . . . 32
8.2 Populating the 2-Hop Neighbor Set . . . . . . . . . . . . 36 9.1. TC Message: Transmission . . . . . . . . . . . . . . . . . 33
8.3 Populating the MPR Selector Set . . . . . . . . . . . . . 37 10. TC Message Processing . . . . . . . . . . . . . . . . . . . . 34
8.4 Neighborhood and 2-Hop Neighborhood Changes . . . . . . . 38 10.1. Single TC Message Processing . . . . . . . . . . . . . . . 34
9. TC Message Generation . . . . . . . . . . . . . . . . . . . . 40 10.1.1. Populating the ANSN History Set . . . . . . . . . . . 35
9.1 TC Message: Transmission . . . . . . . . . . . . . . . . . 41 10.1.2. Populating the Topology Set . . . . . . . . . . . . . 35
10. TC Message Processing . . . . . . . . . . . . . . . . . . . 42 10.1.3. Populating the Attached Network Set . . . . . . . . . 36
10.1 Checking Freshness & Validity of a TC message . . . . . . 42 10.2. Completed TC Message Processing . . . . . . . . . . . . . 37
10.2 Updating the Topology Set . . . . . . . . . . . . . . . . 43 10.2.1. Purging the Topology Set . . . . . . . . . . . . . . . 37
10.3 Purging Old Entries from the Topology Set . . . . . . . . 44 10.2.2. Purging the Attached Network Set . . . . . . . . . . . 37
10.4 Updating the Attached Networks Set . . . . . . . . . . . . 44 11. Populating the MPR Set . . . . . . . . . . . . . . . . . . . . 38
10.5 Purging Old Entries from the Attached Network Set . . . . 45 12. Populating Derived Sets . . . . . . . . . . . . . . . . . . . 39
10.6 Processing Unfragmented TC Messages . . . . . . . . . . . 45 12.1. Populating the Relay Set . . . . . . . . . . . . . . . . . 39
10.7 Processing Partially or Wholly Self-Contained 12.2. Populating the Advertised Neighbor Set . . . . . . . . . . 39
Fragmented TC Messagess . . . . . . . . . . . . . . . . . 45 13. Routing Table Calculation . . . . . . . . . . . . . . . . . . 40
11. Populating the MPR Set . . . . . . . . . . . . . . . . . . . 47 14. Proposed Values for Constants . . . . . . . . . . . . . . . . 44
12. Populating Derived Sets . . . . . . . . . . . . . . . . . . 48 14.1. Neighborhood Discovery Constants . . . . . . . . . . . . . 44
12.1 Populating the Relay Set . . . . . . . . . . . . . . . . . 48 14.2. Message Intervals . . . . . . . . . . . . . . . . . . . . 44
12.2 Populating the Advertised Neighbor Set . . . . . . . . . . 48 14.3. Holding Times . . . . . . . . . . . . . . . . . . . . . . 44
13. Populating the Neighborhood Address Association Set . . . . 49 14.4. Willingness . . . . . . . . . . . . . . . . . . . . . . . 44
14. Routing Table Calculation . . . . . . . . . . . . . . . . . 50 15. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 45
15. Proposed Values for Constants . . . . . . . . . . . . . . . 53 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 46
15.1 Message Intervals . . . . . . . . . . . . . . . . . . . . 53 16.1. Multicast Addresses . . . . . . . . . . . . . . . . . . . 46
15.2 Holding Times . . . . . . . . . . . . . . . . . . . . . . 53 16.2. Message Types . . . . . . . . . . . . . . . . . . . . . . 46
15.3 Willingness . . . . . . . . . . . . . . . . . . . . . . . 53 16.3. TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 46
15.4 Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 17. References . . . . . . . . . . . . . . . . . . . . . . . . . . 48
16. Representing Time . . . . . . . . . . . . . . . . . . . . . 55 17.1. Normative References . . . . . . . . . . . . . . . . . . . 48
17. IANA Considerations . . . . . . . . . . . . . . . . . . . . 56 17.2. Informative References . . . . . . . . . . . . . . . . . . 48
17.1 Multicast Addresses . . . . . . . . . . . . . . . . . . . 56 Appendix A. Example Heuristic for Calculating MPRs . . . . . . . 49
17.2 Message Types . . . . . . . . . . . . . . . . . . . . . . 56 Appendix B. Heuristics for Generating Control Traffic . . . . . 52
17.3 TLV Types . . . . . . . . . . . . . . . . . . . . . . . . 56 Appendix C. Protocol and Port Number . . . . . . . . . . . . . . 53
18. References . . . . . . . . . . . . . . . . . . . . . . . . . 57 Appendix D. Packet and Message Layout . . . . . . . . . . . . . 54
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 58 Appendix D.1. OLSRv2 Packet Format . . . . . . . . . . . . . . . . 54
A. Example Heuristic for Calculating MPRs . . . . . . . . . . . . 59 Appendix E. Node Configuration . . . . . . . . . . . . . . . . . 59
B. Example Algorithms for Generating Control Traffic . . . . . . 62 Appendix F. Jitter . . . . . . . . . . . . . . . . . . . . . . . 60
B.1 Example Algorithm for Generating HELLO messages . . . . . 62 Appendix G. Security Considerations . . . . . . . . . . . . . . 63
B.2 Example Algorithm for Generating TC messages . . . . . . . 63 Appendix G.1. Confidentiality . . . . . . . . . . . . . . . . . . 63
C. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 65 Appendix G.2. Integrity . . . . . . . . . . . . . . . . . . . . . 63
D. Packet and Message Layout . . . . . . . . . . . . . . . . . . 66 Appendix G.3. Interaction with External Routing Domains . . . . . 64
D.1 OLSRv2 Packet Format . . . . . . . . . . . . . . . . . . . 66 Appendix G.4. Node Identity . . . . . . . . . . . . . . . . . . . 65
E. Node Configuration . . . . . . . . . . . . . . . . . . . . . . 73 Appendix H. Flow and Congestion Control . . . . . . . . . . . . 66
F. Security Considerations . . . . . . . . . . . . . . . . . . . 74 Appendix I. Contributors . . . . . . . . . . . . . . . . . . . . 67
F.1 Confidentiality . . . . . . . . . . . . . . . . . . . . . 74 Appendix J. Acknowledgements . . . . . . . . . . . . . . . . . . 68
F.2 Integrity . . . . . . . . . . . . . . . . . . . . . . . . 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 69
F.3 Interaction with External Routing Domains . . . . . . . . 75 Intellectual Property and Copyright Statements . . . . . . . . . . 70
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 [1]. 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 accommodate 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. it 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" (MPRs). selects a set of its neighbor nodes as "MultiPoint Relays" (MPRs).
In OLSRv2, only nodes that are selected as such MPRs are then Only nodes that are selected as such MPRs are then responsible for
responsible for forwarding control traffic intended for diffusion forwarding control traffic intended for diffusion into the entire
into the entire network. MPRs provide an efficient mechanism for network. MPRs provide an efficient mechanism for flooding control
flooding control traffic by reducing the number of transmissions 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. Thus, as reachability to the nodes which have selected it as an MPR. Thus, as
well as 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 routes through MPRs automatically avoids the problems associated with
with data packet transfer over uni-directional links (such as the data packet transfer over uni-directional links (such as the problem
problem of not getting link-layer acknowledgments for data packets at of not getting link-layer acknowledgments for data packets at each
each hop, for link-layers employing this technique for unicast 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
[5]. [6].
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 [2]. document are to be interpreted as described in RFC2119 [2].
Additionally, this document uses the following terminology: MANET specific terminology is to be interpreted as described in [3]
and [4].
node - a MANET router which implements the Optimized Link State Additionally, this document uses the following terminology:
Routing protocol as specified in this document.
OLSRv2 interface - A network device participating in a MANET running node - A MANET router which implements the Optimized Link State
OLSRv2. A node may have several OLSRv2 interfaces, each interface Routing protocol version 2 as specified in this document.
assigned one or more IP addresses.
neighbor - A node X is a neighbor of node Y if node Y can hear node X OLSRv2 interface - A MANET interface, running OLSRv2.
(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
1-hop neighbor.
2-hop neighbor - A node X is a 2-hop neighbor of node Y if node X is symmetric strict 2-hop neighbor - A symmetric 2-hop neighbor which is
a neighbor of a neighbor of node Y, but is not node Y itself. not a symmetric 1-hop neighbor and is not a 2-hop neighbor only
through a symmetric 1-hop neighbor with willingness WILL_NEVER.
(If node Z is a symmetric 2-hop neighbor of node X then there is a
node Y such that node Z is a symmetric 1-hop neighbor of node Y
and node Y is a symmetric 1-hop neighbor of node X. If node Z is a
symmetric strict 2-hop neighbor of node X then there is such a
node Y with willingness which is not WILL_NEVER.)
strict 2-hop neighbor - a 2-hop neighbor which is not a neighbor of symmetric strict 2-hop neighborhood - The set of the symmetric strict
the node, and is not a 2-hop neighbor only through a neighbor with 2-hop neighbors of node X.
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 symmetric
neighbor, node X, to "re-transmit" all the broadcast messages that 1-hop neighbor, node X, to "re-transmit" all the broadcast
it receives from node X, provided that the message is not a messages that it receives from node X, provided that the message
duplicate, and that the time to live field of the message is is not a duplicate, and that the hop limit field of the message is
greater than one. greater than one.
multipoint relay selector (MPR selector, MS) - A node which has MPR selector - A node which has selected its symmetric 1-hop
selected its 1-hop neighbor, node X, as one of its multipoint neighbor, node X, as one of its MPRs is 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
nodes, where at least one interface is able to hear (i.e. receive
traffic from) the other.
symmetric link - A link where both interfaces are able to hear (i.e.
receive messages from) the other.
asymmetric link - A link which is not symmetric.
symmetric 1-hop neighborhood - The symmetric 1-hop neighborhood of
any node X is the set of nodes which have at least one symmetric
link to node X.
symmetric 2-hop neighborhood - The symmetric 2-hop neighborhood of
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 strict 2-hop neighborhood - The symmetric strict 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
nor reachable only through a symmetric 1-hop neighbor of node X
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) [6], [7]. It is well suited to large and dense networks of (MANETs) [7], [8]. 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 need be 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 continuously, traffic is subject to no
delays due to buffering/route-discovery. This continued route delays due to buffering/route-discovery. This continued route
maintenance may be done using periodic message exchange, as detailed maintenance may be done using periodic message exchange, as detailed
in this specification, or triggered by external events if available. in this specification, or triggered by external events if available.
OLSRv2 supports nodes which have multiple interfaces which OLSRv2 supports nodes which have multiple interfaces which
participate in the MANET. OLSRv2, additionally, supports nodes which participate in the MANET. OLSRv2, additionally, supports nodes which
have non-MANET interfaces which can serve as (if configured to do so) have non-MANET interfaces which can serve as (if configured to do so)
gateways towards other networks. gateways towards other networks.
The message exchange format, contained in previous versions of this The message exchange format, contained in previous versions of this
specification, has been factored out to an independant specification specification, has been factored out to an independent specification
[4], which is used for carrying OLSRv2 control signals. OLSRv2 is [3], which is used for carrying OLSRv2 control signals. OLSRv2 is
thereby able to accommodate for extensions via "external" and thereby able to allow for extensions via "external" and "internal"
"internal" extensibility. External extensibility implies that a extensibility. External extensibility implies that a protocol
protocol extension may specify and exchange new message types which extension may specify and exchange new message types, formatted
can be forwarded and delivered correctly according to [4]. Internal according to [3], which can be forwarded and delivered correctly.
extensibility implies, that a protocol extension may define Internal extensibility implies that a protocol extension may define
additional attributes to be carried embedded in the OLSRv2 control additional attributes to be carried embedded in the standard OLSRv2
messages, detailed in this specification, while these OLSRv2 control control messages detailed in this specification, using the TLV
messages with additional attributes can still be correctly understood mechanism specified in [3], while OLSRv2 control messages with
by all OLSRv2 nodes. additional attributes can still be correctly understood by all OLSRv2
nodes.
The OLSRv2 neighborhood discovery protocol using HELLO messages has
likewise been factored out to an independent specification [4]. This
neighborhood discovery protocol serves to ensure that each OLSRv2
node has available continuously updated information repositories
describing the node's 1-hop and 2-hop neighbors. [4] uses the message
format specified in [3], and hence is extensible as described above.
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:
o periodic, unacknowledged transmission of all control messages; o periodic, unacknowledged transmission of all control messages;
o optimized flooding for global link-state information diffusion; o optimized flooding for global link-state information diffusion;
o partial topology maintenance -- each node will know of all o partial topology maintenance - each node knows only a subset of
destinations and a subset of links in the network. the links in the network, sufficient for a minimum hop route to
all destinations.
More specifically, OLSRv2 consists of the following main components:
o A general and flexible signaling framework, allowing for
information exchange between OLSRv2 nodes. This framework allows
for both local information exchange (between neighboring nodes)
and global information exchange using an optimized flooding
mechanism denoted "MPR flooding".
o A specification of local signaling, denoted HELLO messages. HELLO
messages in OLSRv2 serve to:
* discover links to adjacent OLSR nodes;
* perform bidirectionality check on the discovered links;
* advertise neighbors and hence discover 2-hop neighbors; Using the message exchange format [3] and the neighborhood discovery
protocol [4], OLSRv2 also contains the following main components:
* signal MPR selection. o a TLV, to be included within the HELLO messages of [4], allowing a
node to signal MPR selection;
HELLO messages are emitted periodically, thereby allowing nodes to o an optimized flooding mechanism for global information exchange,
continuously track changes in their local neighborhoods. denoted "MPR flooding";
o A specification of global signaling, denoted TC messages. TC o a specification of global signaling, denoted TC (Topology Control)
messages in OLSRv2 serve to: messages. TC 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 * inject addresses of hosts and networks for which they may serve
as a gateway into the entire network. 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 The use of [4] allows a node to continuously track changes to its
acquire and maintain information about its immediate neighborhood. local topology up to two hops away. This allows a node to make
This includes information about immediate neighbors, as well as nodes
which are two hops away. By HELLO messages being exchanged
periodically, a node learns about changes in the neighborhood (new
nodes emerging, old nodes disappearing) without requiring explicit
mechanisms for doing so.
Based on the local topology information, acquired through the
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.
This is done through the notion of Multipoint Relays. This is done through the notion of MultiPoint Relays (MPRs).
The idea of multipoint relays is to minimize the overhead of flooding The idea of MPRs is to minimize the overhead of flooding messages in
messages in the network by reducing redundant retransmissions in the the network by reducing redundant retransmissions of messages in the
same region. Each node in the network selects a set of nodes in its same region. Each node in the network selects an MPR Set, a set of
symmetric 1-hop neighborhood which may retransmit its messages. This nodes in its symmetric 1-hop neighborhood which may retransmit its
set of selected neighbor nodes is called the "Multipoint Relay" (MPR) messages. The 1-hop neighbors of a node which are not in its MPR set
Set of that node. The neighbors of node N which are *NOT* in its MPR receive and process broadcast messages, but do not retransmit
set, receive and process broadcast messages but do not retransmit broadcast messages received from that node. The MPR Set of a node X
broadcast messages received from node N. The MPR Set of a node is may be any subset of its symmetric 1-hop neighborhood such that every
selected such that it covers (in terms of radio range) all symmetric node in its symmetric strict 2-hop neighborhood has a symmetric link
strict 2-hop nodes. The MPR Set of N, denoted as MPR(N), is then an to a node in the MPR Set of node X. The MPR Set of a node may thus be
arbitrary subset of the symmetric 1-hop neighborhood of N which said to "cover" the node's symmetric strict 2-hop neighborhood. The
satisfies the following condition: every node in the symmetric strict smaller a MPR Set, the fewer times messages are forwarded and the
2-hop neighborhood of N MUST have a symmetric link towards MPR(N). less resulting control traffic overhead. [8] gives an analysis and
The smaller a MPR Set, the less control traffic overhead results from example of MPR selection algorithms. Note that as long as the
the routing protocol. [7] gives an analysis and example of MPR condition above is satisfied, any algorithm selecting MPR Sets is
selection algorithms. Notice, that as long as the condition above is acceptable in terms of implementation interoperability.
satisfied, any algorithm selecting MPR Sets is acceptable in terms of
implementation interoperability. Each node maintains information about the set of symmetric 1-hop
neighbors that have selected it as MPR. This set is called the MPR
Selector Set of the node. A node obtains this information from an
MPR TLV which is inserted into the HELLO message exchange of [4].
Each node maintains information about the set of neighbors that have
selected it as MPR. This set is called the "Multipoint Relay
Selector Set" (MPR Selector Set) of a node. A node obtains this
information from periodic HELLO messages received from the neighbors.
Each node also maintains a Relay Set, which is the set of nodes for 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 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 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. nodes in the MPR Selector set and MAY contain additional nodes.
A broadcast message, intended to be diffused in the whole network,
coming from any of the nodes in the Relay Set of node N is assumed to
be retransmitted by node N, if N has not received it yet. This set
can change over time (e.g., when a node selects another MPR Set) and
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. For this purpose, a node maintains an injected into the network. For this purpose, a node maintains an
Advertised Neighbor Set which MUST contain all the nodes in the MPR Advertised Neighbor Set which MUST contain all the nodes in the MPR
selector set and MAY contain additional nodes. If the Advertised selector set and MAY contain additional nodes. If the Advertised
Neighbor Set of a node is non-empty, TC messages, containing the Neighbor Set of a node is non-empty, it is reported in TC messages
links between the node and the nodes in the Advertised Neighbor Set, generated by that node. If the Advertised Neighbor Set is empty, TC
are not generated, unless needed for gateway reporting or multiple messages are not generated by that node, unless needed for gateway
interface address association (if the latter case only, with minimal reporting, or for a short period to accelerate the removal of
scope). unwanted links.
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 may occur frequently in radio
due to collisions or other transmission problems. networks due to collisions or other transmission problems.
Also, OLSRv2 does not require sequenced delivery of messages. Each
control message contains a sequence number which is incremented for
each message. Thus the recipient of a control message can, if
required, easily identify which information is more recent - even if
messages have been re-ordered while in transmission. Furthermore,
OLSRv2 provides support for protocol extensions such as sleep mode
operation, multicast-routing etc. Such extensions may be introduced
as additions to the protocol without breaking backwards compatibility
with earlier versions.
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
with routing table management. OLSR sends its own control messages
using UDP.
2.1 Protocol Extensibility
This specification defines and uses two OLSRv2 message types, HELLO
and TC. As for OLSRv1 [1] extensions to OLSRv2 may define new
message types to carry additional information. This may be
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).
All new messages must be syntactically OLSRv2 messages, as defined in OLSRv2 does not require sequenced delivery of messages. Each control
[4]. (Some additional constraints to that specification are added message contains a sequence number which is incremented for each
for OLSRv2 packets and messages, requiring full packet and message message. Thus the recipient of a control message can, if required,
headers.) Note that if it is required to include one or more blocks easily identify which information is more recent - even if messages
of unstructured data in such a message (possibly as its only content) have been re-ordered while in transmission.
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.)
A network may contain nodes both aware of, and unaware of, any new OLSRv2 does not require any changes to the format of IP packets, any
message types. The originator of a message can control whether a existing IP stack can be used as is: OLSRv2 only interacts with
message flooded through the network is forwarded by nodes which are routing table management. OLSR sends its control messages using UDP.
unaware of the message type, thus reaching all nodes in the network,
or is only flooded by nodes which recognise the message type.
OLSRv2 also supports an alternative, and more powerful, extension 2.1. Protocol Extensibility
mechanism which was not supported by OLSRv1, that of adding new
information to an already defined message type, whilst still leaving
the predefined information unchanged and usable, including by a node
which does not recognise the new information. This may be considered
to be "internal" extensibility of a message.
The mechanism for this extensibility is the use of TLV (type-length- OLSRv2 uses the neighborhood discovery mechanism of [4], and
value) structures in the message format defined in [4] to carry specifies additionally one message type, TC, and a number of TLVs.
information associated with either the message as a whole, or with All messages exchanged by [4] and by OLSRv2 use and comply with the
one or more addresses carried in the message. The messages defined extensible message exchange format of [3], thus OLSR provides both
in this specification carry two types of addresses, those of the "external" extensibility (addition of new message types as in OLSRv1
originating node's own interfaces participating in OLSRv2, and those [1]) and "internal" extensibility (addition of information to
of neighbouring nodes or networks to which it has a route. (New existing messages through TLVs) as described in [3].
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.
Those nodes which do not recognise newly defined TLV types ignore the Those nodes which do not recognize a new message type ("external
added TLVs. (This is facilitated by that the TLVs defined in this extensibility") will ignore this message type for processing, but
specification, or in [4], have the lowest type numbers and that TLVs will correctly forward the message, if specified in the message
must be included in type order, as specified in [4].) It is header. Those nodes which do not recognize a newly defined TLV type
important that newly defined TLV types permit this behaviour. ignore the added TLV, but process (if the message type is recognized)
the message correctly, as well as forwards the message, if specified
in the message header.
3. Processing and Forwarding Repositories 3. Processing and Forwarding Repositories
The following data-structures are employed in order to ensure that a The following data structures are employed in order to ensure that a
message is processed at most once and is forwarded at most once per message is processed at most once and is forwarded at most once per
interface of a node, and that fragmented content is treated interface of a node, and that fragmented content is treated
correctly. correctly.
3.1 Received Message Set 3.1. Received Set
Each node maintains, for each OLSRv2 interface it possesses, a set of Each node maintains, for each OLSRv2 interface, a set of signatures
signatures of messages, which have been received over that interface, of messages, which have been received over that interface, in the
in the form of "Received Tuples": form of "Received Tuples":
(RX_type, RX_addr, RX_seq_number, RX_time) (RX_type, RX_orig_addr, RX_seq_number, RX_time)
where: where:
RX_type is the received message type, or zero if the received message RX_type is the received message type, or zero if the received message
sequence number is not type-specific. sequence number is not type-specific;
RX_addr is the originator address of the received message; RX_orig_addr is the originator address of the received message;
RX_seq_number is the message sequence number of the received message; RX_seq_number is the message sequence number of the received message;
RX_time specifies the time at which this record expires and *MUST* be RX_time specifies the time at which this Received Tuple expires and
removed. *MUST* be removed.
In a node, this is denoted the "Received Message Set" for that In a node, this is denoted the "Received Set" for that interface.
interface.
3.2 Fragment Set 3.2. Fragment Set
Each node stores messages containing fragmented content until all Each node stores messages containing fragmented content until all
fragments are received and the message processing can be completed, fragments are received and the message processing can be completed,
in the form of "Fragment Tuples": in the form of "Fragment Tuples":
(FG_message, FG_time) (FG_message, FG_time)
where: where:
FG_message is the message containing fragmented content; FG_message is the message containing fragmented content;
FG_time specifies the time at which this record expires and MUST be FG_time specifies the time at which this Fragment Tuple expires and
removed. MUST be removed.
In a node, this is denoted the "Fragment Set". In a node, this is denoted the "Fragment Set".
3.3 Processed Set 3.3. Processed Set
Each node maintains a set of signatures of messages which have been Each node maintains a set of signatures of messages which have been
processed by the node, in the form of "Processed Tuples": processed by the node, in the form of "Processed Tuples":
(P_type, P_addr, P_seq_number, P_time) (P_type, P_orig_addr, P_seq_number, P_time)
where: where:
P_type is the processed message type, or zero if the processed P_type is the processed message type, or zero if the processed
message sequence number is not type-specific. message sequence number is not type-specific;
P_addr is the originator address of the processed message; P_orig_addr is the originator address of the processed message;
P_seq_number is the message sequence number 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 Processed Tuple expires and
removed. *MUST* be removed.
In a node, this is denoted the "Processed Set". In a node, this is denoted the "Processed Set".
3.4 Forwarded Set 3.4. Forwarded Set
Each node maintains a set of signatures of messages which have been Each node maintains a set of signatures of messages which have been
retransmitted/forwarded by the node, in the form of "Forwarded retransmitted/forwarded by the node, in the form of "Forwarded
Tuples": Tuples":
(FW_type, FW_addr, FW_seq_number, FW_time) (FW_type, FW_orig_addr, FW_seq_number, FW_time)
where: where:
FW_type is the forwarded message type, or zero if the forwarded FW_type is the forwarded message type, or zero if the forwarded
message sequence number is not type-specific. message sequence number is not type-specific;
FW_addr is the originator address of the forwarded message; FW_orig_addr is the originator address of the forwarded message;
FW_seq_number is the message sequence number of the forwarded FW_seq_number is the message sequence number of the forwarded
message; message;
FW_time specifies the time at which this record expires and *MUST* be FW_time specifies the time at which this Forward Tuple expires and
removed. *MUST* be removed.
In a node, this is denoted the "Forwarded Set". In a node, this is denoted the "Forwarded Set".
3.5 Relay Set 3.5. Relay Set
Each node maintains a set of neighbor interface addresses for which Each node maintains a set of neighbor interface addresses for which
it is to relay flooded messages, in the form of "Relay Tuples": it is to relay flooded messages, in the form of "Relay Tuples":
(RY_if_addr) (RY_iface_addr)
where: where:
RY_if_addr is the address of a neighbor interface for which the node RY_iface_addr is the address of a neighbor interface for which the
SHOULD relay flooded messages. node SHOULD relay flooded messages. This MUST include a prefix
length.
In a node, this is denoted the "Relay Set". In a node, this is denoted the "Relay Set".
4. Packet Processing and Message Forwarding 4. Packet Processing and Message Forwarding
Upon receiving a basic packet, a node examines each of the message On receiving a basic packet, as defined in [3], a node examines each
headers. If the message type is known to the node, the message is of the message headers. If the message type is known to the node,
processed locally according to the specifications for that message the message is processed locally according to the specifications for
type. The message is also independently evaluated for forwarding. that message type. The message is also independently evaluated for
forwarding.
4.1 Actions when Receiving an OLSRv2 Packet 4.1. Actions when Receiving an OLSRv2 Packet
Upon receiving a packet, a node MUST perform the following task: On receiving a packet, a node MUST perform the following tasks:
1. If the packet contains no messages (i.e. the packet length is 1. The packet may be fully parsed on reception, or the packet and
less than or equal to the size of the packet header) or if the its messages may be parsed only as required. (It is possible to
packet cannot be parsed into messages, the packet MUST be parse the packet header, or determine its absence, without
silently discarded. parsing any messages. It is possible to divide the packet into
messages without even fully parsing their headers. It is
possible to determine whether a message is to be forwarded, and
to forward it, without parsing its body. It is possible to
determine whether a message is to be processed without parsing
its body. It is possible to determine if that processing may be
delayed because the message is a fragment by inspecting the first
few octets of the message body without fully parsing it.)
2. Otherwise, each message in the packet is treated according to 2. If parsing fails at any point the relevant entity (packet or
Section 4.2. message) MUST be silently discarded, other parts of the packet
(up to the whole packet) MAY be silently discarded;
4.2 Actions when Receiving an OLSRv2 Message 3. Otherwise if the packet header is present and it contains a
packet TLV block, then each TLV in it is processed according to
its type;
4. Otherwise each message in the packet, if any, is treated
according to Section 4.2.
4.2. Actions when Receiving an OLSRv2 Message
A node MUST perform the following tasks for each received OLSRv2 A node MUST perform the following tasks for each received OLSRv2
message: message:
1. If the received OLSRv2 message header cannot be correctly parsed 1. If the received OLSRv2 message header cannot be correctly parsed
according to the specification in [4], or if the originator according to the specification in [3], or if the node recognizes
address of the message is an interface address of the receiving from the originator address of the message that the message is
node then the message MUST be silently discarded; one which the receiving node itself originated, then the message
MUST be silently discarded;
2. Otherwise: 2. Otherwise:
1. If the message is of a known type then the message is 1. If the received message is of a known type then the message
considered for processing according to Section 4.3; is considered for processing according to Section 4.3, AND;
2. If for the received message TTL > 0, and if either the 2. If for the received message (<hop-limit> + <hop-count>) > 1,
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 then the message is considered for forwarding according to
Section 4.4. Section 4.4.
4.3 Message Considered for Processing 4.3. Message Considered for Processing
If a message is considered for processing, the following tasks MUST If a message (the "current message") is considered for processing,
be performed: the following tasks MUST be performed:
1. If an entry exists in the Processed Set where: 1. If an entry exists in the Processed Set where:
* P_type == the message type, or 0 if bit 2 of the message * P_type == the message type of the current message, or 0 if the
semantics octet (in the message header) is clear, AND; typedep bit in the message semantics octet (in the message
header) of the current message is cleared ('0'), AND;
* P_addr == the originator address of the message, AND; * P_orig_addr == the originator address of the current message,
AND;
* P_seq_number == the sequence number of the message. * P_seq_number == the message sequence number of the current
message.
then the message MUST NOT be processed. then the current message MUST NOT be processed.
2. Otherwise: 2. Otherwise:
1. Create an entry in the Processed Set with: 1. Create an entry in the Processed Set with:
+ P_type = the message type, or 0 if bit 2 of the message + P_type = the message type of the current message, or 0 if
semantics octet (in the message header) is clear; the typedep bit in the message semantics octet (in the
message header) of the current message is cleared ('0');
+ P_addr = originator address of the message; + P_orig_addr = originator address of the current message;
+ P_seq_number = sequence number of the message; + P_seq_number = sequence number of the current message;
+ P_time = current time + P_HOLD_TIME. + P_time = current time + P_HOLD_TIME.
2. If the message does not contain a message TLV of type 2. If the current message does not contain a valid message TLV
Fragment (or if it does and the indicated number of fragments with Type == FRAGMENTATION (or if it does and the indicated
is one) then process the message fully according to its type. number of fragments is one) then process the message fully
according to its type.
3. Otherwise: 3. Otherwise:
1. If the message is "wholly or partially self-contained" as 1. If the current message does not contain a valid message
indicated by its Fragment TLV then process the current TLV with Type == CONT_SEQ_NUM then the current message
message as far as possible according to its type; MUST be silently discarded;
2. If the Fragment Set includes any messages with the same 2. Otherwise if the current message is "partially or wholly
originator address and content sequence number as the self-contained", as indicated by the notselfcont bit in
current message, and either the same fragment number or a the Value field of the TLV with Type == FRAGMENTATION
different number of fragments, then remove these messages being cleared ('0'), then process the current message as
are from the Fragment Set; far as possible according to its type;
3. If the Fragment Set includes messages containing all the 3. If the Fragment Set includes any Fragment Tuples with:
remaining fragments of the same overall message as the
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);
4. Otherwise, the current message is added to the Fragment - either the typedepseq bit in the Value field of the
Set with a FG_time of FG_HOLD_TIME (possibly replacing an TLV with Type == FRAGMENTATION in the current message
identical and previous received instance of the same is cleared ('0') OR message type of FG_message ==
fragment of the same content). message type of current message, AND;
4.4 Message Considered for Forwarding - originator address of FG_message == originator address
of current message, AND;
If a message is considered for forwarding then if it is either of a - content sequence number (the Value field of the
message type defined in this document, or of an unknown message type message TLV with Type == CONT_SEQ_NUM) of FG_message
it MUST use the following algorithm. A message type not defined in == content sequence number of current message; AND
this document may specify the use of this, or another algorithm.
- either fragment number (from the Value field of the
TLV with Type == FRAGMENTATION) in FG_message ==
fragment number of current message OR number of
fragments (from the Value field of the TLV with Type
== FRAGMENTATION) of FG_message != number of fragments
of current message;
then remove these Fragment Tuples from the Fragment Set;
4. If the Fragment Set includes Fragment Tuples containing
all the remaining fragments of the same overall message
as the current message, i.e. if the number of Fragment
Tuples such that:
- either the typedepseq bit in the Value field of the
TLV with Type == FRAGMENTATION in the current message
is cleared ('0') OR message type of FG_message ==
message type of current message, AND;
- originator address of FG_message == originator address
of current message, AND;
- content sequence number (the Value field of the
message TLV with Type == CONT_SEQ_NUM) of FG_message
== content sequence number of current message
is equal to (number of fragments of current message, less
one) then all of these Fragment Tuples are removed from
the Fragment Set and their messages processed according
to their type (taking account of any previous processing
of any which are partially or wholly self-contained);
5. Otherwise, a Fragment Tuple is added to the Fragment Set
with
- FG_message = current message;
- FG_time = current time + FG_HOLD_TIME;
possibly replacing a previously received instance of the
same fragment.
4.4. Message Considered for Forwarding
If a message is considered for forwarding, and it is either of a
message type defined in this document or of an unknown message type,
then 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 (Such an other algorithm MAY use the Received Set for the receiving
interface, it SHOULD use the Forwarded Set similarly to the following interface, it SHOULD use the Forwarded Set similarly to the following
algorithm.) algorithm.)
If a message is considered for forwarding according to this If a message is considered for forwarding according to this
algorithm, the following tasks MUST be performed: algorithm, the following tasks MUST be performed:
1. If there is no symmetric link in the Link Set between the 1. If the sending interface (as indicated by the source interface of
receiving interface and the sending interface (as indicated by the IP datagram containing the message) does not match (taking
the source interface of the IP datagram containing the message) into account any address prefix of) any N_neighbor_iface_addr in
then the message MUST be silently discarded. any Symmetric Neighbor Tuple, then the message MUST be silently
discarded.
2. Otherwise: 2. Otherwise:
1. If an entry exists in the Received Set for the receiving 1. If an entry exists in the Received Set for the receiving
interface, where: interface, where:
+ RX_type == the message type, or 0 if bit 2 of the message + RX_type == the message type, or 0 if the typedep bit in
semantics octet (in the message header) is clear, AND; the message semantics octet (in the message header) is
cleared ('0'), AND;
+ RX_addr == the originator address of the received message,
AND;
+ RX_orig_addr == the originator address of the received
message, AND;
+ RX_seq_number == the sequence number of the received + RX_seq_number == the sequence number of the received
message. message.
then the message MUST be silently discarded. then the message MUST be silently discarded.
2. Otherwise: 2. Otherwise:
1. Create an entry in the Received Set for the receiving 1. Create an entry in the Received Set for the receiving
interface with: interface with:
- RX_type = the message type, or 0 if bit 2 of the - RX_type = the message type, or 0 if the typedep bit in
message semantics octet (in the message header) is the message semantics octet (in the message header) is
clear; cleared ('0');
- RX_addr = originator address of the message; - RX_orig_addr = originator address of the message;
- RX_seq_number = sequence number of the message; - RX_seq_number = sequence number of the message;
- RX_time = current time + RX_HOLD_TIME. - RX_time = current time + RX_HOLD_TIME.
2. If an entry exists in the Forwarded Set where: 2. If an entry exists in the Forwarded Set where:
- FW_type == the message type, or 0 if bit 2 of the - FW_type == the message type, or 0 if the typedep bit
message semantics octet (in the message header) is in the message semantics octet (in the message header)
clear; is cleared ('0');
- FW_addr == the originator address of the received - FW_orig_addr == the originator address of the received
message, AND; message, AND;
- FW_seq_number == the sequence number of the received - FW_seq_number == the sequence number of the received
message. message.
then the message MUST be silently discarded. then the message MUST be silently discarded.
3. Otherwise if an entry exists in the Relay Set, where 3. Otherwise if a Relay Tuple exists whose RY_iface_addr
RY_if_addr == source address of the message (as indicated matches (taking into account any address prefix) the
by the source interface of the IP datagram containing the sending interface (as indicated by the source interface
message): of the IP datagram containing the message):
1. Create an entry in the Forwarded Set with: 1. Create an entry in the Forwarded Set with:
o FW_type = the message type, or 0 if bit 2 of the o FW_type = the message type, or 0 if the typedep
message semantics octet (in the message header) is bit in the message semantics octet (in the message
clear; header) is cleared ('0');
o FW_addr = originator address of the message;
o FW_orig_addr = originator address of the message;
o FW_seq_number = sequence number of the message; o FW_seq_number = sequence number of the message;
o FW_time = current time + FW_HOLD_TIME. o FW_time = current time + FW_HOLD_TIME.
2. The message header is modified as follows: 2. The message header is modified as follows:
o Decrement the message TTL by 1; o Decrement <hop-limit> in the message header by 1;
o Increment <hop-count> in the message header by 1;
o Increment the message hop count by 1;
3. Transmit the message on all OLSRv2 interfaces of the 3. Transmit the message on all OLSRv2 interfaces of the
node. node.
Messages are retransmitted in the format specified by [4] with the Messages are retransmitted in the format specified by [3] with the
All-OLSRv2-Multicast address (see Section 17.1) as destination IP ALL-MANET-NEIGHBORS address (see Section 16.1) as destination IP
address. address.
5. Information Repositories 5. Information Repositories
The purpose of OLSRv2 is to determine the Routing Set, which may be The purpose of OLSRv2 is to determine the Routing Set, which may be
used to update IP's Routing Table, providing "next hop" routing used to update IP's Routing Table, providing "next hop" routing
information for IP datagrams. In order to accomplish this, OLSRv2 information for IP datagrams. In order to accomplish this, OLSRv2
maintains a number of protocol sets, the information repository of uses a number of protocol sets: the Neighborhood Information Base,
the protocol. These sets are updated, directly or indirectly, by the provided by [4], is in OLSRv2 augmented by information allowing MPR
exchange of messages between nodes in the network. In turn the selection and signaling. Additionally, OLSRv2 specifies a Topology
contents of these messages are largely determined by the contents of Information Base, which describes the information used for and
a part of the information repositories, the Neighbourhood Information acquired through TC message exchange - in other words: the topology
Base, which contains information about the 1- and 2- hop base represents the network topology graph as seen from each node.
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 Neighborhood Information Base
The neighborhood information base stores information about links
between local interfaces and interfaces on adjacent nodes.
5.1.1 Link Set
A node records a set of "Link Tuples":
(L_local_iface_addr, L_neighbor_iface_addr,
L_SYM_time, L_ASYM_time, L_willingness, L_time).
where:
L_local_iface_addr is the interface address of the local node;
L_neighbor_iface_addr is the interface address of the neighbor node;
L_SYM_time is the time until which the link is considered symmetric;
L_ASYM_time is the time until which the neighbor interface is
considered heard;
L_willingness is the nodes willingness to be selected as MPR;
L_time specifies when this record expires and *MUST* be removed.
+-------------+-------------+--------------+
| L_SYM_time | L_ASYM_time | L_STATUS |
+-------------+-------------+--------------+
| Expired | Expired | LOST |
| | | |
| Not Expired | Expired | SYMMETRIC |
| | | |
| Not Expired | Not Expired | SYMMETRIC |
| | | |
| Expired | Not Expired | ASYMMETRIC |
+-------------+-------------+--------------+
Table 1
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.
In a node, the set of Link Tuples is denoted the "Link Set".
5.1.2 2-Hop Neighbor Set
A node records a set of "2-Hop Neighbor Tuples"
(N2_local_iface_addr, N2_neighbor_iface_addr, N2_2hop_iface_addr, N2_time)
describing symmetric links between its neighbors and the symmetric
2-hop neighborhood.
N2_local_iface_addr is the address of the local interface over which
the information was received;
N2_neighbor_iface_addr is the interface address of a neighbor; Addresses (other than originator addresses) recorded in the
Neighborhood Information Base and the Topology Information Base MUST
all be recorded with prefix lengths, in order to allow comparison
with addresses received in HELLO and TC messages. For the Topology
Information Base this applies to A_neighbor_iface_addr,
T_dest_iface_addr, T_last_iface_addr, AN_net_addr, AN_gw_iface_addr,
R_dest_addr, R_dest_addr, R_next_iface_addr and R_local_iface_addr,
but not AH_orig_addr. For the Neighborhood Information Base see [4].
N2_2hop_iface_addr is the interface address of a 2-hop neighbor with 5.1. Neighborhood Information Base
a symmetric link to the node with interface address
N_neighbor_iface_addr;
N2_time specifies the time at which the tuple expires and *MUST* be The neighborhood information base stores information about links
removed. between local interfaces and interfaces on adjacent nodes. In
addition to the sets described in [4], OLSRv2 adds an element to each
Link Tuple to allow a node to record the willingness of a 1-hop
neighbor node to be selected as an MPR. Also, OLSRv2 adds an MPR Set
and an MPR Selector Set to the Neighborhood Information Base. The
MPR Set is used by a node to record which of its symmetric 1-hop
neighbors are selected as MPRs, and the MPR Selector Set is used by a
node to record which of its symmetric 1-hop neighbors have selected
it as MPR. Thus the MPR Set is used, in addition to what is
specified in [4], when generating HELLO messages, and the MPR
Selector Set is populated, in addition to what is specified in [4]
when processing HELLO messages.
In a node, the set of 2-Hop Neighbor Tuples is denoted the "2-Hop 5.1.1. Link Set
Neighbor Set".
5.1.3 Neighborhood Address Association Set The Link Tuples, specified in [4] are augmented by an element,
L_willingness:
A node maintains, for each 1-hop and 2-hop neighbor with multiple L_willingness is the node's willingness to be selected as an MPR;
addresses participating in the OLSRv2 network, a "Neighborhood
Address Association Tuple", representing that "these addresses belong
to the same node".
(NA_neighbor_addr_list, NA_time) The remaining elements of the Link Tuples are as specified in [4].
NA_neighbor_iface_addr_list is the list of interface addresses of the 5.1.2. MPR Set
1-hop or 2-hop neighbor node;
NA_time specifies the time at which the tuple expires and *MUST* be A node maintains a set of all of the OLSRv2 interface addresses with
removed. which the node has a symmetric link and which are of 1-hop symmetric
neighbors which the node has selected as MPRs. This is denoted the
"MPR Set".
In a node, the set of Neighborhood Address Association Tuples is 5.1.3. MPR Selector Set
denoted the "Neighborhood Address Association Set".
5.1.4 MPR Set A node maintains a set of "MPR Selector Tuples" containing all of the
OLSRv2 interface addresses with which the node has a symmetric link
and which are of 1-hop symmetric neighbors which have selected the
node as an MPR.
A node maintains a set of neighbors which are selected as MPRs. (MS_neighbor_iface_addr, MS_time)
Their interface addresses are listed in the MPR Set.
5.1.5 MPR Selector Set MS_neighbor_iface_addr specifies an OLSRv2 interface address with
which the node has a symmetric link and which is of a 1-hop
symmetric neighbor which has selected the node as an MPR;
A node maintains, for each interface of an 1-hop neighbor which has MS_time specifies the time at which this MPR Selector Tuple expires
selected it as MPR, an "MPR Selector Tuple", representing the an and *MUST* be removed.
interface of the neighbor node which have selected it as an MPR.
(MS_neighbor_if_addr, MS_time) In a node, the set of MPR Selector Tuples is denoted the "MPR
Selector Set".
MS_neighbor_if_addr specifies the interface address of a 1-hop 5.2. Topology Information Base
neighbor, which has selected the node as MPR;
MS_time specifies the time at which the tuple expires and *MUST* be The Topology Information Base stores information, required for the
removed. generation and processing of TC messages. The Advertised Neighbor
Set contains OLSRv2 interface addresses of symmetric 1-hop neighbors
which are to be reported in TC messages. The Topology Set and
Attached Network Set both record information received through TC
messages. Thus the Advertised Neighbor Set is used for generating TC
messages, while the Topology Set and Attached Network Set are
populated when processing TC messages.
Notice that if a MPR selector node has multiple interface addresses, Additionally, a Routing Set is maintained, derived from the
the MPR Selector Set will contain one tuple for each interface information recorded in the Neighborhood Information Base, Topology
address of the MPR selector. Set and Attached Network Set.
5.1.6 Advertised Neighbor Set 5.2.1. Advertised Neighbor Set
A node maintains a set of neighbor interface addresses, which are to A node maintains a set of OLSRv2 interface addresses of symmetric
be advertised through TC messages: 1-hop neighbors, which are to 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 (ANSN) 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. ANSN MUST be incremented. The ANSN MUST also be incremented if any
locally advertised attached networks are added or removed.
5.2 Topology Information Base
The Topology Information Base stores topological information 5.2.2. ANSN History Set
describing the network beyond the nodes neighborhood (i.e. beyond the
Neighborhood Information Base of the node).
5.2.1 Topology Set A node records a set of "ANSN History Tuples", recording information
about the freshness of the topology information received from each
other node:
Each node in the network maintains topology information about the (AH_orig_addr, AH_seq_number, AH_time)
network.
For each destination in the network, at least one "Topology Tuple" AH_orig_addr is the originator address of a received TC message;
(T_dest_iface_addr, T_last_iface_addr, T_seq, T_time) AH_seq_number is the highest ANSN in any TC message received which
originated from AH_orig_addr;
is recorded. AH_time is the time at which this ANSN History Tuple expires and
*MUST* be removed.
T_dest_iface_addr is the interface address of a node, which may be In a node, the set of ANSN History Tuples is denoted the "ANSN
reached in one hop from the node with the interface address History Set".
T_last_iface_addr;
T_last_iface_addr is, conversely, the last hop towards 5.2.3. Topology Set
T_dest_iface_addr. Typically, T_last_iface_addr is a MPR of
T_dest_iface_addr;
T_seq is a sequence number, and Each node in the network maintains topology information about the
network in the form of "Topology Tuples":
T_time specifies the time at which this tuple expires and *MUST* be (T_dest_iface_addr, T_last_iface_addr, T_seq_number, T_time)
removed.
In a node, the set of Topology Tuples are denoted the "Topology Set". T_dest_iface_addr is an OLSRv2 interface address of a destination
node, which may be reached in one hop from the node with the
OLSRv2 interface address T_last_iface_addr;
5.2.2 Attached Network Set T_last_iface_addr is, conversely, an OLSRv2 interface address of a
node which is the last hop on a path towards the node with OLSRv2
interface address T_dest_iface_addr. Typically, the node with
OLSRv2 interface address T_last_iface_addr is a MPR of the node
with OLSRv2 interface address T_dest_iface_addr;
Each node in the network maintains information about attached T_seq_number is the highest received ANSN associated with the
networks. information contained in this Topology Tuple;
For each attached network, at least one "Attached Network Tuple" T_time specifies the time at which this Topology Tuple expires and
*MUST* be removed.
(AN_net_addr, AN_prefix_lenght, AN_gw_addr, AN_seq_no, AN_time) In a node, the set of Topology Tuples is denoted the "Topology Set".
is recorded. 5.2.4. Attached Network Set
AN_net_addr is the network address (prefix) of a network, which may Each node in the network maintains information about attached
be reached via the node with the OLSRv2 interface address networks in the form of "Attached Network Tuples":
AN_gw_addr;
AN_prefix_length is the length of the prefix of the network address (AN_net_addr, AN_gw_iface_addr, AN_seq_number, AN_time)
AN_net_addr;
AN_gw_addr is the address of an OLSRv2 interface of a node which can AN_net_addr is the network address (including prefix length) of an
act as gateway to the network identified by the AD_net_addr/ attached network, which may be reached via the node with the
AD_prefix_length; OLSRv2 interface address AN_gw_iface_addr;
AN_seq_no is a sequence number, and; AN_gw_iface_addr is the address of an OLSRv2 interface of a node
which can act as gateway to the network identified by AN_net_addr;
AN_time specifies the time at which this tuple expires and *MUST* be AN_seq_number is the highest received ANSN associated with the
removed. information contained in this Attached Network Tuple;
In a node, the set of Topology Tuples are denoted the "Topology Set". AN_time specifies the time at which this Attached Network Tuple
expires and *MUST* be removed.
5.2.3 Routing Set In a node, the set of Attached Network Tuples is denoted the
"Attached Network Set".
A node records a set of "Routing Tuples": 5.2.5. Routing Set
(R_dest_iface_addr, R_next_iface_addr, R_dist, R_iface_addr) A node records a set of "Routing Tuples" describing the selected path
to each destination in the network for which a route is known:
describing the next hop and distance of the path to each destination (R_dest_addr, R_next_iface_addr, R_dist, R_local_iface_addr)
in the network for which a route is known.
R_dest_iface_addr is the interface address of the destination node; R_dest_addr is the address of the destination, either the address of
an OLSRv2 interface of a destination node, or the network address
of an attached network;
R_next_iface_addr is the interface address of the "next hop" on the R_next_iface_addr is the OLSRv2 interface address of the "next hop"
path towards R_dest_iface_addr; on the selected path to the destination;
R_dist is the number of hops on the path to R_dest_iface_addr; R_dist is the number of hops on the selected path to the destination;
R_iface_addr is the address of the local interface over which a R_local_iface_addr is the address of the local interface over which a
packet MUST be sent to reach R_next_iface_addr. packet MUST be sent to reach the destination.
In a node, the set of Routing Tuples is denoted the "Routing Set". In a node, the set of Routing Tuples is denoted the "Routing Set".
6. OLSRv2 Control Message Structures 6. OLSRv2 Control Message Structures
Nodes using OLSRv2 exchange information through messages. One or Nodes using OLSRv2 exchange information through messages. One or
more messages sent by a node at the same time are combined into a 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 packet. These messages may have originated at the sending node, or
have originated at another node and forwarded by the sending node. have originated at another node and forwarded by the sending node.
Messages with different originators may be combined in the same Messages with different originators may be combined in the same
packet. packet.
The packet and message format used by OLSRv2 is defined in [4]. The packet and message format used by OLSRv2 is defined in [3].
However this specification contains some options which are not used However this specification contains some options which are not used
by OLSRv2. In particular (using the syntactical elements defined in by OLSRv2. In particular (using the syntactical elements defined in
the packet format specification): the packet format specification):
o All OLSRv2 packets include a <packet-header>. o All OLSRv2 packets, not limited to those defined in this document,
include a <packet-header>.
o All OLSRv2 packets, not limited to those defined in this document,
have the pseqnum bit of <packet-semantics> cleared ('0'), i.e.
they include a packet sequence number.
o OLSRv2 packets MAY include packet TLVs, however OLSRv2 itself does
not specify any packet TLVs.
o All OLSRv2 messages, not limited to those defined in this o All OLSRv2 messages, not limited to those defined in this
document, include a full <msg-header> and hence have bits 0 and 1 document, include a full <msg-header> and hence have the noorig
of <msg-semantics> cleared. and nohops bits of <msg-semantics> cleared ('0').
o All OLSRv2 message defined in this document have all remaining o All OLSRv2 message defined in this document have the typedep bit,
bits of <msg-semantics> cleared. and all reserved bits of <msg-semantics> cleared ('0').
Other options defined in [4] may be freely used, in particular any Other options defined in [3] may be freely used, in particular any
values of <tlv-semantics> consistent with its specification. An other values of <packet-semantics> or <tlv-semantics> consistent with
implementation of OLSRv2 MAY take full advantage of the features of its specification.
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 messages are sent using UDP, see Appendix C. OLSRv2 messages are sent using UDP, see Appendix C.
The remainder of this section defines, within the framework of [4], The remainder of this section defines, within the framework of [3],
message types and TLVs specific to OLSRv2. message types and TLVs specific to OLSRv2.
6.1 General OLSRv2 Message TLVs 6.1. General OLSRv2 Message TLVs
This document specifies two message TLVs, which can be applied to any This document specifies two message TLVs, which can be applied to any
OLSRv2 control message, VALIDITY_TIME and INTERVAL_TIME, detailed in OLSRv2 control messages, VALIDITY_TIME and INTERVAL_TIME.
this section.
6.1.1 VALIDITY_TIME TLV 6.1.1. VALIDITY_TIME TLV
All OLSRv2 messages specified in this specification MUST include a All OLSRv2 messages specified in this document MUST include a
VALIDITY_TIME TLV, specifying for how long a node may, upon receiving VALIDITY_TIME TLV, specifying a period following receipt of a
a message, consider the message content to be valid. The validity message, after which the receiving node MUST consider the message
time of a message MAY be specified to depend on the distance from the content to no longer be valid (unless repeated in a later message).
originator (i.e. the <hop-count> field in the message header as The validity time of a message MAY be specified to depend on the
defined in [4]). Thus, the VALIDITY_TIME TLV contains a sequence of distance from the originator (i.e. the <hop-count> field in the
pairs (time, hop-limit) in increasing hop-limit order, followed by a message header as defined in [3]). Thus, a VALIDITY_TIME TLV's value
default value. field MAY contain a sequence of pairs (time, hop limit) in increasing
hop limit order; it MUST contain a final default value.
Thus, an instance of a VALIDITY_TIME TLV could have the following This is an extended, and compatible, version of the VALIDITY_TIME TLV
value: defined in [4].
Thus, an instance of a VALIDITY_TIME TLV MAY have the following value
field:
<t_1><hl_1><t_2><hl_2> ... <t_i><hl_i> .... <t_n><hl_n><t_default> <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, Which would mean that the message carrying this VALIDITY_TIME TLV
would have the following validity times: would have the following validity times:
o <t_1> in the interval from 0 (exclusive) to <hl_1> (inclusive) o <t_1> in the interval from 0 (exclusive) to <hl_1> (inclusive)
hops away from the originator; hops away from the originator;
o <t_i> in the interval from <hl_(i-1)> (exclusive) to <hl_i> o <t_i> in the interval from <hl_(i-1)> (exclusive) to <hl_i>
(inclusive) hops away from the originator; and (inclusive) hops away from the originator;
o <t_default> in the interval from <hl_n> (exclusive) to 255> o <t_default> in the interval from <hl_n> (exclusive) to 255
(inclusive) hops away from the originator. (inclusive) hops away from the originator.
The VALIDITY_TIME message TLV specification is given in Table 2. The VALIDITY_TIME message TLV specification is given in Table 1.
VALIDITY_TIME message TLV specification overview
+----------------+--------+-------------------+---------------------+ +----------------+------+-------------------+-----------------------+
| Name | Type | Length | Value | | Name | Type | Length | Value |
+----------------+--------+-------------------+---------------------+ +----------------+------+-------------------+-----------------------+
| VALIDITY_TIME | TBD | (2*n+1) * 8 bits | {<time><hoplimit>}* | | VALIDITY_TIME | TBD | (2*n+1) * 8 bits | {<time><hop_limit>}* |
| | | | <t_default> | | | | | <t_default> |
+----------------+--------+-------------------+---------------------+ +----------------+------+-------------------+-----------------------+
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: Table 1
o a message TLV VALIDITY_TIME Section 6.1.1 where n is the number of (time, hop_limit) pairs in the TLV (i.e. is
equal to (<length>-1)/2, where <length> is the length of the TLV
value field) and where <time> and <t_default> are represented as
specified in [3].
o one or more address blocks with associated address block TLVs 6.2. HELLO Messages
The first (mandatory) address block is a Local Interface Block, as A HELLO message in OLSRv2 is generated as specified in [4].
specified in Section 6.2. Other (optional) address blocks contain
1-hop neighbors' interface addresses.
A HELLO message MAY optionally contain: Additionally, an OLSRv2 node:
o a message TLV INTERVAL_TIME as specified in Section 6.1.2 o MUST include TLV(s) with Type == MPR associated with all OLSRv2
interface addresses included in the HELLO message with a TLV with
Type == LINK_STATUS and Value == SYMMETRIC if that address is also
included in the node's MPR Set (if there is more than one copy of
the address, this applies to the specific copy of the address to
which the TLV is associated);
o a message TLV WILLINGNESS, as specified in Section 6.3.1 o MUST NOT include any TLVs with Type == MPR associated with any
other addresses;
6.3.1 HELLO Message: Message TLVs o MAY include a message TLV with Type == WILLINGNESS, indicating the
node's willingness to be selected as MPR.
In a HELLO message, a node MAY include a message TLV as specified in 6.2.1. HELLO Message OLSRv2 Message TLVs
Table 4.
VALIDITY_TIME message TLV specification overview In a HELLO message, a node MAY include a WILLINGNESS message TLV as
specified in Table 2.
+----------------+--------+-------------------+---------------------+ +----------------+------+-------------------+-----------------------+
| Name | Type | Length | Value | | Name | Type | Length | Value |
+----------------+--------+-------------------+---------------------+ +----------------+------+-------------------+-----------------------+
| WILLINGNESS | TBD | 8 bits | <The node's | | WILLINGNESS | TBD | 8 bits | The node's |
| | | | willingness to be | | | | | willingness to be |
| | | | selected as MPR> | | | | | selected as MPR, any |
+----------------+--------+-------------------+---------------------+ | | | | unused bits (based on |
| | | | the maximum |
| | | | willingness value |
| | | | WILL_ALWAYS) are |
| | | | RESERVED and SHOULD |
| | | | be set to zero. |
+----------------+------+-------------------+-----------------------+
Table 4 Table 2
A node's willingness to be selected as MPR ranges from WILL_NEVER 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 (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. 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.
6.3.2 HELLO Message: Address Blocks TLVs 6.2.2. HELLO Message OLSRv2 Address Block TLVs
HELLO message address block TLV specification overview In a HELLO message, a node MAY include MPR address block TLV(s) as
specified in Table 3.
+----------------+--------+-------------------+---------------------+ +----------------+------+-------------------+-----------------------+
| Name | Type | Length | Value | | Name | Type | Length | Value |
+----------------+--------+-------------------+---------------------+ +----------------+------+-------------------+-----------------------+
| LINK_STATUS | TBD | 8 bits | One of HEARD, |
| | | | SYMMETRIC, LOST. |
| | | | |
| MPR | TBD | 0 bits | No value, i.e. | | MPR | TBD | 0 bits | No value, i.e. |
| | | | novalue bit (see | | | | | novalue bit ([3]) set |
| | | | [4]) set | +----------------+------+-------------------+-----------------------+
| | | | |
| OTHER_IF | TBD | 0 or 8 bits | In a Local |
| | | | Interface Block |
| | | | none, otherwise |
| | | | either of SYMMETRIC |
| | | | or LOST |
+----------------+--------+-------------------+---------------------+
Table 5 Table 3
6.4 TC Messages 6.3. TC Messages
A TC message MUST contain: A TC message MUST contain:
o a message TLV VALIDITY_TIME Section 6.1.1 o a message TLV with Type == CONT_SEQ_NUM, as specified in [3];
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, o a message TLV with Type == VALIDITY_TIME, as specified in
describing general properties of the message and the node emitting Section 6.1.1;
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, o a first address block containing all of the node's OLSRv2
i.e. different HELLO messages are generated and transmitted per interface addresses. This is similar to the Local Interface Block
OLSRv2 interface of a node. specified in [4], however these addresses MUST be included in the
same order in all copies of a given TC message, regardless of
which interface it is transmitted on, and no OTHER_IF address
block TLV(s) are required;
OLSRv2 HELLO messages are generated and transmitted periodically, o additional address block(s) containing all addresses in the
with a default interval between two consecutive HELLO emissions on Advertised Address Set and Attached Network Set, the latter (only)
the same interface of HELLO_INTERVAL. with associated GATEWAY address block TLV(s), as specified in
Section 6.4, both with associated PREFIX_LENGTH TLV(s), as
specified in [3], as necessary.
This section specifies the requirements, which HELLO message A TC message MAY contain:
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 o a message TLV INTERVAL_TIME, as specified in [4].
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.
+---------------------------+---------------------------------------+ 6.4. TC Message: OLSRv2 Address Block TLVs
| The set of neighbor | TLV(s) (Type = Value) |
| interfaces which are ... | |
+---------------------------+---------------------------------------+
| HEARD, but not SYMMETRIC | LINK_STATUS=HEARD |
| over the interface over | |
| which the HELLO message | |
| is being transmitted | |
| | |
| SYMMETRIC over the | LINK_STATUS=SYMMETRIC |
| interface over which the | |
| HELLO message is being | |
| transmitted | |
| | |
| LOST over the interface | LINK_STATUS=LOST |
| over which the HELLO | |
| message is being | |
| transmitted | |
| | |
| Not SYMMETRIC over the | OTHER_IF=SYMMETRIC |
| interface over which the | |
| HELLO message is being | |
| transmitted, but | |
| SYMMETRIC over one or | |
| more other interfaces of | |
| the node | |
| | |
| Not SYMMETRIC over any | OTHER_IF=LOST |
| interface or LOST over | |
| 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 6 In a TC message, a node MAY include GATEWAY address block TLV(s) as
specified in Table 4.
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 | Name | Type | Length | Value |
MAY maintain an Other Interface Set of addresses for each interface. +----------------+------+-------------------+-----------------------+
The Other Interface Set for an interface is updated when a HELLO | GATEWAY | TBD | 0 bits | No value, i.e. |
message is to be transmitted over that interface, and used to | | | | novalue bit ([3]) set |
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 Table 4
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 7. HELLO Message Generation
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 An OLSRv2 HELLO message is composed as defined in [4], with the
with a corresponding TLV with Type=OTHER_IF and Value=SYMMETRIC) following TLVs added:
1. Is removed if the HELLO message is to include it with a o a message TLV with Type == WILLINGNESS and Value == the node's
corresponding TLV with Type=LINK_STATUS and Value=LOST. willingness to act as an MPR, MAY be included in the message;
2. Is removed if it is not HEARD or LOST over an interface other o for each symmetric 1-hop neighbor OLSRv2 interface address which
than the interface over which the HELLO message is to be is included in the HELLO message with an associated TLV with Type
transmitted. == LINK_STATUS and is selected as an MPR (i.e. is present in the
MPR Set), an address TLV with Type == MPR MUST be included, this
SHOULD be associated with the same copy of the address as the TLV
with Type == LINK_STATUS;
3. Otherwise is included in the HELLO message with a TLV with o for each 1-hop neighbor OLSRv2 interface address which is included
Type=OTHER_IF and Value=LOST. (Note that the address may in the HELLO message but is not selected as an MPR (i.e. is not
also have a corresponding TLV with Type=LINK_STATUS and present in the MPR Set), an address TLV with Type == MPR MUST NOT
Value=HEARD if appropriate.) be included.
7.1 HELLO Message: Transmission 7.1. HELLO Message: Transmission
Messages are retransmitted in the packet/message format specified by Messages are retransmitted in the packet/message format specified by
[4] with the All-OLSRv2-Multicast address as destination IP address [3] with the ALL-MANET-NEIGHBORS address as destination IP address
and with a TTL=1. and with TTL (IPv4) or hop limit (IPv6) equal to 1.
8. HELLO Message Processing 8. HELLO Message Processing
Upon receiving a HELLO message, a node will update its local link Subsequent to the processing of HELLO messages, as specified in [4],
information base according to the specification given in this the node MUST:
section.
For the purpose of this section, please notice the following:
o the "validity time" of a message is calculated from the VALIDITY-
TIME TLV of the message as specified in Section 6.1.1;
o the "Source Address" is the source address as indicated by the
source interface of the IP datagram containing the message;
o a HELLO message MUST neither be forwarded nor be recorded in the
Processing and Forwarding Repositories;
o the address blocks considered exclude the Local Interface Block,
unless explicitly specified;
o a HELLO message is only valid when, for each address listed in the
address blocks:
* the address is associated with a TLV with Type=Link Status OR a
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 TLV with Type=Link Status has Value=LOST and the TLV with
Type=Other Interface Status has Value=SYMMETRIC, AND
* if the address is associated with a TLV with Type=MPR, then it
MUST also be associated with a TLV with Type=Link Status and
Value=SYMMETRIC.
Invalid HELLO messages are not processed.
8.1 Populating the Link Set
Upon receiving a HELLO message, a node SHOULD update its Link Set
with the information contained in the HELLO. Thus, for the Local
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:
* L_neighbor_iface_addr == Source Address
a new tuple is created with
* L_neighbor_iface_addr = Source Address;
* L_local_iface_addr = Address of the interface which
received the HELLO message;
* L_SYM_time = current time - 1 (expired);
* L_time = current time + validity time.
2. The tuple (existing or new) with L_neighbor_iface_addr == Source
Address is then modified as follows:
1. if the node finds the address of the interface, which
received the HELLO message, in one of the address blocks
included in message, then the tuple is modified as follows:
1. if the occurrence of L_local_iface_addr in the HELLO
message is:
- associated with a TLV with (Type == "LINK_STATUS",
Value == LOST)
then
- L_SYM_time = current time - 1 (i.e., expired)
2. else if the occurrence of L_local_iface_addr in the HELLO
message:
- is associated with:
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_time = L_SYM_time + L_HOLD_TIME.
2. L_ASYM_time = current time + validity time;
3. L_time = max(L_time, L_ASYM_time)
3. Additionally, the willingness field is updated as follows:
If a TLV with Type=="WILLINGNESS" is present in the message
TLVs, then:
+ L_willingness = Value of the TLV
otherwise:
+ L_willingness = WILL_DEFAULT
The rule for setting L_time is the following: a link losing its
symmetry SHOULD still be advertised in HELLOs (with the remaining
status as defined by Table 1) during at least the duration of the
"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.
8.2 Populating the 2-Hop Neighbor Set
Upon receiving a HELLO message from a symmetric neighbor interface, a
node SHOULD update its 2-hop Neighbor Set.
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
words: if the Source Address is a symmetric neighbor interface) then
the 2-hop Neighbor Set SHOULD be updated as follows:
1. for each address (henceforth: 2-hop neighbor address), listed in
the HELLO message:
1. if the 2-hop neighbor address is an interface address of the
receiving node silently discard the 2-hop neighbor address
(in other words: a node is not its own 2-hop neighbor).
2. else if the 2-hop neighbor address has a TLV with:
+ (Type=LINK_STATUS, Value == SYMMETRIC); OR
+ (Type=OTHER_IF, Value=SYMMETRIC);
a 2-hop tuple is created with:
+ N2_local_iface_addr = address of the interface over
which the HELLO message was received;
+ N2_neighbor_iface_addr = source address of the message;
+ N2_2hop_iface_addr = 2-hop neighbor address;
+ N2_time = current time + validity time.
This tuple may replace an older similar tuple with the same
N2_local_iface_addr, N2_neighbor_iface_addr and
N2_2hop_iface_addr values.
3. else if the 2-hop neighbor address has a TLV with:
+ (Type == LINK_STATUS, Value == LOST); OR 1. Determine the willingness of the originating node to be an MPR
by:
+ (Type == OTHER_IF, Value == LOST), * if the HELLO message contains a message TLV with Type ==
WILLINGNESS then the willingness is the value of that TLV,
ignoring the reserved bits in that field;
then any 2-hop tuple with: * otherwise the willingness is WILL_DEFAULT.
+ N2_local_iface_addr equal to the address of the interface 2. Update each Link Tuple whose L_neighbor_iface_addr is present in
over which the HELLO message was received; AND the Local Interface Block of the HELLO message, with:
+ N2_neighbor_iface_addr equal to the source address of the * L_willingness = the willingness of the originating node;
message; AND
+ and N2_2hop_iface_addr equal to the 2-hop neighbour 3. Update its MPR Selector Set, according to Section 8.1.
address
MUST be deleted. 8.1. Populating the MPR Selector Set
8.3 Populating the MPR Selector Set On receiving a HELLO message, a node MUST:
Upon receiving a HELLO message, if a node finds one of its own 1. If a node finds one of its own interface addresses with an
interface addresses, listed with an MPR TLV (indicating that the associated TLV with Type == MPR in the HELLO message (indicating
originator node has selected one of the receiving node's interfaces that the originator node has selected the receiving node as an
as MPR), the MPR Selector Set SHOULD be updated as follows: MPR), the MPR Selector Set MUST be updated as follows:
For each address in the Local Interface Block of the received 1. For each address, henceforth neighbor address, in the Local
message: Interface Block of the received HELLO message, where the
neighbor address is present as an N_neighbor_iface_addr in a
Symmetric Neighbor Tuple with N_STATUS == SYMMETRIC:
1. If there exists no MPR Selector tuple with: 1. If there exists no MPR Selector Tuple with:
* MS_if_addr == that address - MS_neighbor_iface_addr == neighbor address
then a new tuple is created with: then a new MPR Selector Tuple is created with:
* MS_if_addr = that address - MS_neighbor_iface_addr = neighbor address
2. The tuple (new or otherwise) with: 2. The MPR Selector Tuple (new or otherwise) with:
* MS_if_addr == that address - MS_neighbor_iface_addr == neighbor address
is then modified as follows: is then modified as follows:
* MS_time = current time + validity time. - MS_time = current time + validity time
MPR Selector tuples are removed upon expiration of MS_time, or upon
link breakage as described in Section 8.4.
8.4 Neighborhood and 2-Hop Neighborhood Changes 2. Otherwise if a node finds one of its own interface addresses with
an associated TLV with Type == LINK_STATUS and Value == SYMMETRIC
in the HELLO message (indicating, since there is no TLV with Type
== MPR, that originator node has de-selected the receiving node
as an MPR), the MPR Selector Set MUST be updated as follows:
A change in the neighborhood is detected when: 1. All MPR Selector Tuples whose N_neighbor_iface_addr is in the
Local Interface Block of the HELLO message are removed.
o Link Loss: the L_SYM_time field of a link tuple expires (either MPR Selector Tuples are also removed upon expiration of MS_time, or
due to time out, or as a result of processing a TLV (Type == upon symmetric link breakage as described in Section 8.2.
LINK_STATUS, Value == LOST)).
o Link Acquisition: a new link tuple is inserted in the Link Set 8.2. Symmetric Neighborhood and 2-Hop Neighborhood Changes
with a non expired L_SYM_time or a tuple with expired L_SYM_time
is modified so that L_SYM_time becomes non-expired. This is
considered as a link acquisition if there was previously no such
link tuple.
o Neighbor Loss: all links to a neighbor node have have been lost. A node MUST also perform the following:
A change in the 2-hop neighborhood is detected when a 2-Hop Neighbor 1. If a Link Tuple with L_STATUS == SYMMETRIC is removed, or its
Tuple expires or is deleted according to section Section 8.2. L_STATUS changes from SYMMETRIC to HEARD or LOST, and if that
Link Tuple's L_neighbor_iface_addr is an MS_iface_addr of an MPR
Selector Tuple, then that MPR Selector Tuple MUST be removed.
The following processing occurs when changes in the neighborhood or 2. If any of:
the 2-hop neighborhood are detected:
o In case of link loss, all 2-Hop Neighbor Tuples with * a Link Tuple is added with L_STATUS == SYMMETRIC, OR;
* N2_local_iface_addr == interface address of the node where the * a Link Tuple with L_STATUS == SYMMETRIC is removed, or its
link was lost L_STATUS changes from SYMMETRIC to HEARD or LOST, or vice
versa, OR;
* N2_neighbor_iface_addr == interface address of the neighbor * a 2-Hop Neighbor Tuple is added or removed, OR;
MUST be deleted. * the Neighbor Address Association Set is changed such that the
subset of any NA_neighbor_iface_addr_list consisting of those
addresses which are the L_neighbor_iface_addr of a Link Tuple
with L_STATUS == SYMMETRIC is changed, including the cases of
removal or addition of a Neighbor Address Association Tuple
containing any such addresses;
o In case of neighbor loss, all MPR Selector tuples associated with then the MPR Set MUST be recalculated.
that neighbor are deleted. More precisely:
* all MPR selector tuples with MS_iface_addr == interface address An additional HELLO message MAY be sent when the MPR Set changes, in
of the neighbor MUST be deleted, along with any interface addition to the cases specified in [4], and subject to the same
addresses associated in the Neighbor Address Association Set. constraints.
o The MPR Set MUST be re-calculated when a link acquisition or loss 9. TC Message Generation
is detected, or when a change in the 2-hop neighborhood is
detected.
o An additional HELLO message MAY be sent when the MPR Set or the A node with one or more OLSRv2 interfaces, and with a non-empty
neighborhood changes. Advertised Neighbor Set or which acts as a gateway to an associated
network which is to be advertised in the MANET, MUST generate TC
messages. A node with an empty Advertised Neighbor Set and which is
not acting as such a gateway SHOULD also generate "empty" TC messages
for a period A_HOLD_TIME after it last generated a non-empty TC
message. TC messages (non-empty and empty) are generated according
to the following:
Additionally, proper update of the sets describing local topology 1. the TC message MUST contain a message TLV with Type ==
should be made when a Neighbor Association Address Tuple has a list CONT_SEQ_NUM and Value == ANSN from the Advertised Neighbor Set;
of addresses which is modified.
9. TC Message Generation 2. the TC message MUST contain a message TLV with Type ==
VALIDITY_TIME and Value == T_HOLD_TIME as specified in
Section 6.1.1;
TC messages are, in OLSRv2, transmitted with the purpose of 3. the TC message MAY contain a message TLV with Type ==
populating the Topology Set, the Attached Network Set and the INTERVAL_TIME and Value == TC_INTERVAL as specified in [4];
Neighborhood Address Association Set:
o Topology Discovery: ensure that information is present in each 4. the TC message MUST contain the addresses of all of its OLSRv2
node describing all destinations and a sufficient subset of links interfaces in its first address block, note that the TC message
in order to provide least-hop paths to all destinations. generated on all OLSRv2 interfaces MUST be identical (including
having identical message sequence number) and hence these
addresses are not ordered or otherwise identified according to
the interface on which the TC message is transmitted;
o Multiple Interface Declaration: ensure that nodes, up to two hops 5. the TC message MUST contain, in address blocks other than its
away from the originator, are aware of the interface configuration first:
of the originator node.
Thus, nodes with a non-empty Advertised Neighbor Set, or which are 1. A_neighbor_iface_addr from each Advertised Neighbor Tuple;
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:
1. The node includes, in its first address block of the TC message, 2. the addresses of all associated hosts and networks for which
a Local Interface Block as specified in Section 6.2 this node is to act as a gateway and which is to be
advertised in the MANET, each associated with a TLV with Type
== GATEWAY.
2. If the node has a non-empty Advertised Neighbor Set or is 6. the TC message MAY be fragmented, only by its originator. It
specifically reporting an empty Advertised Neighbor Set, or it SHOULD be fragmented only if necessary; if the TC message is
has a one or more attached non-OLSRv2 networks, to which it fragmented, a FRAGMENTATION TLV MUST be included, and each
wishes to advertise routes to the network, it furthermore: fragment SHOULD be indicated as "partially or wholly self
contained" in it, and MUST indicate that the content sequence
number (ANSN) is message type specific.
1. includes a message TLV (Type = CONTENT_SEQ_NUMBER TLV, Value 9.1. TC Message: Transmission
= the Advertised Neighbor Set Sequence Number);
2. includes address blocks, containing its Advertised Neighbor TC messages are generated and transmitted periodically on all OLSRv2
Set (if non-empty); interfaces, with a default interval between two consecutive TC
emissions by the same node of TC_INTERVAL. TC messages MAY be
generated in response to a change of contents (a change in ANSN, due
to a change in the Advertised Neighbor Set or the advertised locally
attached networks) but a node must respect a minimum interval of
TC_MIN_INTERVAL between generated TC messages.
3. includes address blocks and PREFIX_LENGTH TLVs, describing TC messages SHOULD be generated with a message hop limit [3] greater
attached non-OLSRv2 networks; than or equal to the expected network diameter (by default with a hop
limit of 255).
4. sets the TTL of the message to the network diameter. TC messages are transmitted with the ALL-MANET-NEIGHBORS multicast
address as destination IP address and are forwarded according to the
specification in Section 4.4.
3. Otherwise, the node: 10. TC Message Processing
1. sets the TTL of the message to 2. When according to Section 4.3 a TC message is to be processed
according to its type, this means that processing is carried out
according to Section 10.1 and Section 10.2. The timing of this
processing depends on whether the TC message is a fragment, and if so
whether it is "partially or wholly self-contained":
OLSRv2 TC messages are generated and transmitted periodically, with a o if the message is not a fragment, then first Section 10.1 and then
default interval between two consecutive TC emissions by the same Section 10.2 are carried out when the message is received;
node of TC_INTERVAL.
9.1 TC Message: Transmission o if the message is a fragment which is "partially or wholly self-
contained", then processing according to Section 10.1 is carried
out when the message is received, and processing according to
Section 10.2 is carried out when all matching fragments have been
received and all processing according to Section 10.1 has been
carried out;
Messages are retransmitted in the packet/message format specified by o if the message is a fragment which is not "partially or wholly
[4] with the All-OLSRv2-Multicast address as destination IP address self-contained", then processing according to Section 10.1 is
and is forwarded according to the specification in section carried out when all matching fragments have been received, and
Section 4.4. If fragmentation is necessary, a FRAGMENTATION TLV MUST processing according to Section 10.2 is carried out when all
be included, and each fragment SHOULD be flagged as partially or matching fragments have been received and all processing according
wholly self contained as specified in [4]. to Section 10.1 has been carried out.
10. TC Message Processing For all processing purposes, "ANSN" is defined as being the value of
the message TLV with Type == CONT_SEQ_NUM in the TC message. If a TC
message has no such TLV then the processing of Section 10.1 and
Section 10.2 MUST NOT be carried out. (Note that if the message is a
fragment it will have already been discarded according to
Section 4.3.) If more than one TC message is processed according to
Section 10.2 then these must have the same ANSN to be recognized as
fragments of the same message.
Upon receiving a TC message, a node MUST update its topology 10.1. Single TC Message Processing
information base according to the specification given in this
section.
For the purpose of this section, note the following: For the purpose of this section, note the following:
o the "validity time" of a message is calculated from the o "validity time" is calculated from the VALIDITY_TIME message TLV
VALIDITY_TIME message TLV according to the specification in in the TC message according to the specification in Section 6.1.1;
Section 16;
o the "originator address" refers to the address, contained in the
"originator address" field of the OLSRv2 message header specified
in [4];
o the ASSN of the node, originating the TC message, is recovered as o "originator address" refers to the originator address in the TC
the value of the CONTENT_SEQ_NO message TLV in the TC message, if message header;
any.
10.1 Checking Freshness & Validity of a TC message o comparisons of sequence numbers are carried out as specified in
Section 15.
In order to be able to ensure that only valid and fresh information The TC message is processed as follows:
is recorded in the Topology Set, each node maintains an ASSN History
Set, recording the highest ASSN received from each node in the
network, in the form of a "ASSN History Tuples":
(AS_Address, AS_seq, AS_time) 1. the ANSN History Set is updated according to Section 10.1.1; if
the TC message is indicated as discarded in that processing then
the following steps are not carried out;
AS_Address is the originator address of a received TC message; 2. the Topology Set is updated according to Section 10.1.2;
AS_seq is the highest received ASSN seen in a TC message from 3. the Attached Network Set is updated according to Section 10.1.3.
AS_Address;
AS_time is the time at which this tuple expires and MUST be removed. 10.1.1. Populating the ANSN History Set
Upon receiving a TC message, a node MUST check if the TC message is The node MUST update its ANSN History Set as follows:
fresh and valid as follows:
1. If the TC message has more than one address block (i.e. not just 1. if there is an ANSN History Tuple with:
a Local Interface Block) and does not contain a message-TLV of
type CONTENT_SEQ_NO. then the message MUST be discarded;
2. otherwise, if the ASSN History Set contains a tuple where: * AH_orig_addr == originator address; AND
* AS_Address == Originator Address of the TC message; AND * AH_seq_number > ANSN
* AS_seq > the ASSN recovered from the TC message,
then the TC message MUST be discarded; then the TC message MUST be discarded;
3. otherwise a tuple is inserted in the ASSN History Set with: 2. otherwise create a new ANSN History Tuple with:
* AS_Address = Originator Address in the message; * AH_orig_addr = originator address;
* AS_seq = The ASSN, extracted from the message; * AH_seq_number = ANSN;
* AS_time = current time + AS_HOLD_TIME. * AH_time = current time + validity time.
possibly replacing an existing tuple with the same AS_Address. possibly replacing an existing ANSN History Tuple with the same
AH_orig_addr.
10.2 Updating the Topology Set 10.1.2. Populating the Topology Set
A node SHOULD update its Topology Set as follows: The node SHOULD update its Topology Set as follows:
1. For each address, LocAddr, from the Local Interface Block in the 1. for each address, henceforth local address, in the first address
TC message: block in the TC message:
1. For each advertised neighbor address, listed in an address 1. for each address, henceforth advertised address, in an
block other than the Local Interface Block in the TC message, address block other than the first in the TC message, and
which does NOT have an associated PREFIX_LENGTH TLV: which does not have an associated TLV with Type == GATEWAY:
1. if there exists a tuple in the Topology Set where: 1. if there is a Topology Tuple with:
T_dest_iface_addr == advertised neighbor address; AND T_dest_iface_addr == advertised address; AND
T_last_iface_addr == local address
T_last_iface_addr == LocAddr. then update this Topology Tuple to have:
then the tuple is updated as follows: T_seq_number = ANSN;
T_time = current time + validity time T_time = current time + validity time
T_seq = ASSN 2. otherwise create a new Topology Tuple with:
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_dest_iface_addr = advertised address;
T_last_iface_addr == LocAddr AND T_last_iface_addr = local address;
T_seq < ASSN T_seq_number = ANSN;
MUST be removed. T_time = current time + validity time.
10.4 Updating the Attached Networks Set 10.1.3. Populating the Attached Network Set
A node SHOULD update its Attached Networks Set as follows: The node SHOULD update its Attached Network Set as follows:
1. For each address, LocAddr, from the Local Interface Block in the 1. for each address, henceforth gateway address, in the first
TC message: address block in the TC message:
1. For each advertised neighbor address, listed in an address 1. for each address, henceforth network address, in an address
block other than the Local Interface Block in the TC message, block other than the first in the TC message, and which has
which does have an associated PREFIX_LENGTH TLV: an associated TLV with Type == GATEWAY:
1. if there exists a tuple in the Attached Networks Set 1. if there is a Attached Network Tuple with:
where:
AN_net_addr == advertised neighbor address; AND AN_net_addr == network address; AND
AN_prefix_length == the prefix length as recoveredf from AN_gw_iface_addr == gateway address
the PREFIX_LENGTH TLV; AND
AN_gw_addr == LocAddr. then update this Attached Network Tuple to have:
then the tuple is updated as follows: AN_seq_number = ANSN;
AN_time = current time + validity time AN_time = current time + validity time
AN_seq = ASSN 2. otherwise create a new Attached Network Tuple with:
2. Otherwise, a new topology tuple is created with:
AN_net_addr == advertised neighbor address; AND
AN_prefix_length == the prefix length as recoveredf from AN_net_addr = network address;
the PREFIX_LENGTH TLV; AND AN_gw_iface_addr = gateway address
AN_gw_addr == LocAddr. AN_seq_number = ANSN;
AN_time = current time + validity time AN_time = current time + validity time
AN_seq = ASSN 10.2. Completed TC Message Processing
10.5 Purging Old Entries from the Attached Network Set
TBD
10.6 Processing Unfragmented TC Messages
If an unfragmented TC message, i.e. a TC message without a The TC message(s) are processed as follows:
FRAGMENTATION message TLV, is received, it MUST be processed as
follows:
1. Verify freshness and validity of the TC message (see 1. the Topology Set is updated according to Section 10.2.1;
Section 10.1). If the message is not discarded, then continue;
2. Update the Topology Set (see Section 10.2); 2. the Attached Network Set is updated according to Section 10.2.2.
3. Purge old entries from the Topology Set (see Section 10.3); 10.2.1. Purging the Topology Set
4. Update the Attached Networks Set (see Section 10.4; The Topology Set MUST be updated as follows:
5. Purge old entries from the Attached Networks Set (see 1. for each address, henceforth local address, in the first address
Section 10.5); block of any of the TC messages, all Topology Tuples with:
6. Update the Neighborhood Address Association Set (see Section 13). T_last_iface_addr == local address; AND
10.7 Processing Partially or Wholly Self-Contained Fragmented TC T_seq_number < ANSN
Messagess
If a TC message contains a FRAGMENTATION message TLV which indicates MUST be removed.
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):
1. Verify freshness and validity of the TC message (see 10.2.2. Purging the Attached Network Set
Section 10.1). If the message is not discarded, then continue;
2. Update the Topology Set (see Section 10.2);
3. Update the Neighborhood Address Association Set (see Section 13). The Attached Network Set MUST be updated as follows:
4. Update the Attached Networks Set (see Section 10.4; 1. for each address, henceforth local address, in the first address
block of any of the TC messages, all Attached Network Tuples
with:
Once all fragments have been received, the following processing MUST AN_gw_iface_addr == local address; AND
be carried out once:
1. Purge old entries from the Topology Set (see Section 10.3); AN_seq_number < ANSN
2. Purge old entries from the Attached Networks Set (see MUST be removed.
Section 10.5);
11. Populating the MPR Set 11. Populating the MPR Set
Each node MUST select, from among its one-hop neighbors, a subset of Each node MUST select, from among its symmetric 1-hop neighbors, a
nodes as MPRs. This subset MUST be selected such that a message subset of nodes as MPRs. This subset MUST be selected such that a
transmitted by the node, and retransmitted by all its MPR nodes, will message transmitted by the node, and retransmitted by all its MPRs,
be received by all nodes 2 hops away. will be received by all of its symmetric strict 2-hop neighbors.
Each node selects its MPR Set individually, utilizing the information Each node selects its MPR Set individually, utilizing the information
in the Link Set, 2-Hop Neighbor Set and Neighborhood Address in the Symmetric Neighbor Set, the 2-Hop Neighbor Set and the
Association Set. Initially these sets will be empty, as will be the Neighborhood Address Association Set. Initially these sets will be
MPR Set. A node SHOULD recalculate its MPR Set when a relevant change empty, as will be the MPR Set. A node SHOULD recalculate its MPR Set
is made to the Link Set, 2-Hop Neighbor Set or Neighborhood Address when a relevant change is made to the Symmetric Neighbor Set, the
Association Set. 2-Hop Neighbor Set or the Neighborhood Address Association Set.
More specifically, a node MUST calculate MPRs per interface, the 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 union of the MPR Sets of each interface make up the MPR Set for the
node. node. All OLSRv2 interfaces of nodes selected as MPRs with which the
node has a symmetric link MUST be added to the MPR Set. Also
symmetric 1-hop neighbor nodes with willingness WILL_NEVER (as
recorded in the Link Set) MUST NOT be considered as MPRs.
MPRs are used to flood control messages from a node into the network MPRs are used to flood control messages from a node into the network
while reducing the number of retransmissions that will occur in a while reducing the number of retransmissions that will occur in a
region. Thus, the concept of MPR is an optimization of a classical region. Thus, the concept of MPR is an optimization of a classical
flooding mechanism. While it is not essential that the MPR Set is flooding mechanism. While it is not essential that the MPR Set is
minimal, it is essential that all strict 2-hop neighbors can be minimal, it is essential that all symmetric strict 2-hop neighbors
reached through the selected MPR nodes. A node MUST select an MPR can be reached through the selected MPR nodes. A node MUST select an
Set such that any strict 2-hop neighbor is covered by at least one MPR Set such that any strict 2-hop neighbor is "covered" by at least
MPR node. A node MAY select additional MPRs beyond the minimum set. one MPR node. A node MAY select additional MPRs beyond the minimum
Keeping the MPR Set small ensures that the overhead of OLSRv2 is kept set. Keeping the MPR Set small ensures that the overhead of OLSRv2
at a minimum. is kept at a minimum.
Appendix A contains an example heuristic for selecting MPRs. Appendix A contains an example heuristic for selecting MPRs.
12. Populating Derived Sets 12. Populating Derived Sets
The Relay Set and the Advertised Neighbor Set of OLSRv2 are denoted The Relay Set and the Advertised Neighbor Set of OLSRv2 are denoted
derived sets, since updates to these sets are not directly a function derived sets, since updates to these sets are not directly a function
of message exchanges, but rather are derived from updates to other of message exchanges, but rather are derived from updates to other
sets, in particular the MPR Selector Set. sets, in particular the MPR Selector Set.
12.1 Populating the Relay Set 12.1. Populating the Relay Set
The Relay Set contains the set of neighbor addresses, for which a The Relay Set contains the set of neighbor addresses, for which a
node is supposed to relay broadcast traffic. This set SHOULD at node is supposed to relay broadcast traffic. This set SHOULD at
least contain the addresses of the MPR Selector set (i.e. all least contain all addresses in the MPR Selector Set. This set MAY
addresses, associated with a MPR selector through the Neighborhood contain additional symmetric 1-hop neighbor addresses.
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 12.2. Populating the Advertised Neighbor Set
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 The Advertised Neighbor Set contains the set of OLSRv2 interface
whose addresses are in the Local Interface Block being processed, addresses of those 1-hop neighbors to which a node advertises a
then discard that tuple. symmetric link in TC messages. This set SHOULD at least contain all
of the OLSRv2 interface addresses of the nodes in the MPR Selector
Set (i.e. all addresses associated with an MPR Selector node through
the Neighborhood Address Association Set, that is, appearing in the
same NA_neighbor_iface_addr_list as any MS_neighbor_iface_addr).
This set MAY also contain OLSRv2 interface addresses of other
symmetric 1-hop neighbors.
2. A tuple is added to the Neighborhood Address Association Set, Whenever an address is removed from the Advertised Neighbor Set, the
where: ANSN MUST be incremented. Whenever an address is added to the
Advertised Neighbor Set, the ANSN MUST be incremented.
* NA_neighbor_addr_list = all addresses from the Local Interface 13. Routing Table Calculation
Block;
* NA_time = current time + NA_HOLD_TIME. The Routing Set is updated when a change (an entry appearing or
disappearing, or changing between SYMMETRIC and LOST) is detected in:
14. Routing Table Calculation o the Link Set, OR;
The Routing Set is updated when a change (an entry appearing/ o the Neighbor Address Association Set, OR;
disappearing) is detected in:
o the Link Set, o the 2-Hop Neighbor Set, OR;
o the Neighbor Address Association Set, o the Topology Set, OR;
o the 2-hop Neighbor Set, o the Attached Network Set.
o the Topology Set, Note that some changes to these sets do not necessitate a change to
the Routing Set, in particular changes to the Link Set which do not
involve Link Tuples with L_STATUS == SYMMETRIC (either before or
after the change), similar changes to the Neighbor Address
Association Set. A node MAY avoid updating the Routing Set in such
cases.
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
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 o the arcs X -> Y where there exists a Link Tuple with Y as
and there exists an entry in the 2-hop Neighbor Set with Y as L_neighbor_iface_addr and L_STATUS == SYMMETRIC (i.e. Y is a
N2_neighbor_iface_addr and Z as N2_2hop_iface_addr, and the arcs U -> symmetric 1-hop neighbor of X), AND;
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 o the arcs Y -> Z where Y is added as above and the Link Tuple with
complemented with the arcs W0 -> W1 where W0 and W1 are two addresses Y as L_neighbor_iface_addr has L_willingness not equal to
of interfaces of a same neighbor (in a neighbor address association WILL_NEVER, and there exists a 2-Hop Neighbor Tuple with Y as
tuple). N2_neighbor_iface_addr and Z as N2_2hop_iface_addr (i.e. Z is a
symmetric 2-hop neighbor of Z through Y, which does not have
willingness WILL_NEVER), AND;
o the arcs U -> V, where there exists a Topology Tuple with U as
T_last_iface_addr and V as T_dest_iface_addr (i.e. this is an
advertised link in the network).
The graph is complemented with:
o arcs Y -> W where there exists a Link Tuple with Y as
L_neighbor_iface_addr and L_STATUS == SYMMETRIC and a Neighborhood
Address Association Tuple with Y and W both contained in
NA_neighbor_iface_addr_list (i.e. Y and W are both addresses of
the same symmetric 1-hop neighbor), AND;
o arcs U -> T where there exists an Attached Network Tuple with U as
AN_net_addr and T as AN_gw_iface_addr (i.e. U is a gateway to
network T).
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 using a variation of Dijkstra's algorithm. Thus:
1. All the tuples from the Routing Set are removed. 1. All Routing Tuples are removed.
2. The new routing tuples are added starting with the symmetric 2. For each Link Tuple with L_STATUS == SYMMETRIC, a new Routing
neighbors (h=1) as the destinations. Thus, for each tuple in the Tuple is added with:
Link Set where:
* L_STATUS == SYMMETRIC (L_STATUS is calculated as * R_dest_addr = L_neighbor_iface_addr of the Link Tuple;
indicated in Table 1)
a new routing tuple is recorded in the Routing Set with: * R_next_iface_addr = L_neighbor_iface_addr of the Link Tuple;
* R_dest_iface_addr = L_neighbor_iface_addr, of the link tuple; * R_dist = 1;
* R_local_iface_addr = L_local_iface_addr of the Link Tuple.
3. For each Neighbor Address Association Tuple, for which two
addresses A1 and A2 are in NA_neighbor_iface_addr_list where:
* there is a Routing Tuple with:
+ R_dest_addr == A1
* and there is no Routing Tuple with:
+ R_dest_addr == A2
then a Routing Tuple is added with:
* R_dest_addr = A2;
* R_next_iface_addr = R_next_iface_addr of the Routing Tuple in
which R_dest_addr == A1;
* 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_local_iface_addr = R_local_iface_addr of the Routing Tuple
in which R_dest_addr == A1.
3. for each neighbor address association tuple, for which two 4. The following procedure, which adds Routing Tuples for
addresses A1 and A2 exist in I_neighbor_iface_addr_list where: destination nodes h+1 hops away, MUST be executed for each value
of h, starting with h=2 and incrementing by 1 for each iteration.
The execution MUST stop if no new Routing Tuples are added in an
iteration.
* there exists a routing tuple with: 1. For each Topology Tuple, if
+ R_dest_iface_addr == A1 + T_dest_iface_addr is not equal to R_dest_addr of any
Routing Tuple, AND;
* there is no routing tuple with: + T_last_iface_addr is equal to R_dest_addr of a Routing
Tuple whose R_dist == h;
+ R_dest_iface_addr == A2 then a new Routing Tuple MUST be added, with:
then a tuple in the Routing Set is created with: + R_dest_addr = T_dest_iface_addr;
* R_dest_iface_addr = A2; + R_next_iface_addr = R_next_iface_addr of the Routing Tuple
whose R_dest_addr == T_last_iface_addr;
* R_next_iface_addr = R_next_iface_addr of the route tuple of + R_dist = h+1;
A1;
* R_dist = R_dist of the route tuple of A1 (e.g. 1); + R_local_iface_addr = R_local_iface_addr of the Routing
Tuple whose R_dest_addr == T_last_iface_addr.
* R_iface_addr = R_iface_addr of the route tuple of A1. Several Topology Tuples may be used to select a next hop
R_next_iface_addr for reaching the address R_dest_addr. When
h == 1, ties should be broken such that nodes with highest
willingness are preferred, and between nodes of equal
willingness, MPR selectors are preferred over non-MPR
selectors.
4. for each symmetric strict 2-hop neighbor where the 2. After the above iteration has completed, if h == 1, for each
N2_neighbor_iface_addr has a willingness different from 2-Hop Neighbor Tuple where:
WILL_NEVER a tuple in the Routing Set is created with:
* R_dest_iface_addr = N2_2hop_iface_addr of the 2-hop neighbor; + N2_2hop_iface_addr is not equal to R_dest_addr of any
Routing Tuple, AND;
* R_next_iface_addr = the R_next_iface_addr of the route tuple + N2_neighbor_iface_addr has a willingness (i.e. the
with: L_willingness of the Link Tuple of which
L_neighbor_iface_addr == N2_neighbor_iface_addr) which is
not equal to WILL_NEVER;
+ R_dest_iface_addr == N2_neighbor_iface_addr of the 2-hop a Routing Tuple is added with:
tuple;
* R_dist = 2; + R_dest_addr = N2_2hop_iface_addr of the 2-Hop Neighbor
Tuple;
+ R_next_iface_addr = R_next_iface_addr of the Routing Tuple
in which R_dest_addr == N2_neighbor_iface_addr;
* R_iface_addr = the R_iface_addr of the route tuple with: + R_dist = 2;
+ R_dest_iface_addr == N2_neighbor_iface_addr of the 2-hop + R_local_iface_addr = R_local_iface_addr of the Routing
tuple; Tuple in which R_dest_addr == N2_neighbor_iface_addr.
5. The new route tuples for the destination nodes h+1 hops away are 5. For each Attached Network Tuple, if
recorded in the routing table. The following procedure MUST be
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
is recorded in an iteration.
1. For each topology tuple in the Topology Set, if its * AN_net_addr is not equal to R_dest_addr of any Routing Tuple,
T_dest_iface_addr does not correspond to R_dest_iface_addr of AND;
any route tuple in the Routing Set AND its T_last_iface_addr
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
in the Routing Set (if it does not already exist) where:
+ R_dest_iface_addr = T_dest_iface_addr; * AN_gw_iface_addr is equal to R_dest_addr of a Routing Tuple;
+ R_next_iface_addr = R_next_iface_addr of the route tuple then a new Routing Tuple MUST be added, with:
where:
- R_dest_iface_addr == T_last_iface_addr * R_dest_addr = AN_net_addr;
+ R_dist = h+1; and * R_next_iface_addr = R_next_iface_addr of the Routing Tuple
whose R_dest_addr == AN_gw_iface_addr;
+ R_iface_addr = R_iface_addr of the route tuple where: * R_dist = R_dist of the Routing Tuple whose R_dest_addr ==
AN_gw_iface_addr;
- R_dest_iface_addr == T_last_iface_addr. * R_local_iface_addr = R_local_iface_addr of the Routing Tuple
whose R_dest_addr == AN_gw_iface_addr.
2. Several topology tuples may be used to select a next hop If more than one Attached Network Tuple has the same AN_net_addr,
R_next_iface_addr for reaching the node R_dest_iface_addr. then more than one Routing Tuple MUST NOT be added, and the added
When h==1, ties should be broken such that nodes with highest Routing Tuple MUST have minimum R_dist.
willingness and MPR selectors are preferred as next hop.
15. Proposed Values for Constants 14. 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.
15.1 Message Intervals 14.1. Neighborhood Discovery Constants
o HELLO_INTERVAL = 2 seconds The constants HELLO_INTERVAL, REFRESH_INTERVAL, HELLO_MIN_INTERVAL,
H_HOLD_TIME, L_HOLD_TIME, N_HOLD_TIME and C are used as in [4].
o REFRESH_INTERVAL = 2 seconds 14.2. Message Intervals
o TC_INTERVAL = 5 seconds o TC_INTERVAL = 5 seconds
15.2 Holding Times o TC_MIN_INTERVAL = TC_INTERVAL/4
o L_HOLD_TIME = 3 x HELLO_INTERVAL
o N2_HOLD_TIME = 3 x REFRESH_INTERVAL
o NA_HOLD_TIME = 3 x TC_INTERVAL 14.3. Holding Times
o T_HOLD_TIME = 3 x TC_INTERVAL o T_HOLD_TIME = 3 x TC_INTERVAL
o RX_HOLD_TIME = 30 seconds o A_HOLD_TIME = T_HOLD_TIME
o FW_HOLD_TIME = 30 seconds
o P_HOLD_TIME = 30 seconds o P_HOLD_TIME = 30 seconds
o FG_HOLD_TIME = 30 seconds o FG_HOLD_TIME = 30 seconds
15.3 Willingness o RX_HOLD_TIME = 30 seconds
o WILL_NEVER = 0 o FW_HOLD_TIME = 30 seconds
o WILL_LOW = 1 14.4. Willingness
o WILL_DEFAULT = 3 o WILL_NEVER = 0
o WILL_HIGH = 6 o WILL_DEFAULT = 3
o WILL_ALWAYS = 7 o WILL_ALWAYS = 7
15.4 Time 15. Sequence Numbers
o C = 0.0625 seconds (1/16 second) Sequence numbers are used in OLSRv2 with the purpose of discarding
"old" information, i.e. messages received out of order. However with
a limited number of bits for representing sequence numbers, wrap-
around (that the sequence number is incremented from the maximum
possible value to zero) will occur. To prevent this from interfering
with the operation of OLSRv2, the following MUST be observed when
determining the ordering of sequence numbers.
16. Representing Time The term MAXVALUE designates in the following one more than the
largest possible value for a sequence number. For a 16 bit sequence
number (as are those defined in this specification) MAXVALUE is
65536.
OLSRv2 specifies several TLVs, where time, in seconds, is to be The sequence number S1 is said to be "greater than" the sequence
represented via an 8 bit field. number S2 if:
Of these 8 bits, the highest four bits represent the mantissa (a) and o S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR
the four lowest bits represent the exponent (b), yielding that:
o time = C*(1+a/16)* 2^b [in seconds] o S2 > S1 AND S2 - S1 > MAXVALUE/2
where a is the integer represented by the four highest bits of the Thus when comparing two messages, it is possible - even in the
time field and b the integer represented by the four lowest bits of presence of wrap-around - to determine which message contains the
the time field. The proposed value of the scaling factor C is most recent information.
specified in Section 15. All nodes in the network MUST use the same
value of C.
17. IANA Considerations 16. IANA Considerations
17.1 Multicast Addresses 16.1. Multicast Addresses
A well-known multicast address, All-OLSRv2-Multicast, must be A well-known multicast address, ALL-MANET-NEIGHBORS, must be
registered and defined for both IPv6 and IPv4. The addressing scope 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 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 multicast address of IPv6 in that it targets all OLSRv2 capable nodes
adjacent to the originator of an IP datagram. adjacent to the originator of an IP datagram.
17.2 Message Types 16.2. Message Types
OLSRv2 defines two message types, which must be allocated from the OLSRv2 defines one message type, which must be allocated from the
"Assigned Message Types" repository of [4] "Assigned Message Types" repository of [3]
+--------------------+--------+-------------------------------------+ +--------------------+-------+--------------------------------------+
| Mnemonic | Value | Description | | Mnemonic | Value | Description |
+--------------------+--------+-------------------------------------+ +--------------------+-------+--------------------------------------+
| HELLOv2 | TBD | Local Signaling | | TC | TBD | Topology Control (global signaling) |
| | | | +--------------------+-------+--------------------------------------+
| TCv2 | TBD | Global Signaling |
+--------------------+--------+-------------------------------------+
Table 7 Table 5
17.3 TLV Types 16.3. TLV Types
OLSRv2 defines three Message TLV types, which must be allocated from OLSRv2 defines one Message TLV type, which must be allocated from the
the "Assigned message TLV Types" repository of [4] "Assigned message TLV Types" repository of [3]
+--------------------+--------+-------------------------------------+ +--------------------+-------+--------------------------------------+
| Mnemonic | Value | Description | | Mnemonic | Value | Description |
+--------------------+--------+-------------------------------------+ +--------------------+-------+--------------------------------------+
| VALIDITY_TIME | TBD | The time (in seconds) from receipt | | WILLINGNESS | TBD | Specifies a node's willingness to |
| | | of the message during which the | | | | act as a relay and to partake in |
| | | information contained in a message | | | | network formation |
| | | 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 Table 6
from the "Assigned address block TLV Types" repository of [4] OLSRv2 defines one Address Block TLV type, which must be allocated
from the "Assigned address block TLV Types" repository of [3]
+--------------------+--------+-------------------------------------+ +--------------------+-------+--------------------------------------+
| Mnemonic | Value | Description | | 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 |
| | | bidirectional, lost) |
| | | |
| MPR | TBD | Specifies that a given address is | | MPR | TBD | Specifies that a given address is |
| | | selected as MPR | | | | selected as MPR |
+--------------------+--------+-------------------------------------+ +--------------------+-------+--------------------------------------+
Table 9 Table 7
18. References 17. References
[1] Clausen, T., "The Optimized Link State Routing Protocol", 17.1. Normative References
RFC 3626, October 2003.
[1] Clausen, T. and P. Jacquet, "The Optimized Link State Routing
Protocol", RFC 3626, October 2003.
[2] Bradner, S., "Key words for use in RFCs to Indicate Requirement [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", RFC 2119, BCP 14, March 1997. Levels", RFC 2119, BCP 14, March 1997.
[3] Atkins, D., Stallings, W., and P. Zimmermann, "PGP Message [3] Clausen, T., Dean, J., Dearlove, C., and C. Adjih, "Generalized
Exchange Formats", RFC 1991, August 1996. MANET Packet/Message Format", work in
progress draft-ietf-manet-packetbb-01.txt, June 2006.
[4] Clausen, T., Dean, J., and C. Dearlove, "Generalized MANET [4] Clausen, T., Dean, J., and C. Dearlove, "MANET Neighborhood
Packet/Message Format", Work In Discovery Protocol (NHDP)", work in
Progress draft-ietf-manet-packetbb-00.txt, February 2006. progress draft-ietf-manet-nhdp-00.txt, June 2006.
[5] ETSI, "ETSI STC-RES10 Committee. Radio equipment and systems: 17.2. Informative References
[5] Atkins, D., Stallings, W., and P. Zimmermann, "PGP Message
Exchange Formats", RFC 1991, August 1996.
[6] ETSI, "ETSI STC-RES10 Committee. Radio equipment and systems:
HIPERLAN type 1, functional specifications ETS 300-652", HIPERLAN type 1, functional specifications ETS 300-652",
June 1996. June 1996.
[6] Jacquet, P., Minet, P., Muhlethaler, P., and N. Rivierre, [7] Jacquet, P., Minet, P., Muhlethaler, P., and N. Rivierre,
"Increasing reliability in cable free radio LANs: Low level "Increasing reliability in cable free radio LANs: Low level
forwarding in HIPERLAN.", 1996. forwarding in HIPERLAN.", 1996.
[7] Qayuum, A., Viennot, L., and A. Laouiti, "Multipoint relaying: [8] Qayuum, A., Viennot, L., and A. Laouiti, "Multipoint relaying:
An efficient technique for flooding in mobile wireless An efficient technique for flooding in mobile wireless
networks.", 2001. 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 symmetric
interfaces by relaying through an MPR node. 2-hop neighbors by relaying through an MPR node.
There are several peripheral issues that the algorithm need to There are several peripheral issues that the algorithm needs 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 can be summarized by:
o All neighbor nodes with willingness equal to WILL_NEVER MUST o All 1-hop 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 MPRs), nor as 2-hop neighbors (hence 1-hop neighbors (hence not used as MPRs).
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 1-hop neighbor OLSRv2 interfaces, and 2-hop
(and their addresses). Additionally, asymmetric links are neighbor OLSRv2 interfaces (and their addresses). Additionally,
ignored. This is reflected in the definitions below. asymmetric links are 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 interfaces, each interface I, the node MUST select some neighbor interfaces,
so that all 2-hop interfaces are reached. so that all 2-hop neighbor interfaces are reached.
From now on, MPR calculation will be described for one interface I on From now on, MPR calculation will be described for one interface I 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 OLSRv2 interface of a 1-hop neighbor
exist a symmetrical link on interface I. to which there exist a symmetric link using 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 which can be reached from a neighbor interface for
for I. 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 MPRs. 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
MPRs 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 L_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 a MPR Set. Remove the interfaces from N2 which are now covered by 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 an MPR the interface with highest N_willingness 2. Select as an MPR the interface with highest L_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
algorithm attempts to reach every such interface of the nodes.
However, whenever information that several 2-hop interfaces are,
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
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 o In a multiple interface scenario MPRs are selected for each
interface of the selecting node, providing full coverage of all interface of the selecting node, providing full coverage of all
2-hop nodes accessible through that interface. The overall MPR 2-hop nodes accessible through that interface. The overall MPR
Set is then the union of these sets. These sets do not however 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 have to be selected independently, if a node is selected as an MPR
for one interface it may be automatically added to the MPR for one interface it may be automatically added to the MPR
selection for other interfaces. selection for other interfaces.
Appendix B. Example Algorithms for Generating Control Traffic Appendix B. Heuristics for Generating Control Traffic
The proposed generation of the control messages proceeds in four
steps. HELLO messages and TC messages both essentially consist of a
list of advertised addresses of neighbors (some part of the
topology).
Hence, a first step is to collect the set of relevant addresses which
are to be advertised. Because there are a number of TLVs which can
be associated with each address (including mandatory ones), this step
results in a list of addresses, each associated with a certain number
of TLVs.
The second step is then to regroup the addresses which share exactly
the same TLVs (same Type and same Value), into an address block which
will be associated with a list of TLVs.
The third step is to pack the message header and message TLVs into a
sequence of octets.
The fourth step consists of packing every address block obtained in
the second step by finding the longest common prefix of the addresses
in the address block (the head), then, packing the list of the tails
of the addresses into a sequence of octets, followed by the TLVs of
the address block.
This generation method can be used for TC generation and HELLO
generation: in each case, all what need to be specified is the
message headers, message TLVs, and the list of each address with its
associated TLVs.
The Local Interface Block MUST include all of the participating
interface addresses of the node (including the one of chosen as the
node's originator address and included in the message header).
Appendix B.1 Example Algorithm for Generating HELLO messages
This section proposes an algorithm for generating HELLO messages.
Periodically, on each interface I, the node generates a HELLO message
specific to that interface, as follows:
1. First, the list of the links of the interface is collected. It
is the list of the Link Tuples where:
* L_local_iface_addr == address of the interface
Each corresponding address L_neighbor_iface_addr is then
advertised with the following TLVs:
* Type="LINK-STATUS", Value=L_STATUS, the status of the link
(see Section 5.1.1);
* Type="OTHER_IF", if and only if as specified in Section 7);
* Type="MPR", if and only of the address L_neighbor_iface_addr
is an interface address in the MPR Set.
2. Second, if the node has more than one interface, for each address
which was not previously advertised and for which there exists a
Link Tuple on another interface where:
* L_local_iface_addr is different from address of the interface
I; AND
* L_STATUS == SYMMETRIC
the corresponding address L_neighbor_iface_addr is advertised
with the following TLV:
* Type="OTHER_IF", Value=SYMMETRIC.
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:
* Type="OTHER_IF", Value=LOST.
4. Then a HELLO message is generated using the previous method, with
the specified headers and TLVs:
* a message TLV with Type="VALIDITY_TIME" and Value=encoding of
L_HOLD_TIME, SHALL be added
* a message TLV with Type="INTERVAL_TIME" and Value=encoding of
HELLO_INTERVAL, SHOULD be added
* 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
Periodically, the node generates TC messages, broadcast on all the
interfaces of the node, as follows:
1. Each A_iface_addr in the Advertised Neighbor Set, SHALL be
included in the TC message.
2. The TC message is generated with the proper headers, and (except A node creates HELLO messages and TC messages as specified in
where the Advertised Neighbor Set is empty and the TC message is Section 7 and Section 9, the former being a modification of the
not specifically reporting this, see Section 9) including the specification in [4]. The heuristics for creation of HELLO messages
message TLV, Type="CONTENT_SEQUENCE_NUMBER", Value=the current in [4] remain applicable, with the division of the address TLVs with
ASSN of the node. Type == LINK_STATUS and Value == SYMMETRIC into separate ranges with
and without an associated TLV with Type == MPR. The heuristics for
collection of addresses are also generally applicable to TC messages,
excepting that the first address block is not sorted as the Local
Interface Block of a HELLO message is, and that other addresses
recorded in TC messages are divided into those with and without a TLV
with Type == GATEWAY. These should be ordered so that the range of
addresses without that TLV is continuous (and it is suggested that
the range without is also continuous).
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. 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 packets employed in the protocol specification, and the bit-layout of packets employed in the protocol specification, and the bit-layout
packets actually exchanged between the nodes. packets actually exchanged between the nodes.
Appendix D.1 OLSRv2 Packet Format Appendix D.1. OLSRv2 Packet Format
The basic layout of an OLSRv2 packet is as described in [4]. However The basic layout of an OLSRv2 packet is as described in [3]. However
the following points should be noted. the following points should be noted.
OLSRv2 uses only packets with a packet header. Thus all OLSRv2 OLSRv2 uses only packets with a packet header including a packet
packets have the following layout. sequence number, either with or without a packet TLV block. Thus all
OLSRv2 packets have the layout of either
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 0| Reserved |0|0| Packet Sequence Number |
|0 0 0 0 0 0 0 0| Reserved | Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Message + Padding |
| Message |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
: ... : : ... :
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Message + Padding |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message | or
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 0 0 0 0 0 0 0| Reserved |1|0| Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Packet TLV Block |
| |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Message + Padding |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: ... :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Message + Padding |
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
All reserved bits are also unset (zero). The reserved bits marked Resv SHOULD be cleared ('0'). The octets
indicated as Padding are optional and MAY be omitted; if not omitted
they SHOULD be used to pad to a 32 bit boundary and MUST all be zero.
OLSRv2 uses only packets with a complete message header. Thus all OLSRv2 uses only messages with a complete message header. Thus all
OLSRv2 messages have the following layout. OLSRv2 messages, plus padding if any, 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Resv |N|0|0| Message Size |
| Message Type | Resv |U|N|0|0| Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Limit | Hop Count | Message Sequence Number |
| Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | |
| Message Body |
| Message Body + Padding |
| | | |
| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The reserved bits marked Resv SHOULD be cleared ('0'). In standard
In standard OLSRv2 messages (HELLO and TC) the U and N bits are also OLSRv2 messages (HELLO and TC) the type dependent sequence number bit
unset(zero). In all OLSRv2 messages the reserved bits marked Resv marked N SHOULD also be cleared ('0').
above are also unset (zero).
The layouts of the message body, address block, TLV block and TLV are The layouts of the message body, address block, TLV block and TLV are
as in [4], allowing all options. Standard (HELLO and TC) messages as in [3], allowing all options. Standard (HELLO and TC) messages
contain a first address block which contains local interface contain a first address block which contains local interface address
addresses, all other address blocks contain information specific to information, all other address blocks contain neighbor interface
the message type. Except by being first, the local interface address address information (or for a TC message address information for
block is not distinguished in any way. which it is a gateway) specific to the message type.
An example HELLO message, using IPv4 (four octet) addresses is as An example HELLO message, using IPv4 (four octet) addresses is as
follows. The overall message length is 56 octets (it does not need 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 padding). The message has a hop limit of 1 and a hop count of 0, as
by its originator. sent by its originator.
The message has a message TLV block with content length 12 octets The message has a message TLV block with content length 12 octets
containing three message TLVs. These TLVs represent message validity containing three message TLVs. These TLVs represent message validity
time, message interval time and willingness. Each uses a TLV with time, message interval time and willingness. Each uses a TLV with
semantics value 4, indicating no start and stop indexes are included, semantics value 4, indicating no start and stop indexes are included,
and each has a value length of 1 octet. and each has a value length of 1 octet.
The first address block contains a single local interface address, The first address block contains a 1 local interface address, with
with head length 4; thus although 1 tail is indicated, no tail octets head length 4. This is equal to the address length, thus no tail or
are included. This address block has no TLVs (TLV block content mid sections of the address are included. This address block has no
length 0 octets). TLVs (the TLV block content length is 0 octets).
The second, and last, address block reports 4 neighbour interface The second, and last, address block reports 4 neighbor interface
addresses, with address head length 3 octets. The following TLV addresses, with address head length 3 octets, and no tail octet (zero
block (content length 11 octets) includes two TLVs. tail length). Thus each mid address section is of length one octet.
The following address TLV block (content length 11 octets) includes
two TLVs.
The first of these TLVs reports the link status of all four The first of these TLVs reports the link status of all four neighbors
neighbours in a single multivalue TLV, the first two addresses are in a single multivalue TLV, the first two addresses are HEARD, the
HEARD, the last two addresses are SYMMETRIC. The TLV semantics value last two addresses are SYMMETRIC. The TLV semantics value of 12
of 12 indicates, in addition to that this is a multivalue TLV, that indicates, in addition to that this is a multivalue TLV, that no
no start index and stop index are included, since values for all start index and stop index are included, hence values for all
addresses are included. The TLV value length of 4 octets indicates addresses are included. The TLV value length of 4 octets indicates
one octet per value per address. one octet per value per address.
The second of these TLV indicates that the last address (start index 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, 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. fields, as indicated by its semantics octet being equal to 1.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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| | 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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address | | Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number | |0 0 0 0 0 0 0 1|0 0 0 0 0 0 0 0| Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|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|
|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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |0 0 0 0 0 1 0 0|
|0 0 0 0 0 0 0 1| Value | INTERVAL-TIME |0 0 0 0 0 1 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value | WILLINGNESS |0 0 0 0 0 1 0 0| |0 0 0 0 0 0 0 1| Value | WILLINGNESS |0 0 0 0 0 1 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 1| Value |0 0 0 0 0 0 0 1|0 0 0 0 0 1 0 0|
|0 0 0 0 0 0 0 1| Value |0 0 0 0 0 1 0 0| Head |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Head |
| Head (cont) |0 0 0 0 0 0 0 1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 1 0 0|0 0 0 0 0 0 1 1|
|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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Head | Mid |
| Head (cont) |0 0 0 0 0 1 0 0| Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid | Mid | Mid |0 0 0 0 0 0 0 0|
| Tail | Tail | Tail |0 0 0 0 0 0 0 0|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|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|
|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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| HEARD | HEARD | SYMMETRIC | SYMMETRIC | | HEARD | HEARD | SYMMETRIC | SYMMETRIC |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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| | 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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
An example TC message, using IPv4 (four octet) addresses, is as An example TC message, using IPv4 (four octet) addresses, is as
follows. The overall message length is 67 octets, the final octet is follows. The overall message length is 64 octets, it also does not
padding. need padding.
The message has a message TLV block with content length 13 octets The message has a message TLV block with content length 13 octets
containing three TLVs. The first TLV is a content sequence number containing three TLVs. The first TLV is a content sequence number
TLV used to carry the 2 octet ANSN. The semantics value is 4 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 indicating that no index fields are included. The other two TLVs are
validity and interval times as for the HELLO message above. validity and interval times as for the HELLO message above.
The message has three address blocks. The first address block The message has three address blocks. The first address block
contains 3 local interface addresses (with common head length 2 contains 3 local interface addresses (with common head length 2
octets) and has a TLV block with content length 4 octets containing a octets) and has a TLV block with content length 0 octets.
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, The other two address blocks contain neighbor interface addresses.
with head lengths 2 and 4 respectively. The first of these, with 3
addresses, has an empty TLV block (content length 0 octets). The
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).
0 1 2 3 The first contains 3 addresses and has an empty TLV block (content
length 0 octets). The second contains 1 address. The head octet
(hex 82) indicates a head length of two octets and the presence of a
tail octet. The tail octet (hex 82) indicates a tail length of two
octets, all zero bits and not included. The following TLV block
(content length 6 octets) includes two TLVs, the first (semantics
value 4 indicating no indexes are needed) indicates that the address
has a netmask, with length given by the value (of length 1 octet) of
16. Thus this address is Head.0.0/16. The second TLV indicates that
the originating node is a gateway to this network, the TLV semantics
value of 5 indicates that neither indexes nor value are needed.
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 |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0|
| 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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hop Limit | Hop Count | Message Sequence Number |
| Time to Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|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| |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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 1 0| Value (ANSN) | VALIDITY_TIME |
|0 0 0 0 0 0 1 0| Value (ASSN) | VALIDITY_TIME |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 1 0 0|0 0 0 0 0 0 0 1| Value | INTERVAL_TIME | |0 0 0 0 0 1 0 0|0 0 0 0 0 0 0 1| Value | INTERVAL_TIME |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 1 0 0|0 0 0 0 0 0 0 1| Value |0 0 0 0 0 0 1 1|
|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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Head |0 0 0 0 0 0 1 1| Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 1 0| Head | Mid |
| Tail (cont) | Tail | Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid (cont) | Mid | Mid |
| Tail (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0| OTHER_IF |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 1 1|
|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|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 1 0| Head | Mid |
| Head |0 0 0 0 0 0 1 1| Tail |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mid (cont) | Mid | Mid |
| 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| | Mid (cont) |0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 1|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1 0 0 0 0 0 1 0| Head |1 0 0 0 0 0 1 0|
| Head |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0| PREFIX_LENGTH |0 0 0 0 0 1 0 0|
|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 0 0 1|0 0 0 1 0 0 0 0| GATEWAY |0 0 0 0 0 1 0 1|
|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 at least one a unique and routable 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 IP address for each interface that it has which participates in the
MANET. MANET.
When applicable, a recommended way of connecting an OLSRv2 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 OLSRv2 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 F. Security Considerations Appendix F. Jitter
In a wireless network, simultaneous packet transmission by nearby
nodes is undesirable as, depending on the medium access control and
other lower layer mechanisms, the interference between these messages
may cause at best increased delay, and at worst complete packet loss
by both nodes. This is often particularly true when using a
broadcast mechanism, such as is used by OLSRv2 packets.
The problems of simultaneous packet transmission in OLSRv2 are
increased by the following features of the protocol:
o If two nodes send packets containing regularly scheduled messages
of the same type at the same time, then if, as is typical, they
are using the same message interval, further transmissions of
these messages will also be at the same time, and will also
interfere. This node synchronization could even result in
complete operational failure of these nodes.
o OLSRv2 allows nodes to respond to changes in their circumstances,
usually changes in the neighborhood, with immediate messages of
appropriate types. Nearby nodes will have overlapping
neighborhoods, and may respond to the same change in
circumstances. For example a single link failure can result in a
node having to change its MPR Set, and then two or more of its
neighbors having changed MPR status responding simultaneously with
revised TC messages, whose packets may interfere.
o When a node sends such a responsive message, there is no apparent
reason why it should not restart its message schedule of the
appropriate type of message. This results in nodes responding to
the same change not just sending single simultaneous packets, but
becoming synchronized.
o Nodes also forward messages they receive from other nodes. Two
nearby nodes will thus commonly receive and forward the same
message. The consequent packet transmissions can easily interfere
with each other.
Because interference can easily occur, is self-reinforcing, and is
anything from undesirable to catastrophic, mechanisms to minimize it,
and to break synchronization of nodes, SHOULD be used in OLSRv2.
These all make a deliberate adjustment to the timing, known as
"jitter". Three cases exist:
o When a node generates a control message periodically, it would
normally wait for a delay equal to MESSAGE_INTERVAL (e.g.
HELLO_INTERVAL for HELLO messages or TC_INTERVAL for TC messages)
between two transmissions of messages of that type. This delay
SHOULD be mitigated by subtracting a jitter time, so that the
delay between consecutive transmissions of a messages of the same
type SHOULD be equal to MESSAGE_INTERVAL - jitter, where jitter is
a random value whose generation is discussed below. Note that
this is a deliberately asymmetric process. It ensures that the
message interval does not exceed MESSAGE_INTERVAL (which leaves
MESSAGE_INTERVAL an appropriate value for reporting in an
INTERVAL_TIME message TLV) and also allows different nodes to
become completely desynchronized as each interval is based on the
previous actual transmission time, not on a fixed clock of period
MESSAGE_INTERVAL.
o When a node responds to an externally triggered change in
circumstances, it SHOULD delay the transmission of a message in
response by a random jitter time. It MAY restart its schedule of
messages of the appropriate type based on that new time. If such
a message is delayed due to the need to respect the appropriate
MESSAGE_MIN_INTERVAL (e.g. HELLO_MIN_INTERVAL for HELLO messages
or TC_MIN_INTERVAL for TC messages) then the node MAY reduce this
minimum interval by a jitter time as the normal message interval
is reduced (thus allowing MESSAGE_MIN_INTERVAL to equal
MESSAGE_INTERVAL even when using jitter).
o When a node forwards a message, it SHOULD delay the message
retransmission by a random jitter time.
In the first and second cases above, the maximum jitter time may be
specified by a parameter MAXJITTER. It is necessary only that this
be significantly less than each MESSAGE_INTERVAL, and less than each
MESSAGE_MIN_INTERVAL. Normally the actual value of the jitter
(reduction in message interval or delay of responsive message) SHOULD
be uniformly generated in the interval 0 <= jitter <= MAXJITTER,
however this may be modified as indicated below.
In the third case above, a message SHOULD be delayed by a jitter
value which is significantly less than the originating node's message
interval. This MAY be available in an INTERVAL_TIME message TLV in
the message to be forwarded. If not so available, a node MAY
estimate an acceptable maximum jitter by any other means available to
it, which may be by use of its own MAXJITTER parameter for as long as
this works. In a network in which this is likely to be unsuccessful,
nodes SHOULD include an INTERVAL_TIME message TLV in messages which
are to be forwarded.
In all cases, as well as constraints imposed by message intervals and
message minimum intervals, the maximum jitter delay SHOULD only be as
large as is required to achieve the required objective of minimizing
interference due to synchronization. This is because all jitter, and
forwarding jitter in particular, is undesirable for otherwise ideal
functioning of the network.
Because of differing parameters, or due to responsive messages with a
small minimum message interval, a node may receive a message from an
originating node while still waiting to forward an earlier message of
the same type originating from the same node. The forwarding node
SHOULD NOT allow forwarding jitter delay to reorder these messages.
A node MAY discard the earlier message, transmitting the later
message no later than the earlier message was due to be
retransmitted, if, and only if, it can guarantee that this will not
have any adverse effect.
OLSRv2 messages are transmitted in potentially multi-message packets.
Whilst a packet is a hop by hop construct and it is the messages in
it which are forwarded, if a number of messages are received in the
same packet, they SHOULD (if their maximum jitter delays are
compatible) be permitted to be forwarded in the same new packet.
This may be accomplished by generating the same random delay for all
messages received in a single packet. Furthermore, the opportunity
to combine messages to be forwarded from different sources, and
locally generated messages in a single packet SHOULD be allowed even
when this means adjusting (forwards or backwards) the strictly
uniformly generated random jitter times, however these SHOULD NOT be
allowed to exceed their maximum value, nor allow a message interval
to be exceeded, nor compromise the purpose of jitter. (It is for
this reason that messages in the same packet should be given the same
random jitter, as giving them independent jitter values but then, for
example, allowing all to be sent with the earliest would reduce the
mean jitter delay.)
Appendix G. Security Considerations
Currently, OLSRv2 does not specify any special security measures. As Currently, OLSRv2 does not specify any special security measures. As
a proactive routing protocol, OLSRv2 makes a target for various a proactive routing protocol, OLSRv2 makes a target for various
attacks. The various possible vulnerabilities are discussed in this attacks. The various possible vulnerabilities are discussed in this
section. section.
Appendix F.1 Confidentiality Appendix G.1. Confidentiality
Being a proactive protocol, OLSRv2 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 OLSRv2 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 importance, regular cryptographic techniques, such as exchange of
OLSRv2 control traffic messages encrypted by PGP [3] or encrypted by OLSRv2 control traffic messages encrypted by PGP [5] or encrypted by
some shared secret key, can be applied to ensure that control traffic some shared secret key, can be applied to ensure that control traffic
can 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 G.2. Integrity
In OLSRv2, 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
skipping to change at page 75, line 38 skipping to change at page 64, line 38
are transmitted either to all nodes in the neighborhood (HELLO are transmitted either to all nodes in the neighborhood (HELLO
messages) or broadcast to all nodes in the network (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 G.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. Appendix E 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 OLSRv2 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 Appendix E, 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
skipping to change at page 76, line 14 skipping to change at page 65, line 14
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 G.4. Node Identity
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 at least one a unique and routable 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 IP address for each interface that it has which participates in the
MANET. MANET.
Appendix G. Flow and Congestion Control Appendix H. Flow and Congestion Control
TBD TBD
Appendix H. Sequence Numbers
Sequence numbers are used in OLSR with the purpose of discarding
"old" information, i.e., messages received out of order. However
with a limited number of bits for representing sequence numbers,
wrap-around (that the sequence number is incremented from the maximum
possible value to zero) will occur. To prevent this from interfering
with the operation of OLSRv2, the following MUST be observed.
The term MAXVALUE designates in the following the largest possible
value for a sequence number.
The sequence number S1 is said to be "greater than" the sequence
number S2 if:
o S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR
o S2 > S1 AND S2 - S1 > MAXVALUE/2
Thus when comparing two messages, it is possible - even in the
presence of wrap-around - to determine which message contains the
most recent information.
Appendix I. Contributors Appendix I. 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 contributors -- listed alphabetically.
o Cedric Adjih, INRIA, France, <Cedric.Adjih@inria.fr> o Cedric Adjih, INRIA, France, <Cedric.Adjih@inria.fr>
o Emmanuel Baccelli, Hitachi Labs Europe, France, o Emmanuel Baccelli, Hitachi Labs Europe, France,
<Emmanuel.Baccelli@inria.fr> <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, Niigata 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 J. 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 Anis Laouiti, Pascale Minet, Laurent specified in RFC3626, including Anis Laouiti, Pascale Minet, Laurent
Viennot (all at INRIA, France), and Amir Qayuum (Center for Advanced Viennot (all at INRIA, France), and Amir Qayuum (Center for Advanced
Research in Engineering) for their contributions. Research in Engineering, Pakistan) for their 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: Li Li (CRC), Louise Lamont (CRC),
Li Li (CRC), Louise Lamont (CRC), Joe Macker (NRL), Alan Cullen (BAE Joe Macker (NRL), Alan Cullen (BAE Systems), Philippe Jacquet
Systems), Philippe Jacquet (INRIA), Khaldoun Al Agha (LRI), Richard (INRIA), Khaldoun Al Agha (LRI), Richard Ogier (SRI), Song-Yean Cho
Ogier (?), Song-Yean Cho (Samsung Software Center), Shubhranshu Singh (Samsung Software Center), Shubhranshu Singh (Samsung AIT) and the
(Samsung AIT) and the entire IETF MANET working group. entire IETF MANET working group.
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
URI: http://www.baesystems.com/ocs/sharedservices/atc/
Philippe Jacquet
Project Hipercom, INRIA
Phone: +33 1 3963 5263
Email: philippe.jacquet@inria.fr
URI: http://hipercom.inria.fr/test/Jacquet.htm
The OLSRv2 Design Team
MANET Working Group
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
 End of changes. 527 change blocks. 
1776 lines changed or deleted 1424 lines changed or added

This html diff was produced by rfcdiff 1.32. The latest version is available from http://www.levkowetz.com/ietf/tools/rfcdiff/