RFC 3626
Optimized Link State Routing Protocol (OLSR)
Optimized Link State Routing Protocol (OLSR) 💖
Title block, bestie 🎀
- Series: Network Working Group, RFC 3626
- Editors: T. Clausen, Ed. and P. Jacquet, Ed.
- Affiliation: Project Hipercom, INRIA
- Category: Experimental 🧪
- Date: October 2003 📅
- Obsoletes / Updates: none listed in this header 🙅♀️
Status of This Memo 📜
okay so this memo defines an Experimental Protocol for the Internet community 🧪✨ It is not an Internet standard of any kind, so don't go calling it one, periodt 💅 Discussion and suggestions for improvement are requested, so if you have ideas, bring them 🫶 And distribution of this memo is unlimited, so share it with everyone 🌈
Copyright Notice ©️
Copyright (C) The Internet Society (2003). All Rights Reserved. 🔒
Abstract 🦋
okay this one is so iconic 😭 This document describes the Optimized Link State Routing (OLSR) protocol for mobile ad hoc networks 📡 It's basically a glow-up of the classic link state algorithm, tailored for the vibes of a mobile wireless LAN 💜
The main star of the show is the concept of multipoint relays (MPRs) 👑 MPRs are selected nodes that forward broadcast messages during the flooding process. This is giving huge efficiency 🔥 because a classical flooding setup has every node retransmit each message the moment it gets the first copy, and that's a lot of chaos 💀 OLSR cuts that down a ton.
Here's the rest of the glow-up:
- Optimization two: link state information is only generated by nodes that were elected as MPRs, so fewer control messages get flooded around the network 🧚
- Optimization three: an MPR node may choose to report only the links between itself and its MPR selectors 🎀 Unlike the classic link state algorithm, this means partial link state information is what gets distributed, and it's still used for route calculation 🌸
Even with all that trimming, OLSR still provides optimal routes in terms of number of hops ⭐ It's especially well suited to large and dense networks, because the MPR technique works really well in that setting 🍓
Table of Contents 📑
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. OLSR Terminology. . . . . . . . . . . . . . . . . . . . 5
1.2. Applicability. . . . . . . . . . . . . . . . . . . . . . 7
1.3. Protocol Overview . . . . . . . . . . . . . . . . . . . 8
1.4. Multipoint Relays . . . . . . . . . . . . . . . . . . . 9
2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 9
2.1. Core Functioning . . . . . . . . . . . . . . . . . . . 10
2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . 12
3. Packet Format and Forwarding . . . . . . . . . . . . . . . . 13
3.1. Protocol and Port Number. . . . . . . . . . . . . . . . 13
3.2. Main Address . . . . . . . . . . . . . . . . . . . . . 13
3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . 14
3.3.1. Packet Header . . . . . . . . . . . . . . . . . . 14
3.3.2. Message Header . . . . . . . . . . . . . . . . . 15
3.4. Packet Processing and Message Flooding . . . . . . . . . 16
3.4.1. Default Forwarding Algorithm. . . . . . . . . . . 18
3.4.2. Considerations on Processing and Forwarding . . . 20
3.5. Message Emission and Jitter. . . . . . . . . . . . . . . 21
4. Information Repositories . . . . . . . . . . . . . . . . . . 22
4.1. Multiple Interface Association Information Base . . . . 22
4.2. Link sensing: Local Link Information Base. . . . . . . . 22
4.2.1. Link Set. . . . . . . . . . . . . . . . . . . . . 22
4.3. Neighbor Detection: Neighborhood Information Base. . . . 23
4.3.1. Neighbor Set. . . . . . . . . . . . . . . . . . . 23
4.3.2. 2-hop Neighbor Set. . . . . . . . . . . . . . . . 23
4.3.3. MPR Set . . . . . . . . . . . . . . . . . . . . . 23
4.3.4. MPR Selector Set. . . . . . . . . . . . . . . . . 23
4.4. Topology Information Base . . . . . . . . . . . . . . . 24
5. Main Addresses and Multiple Interfaces . . . . . . . . . . . 24
5.1. MID Message Format . . . . . . . . . . . . . . . . . . . 25
5.2. MID Message Generation . . . . . . . . . . . . . . . . . 25
5.3. MID Message Forwarding . . . . . . . . . . . . . . . . . 26
5.4. MID Message Processing . . . . . . . . . . . . . . . . . 26
5.5. Resolving a Main Address from an Interface Address . . . 27
6. HELLO Message Format and Generation . . . . . . . . . . . . . 27
6.1. HELLO Message Format . . . . . . . . . . . . . . . . . . 27
6.1.1. Link Code as Link Type and Neighbor Type. . . . . 29
6.2. HELLO Message Generation . . . . . . . . . . . . . . . . 30
6.3. HELLO Message Forwarding . . . . . . . . . . . . . . . . 33
6.4. HELLO Message Processing . . . . . . . . . . . . . . . . 33
7. Link Sensing . . . . . . . . . . . . . . . . . . . . . . . . 33
7.1. Populating the Link Set . . . . . . . . . . . . . . . . 33
7.1.1. HELLO Message Processing . . . . . . . . . . . . 34
8. Neighbor Detection . . . . . . . . . . . . . . . . . . . . . 35
8.1. Populating the Neighbor Set . . . . . . . . . . . . . . . 35
8.1.1. HELLO Message Processing . . . . . . . . . . . . 37
8.2. Populating the 2-hop Neighbor Set. . . . . . . . . . . . 37
8.2.1. HELLO Message Processing. . . . . . . . . . . . . 37
8.3. Populating the MPR set . . . . . . . . . . . . . . . . . 38
8.3.1. MPR Computation . . . . . . . . . . . . . . . . . 39
8.4. Populating the MPR Selector Set. . . . . . . . . . . . . 41
8.4.1. HELLO Message Processing. . . . . . . . . . . . . 41
8.5. Neighborhood and 2-hop Neighborhood Changes. . . . . . . 42
9. Topology Discovery . . . . . . . . . . . . . . . . . . . . . 43
9.1. TC Message Format. . . . . . . . . . . . . . . . . . . . 43
9.2. Advertised Neighbor Set. . . . . . . . . . . . . . . . . 44
9.3. TC Message Generation. . . . . . . . . . . . . . . . . . 45
9.4. TC Message Forwarding. . . . . . . . . . . . . . . . . . 45
9.5. TC Message Processing. . . . . . . . . . . . . . . . . . 45
10. Routing Table Calculation . . . . . . . . . . . . . . . . . . 47
11. Node Configuration. . . . . . . . . . . . . . . . . . . . . . 50
11.1. Address Assignment. . . . . . . . . . . . . . . . . . . 50
11.2. Routing Configuration . . . . . . . . . . . . . . . . . 51
11.3. Data Packet Forwarding. . . . . . . . . . . . . . . . . 51
12. Non OLSR Interfaces . . . . . . . . . . . . . . . . . . . . . 51
12.1. HNA Message Format. . . . . . . . . . . . . . . . . . . 52
12.2. Host and Network Association Information Base . . . . . 52
12.3. HNA Message Generation. . . . . . . . . . . . . . . . . 53
12.4. HNA Message Forwarding. . . . . . . . . . . . . . . . . 53
12.5. HNA Message Processing. . . . . . . . . . . . . . . . . 53
12.6. Routing Table Calculation . . . . . . . . . . . . . . . 54
12.7. Interoperability Considerations . . . . . . . . . . . . 55
13. Link Layer Notification . . . . . . . . . . . . . . . . . . . 55
13.1. Interoperability Considerations . . . . . . . . . . . . 56
14. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 56
14.1. Local Link Set . . . . . . . . . . . . . . . . . . . . 56
14.2. Hello Message Generation . . . . . . . . . . . . . . . 57
14.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . . 57
14.4. Interoperability Considerations . . . . . . . . . . . . 59
15. Redundant Topology Information. . . . . . . . . . . . . . . . 59
15.1. TC_REDUNDANCY Parameter . . . . . . . . . . . . . . . . 60
15.2. Interoperability Considerations . . . . . . . . . . . . 60
16. MPR Redundancy. . . . . . . . . . . . . . . . . . . . . . . . 60
16.1. MPR_COVERAGE Parameter. . . . . . . . . . . . . . . . . 61
16.2. MPR Computation . . . . . . . . . . . . . . . . . . . . 61
16.3. Interoperability Considerations . . . . . . . . . . . . 62
17. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . 63
18. Proposed Values for Constants . . . . . . . . . . . . . . . . 63
18.1. Setting emission interval and holding times . . . . . . 63
18.2. Emission Interval . . . . . . . . . . . . . . . . . . . 64
18.3. Holding time . . . . . . . . . . . . . . . . . . . . . 64
18.4. Message Types . . . . . . . . . . . . . . . . . . . . . 65
18.5. Link Types. . . . . . . . . . . . . . . . . . . . . . . 65
18.6. Neighbor Types . . . . . . . . . . . . . . . . . . . . 65
18.7. Link Hysteresis . . . . . . . . . . . . . . . . . . . . 66
18.8. Willingness . . . . . . . . . . . . . . . . . . . . . . 66
18.9. Misc. Constants . . . . . . . . . . . . . . . . . . . . 67
19. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . . . 67
20. Security Considerations . . . . . . . . . . . . . . . . . . . 67
20.1. Confidentiality . . . . . . . . . . . . . . . . . . . . 67
20.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . 68
20.3. Interaction with External Routing Domains . . . . . . . 69
20.4. Node Identity . . . . . . . . . . . . . . . . . . . . . 70
21. Flow and congestion control . . . . . . . . . . . . . . . . . 70
22. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 70
23. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 71
24. Contributors. . . . . . . . . . . . . . . . . . . . . . . . . 71
25. References. . . . . . . . . . . . . . . . . . . . . . . . . . 73
26. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . 74
27. Full Copyright Statement. . . . . . . . . . . . . . . . . . . 751. Introduction ✨
okay so OLSR (the Optimized Link State Routing Protocol) was built for mobile ad hoc networks 🛸 It's a table driven, proactive protocol, which basically means it swaps topology info with the other nodes in the network on a regular schedule 📅 so routes are already sorted when someone needs one. 💅
Each node picks some of its neighbors to be its "multipoint relays" (MPRs) 🦋 Only the nodes that got picked as MPRs are in charge of forwarding control traffic meant to reach the whole network. That's the iconic part: MPRs make flooding way more efficient because the number of transmissions needed goes down 🔥
Nodes that are MPRs also have a special job when it comes to declaring link state info 👑 The only requirement for OLSR to give shortest path routes to every destination is that MPR nodes declare link-state info for their MPR selectors 🫶 Any extra link-state info floating around can also be used, e.g., for redundancy 🌈
Nodes that got selected as multipoint relays by some neighbor node(s) announce that periodically in their control messages 📣 So a node basically tells the whole network, "hey, I can reach the nodes that picked me as an MPR" 🧚 When it's time to calculate routes, the MPRs are used to build the path from a given node to any destination. The protocol also uses MPRs to make flooding control messages efficient across the network ✨
A node picks its MPRs from its one hop neighbors that have "symmetric", i.e., bi-directional, linkages 🎀 Which means choosing routes through MPRs automatically dodges the problems that come with sending data over uni-directional links 🙈 (like not getting link-layer acknowledgments for data packets at each hop, for link-layers that use this technique for unicast traffic). Not me being so grateful for that. 😭
OLSR is developed to work independently from other protocols 🦋 and it makes no assumptions about the underlying link-layer. Zero drama. 💜
OLSR inherits the concept of forwarding and relaying from HIPERLAN (a MAC layer protocol), which is standardized by ETSI [3] 🌸 The protocol was developed in the IPANEMA project (part of the Euclid program) and in the PRIMA project (part of the RNRT program). Such a big-brain origin story, literally 🤯
1.1. OLSR Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC2119 [5]. 📖
Additionally, this document uses the following terminology, so let's get the vocab down, bestie 🍓
- node: A MANET router which implements the Optimized Link State Routing protocol as specified in this document. 🌟
- OLSR interface: A network device participating in a MANET running OLSR. A node may have several OLSR interfaces, each interface assigned an unique IP address. 💖
- non OLSR interface: A network device, not participating in a MANET running OLSR. A node may have several non OLSR interfaces (wireless and/or wired). Routing information from these interfaces MAY be injected into the OLSR routing domain. 🔥
- single OLSR interface node: A node which has a single OLSR interface, participating in an OLSR routing domain. 🎀
- multiple OLSR interface node: A node which has multiple OLSR interfaces, participating in an OLSR routing domain. 🌈
- main address: The main address of a node, which will be used in OLSR control traffic as the "originator address" of all messages emitted by this node. It is the address of one of the OLSR interfaces of the node. 👑
- A single OLSR interface node MUST use the address of its only OLSR interface as the main address.
- A multiple OLSR interface node MUST choose one of its OLSR interface addresses as its "main address" (equivalent of "router ID" or "node identifier"). It is of no importance which address is chosen, however a node SHOULD always use the same address as its main address. 💅
- neighbor node: A node X is a neighbor node of node Y if node Y can hear node X (i.e., a link exists between an OLSR interface on node X and an OLSR interface on Y). 🫶
- 2-hop neighbor: A node heard by a neighbor. 👀
- strict 2-hop neighbor: a 2-hop neighbor which is not the node itself or a neighbor of the node, and in addition is a neighbor of a neighbor, with willingness different from
WILL_NEVER, of the node. 🧚 - multipoint relay (MPR): A node which is selected by its 1-hop neighbor, node X, to "re-transmit" all the broadcast messages that it receives from X, provided that the message is not a duplicate, and that the time to live field of the message is greater than one. 🦋
- multipoint relay selector (MPR selector, MS): A node which has selected its 1-hop neighbor, node X, as its multipoint relay, will be called a multipoint relay selector of node X. 💜
- link: A link is a pair of OLSR interfaces (from two different nodes) susceptible to hear one another (i.e., one may be able to receive traffic from the other). A node is said to have a link to another node when one of its interface has a link to one of the interfaces of the other node. 🌸
- symmetric link: A verified bi-directional link between two OLSR interfaces. ✨
- asymmetric link: A link between two OLSR interfaces, verified in only one direction. 🙈
- 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 X. 💖
- symmetric 2-hop neighborhood: The symmetric 2-hop neighborhood of X is the set of nodes, excluding 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 X is the set of nodes, excluding X itself and its neighbors, which have a symmetric link to some symmetric 1-hop neighbor, with willingness different of
WILL_NEVER, of X. 👑
1.2. Applicability
OLSR is a proactive routing protocol for mobile ad-hoc networks (MANETs) [1], [2]. It is well suited to large and dense mobile networks, because the optimization achieved using the MPRs works really well in that context 🌈 The larger and more dense a network gets, the more optimization can be achieved compared to the classic link state algorithm. 📈 OLSR uses hop-by-hop routing, i.e., each node uses its local information to route packets. 🧚
OLSR is well suited for networks where the traffic is random and sporadic between a larger set of nodes, rather than being almost exclusively between a small specific set of nodes 🦋 And since it's proactive, OLSR is also a good fit for scenarios where the communicating pairs change over time. No extra control traffic gets generated in that situation, since routes are maintained for all known destinations at all times. Main character energy, fr fr. 💅
1.3. Protocol Overview
OLSR is a proactive routing protocol for mobile ad hoc networks. It inherits the stability of a link state algorithm and has the advantage of having routes immediately available when needed, thanks to its proactive nature. OLSR is an optimization over the classical link state protocol, tailored for mobile ad hoc networks. 💖
OLSR minimizes the overhead from flooding control traffic by using only selected nodes, called MPRs, to retransmit control messages. This technique significantly reduces the number of retransmissions required to flood a message to all nodes in the network. Secondly, OLSR requires only partial link state to be flooded in order to provide shortest path routes. The minimal set of link state information required is that all nodes selected as MPRs MUST declare the links to their MPR selectors. Additional topological information, if present, MAY be utilized, e.g., for redundancy purposes. 🫶
OLSR MAY optimize the reactivity to topological changes by reducing the maximum time interval for periodic control message transmission. 🔥 Furthermore, since OLSR continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes, and where the [source, destination] pairs are changing over time. It's particularly suited for large and dense networks, since the optimization done using MPRs works well there. The larger and more dense a network, the more optimization can be achieved compared to the classic link state algorithm. 🌸
OLSR is designed to work in a completely distributed manner and does not depend on any central entity. 👑 The protocol does NOT REQUIRE reliable transmission of control messages. Each node sends control messages periodically, so it can sustain a reasonable loss of some of them. Those losses happen a lot in radio networks because of collisions or other transmission problems. 📡
Also, OLSR does not require sequenced delivery of messages. Each control message contains a sequence number which is incremented for each message, so the recipient can easily identify which information is more recent, even if messages got re-ordered while in transmission. Lowkey genius. 🧠✨
Furthermore, OLSR 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. 🎀
OLSR does not require any changes to the format of IP packets. Thus any existing IP stack can be used as is, since the protocol only interacts with routing table management. Literally no notes. 🦋
1.4. Multipoint Relays 🦋
okay so the whole point of multipoint relays is to stop the flooding from getting out of hand 😭 by cutting down on the repeat retransmissions in the same region. 💅 Every node picks a squad of nodes from its symmetric 1-hop neighborhood that are allowed to retransmit its messages. That squad is called the "Multipoint Relay" (MPR) set of that node. Any neighbor of node N that is not in N's MPR set still receives and processes broadcast messages, but it does not retransmit broadcast messages it gets from node N. 🫶
Each node picks its MPR set from its 1-hop symmetric neighbors, and the picks have to cover (in terms of radio range) all of the symmetric strict 2-hop nodes. ✨ So MPR(N) is an arbitrary subset of N's symmetric 1-hop neighborhood that meets this one condition: every node in N's symmetric strict 2-hop neighborhood must have a symmetric link towards MPR(N). 🎀 The smaller the MPR set, the less control traffic overhead the routing protocol makes, so smaller is iconic. [2] gives an analysis and example of MPR selection algorithms, so go check that if you're curious. 🧚
Each node also keeps track of the neighbors that picked it as an MPR. That group is called the "Multipoint Relay Selector set" (MPR selector set) of a node. 🌸 A node learns who's in that group from the periodic HELLO messages it gets from its neighbors. 💜
Now here's the tea. A broadcast message meant to spread across the whole network, coming from any of node N's MPR selectors, is assumed to be retransmitted by node N, as long as N hasn't received it yet. 🔥 This set can change over time (for example, when a node selects another MPR set), and the selector nodes show that in their HELLO messages. 👑
2. Protocol Functioning 🌈
okay, this section gives you the big picture of how the protocol works. 🦋
OLSR is split into a "core" of functionality, which the protocol always needs in order to run, and a set of auxiliary functions. ✨ The core is a complete protocol that can provide routing in a stand-alone MANET all on its own. 💖
Each auxiliary function adds extra features that might only matter in certain situations, like when a node is connecting the MANET to another routing domain. 🎀
All the auxiliary functions play nicely together, so any (sub)set of them can be implemented alongside the core. 🫶 The protocol even lets heterogeneous nodes (nodes that implement different subsets of the auxiliary functions) hang out in the same network. 🌸
Splitting OLSR into a core and auxiliary functions keeps it simple and easy to understand, and it means you only add complexity when a specific feature actually needs it. 💅
2.1. Core Functioning 💜
The core functionality describes how a node behaves when it has OLSR interfaces, takes part in the MANET, and runs OLSR as its routing protocol. 🧚 It covers a universal spec for OLSR protocol messages and how they get sent through the network, plus link sensing, topology diffusion, and route calculation. 🔥
Here's what the core is made up of:
Packet Format and Forwarding 📦
A universal packet format and an optimized flooding mechanism act as the transport for all OLSR control traffic. 🎀
Link Sensing 👀
Link sensing happens through periodic emission of HELLO messages over the interfaces where connectivity is being checked. ✨ A separate HELLO message is generated for each interface and emitted according to the provisions in section 7.
Link sensing produces a local link set, which describes links between "local interfaces" and "remote interfaces" (in other words, interfaces on neighbor nodes). 🦋
If the link layer gives enough information, that can be used to fill in the local link set instead of doing the HELLO message exchange. 🌈
Neighbor Detection 🫶
In a network where every node has only one interface, a node can deduce its neighbor set straight from the information exchanged during link sensing. 💖 The "main address" of a single-interface node is, by definition, the address of the only interface on that node. 💅
In a network with multi-interface nodes, extra info is needed to map interface addresses to main addresses (and so to nodes). 😭 That extra info comes from multiple interface declaration (MID) messages, which are described in section 5. 🍓
MPR Selection and MPR Signaling 👑
The whole goal of MPR selection is for a node to pick a subset of its neighbors so that a broadcast message, retransmitted by those picked neighbors, reaches every node two hops away. 🔥 The MPR set of a node is computed so that, for each interface, this condition is satisfied. 🎀 The info needed for that calculation comes from the periodic exchange of HELLO messages, as described in section 6. MPR selection procedures are detailed in section 8.3. ✨
MPR signaling happens according to the provisions in section 6. 💜
Topology Control Message Diffusion 🌸
Topology Control messages get diffused so that every node in the network has enough link-state info to do route calculation. 🧚 They're diffused according to the provisions in section 9. 🦋
Route Calculation 🗺️
With the link state info gathered through periodic message exchange, plus the interface configuration of the nodes, the routing table for each node can be computed. 💅 This is detailed in section 10. ✨
The key notion behind all of these mechanisms is the MPR relationship. 💖
The table below shows the core components of OLSR and where each one is covered in this document. 🌈
Feature | Section
------------------------------+--------------
Packet format and forwarding | 3
Information repositories | 4
Main addr and multiple if. | 5
Hello messages | 6
Link sensing | 7
Neighbor detection | 8
Topology discovery | 9
Routing table computation | 10
Node configuration | 112.2. Auxiliary Functioning 🎀
Beyond the core, there are situations where extra functionality is wanted. 🫶 That includes when a node has several interfaces and some of them take part in another routing domain, when the programming interface to the networking hardware gives extra info in the form of link layer notifications, and when you want to send redundant topological info around the network at the cost of extra protocol overhead. 😭
The table below lists the auxiliary functions and where each one is covered in this document. 🦋
Feature | Section
------------------------------+--------------
Non-OLSR interfaces | 12
Link-layer notifications | 13
Advanced link sensing | 14
Redundant topology | 15
Redundant MPR flooding | 16Here's how to read that table: if a listed feature is required, it SHOULD be provided as specified in the corresponding section. 💜
3. Packet Format and Forwarding 💖
OLSR talks using one unified packet format for all of its protocol data. 🧚 The whole point is to make the protocol easy to extend without breaking backwards compatibility. ✨ It also gives you an easy way to piggyback different "types" of info into a single transmission, so an implementation can aim to use the maximum frame size the network provides. 🔥 These packets are embedded in UDP datagrams for transmission over the network. 🌈 This document is written with IPv4 addresses. Considerations for IPv6 are in section 17. 🌸
Each packet wraps up one or more messages. 🎁 The messages all share a common header format, which lets nodes correctly accept and (when applicable) retransmit messages of a type they don't recognize yet. 🫶
Messages can be flooded across the entire network, or the flooding can be limited to nodes within a certain diameter (measured in number of hops) from the message's originator. 🦋 So sending a message to a node's neighborhood is just a special case of flooding. 💅 When flooding any control message, duplicate retransmissions get eliminated locally (each node keeps a duplicate set so it never transmits the same OLSR control message twice) and get minimized across the whole network through the use of MPRs, as described in later sections. 😭
A node can also look at the header of a message to figure out how many hops away its originator is. 👀 That can be handy when, for example, the time info stored in a node from a received control message depends on how far away the originator is. 🍓
3.1. Protocol and Port Number 🎀
OLSR packets are sent over UDP. Port 698 has been assigned by IANA for the exclusive use of the OLSR protocol. 💜
3.2. Main Address 👑
For a node with one interface, the main address of the node, as defined in "OLSR Terminology", MUST be set to the address of that interface. 🔥
3.3. Packet Format ✨
okay bestie, let's talk packets 📦 the basic layout of any OLSR packet looks like this (IP and UDP headers left out, since they're not ours to worry about rn 💅):
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Packet Length | Packet Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Vtime | Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: MESSAGE :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Message Type | Vtime | Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time To Live | Hop Count | Message Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
: MESSAGE :
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
(etc.)3.3.1. Packet Header 🎀
Packet Length
The length (in bytes) of the packet
Packet Sequence Number
The Packet Sequence Number (PSN) MUST be incremented by one each time a new OLSR packet is transmitted. "Wrap-around" is handled as described in section 19. A separate Packet Sequence Number is maintained for each interface such that packets transmitted over an interface are sequentially enumerated. 🔢
The IP address of the interface over which a packet was transmitted is obtainable from the IP header of the packet.
If the packet contains no messages (i.e., the Packet Length is less than or equal to the size of the packet header), the packet MUST silently be discarded. 🗑️
For IPv4 addresses, this implies that packets, where the Packet Length < 16 MUST silently be discarded.
3.3.2. Message Header 💌
Message Type
This field indicates which type of message is to be found in the "MESSAGE" part. Message types in the range of 0-127 are reserved for messages in this document and in possible extensions.
Vtime
This field indicates for how long time after reception a node MUST consider the information contained in the message as valid, unless a more recent update to the information is received. The validity time is represented by its mantissa (four highest bits of Vtime field) and by its exponent (four lowest bits of Vtime field). In other words:
validity time = C*(1+a/16)* 2^b [in seconds]where a is the integer represented by the four highest bits of Vtime field and b the integer represented by the four lowest bits of Vtime field. The proposed value of the scaling factor C is specified in section 18. 🧮
Message Size
This gives the size of this message, counted in bytes and measured from the beginning of the "Message Type" field and until the beginning of the next "Message Type" field (or - if there are no following messages - until the end of the packet).
Originator Address
This field contains the main address of the node, which has originally generated this message. This field SHOULD NOT be confused with the source address from the IP header, which is changed each time to the address of the intermediate interface which is re-transmitting this message. The Originator Address field MUST NEVER be changed in retransmissions. 🚫 bestie, this one's serious!
Time To Live
This field contains the maximum number of hops a message will be transmitted. Before a message is retransmitted, the Time To Live MUST be decremented by 1. When a node receives a message with a Time To Live equal to 0 or 1, the message MUST NOT be retransmitted under any circumstances. Normally, a node would not receive a message with a TTL of zero.
Thus, by setting this field, the originator of a message can limit the flooding radius. 🌸
Hop Count
This field contains the number of hops a message has attained. Before a message is retransmitted, the Hop Count MUST be incremented by 1.
Initially, this is set to '0' by the originator of the message.
Message Sequence Number
While generating a message, the "originator" node will assign a unique identification number to each message. This number is inserted into the Sequence Number field of the message. The sequence number is increased by 1 (one) for each message originating from the node. "Wrap-around" is handled as described in section 19. Message sequence numbers are used to ensure that a given message is not retransmitted more than once by any node. 🦋
3.4. Packet Processing and Message Flooding 🌊
okay so, upon receiving a basic packet, a node looks at each of the "message headers". Based on the value of the "Message Type" field, the node can determine the fate of the message. 🔍 A node may receive the same message several times, so to avoid re-processing stuff it already handled, each node keeps a Duplicate Set. In this set, the node records information about the most recently received messages where duplicate processing of a message is to be avoided. For such a message, a node records a "Duplicate Tuple" (D_addr, D_seq_num, D_retransmitted, D_iface_list, D_time), where:
- D_addr is the originator address of the message,
- D_seq_num is the message sequence number of the message,
- D_retransmitted is a boolean indicating whether the message has been already retransmitted,
- D_iface_list is a list of the addresses of the interfaces on which the message has been received, and
- D_time specifies the time at which a tuple expires and MUST be removed.
In a node, the set of Duplicate Tuples are denoted the "Duplicate set". 📚
In this section, the term "Originator Address" will be used for the main address of the node which sent the message. The term "Sender Interface Address" will be used for the sender address (given in the IP header of the packet containing the message) of the interface which sent the message. The term "Receiving Interface Address" will be used for the address of the interface of the node which received the message. 🏷️
So, upon receiving a basic packet, a node MUST perform the following tasks for each encapsulated message:
- Step 1. If the packet contains no messages (i.e., the Packet Length is less than or equal to the size of the packet header), the packet MUST silently be discarded.
For IPv4 addresses, this implies that packets, where the Packet Length < 16 MUST silently be discarded.
- Step 2. If the time to live of the message is less than or equal to
'0'(zero), or if the message was sent by the receiving node (i.e., the Originator Address of the message is the main address of the receiving node): the message MUST silently be dropped. 🙅♀️ - Step 3. Processing condition:
3.1 If there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND
D_seq_num == Message Sequence Numberthen the message has already been completely processed and MUST not be processed again. ✅
3.2 Otherwise, if the node implements the Message Type of the message, the message MUST be processed according to the specifications for the message type. ⚙️
- Step 4. Forwarding condition:
4.1 If there exists a tuple in the duplicate set, where:
D_addr == Originator Address, AND
D_seq_num == Message Sequence Number,
AND
the receiving interface (address) is
in D_iface_listthen the message has already been considered for forwarding and SHOULD NOT be retransmitted again. 🔁
4.2 Otherwise:
4.2.1 If the node implements the Message Type of the message, the message MUST be considered for forwarding according to the specifications for the message type. 📨
4.2.2 Otherwise, if the node does not implement the Message Type of the message, the message SHOULD be processed according to the default forwarding algorithm described below. 🧚
3.4.1. Default Forwarding Algorithm 💅
okay so this is the default forwarding algorithm, bestie 🎀 think of it as a checklist your node runs on every incoming message. If you fail a step, you stop. If you pass, you keep going ✨
1. If the sender interface address of the message is not detected to be in the symmetric 1-hop neighborhood of the node, the forwarding algorithm MUST silently stop here (and the message MUST NOT be forwarded). 🙈
2. If there exists a tuple in the duplicate set where:
D_addr == Originator Address
D_seq_num == Message Sequence NumberThen the message will be further considered for forwarding if and only if:
D_retransmitted is false, AND
the (address of the) interface which received the message
is not included among the addresses in D_iface_list3. Otherwise, if such an entry doesn't exist, the message is further considered for forwarding. 🦋
If after those steps the message is not considered for forwarding, then the processing of this section stops (so steps 4 to 8 get skipped 🙃). Otherwise, if it's still in the running, the following algorithm kicks in 🔥
4. If the sender interface address is an interface address of a MPR selector of this node and the time to live of the message is greater than 1, the message MUST be retransmitted (as described later in steps 6 to 8). 👑
5. If an entry in the duplicate set exists, with same Originator Address, and same Message Sequence Number, the entry is updated as follows:
D_time = current time + DUP_HOLD_TIME.
The receiving interface (address) is added to
D_iface_list.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.Otherwise an entry in the duplicate set is recorded with:
D_addr = Originator Address
D_seq_num = Message Sequence Number
D_time = current time + DUP_HOLD_TIME.
D_iface_list contains the receiving interface address.
D_retransmitted is set to true if and only if the message
will be retransmitted according to step 4.If, and only if, according to step 4, the message must be retransmitted then:
6. The TTL of the message is reduced by one. ⏳
7. The hop-count of the message is increased by one
8. The message is broadcast on all interfaces (Notice: The remaining fields of the message header SHOULD be left unmodified.) 📣
3.4.2. Considerations on Processing and Forwarding 🧠
bestie, processing and forwarding are NOT the same thing 😤 Processing is about using what's inside the message. Forwarding is about passing the same message along to other nodes in the network. Two different actions, two different sets of rules 💖
Heads up, this spec describes both forwarding and processing for every known message type. Messages with known message types MUST NOT be forwarded "blindly" by this algorithm 🚫 Forwarding (plus setting the right message header on the forwarded, known, message) is the job of whatever algorithm says how that message type gets handled and, if needed, retransmitted. This is what lets a message type get changed while it's in transit (for example, to record the route it took) 🛤️ It also means you can bypass MPR flooding if some message type really needs classic flooding. The handling algorithm for that type just rebroadcasts the message, MPRs or no MPRs 🌸
By defining a set of message types that MUST be recognized by all implementations of OLSR, the protocol can grow with new message types and still play nicely with older implementations 🧚 The REQUIRED message types for OLSR's core functionality are:
HELLO-messages, which handle link sensing, neighbor detection and MPR signalingTC-messages, which handle topology declaration (advertising link states)MID-messages, which declare that a node has multiple interfaces
Other message types include the ones in later sections, plus possible future extras like power conservation / sleep mode, multicast routing, support for unidirectional links, and auto-configuration / address assignment etc. ✨
3.5. Message Emission and Jitter 🦋
as a basic implementation requirement, synchronization of control messages SHOULD be avoided 🙅♀️ So OLSR control messages SHOULD be emitted in a way that avoids synchronization.
Why does this matter? Neighboring nodes can end up with their timers lining up (mostly because of how timers and packet processing interact) so several of them try to transmit control traffic at the exact same moment 😭 Depending on the link layer, that might cause collisions and lost messages, possibly several in a row of the same type 💀
To dodge that drama, here's a simple strategy for emitting control messages. A node SHOULD add some jitter to the interval at which it generates messages 🎲 The jitter must be a random value for each message generated. So for a node using jitter:
Actual message interval = MESSAGE_INTERVAL - jitterWhere jitter is a value randomly picked from the interval [0,MAXJITTER], and MESSAGE_INTERVAL is the message interval for the message being emitted (for example HELLO_INTERVAL for HELLO messages, TC_INTERVAL for TC-messages, etc.) 🌈
Jitter SHOULD also show up when forwarding messages 🏃♀️ One simple approach: when a node is about to forward a message, it holds onto it for a short while:
Keep message period = jitterWhere jitter is a random value in [0,MAXJITTER].
Also, when the node sends a control message, that's a chance to piggyback other messages (as long as their keeping period hasn't expired yet) 🎀 That can cut down on how many packet transmissions happen 💅
And one more thing: a minimal rate of control messages is imposed. A node MAY send control messages at a higher rate if that's beneficial for a specific deployment 🚀
4. Information Repositories 📚
okay so through the exchange of OLSR control messages, each node builds up info about the network 🕸️ This info gets stored in the repositories described in this section. Think of them as the node's notebooks 📓
4.1. Multiple Interface Association Information Base 🪪
For each destination in the network, "Interface Association Tuples" (I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an interface address of a node, and I_main_addr is the main address of this node. I_time is the time at which this tuple expires and it MUST be removed. 🗑️
In a node, the set of Interface Association Tuples is called the "Interface Association Set" 💖
4.2. Link Sensing: Local Link Information Base 🔗
The local link information base stores info about links to neighbors. Spill ✨
4.2.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_time). L_local_iface_addr is the interface address of the local node (one endpoint of the link). L_neighbor_iface_addr is the interface address of the neighbor node (the other endpoint). 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. And L_time is the time at which this record expires and it MUST be removed. When both L_SYM_time and L_ASYM_time have expired, the link is considered lost 💀
This info is used when declaring the neighbor interfaces in HELLO messages 📣
L_SYM_time decides the Link Type declared for the neighbor interface:
- If
L_SYM_timeis not expired, the link MUST be declared symmetric. - If
L_SYM_timeis expired, the link MUST be declared asymmetric. - If both
L_SYM_timeandL_ASYM_timeare expired, the link MUST be declared lost.
In a node, the set of Link Tuples is called the "Link Set" 🧠
4.3. Neighbor Detection: Neighborhood Information Base 👯♀️
The neighborhood information base stores info about neighbors, 2-hop neighbors, MPRs and MPR selectors 💜
4.3.1. Neighbor Set 🫶
A node records a set of "neighbor tuples" (N_neighbor_main_addr, N_status, N_willingness), describing neighbors. N_neighbor_main_addr is the main address of a neighbor. N_status specifies if the node is NOT_SYM or SYM. N_willingness in an integer between 0 and 7, and specifies the node's willingness to carry traffic on behalf of other nodes 🍓
4.3.2. 2-hop Neighbor Set 🌈
A node records a set of "2-hop tuples" (N_neighbor_main_addr, N_2hop_addr, N_time), describing symmetric links between its neighbors and the symmetric 2-hop neighborhood. Since MPR links are symmetric by definition, these are also MPR links 👑 N_neighbor_main_addr is the main address of a neighbor. N_2hop_addr is the main address of a 2-hop neighbor with a symmetric link to N_neighbor_main_addr. N_time is the time at which the tuple expires and it MUST be removed.
In a node, the set of 2-hop tuples is called the "2-hop Neighbor Set" ✨
4.3.3. MPR Set 🎀
A node maintains a set of neighbors that were selected as MPR. Their main addresses are listed in the MPR Set 💅
4.3.4. MPR Selector Set 🦋
A node records a set of MPR-selector tuples (MS_main_addr, MS_time), describing the neighbors that have selected this node as an MPR. MS_main_addr is the main address of a node that has selected this node as MPR. MS_time is the time at which the tuple expires and it MUST be removed. ⏰
In a node, the set of MPR-selector tuples is called the "MPR Selector Set" 🌸
4.4. Topology Information Base 🗺️
Each node in the network keeps topology info about the network 🧭 This info comes from TC-messages and gets used for routing table calculations.
So for each destination in the network, at least one "Topology Tuple" (T_dest_addr, T_last_addr, T_seq, T_time) is recorded. T_dest_addr is the main address of a node that may be reached in one hop from the node with the main address T_last_addr. Typically, T_last_addr is an MPR of T_dest_addr. T_seq is a sequence number, and T_time is the time at which this tuple expires and it MUST be removed. 💫
In a node, the set of Topology Tuples is called the "Topology Set" 👑
5. Main Addresses and Multiple Interfaces 💖
okay so for single OLSR interface nodes it's super simple 🫶 the relationship between an OLSR interface address and the main address is trivial: the main address is the OLSR interface address, no drama. but for multiple OLSR interface nodes, the link between interface addresses and main addresses gets set up through the exchange of Multiple Interface Declaration (MID) messages. this section is all about how those MID messages get exchanged and processed 🦋
each node with multiple interfaces MUST announce its interface configuration to other nodes in the network, periodically 📣 this happens by flooding a Multiple Interface Declaration message to every node in the network through the MPR flooding mechanism ✨
every node also keeps interface info about the other nodes in the network. that info comes from MID messages sent by the multi-interface nodes participating in the MANET, and it's what gets used for routing table calculations 🗺️
basically, multiple interface declaration associates multiple interfaces with a node (and its main address) by filling up the multiple interface association base in each node 💅
5.1. MID Message Format 🎀
the proposed format of a MID message looks like this:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OLSR Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+this gets sent as the data-portion of the general packet format from section 3.4, with the "Message Type" set to MID_MESSAGE. the time to live SHOULD be set to 255 (maximum value) so the message diffuses into the entire network, and Vtime gets set accordingly to the value of MID_HOLD_TIME, as specified in section 18.3 🌈
OLSR Interface Address 🫧 this field contains the address of an OLSR interface of the node, excluding the node's main address (which is already indicated in the originator address).
all interface addresses other than the main address of the originator node go into the MID message. if the maximum allowed message size (as imposed by the network) gets reached while there are still interface addresses that haven't been inserted into the MID message, more MID messages get generated until the entire interface addresses set has been sent 📦
5.2. MID Message Generation 🍓
a MID message is sent by a node in the network to declare its multiple interfaces (if any). so basically, the MID message contains the list of interface addresses associated with its main address. the list can be partial in each MID message (for example because of message size limitations imposed by the network), but parsing all the MID messages describing a node's interface set MUST be complete within a certain refreshing period (MID_INTERVAL). the info these MID messages spread around is what helps each node calculate its routing table 🧠
a node that has only a single interface address participating in the MANET (i.e., running OLSR) MUST NOT generate any MID message 🙅♀️
a node with several interfaces, where only one is participating in the MANET and running OLSR (e.g., a node connected to a wired network as well as to a MANET), MUST NOT generate any MID messages 🙅♀️
a node with several interfaces, where more than one is participating in the MANET and running OLSR, MUST generate MID messages as specified 🔥
5.3. MID Message Forwarding 🦋
MID messages are broadcast and retransmitted by the MPRs so the messages diffuse through the entire network 📡 the "default forwarding algorithm" (described in section 3.4) MUST be used for forwarding MID messages 💖
5.4. MID Message Processing ✨
the tuples in the multiple interface association set get recorded with the info exchanged through MID messages.
when a node receives a MID message, the "validity time" MUST be computed from the Vtime field of the message header (as described in section 3.3.2). after that, the Multiple Interface Association Information Base SHOULD be updated as follows 🫶
- if the sender interface (NB: not originator) of this message is not in the symmetric 1-hop neighborhood of this node, the message MUST be discarded 🗑️
- for each interface address listed in the MID message:
2.1 if there exists some tuple in the interface association set where:
I_iface_addr == interface address, AND
I_main_addr == originator address,then the holding time of that tuple is set to:
I_time = current time + validity time.2.2 otherwise, a new tuple is recorded in the interface association set where:
I_iface_addr = interface address,
I_main_addr = originator address,
I_time = current time + validity time.5.5. Resolving a Main Address from an Interface Address 🔍
okay so generally, the only part of OLSR that needs "interface addresses" is link sensing. everything else in OLSR works on nodes, which are uniquely identified by their "main addresses" 👑 (effectively, the main address of a node is its "node id", which for convenience corresponds to the address of one of its interfaces). in a network with only single interface nodes, a node's main address will, by definition, be equal to its interface address. but in networks with multiple interface nodes operating within a common OLSR area, it's required to be able to map any interface address to the corresponding main address, and that's the part that makes this section so iconic 🌸
the exchange of MID messages is how nodes in the network acquire interface information. that's what lets someone figure out a node's "main address" when they only have one of its interface addresses 🧚
given an interface address:
- if there exists some tuple in the interface association set where:
I_iface_addr == interface addressthen the result of the main address search is the originator address I_main_addr of that tuple.
- otherwise, the result of the main address search is the interface address itself.
6. HELLO Message Format and Generation 🎀
a common mechanism is used to fill up both the local link information base and the neighborhood information base: periodic exchange of HELLO messages 💬 so this section describes the general HELLO message mechanism first, then link sensing and topology detection, respectively 🫶
6.1. HELLO Message Format 🌈
to support link sensing, neighborhood detection and MPR selection signalling, and to leave room for future extensions, the format takes an approach similar to the overall packet format. so the proposed format of a HELLO message looks like this 🦋
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved | Htime | Willingness |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: . . . :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Link Code | Reserved | Link Message Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor Interface Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
: :
(etc.)this gets sent as the data-portion of the general packet format from section 3.4, with the "Message Type" set to HELLO_MESSAGE, the TTL field set to 1 (one), and Vtime set accordingly to the value of NEIGHB_HOLD_TIME, specified in section 18.3 ⏱️
Reserved 🫧 this field must be set to "0000000000000" to be in compliance with this specification.
HTime ⏳ this field specifies the HELLO emission interval used by the node on this particular interface, i.e., the time before the transmission of the next HELLO. (this info may be used in advanced link sensing, see section 14.) the HELLO emission interval is represented by its mantissa (the four highest bits of the Htime field) and by its exponent (the four lowest bits of the Htime field). in other words:
HELLO emission interval=C*(1+a/16)*2^b [in seconds]where a is the integer represented by the four highest bits of the Htime field and b the integer represented by the four lowest bits of the Htime field. the proposed value of the scaling factor C is specified in section 18 ✨
Willingness 💅 this field specifies the willingness of a node to carry and forward traffic for other nodes.
a node with willingness WILL_NEVER (see section 18.8, for willingness constants) MUST never be selected as MPR by any node 🚫 a node with willingness WILL_ALWAYS MUST always be selected as MPR 👑 by default, a node SHOULD advertise a willingness of WILL_DEFAULT 🌸
Link Code 🔗 this field specifies info about the link between the interface of the sender and the following list of neighbor interfaces. it also specifies info about the status of the neighbor.
link codes that a node doesn't know are silently discarded 🤫
Link Message Size 📏 the size of the link message, counted in bytes and measured from the beginning of the "Link Code" field until the next "Link Code" field (or, if there are no more link types, the end of the message).
Neighbor Interface Address 🏡 the address of an interface of a neighbor node.
6.1.1. Link Code as Link Type and Neighbor Type ✨
okay so this doc only specifies processing for Link Codes < 16 🎀 anything bigger is not covered here, bestie.
If the Link Code value is less than or equal to 15, then it MUST be interpreted as holding two different fields, two bits each 💅
7 6 5 4 3 2 1 0
+-------+-------+-------+-------+-------+-------+-------+-------+
| 0 | 0 | 0 | 0 | Neighbor Type | Link Type |
+-------+-------+-------+-------+-------+-------+-------+-------+The following four Link Types are REQUIRED by OLSR 🦋
UNSPEC_LINKmeans no specific info about the links is given.ASYM_LINKmeans the links are asymmetric, so the neighbor interface is "heard" 👂SYM_LINKmeans the links are symmetric with the interface 🫶LOST_LINKmeans the links have been lost 😭
The following three Neighbor Types are REQUIRED by OLSR 🌸
SYM_NEIGHmeans the neighbors have at least one symmetrical link with this node.MPR_NEIGHmeans the neighbors have at least one symmetrical link AND have been selected as MPR by the sender 👑NOT_NEIGHmeans the nodes are either no longer symmetric neighbors, or have not yet become symmetric neighbors 🙈
Be so careful, bestie, not to mix up Link Type with Neighbor Type, or the constants either. SYM_NEIGH and SYM_LINK look like twins but they are NOT the same thing 💀
A link code advertising this combo is invalid 🚫
Link Type == SYM_LINK AND
Neighbor Type == NOT_NEIGHAny links advertised like that MUST be silently discarded without any processing. Same vibe for a Neighbor Type field with a numerical value that isn't SYM_NEIGH, MPR_NEIGH or NOT_NEIGH. It's invalid too, and those links MUST be silently discarded without any processing 🗑️
6.2. HELLO Message Generation 📣
This involves transmitting the Link Set, the Neighbor Set and the MPR Set. In principle, a HELLO message has three independent jobs 🧚
- link sensing
- neighbor detection
- MPR selection signaling
All three are based on periodic info exchange within a node's neighborhood, and they all serve the same purpose of "local topology discovery" 🔍 So a HELLO message is generated from the info stored in the Local Link Set, the Neighbor Set and the MPR Set from the local link information base.
A node must perform link sensing on each interface, so it can detect links between that interface and neighbor interfaces. A node must also advertise its entire symmetric 1-hop neighborhood on each interface to do neighbor detection ✨ So for a given interface, a HELLO message contains a list of links on that interface (with their link types), plus the whole neighborhood (with their neighbor types) 💖
The Vtime field is set to match the node's NEIGHB_HOLD_TIME parameter. The Htime field is set to match the node's HELLO_INTERVAL parameter (see section 18.3) ⏰
The Willingness field is set to match the node's willingness to forward traffic for other nodes (see section 18.8). A node MUST advertise the same willingness on all interfaces 🎀
The address lists in a HELLO message are lists of neighbor interface addresses, computed like this 🧮
For each tuple in the Link Set, where L_local_iface_addr is the interface where the HELLO is to be transmitted, and where L_time >= current time (so not expired), L_neighbor_iface_addr is advertised with:
- The Link Type set according to the following:
- 1.1 if
L_SYM_time >= current time (not expired), thenLink Type = SYM_LINK - 1.2 Otherwise, if
L_ASYM_time >= current time (not expired)ANDL_SYM_time < current time (expired), thenLink Type = ASYM_LINK - 1.3 Otherwise, if
L_ASYM_time < current time (expired)ANDL_SYM_time < current time (expired), thenLink Type = LOST_LINK
- 1.1 if
- The Neighbor Type is set according to the following:
- 2.1 If the main address, corresponding to
L_neighbor_iface_addr, is included in the MPR set, thenNeighbor Type = MPR_NEIGH - 2.2 Otherwise, if the main address, corresponding to
L_neighbor_iface_addr, is included in the neighbor set:- 2.2.1 if
N_status == SYM, thenNeighbor Type = SYM_NEIGH - 2.2.2 Otherwise, if
N_status == NOT_SYM, thenNeighbor Type = NOT_NEIGH
- 2.2.1 if
- 2.1 If the main address, corresponding to
For each tuple in the Neighbor Set where no L_neighbor_iface_addr from an associated link tuple has been advertised by the previous algorithm, N_neighbor_main_addr is advertised with:
Link Type = UNSPEC_LINK- Neighbor Type set as described in step 2 above
For a node with a single OLSR interface, the main address is just the address of that OLSR interface. So the main address corresponding to L_neighbor_iface_addr is simply L_neighbor_iface_addr 🥰
A HELLO message can be partial (for example, because of message size limits imposed by the network) 📏 The rule is this, on each interface: each link and each neighbor node MUST be cited at least once within a predetermined refreshing period, REFRESH_INTERVAL. To keep up with fast connectivity changes, a HELLO message must be sent at least every HELLO_INTERVAL period, which has to be smaller than or equal to REFRESH_INTERVAL 🏃♀️
Also, to limit the damage from losing control messages, it's desirable that a message (plus the generic packet header) fits into a single MAC frame 📦 very important, bestie!
6.3. HELLO Message Forwarding 📡
Each HELLO message generated is broadcast by the node on one interface to its neighbors, meaning the interface it was generated for 📢 HELLO messages MUST never be forwarded. Not even a little 🙅♀️
6.4. HELLO Message Processing 📥
A node processes incoming HELLO messages for three reasons: link sensing (detailed in section 7), neighbor detection, and MPR selector set population (detailed in section 8) 💅
7. Link Sensing 🔗
Link sensing fills up the local link information base 🧠 It's only concerned with OLSR interface addresses and whether packets can actually be exchanged between those OLSR interfaces.
The mechanism for link sensing is the periodic exchange of HELLO messages 🔁
7.1. Populating the Link Set 🌈
The Link Set holds info on links to neighbor nodes. The process of filling this set is called "link sensing", and it's done with HELLO message exchange, which updates a local link information base in each node 📝
Each node should detect the links between itself and its neighbor nodes 🔎 Radio propagation can be sketchy, so some links might only work one way. That's why all links MUST be checked in both directions before they count as valid ✅
A "link" is described by a pair of interfaces: a local one and a remote one 👯
For link sensing, each neighbor node (or really, the link to each neighbor) has a status of either "symmetric" or "asymmetric" 🪞 "Symmetric" means the link to that neighbor has been verified to be bi-directional, so data can go both ways. "Asymmetric" means HELLO messages from the node have been heard, so communication from the neighbor is possible, but it's not confirmed that this node can receive messages back 👀
Whatever link sensing learns is stored in the link set 💾
7.1.1. HELLO Message Processing 💌
The "Originator Address" of a HELLO message is the main address of the node that emitted it 🙋♀️
When a node receives a HELLO message, it SHOULD update its Link Set. Also, a HELLO message MUST neither be forwarded nor recorded in the duplicate set. Not allowed, periodt 🚫
When a HELLO message comes in, the "validity time" MUST be computed from the Vtime field of the message header (see section 3.3.2). Then the Link Set SHOULD be updated like this 🧩
- When a HELLO message arrives and there is no link tuple with
L_neighbor_iface_addr == Source Address, a new tuple is created with:L_neighbor_iface_addr = Source AddressL_local_iface_addr = Address of the interface which received the HELLO messageL_SYM_time = current time - 1 (expired)L_time = current time + validity time
- The tuple (existing or new) with
L_neighbor_iface_addr == Source Addressis then modified as follows:- 2.1
L_ASYM_time = current time + validity time; - 2.2 if the node finds the address of the interface which received the HELLO message among the addresses listed in the link message, then the tuple is modified as follows:
- 2.2.1 if Link Type is equal to
LOST_LINK, thenL_SYM_time = current time - 1(i.e., expired) - 2.2.2 else if Link Type is equal to
SYM_LINKorASYM_LINK, thenL_SYM_time = current time + validity time, andL_time = L_SYM_time + NEIGHB_HOLD_TIME
- 2.2.1 if Link Type is equal to
- 2.3
L_time = max(L_time, L_ASYM_time)
- 2.1
Here's the reason for the rule on setting L_time: a link that loses its symmetry SHOULD still be advertised for at least the duration of the "validity time" advertised in the generated HELLO 🕰️ That way neighbors can notice the link broke 💔
8. Neighbor Detection 🏡
Neighbor detection fills up the neighborhood information base, and it's all about nodes and node main addresses 🧑🤝🧑 The relationship between OLSR interface addresses and main addresses is explained in section 5 🎀
The mechanism for neighbor detection is also the periodic exchange of HELLO messages 🔁✨
8.1. Populating the Neighbor Set ✨
okay so a node keeps a set of neighbor tuples that's built from its link tuples, and it updates that set whenever the Link Set changes 🦋
the Link Set keeps the info about links, the Neighbor Set keeps the info about neighbors, and they're literally besties. a node is a neighbor of another node if and only if there's at least one link between the two 💖
here's the formal matchup, bestie 🎀
The "associated neighbor tuple" of a link tuple, is, if it
exists, the neighbor tuple where:
N_neighbor_main_addr == main address of
L_neighbor_iface_addr
The "associated link tuples" of a neighbor tuple, are all the
link tuples, where:
N_neighbor_main_addr == main address of
L_neighbor_iface_addrThe Neighbor Set MUST be populated by keeping the right correspondence between link tuples and associated neighbor tuples, and it works like this 💅
Creation
Each time a link appears (so each time a link tuple is created), the associated neighbor tuple MUST be created if it doesn't already exist yet, with these values:
N_neighbor_main_addr = main address of
L_neighbor_iface_addr
(from the link tuple)In any case, the N_status MUST then be computed as described in the next step ✨
Update
Each time a link changes (so each time the info in a link tuple is modified), the node MUST make sure that the N_status of the associated neighbor tuple respects this property 🔥
If the neighbor has any associated link tuple which
indicates a symmetric link (i.e., with L_SYM_time >=
current time), then
N_status is set to SYM
else N_status is set to NOT_SYMRemoval
Each time a link is deleted (so each time a link tuple is removed), the associated neighbor tuple MUST be removed if it no longer has any associated link tuples 🙈
these rules make sure there's exactly one associated neighbor tuple for each link tuple, and that every neighbor tuple has at least one associated link tuple. iykyk, it's giving consistency 👑
8.1.1. HELLO Message Processing 🌸
the "Originator Address" of a HELLO message is the main address of the node that emitted it. and the "willingness" MUST be computed from the Willingness field of the HELLO message (see section 6.1) 💜
when a node gets a HELLO message, it SHOULD first update its Link Set like we talked about. then it SHOULD update its Neighbor Set like this:
- if the Originator Address is the
N_neighbor_main_addrfrom a neighbor tuple included in the Neighbor Set:- then, the neighbor tuple SHOULD be updated as follows:
N_willingness = willingness from the HELLO message8.2. Populating the 2-hop Neighbor Set 🦋
the 2-hop neighbor set describes the set of nodes that have a symmetric link to a symmetric neighbor. this info is kept up to date through periodic HELLO exchanges, as explained in this section 🌈
8.2.1. HELLO Message Processing 💅
the "Originator Address" of a HELLO message is the main address of the node that emitted it.
when a node gets a HELLO message from a symmetric neighbor, it SHOULD update its 2-hop Neighbor Set. and notice, a HELLO message MUST neither be forwarded nor be recorded in the duplicate set. not me forgetting this one 🙈
when a HELLO message comes in, the "validity time" MUST be computed from the Vtime field of the message header (see section 3.3.2) ✨
if the Originator Address is the main address of an L_neighbor_iface_addr from a link tuple in the Link Set with this condition:
L_SYM_time >= current time (not expired)(in other words: if the Originator Address is a symmetric neighbor), then the 2-hop Neighbor Set SHOULD be updated like this:
- For each address (henceforth: 2-hop neighbor address) listed in the HELLO message with Neighbor Type equal to
SYM_NEIGHorMPR_NEIGH:- 1.1 If the main address of the 2-hop neighbor address = main address of the receiving node: silently discard the 2-hop neighbor address. (in other words: a node is not its own 2-hop neighbor 🎀)
- 1.2 Otherwise, a 2-hop tuple is created with:
N_neighbor_main_addr = Originator Address;
N_2hop_addr = main address of the
2-hop neighbor;
N_time = current time
+ validity time.This tuple may replace an older similar tuple with the same N_neighbor_main_addr and N_2hop_addr values.
- For each 2-hop node listed in the HELLO message with Neighbor Type equal to
NOT_NEIGH, all 2-hop tuples where this is true get deleted:
N_neighbor_main_addr == Originator Address AND
N_2hop_addr == main address of the
2-hop neighbor8.3. Populating the MPR set 🧚
MPRs are used to flood control messages from a node into the network while cutting down the number of retransmissions that happen in a region. so the MPR idea is basically an optimized version of classic flooding. it's giving efficiency 💖
each node in the network picks its own set of MPRs, independently, from its symmetric 1-hop neighborhood. the symmetric links that have MPRs get advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in HELLO messages 🌸
the MPR set MUST be calculated by a node in a way that, through the neighbors in the MPR set, it can reach all symmetric strict 2-hop neighbors. (notice that a node, a, which is a direct neighbor of another node, b, is not also a strict 2-hop neighbor of node b). this means the union of the symmetric 1-hop neighborhoods of the MPR nodes contains the symmetric strict 2-hop neighborhood. the MPR set should be recalculated when changes are detected in the symmetric neighborhood or in the symmetric strict 2-hop neighborhood 🔥
MPRs are computed per interface, and the union of the MPR sets of each interface makes up the MPR set for the node 👑
it's not essential that the MPR set is minimal, but it's essential that all strict 2-hop neighbors can be reached through the selected MPR nodes. a node SHOULD select an MPR set so that any strict 2-hop neighbor is covered by at least one MPR node. keeping the MPR set small keeps the protocol overhead at a minimum, so that's the goal 🦋
the MPR set can coincide with the entire symmetric neighbor set. this could be the case at network initialization, and it will correspond to classic link-state routing ✨
8.3.1. MPR Computation 💜
the following describes a proposed heuristic for picking MPRs. it builds an MPR set that lets a node reach any node in the symmetric strict 2-hop neighborhood by relaying through one MPR node whose willingness is different from WILL_NEVER. the heuristic MUST be applied per interface, I. the MPR set for a node is the union of the MPR sets found for each interface. here's the terminology we'll use 🎀
- neighbor of an interface: a node is a "neighbor of an interface" if the interface (on the local node) has a link to any one interface of the neighbor node.
- 2-hop neighbors reachable from an interface: the list of 2-hop neighbors of the node that can be reached from neighbors of this interface.
- MPR set of an interface: a (sub)set of the neighbors of an interface with a willingness different from
WILL_NEVER, selected so that through these selected nodes, all strict 2-hop neighbors reachable from that interface are reachable. - N: N is the subset of neighbors of the node that are neighbors of the interface I.
- N2: the set of 2-hop neighbors reachable from the interface I, excluding:
- (i) the nodes only reachable by members of N with willingness
WILL_NEVER - (ii) the node performing the computation
- (iii) all the symmetric neighbors: the nodes for which there exists a symmetric link to this node on some interface.
- (i) the nodes only reachable by members of N with willingness
- D(y): the degree of a 1-hop neighbor node y (where y is a member of N). it's defined as the number of symmetric neighbors of node y, EXCLUDING all the members of N and EXCLUDING the node performing the computation.
the proposed heuristic goes like this 💅
- Start with an MPR set made of all members of N with
N_willingnessequal toWILL_ALWAYS. - Calculate D(y), where y is a member of N, for all nodes in N.
- Add to the MPR set those nodes in N that are the only nodes providing reachability to a node in N2. for example, if node b in N2 can be reached only through a symmetric link to node a in N, then add node a to the MPR set. remove the nodes from N2 that are now covered by a node in the MPR set.
- While there exist nodes in N2 that are not covered by at least one node in the MPR set:
- 4.1 For each node in N, calculate the reachability, i.e., the number of nodes in N2 that are not yet covered by at least one node in the MPR set and that are reachable through this 1-hop neighbor.
- 4.2 Select as an MPR the node with the highest
N_willingnessamong the nodes in N with non-zero reachability. if there's a tie, select the node that provides reachability to the maximum number of nodes in N2. if there are still multiple nodes providing the same amount of reachability, select the node as MPR whose D(y) is greater. remove the nodes from N2 that are now covered by a node in the MPR set.
- A node's MPR set is generated from the union of the MPR sets for each interface. as an optimization, process each node, y, in the MPR set in increasing order of
N_willingness. if all nodes in N2 are still covered by at least one node in the MPR set excluding node y, and if theN_willingnessof node y is smaller thanWILL_ALWAYS, then node y MAY be removed from the MPR set.
other algorithms, plus improvements over this one, are possible. for example, say that in a multiple-interface scenario there's more 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 selected as MPR without additional performance loss by any other interfaces on node 'a' 🌈
8.4. Populating the MPR Selector Set 🫶
the MPR selector set of a node, n, is filled with the main addresses of the nodes that have selected n as MPR. MPR selection gets signaled through HELLO messages 💜
8.4.1. HELLO Message Processing 🎀
Okay bestie, so when a HELLO message lands, the node checks if it can spot one of its own interface addresses in the list with a Neighbor Type equal to MPR_NEIGH. If it does, the info from that HELLO must be recorded in the MPR Selector Set. Main character energy ✨
The "validity time" MUST be computed from the Vtime field of the message header (see section 3.3.2). Then the MPR Selector Set SHOULD be updated like this 💅
Step 1 🌸: If there's no MPR selector tuple with:
MS_main_addr == Originator Addressthen a new tuple gets created with:
MS_main_addr = Originator AddressStep 2 🦋: The tuple (new or otherwise) with:
MS_main_addr == Originator Addressthen gets modified like this:
MS_time = current time + validity time.Deleting MPR selector tuples happens when the timer expires, or when a link breaks, as described in the "Neighborhood and 2-hop Neighborhood Changes" part. It's giving tidy housekeeping 🧹💖
8.5. Neighborhood and 2-hop Neighborhood Changes ✨
Okay so a change in the neighborhood gets detected when:
- The L_SYM_time field of a link tuple expires. This counts as a neighbor loss if the link in that expired tuple was the last link with a neighbor node. (On the other hand, a link with one interface might break while a link with another interface of that neighbor node stays up, and that's not seen as a neighborhood change 🙈)
- A new link tuple gets inserted in the Link Set with a non expired L_SYM_time, or a tuple with an expired L_SYM_time gets modified so that L_SYM_time becomes non-expired. This counts as a neighbor appearance if there was no link tuple before that described a link with the matching neighbor node. New friend unlocked! 🧚
A change in the 2-hop neighborhood gets detected when a 2-hop neighbor tuple expires or is deleted, according to section 8.2. 🫶
When a change in the neighborhood or the 2-hop neighborhood gets detected, this processing happens:
- If there's a neighbor loss, all 2-hop tuples with N_neighbor_main_addr == Main Address of the neighbor MUST be deleted. 💀
- If there's a neighbor loss, all MPR selector tuples with MS_main_addr == Main Address of the neighbor MUST be deleted.
- The MPR set MUST be re-calculated when a neighbor appearance or loss is detected, or when a change in the 2-hop neighborhood is detected. Recalc time 🔥
- An additional HELLO message MAY be sent when the MPR set changes. Extra hellos are optional, bestie 🌈
9. Topology Discovery 🦋
So the link sensing and neighbor detection part of the protocol basically gives each node a list of neighbors it can talk to directly. Combine that with the Packet Format and Forwarding part, and you get an optimized flooding mechanism through MPRs ✨ Based on that, topology info gets spread through the whole network. This section covers which bits of the link sensing and neighbor detection info get shared with the entire network, and how that info gets used to build routes. It's literally the plot twist 😭
Routes are built through advertised links and links with neighbors. A node must at least disseminate links between itself and the nodes in its MPR-selector set, so there's enough info to make routing work. 🛣️💅
9.1. TC Message Format 🎀
The proposed format of a TC message looks like this:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ANSN | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised Neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Advertised Neighbor Main Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+This gets sent as the data portion of the general message format, with the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set to 255 (maximum value) so the message spreads through the entire network. Vtime gets set to match the value of TOP_HOLD_TIME, as specified in section 18.3. 🌍
Advertised Neighbor Sequence Number (ANSN) 🔢
A sequence number is tied to the advertised neighbor set. Every time a node notices a change in its advertised neighbor set, it increments this number ("Wraparound" is handled as described in section 19). This number goes in the ANSN field of the TC message, so everyone can tell what's the most recent info. When a node gets a TC message, it can use this ANSN to decide whether the info about the originator's advertised neighbors is more recent than what it already has. Lowkey the best tracking system ever 📈
Advertised Neighbor Main Address 🏠
This field holds the main address of a neighbor node. All the main addresses of the Originator's advertised neighbors go in the TC message. If the maximum allowed message size (as imposed by the network) is hit while there are still advertised neighbor addresses that haven't been put into the TC message, more TC messages get generated until the whole advertised neighbor set has been sent. Extra main addresses of neighbor nodes may be included if redundancy is wanted. 🧩
Reserved 🚫
This field is reserved, and MUST be set to "0000000000000000" for compliance with this document. 🙅♀️
9.2. Advertised Neighbor Set 💖
A TC message is sent by a node in the network to declare a set of links, called the advertised link set. This set MUST include at least the links to all nodes in its MPR Selector set, which means the neighbors that picked the sender node as an MPR. Essential. No skipping 🫶
If, for some reason, you need to distribute redundant TC information, check out section 15. 🔁
The sequence number (ANSN) tied to the advertised neighbor set gets sent along with the list. The ANSN number MUST be incremented when links are removed from the advertised neighbor set. The ANSN number SHOULD be incremented when links are added to the advertised neighbor set. ⬆️
9.3. TC Message Generation 🌸
To build the topology information base, every node that has been selected as an MPR broadcasts Topology Control (TC) messages. TC messages get flooded to all nodes in the network and take advantage of MPRs. MPRs make the distribution of topology info way more scalable [1]. Iconic behaviour 👑
The list of addresses can be partial in each TC message (for example, because of message size limits imposed by the network). Parsing all the TC messages that describe a node's advertised link set MUST be complete within a certain refreshing period (TC_INTERVAL). The info spread by these TC messages helps each node calculate its routing table. 🗺️
When a node's advertised link set becomes empty, that node SHOULD still send (empty) TC messages for a duration equal to the "validity time" of its previously emitted TC messages (usually this will be TOP_HOLD_TIME). This invalidates the earlier TC messages. After that, it SHOULD stop sending TC messages until some node gets inserted into its advertised link set. Bye for now, empty set 👋
A node MAY transmit additional TC messages to be more reactive to link failures. When a change to the MPR selector set is detected and that change can be blamed on a link failure, a TC message SHOULD be transmitted after an interval shorter than TC_INTERVAL. Speed is everything ⚡💜
9.4. TC Message Forwarding 🦋
TC messages get broadcast and retransmitted by the MPRs to spread the messages through the entire network. TC messages MUST be forwarded according to the "default forwarding algorithm" (described in section 3.4). 🔁✨
9.5. TC Message Processing 🎀
When a TC message comes in, the "validity time" MUST be computed from the Vtime field of the message header (see section 3.3.2). Then the topology set SHOULD be updated like this (using section 19 to compare ANSN) 💅
Step 1 🚪: If the sender interface (NB: not the originator) of this message isn't in the symmetric 1-hop neighborhood of this node, the message MUST be discarded. Not on the list, not invited 🙅♀️
Step 2 🙈: If there's a tuple in the topology set where:
T_last_addr == originator address AND
T_seq > ANSN,then further processing of this TC message MUST NOT be performed, and the message MUST be silently discarded (case: message received out of order). Late messages get ghosted 👻
Step 3 🧹: All tuples in the topology set where:
T_last_addr == originator address AND
T_seq < ANSNMUST be removed from the topology set. Clean slate, babe ✨
Step 4 🗺️: For each advertised neighbor main address received in the TC message:
Step 4.1 💖: If there's a tuple in the topology set where:
T_dest_addr == advertised neighbor main address, AND
T_last_addr == originator address,then the holding time of that tuple MUST be set to:
T_time = current time + validity time.Step 4.2 🌈: Otherwise, a new tuple MUST be recorded in the topology set where:
T_dest_addr = advertised neighbor main address,
T_last_addr = originator address,
T_seq = ANSN,
T_time = current time + validity time.That's the whole topology processing flow, bestie! 🌈🫶
10. Routing Table Calculation ✨
okay so every node keeps its own routing table 🗺️ and it's basically the cheat sheet for how to reach everyone else in the network. it gets built from the local link information base and the topology set, so if either of those changes, the table gets recalculated so every destination's route info stays fresh 💅 each entry looks like this:
1. R_dest_addr R_next_addr R_dist R_iface_addr
2. R_dest_addr R_next_addr R_dist R_iface_addr
3. ,, ,, ,, ,,each entry has four parts: R_dest_addr, R_next_addr, R_dist, and R_iface_addr. so basically an entry says the node at R_dest_addr is about R_dist hops away, the symmetric neighbor with interface address R_next_addr is the next hop on the way there, and you can reach that neighbor through your local interface at R_iface_addr 🦋 entries only get recorded for destinations where a route is actually known. anything with a broken route, or only partly known, just doesn't make it into the table 🙈
here's when the table gets updated. it happens when a change shows up in any of these:
- the link set,
- the neighbor set,
- the 2-hop neighbor set,
- the topology set,
- the Multiple Interface Association Information Base,
more specifically, it gets recalculated when a neighbor appears or disappears, when a 2-hop tuple gets created or removed, when a topology tuple gets created or removed, or when multiple interface association info changes. and this part is so important: updating the routing info does NOT send or trigger any messages, either across the network or to the 1-hop neighborhood 🫶
the routing table is just local bookkeeping. no extra chatter, no drama 💀
to build node X's routing table, a shortest path algorithm runs on a directed graph. the arcs are:
- X -> Y, where Y is any symmetric neighbor of X (Neighbor Type equal to SYM),
- Y -> Z, where Y is a neighbor node whose willingness is different from WILL_NEVER and there's an entry in the 2-hop Neighbor set with Y as N_neighbor_main_addr and Z as N_2hop_addr,
- U -> V, where there's an entry in the topology set with V as T_dest_addr and U as T_last_addr.
the spec gives this procedure as an example for calculating (or recalculating) the table. it's giving algorithm energy 🧚
1. first, all the entries get removed from the routing table, so we start fresh ✨
2. new entries get added starting with the symmetric neighbors (h=1) as destinations. for each neighbor tuple where N_status is SYM (there's a symmetric link to that neighbor), and for each associated link tuple with L_time >= current time, a new routing entry gets recorded like this:
R_dest_addr = L_neighbor_iface_addr, of the associated link tuple;
R_next_addr = L_neighbor_iface_addr, of the associated link tuple;
R_dist = 1;
R_iface_addr = L_local_iface_addr of the associated link tuple.if none of the R_dest_addr values match the neighbor's main address, then another new routing entry MUST be added, with:
R_dest_addr = main address of the neighbor;
R_next_addr = L_neighbor_iface_addr of one of the associated link
tuples with L_time >= current time;
R_dist = 1;
R_iface_addr = L_local_iface_addr of the associated link tuple.3. next up are the 2-hop neighbors, aka the N2 nodes. this covers every node in N2 that isn't a neighbor node or the node itself, as long as there's at least one 2-hop neighbor set entry whose N_neighbor_main_addr is a neighbor node with willingness different from WILL_NEVER. you pick one 2-hop tuple and create one routing entry like this:
R_dest_addr = the main address of the 2-hop neighbor;
R_next_addr = the R_next_addr of the entry in the routing table with:
R_dest_addr == N_neighbor_main_addr of the 2-hop tuple;
R_dist = 2;
R_iface_addr = the R_iface_addr of the entry in the routing table with:
R_dest_addr == N_neighbor_main_addr of the 2-hop tuple;3. now for the nodes h+1 hops away. this part is basically a loop 🔁 the following procedure MUST be run for each value of h, starting at h=2 and going up by 1 each time. it stops as soon as an iteration records no new entry.
3.1 for each topology entry, if its T_dest_addr doesn't match R_dest_addr in any route entry, AND its T_last_addr matches the R_dest_addr of a route entry whose R_dist equals h, then a new route entry MUST be recorded in the routing table (if it doesn't already exist), like this:
R_dest_addr = T_dest_addr;
R_next_addr = R_next_addr of the recorded route entry where:
R_dest_addr == T_last_addr
R_dist = h+1; and
R_iface_addr = R_iface_addr of the recorded route entry where:
R_dest_addr == T_last_addr.3.2 sometimes several topology entries could be used to pick a next hop R_next_addr for reaching R_dest_addr. when h=1, ties should be broken so that nodes with the highest willingness and MPR selectors are preferred as next hop 👑
4. last step, the multiple interface association base. for each entry there, if there's a routing entry where R_dest_addr == I_main_addr, AND there's NO routing entry where R_dest_addr == I_iface_addr, then a route entry gets created like this:
R_dest_addr = I_iface_addr (of the multiple interface association entry)
R_next_addr = R_next_addr (of the recorded route entry)
R_dist = R_dist (of the recorded route entry)
R_iface_addr = R_iface_addr (of the recorded route entry).11. Node Configuration 🎀
this section is all about how a node should be set up so it can run in an OLSR MANET. it's the "get ready for the group project" part 📚
11.1. Address Assignment
the nodes in the MANET SHOULD get addresses from a defined address sequence. so basically, each node SHOULD be reachable through a network address and a netmask 🌸
the nodes in each associated network SHOULD also get addresses from a defined address sequence, and that sequence should be different from the one used in the MANET ✨
11.2. Routing Configuration
any MANET node with associated networks or hosts SHOULD be set up with routes to the interfaces that lead to those associated hosts or networks 🗺️
11.3. Data Packet Forwarding
okay this one's a plot twist 😭 OLSR does NOT forward packets itself. instead it keeps the routing table in the underlying operating system, and the OS is assumed to forward packets as specified in RFC1812 💅
12. Non OLSR Interfaces 🦋
a node MAY have multiple interfaces, and some of them might not take part in the OLSR MANET. these non OLSR interfaces could be point-to-point links to other individual hosts, or they could connect to separate networks 🌈
to give the OLSR MANET interface(s) connectivity to those non OLSR interface(s), a node SHOULD be able to inject external route info into the OLSR MANET 🫶
injecting routing info going the other way, from the OLSR MANET out to non OLSR interfaces, is outside the scope of this spec. but it's worth knowing that the routing info for the OLSR MANET can be pulled from the topology table (see section 4.4) or straight from OLSR's routing table. and it SHOULD be injected onto the non OLSR interfaces using whatever mechanism is provided on those interfaces, like a routing protocol or static configuration 🧚
an example would be a node with a fixed network (say, an Ethernet) connecting to a bigger network, plus a wireless interface running OLSR 🍓
and notice this is a different case from "multiple interfaces", where ALL of the interfaces take part in the MANET by running OLSR 👀
to inject external routing info into an OLSR MANET, a node with those non-MANET interfaces periodically issues a Host and Network Association (HNA) message. it contains enough info for recipients to build a proper routing table 💖
12.1. HNA Message Format
the proposed format of an HNA message is:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Network Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Netmask |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+this gets sent as the data part of the general packet format, with "Message Type" set to HNA_MESSAGE, the TTL field set to 255, and Vtime set based on HNA_HOLD_TIME, as specified in section 18.3 ⏰
Network Address
the network address of the associated network 🏠
Netmask
the netmask that goes with the network address right above it 🎀
12.2. Host and Network Association Information Base ✨
okay so every node keeps a little list of which nodes can act as "gateways" to hosts and networks behind them 🌸 each entry is an "association tuple" that looks like this:
(A_gateway_addr, A_network_addr, A_netmask, A_time)A_gateway_addris the address of the gateway's OLSR interface 🚪A_network_addrandA_netmaskare the network address and netmask of a network you can reach through that gateway 🗺️A_timeis when the tuple expires, and hence it MUST be removed 💀
all the association tuples in a node together make up the "association set" 💅
bestie, notice that the HNA message is basically a "generalized version" of the TC message 🦋 the originator of both HNA and TC messages is announcing "reachability" to some other host(s), so they're kind of cousins 🫶
in a TC message you don't need a netmask, since all reachability is announced per host 🎀 in HNA messages, announcing reachability to a sequence of addresses through a network and netmask is usually the preferred move over listing individual host addresses 🧚
one big difference is that a TC message can cancel older info if the ANSN gets incremented 🔄 but info in HNA messages only goes away when it expires ⏳ no take-backs, periodt 😭
12.3. HNA Message Generation 🎀
a node with associated hosts and/or networks SHOULD periodically generate a Host and Network Association (HNA) message 📣 it contains pairs of (network address, netmask) for the hosts and networks it's connected to 🌈 HNA messages SHOULD be sent out periodically every HNA_INTERVAL ⏰ the Vtime gets set based on HNA_HOLD_TIME, as specified in section 18.3 🍓
and a node without any associated hosts and/or networks SHOULD NOT generate HNA messages 🙈 nothing to announce, no drama 💅
12.4. HNA Message Forwarding 🦋
when a node receives an HNA message, and so follows the rules of section 3 in this version of the spec, the message MUST be forwarded according to section 3.4 🔁 no skipping the forwarding step, bestie ✨
12.5. HNA Message Processing 💖
quick note first: "originator address" just means the main address on the OLSR MANET of the node that originally issued the HNA message 🫶
when processing an HNA message, the "validity time" MUST be computed from the Vtime field of the message header (see section 3.3.2) 🕰️ then the association base SHOULD be updated like this 💫
- If the sender interface (NB: not originator) of this message is not in the symmetric 1-hop neighborhood of this node, the message MUST be discarded 🚫
- Otherwise, for each (network address, netmask) pair in the message:
2.1 If an entry in the association set already exists, where:
A_gateway_addr == originator address
A_network_addr == network address
A_netmask == netmaskthen the holding time for that tuple MUST be set to:
A_time = current time + validity time2.2 Otherwise, a new tuple MUST be recorded with:
A_gateway_addr = originator address
A_network_addr = network address
A_netmask = netmask
A_time = current time + validity time12.6. Routing Table Calculation 🗺️
on top of the routing table computation from section 10, the host and network association set MUST also be added in the following way ✨ for each tuple in the association set:
- If there is no entry in the routing table with:
R_dest_addr == A_network_addr/A_netmaskthen a new routing entry is created 🌱
- If a new routing entry was created at the previous step, or else if there existed one with:
R_dest_addr == A_network_addr/A_netmask
R_dist > dist to A_gateway_addr of
current association set tuplethen the routing entry is modified as follows 🛠️
R_dest_addr = A_network_addr/A_netmask
R_next_addr = the next hop on the path
from the node to A_gateway_addr
R_dist = dist to A_gateway_addrand R_next_addr and R_iface_addr MUST be set to the same values as the tuple from the routing set with R_dest_addr == A_gateway_addr 💅
12.7. Interoperability Considerations 🫶
nodes that don't support non OLSR interfaces can totally coexist with nodes that do 🤝 the generic packet format and message forwarding (section 3) make sure HNA messages get forwarded correctly by every node 🚀 so nodes that do support non OLSR interfaces can send and process HNA messages according to this section 💖
nodes that don't support non OLSR interfaces can not take advantage of the stuff in this section 😭 but they'll still forward HNA messages correctly, as specified in section 3 🥹
13. Link Layer Notification 🔗
OLSR is designed so it doesn't impose or expect any specific info from the link layer 🙅♀️ but if info from the link layer describing link breakage is available, a node MAY use it, as described in this section ✨
if link layer info describing connectivity to neighboring nodes is available (like losing a link when there's no link layer acknowledgment), it gets used on top of the HELLO message info to maintain the neighbor information base and the MPR selector set 🧠
so when a node gets a link layer notification that its link to a neighbor interface is broken, these actions happen for link sensing 👀
each link tuple in the local link set SHOULD, on top of what's in section 4.2, include an L_LOST_LINK_time field ⏱️ L_LOST_LINK_time is a timer for declaring a link as lost when an established link becomes pending 💀 (notice this is a subset of what section 14 recommends, so link hysteresis and link layer notifications can coexist 🫶)
HELLO message generation should consider those new fields like this:
- if L_LOST_LINK_time is not expired, the link is advertised with a link type of LOST_LINK 📢 on top of that, it is not considered a symmetric link in the updates of the associated neighbor tuple (see section 8.1) 🚫
- if the link to a neighboring symmetric or asymmetric interface is broken, the corresponding link tuple is modified: L_LOST_LINK_time and L_time are set to current time + NEIGHB_HOLD_TIME ⏳
- this counts as a link loss, so the appropriate processing described in section 8.5 should be performed 🧹
13.1. Interoperability Considerations 🌷
link layer notifications give a node one more way to figure out that a link to a neighbor is lost 👀 once a link is detected as lost, it gets advertised according to the earlier sections of this spec 📣
14. Link Hysteresis 🌊
established links should be as reliable as possible so data packets don't get lost 📦 that means link sensing should be robust against bursty loss or transient connectivity between nodes 🌪️ so to make link sensing extra sturdy, the following implementation recommendations SHOULD be considered 💪
14.1. Local Link Set 🧺
each link tuple in the local link set SHOULD, on top of what's in section 4.2, include an L_link_pending field, an L_link_quality field, and an L_LOST_LINK_time field 🎀 L_link_pending is a boolean value saying whether the link is considered pending (aka the link isn't considered established yet) ⏸️ L_link_quality is a dimensionless number between 0 and 1 describing the quality of the link 📊 and L_LOST_LINK_time is a timer for declaring a link as lost when an established link becomes pending ⏱️
14.2. Hello Message Generation 💌
HELLO message generation should consider those new fields like this:
- if L_LOST_LINK_time is not expired, the link is advertised with a link type of LOST_LINK 📢
- otherwise, if L_LOST_LINK_time is expired and L_link_pending is set to "true", the link SHOULD NOT be advertised at all 🙈
- otherwise, if L_LOST_LINK_time is expired and L_link_pending is set to "false", the link is advertised as described previously in section 6 ✅
a node considers that it has a symmetric link for each link tuple where:
- L_LOST_LINK_time is expired, AND
- L_link_pending is "false", AND
- L_SYM_time is not expired 🫶
this definition for "symmetric link" SHOULD be used when updating the associated neighbor tuple (see section 8.1) to compute the N_status of a neighbor node 🧮 this definition SHOULD also be used as the basis for the symmetric neighborhood when computing the MPR set, and for "the symmetric neighbors" in the first steps of the routing table calculation 🗺️
apart from all that, what's described above doesn't interfere with the advanced link sensing fields in the link tuples 🦋 the L_link_quality, L_link_pending and L_LOST_LINK_time fields are updated exclusively according to this section, and this section doesn't change the function of any other fields in the link tuples 💜
14.3. Hysteresis Strategy ✨
okay so the link between a node and some of its neighbor interfaces can be bad 💀. Sometimes HELLOs sneak through and then just fade out right after, and the neighbor information base ends up holding a bad link for at least "validity time". The following hysteresis strategy SHOULD be adopted to counter this situation 🫶.
For each neighbor interface NI heard by interface I, the L_link_quality field of the matching Link Tuple decides whether the link gets established 🦋. That value gets compared to two thresholds, HYST_THRESHOLD_HIGH and HYST_THRESHOLD_LOW. Both are fixed between 0 and 1, and HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW, always.
The L_link_pending field gets set like this:
1 if L_link_quality > HYST_THRESHOLD_HIGH:
L_link_pending = false
L_LOST_LINK_time = current time - 1 (expired)
2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW:
L_link_pending = true
L_LOST_LINK_time = min (L_time, current time +
NEIGHB_HOLD_TIME)
(the link is then considered as lost according to section
8.5 and this may produce a neighbor loss).
3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality
<= HYST_THRESHOLD_HIGH:
L_link_pending and L_LOST_LINK_time remain unchanged.So the bar to establish a link is stricter than the bar to drop one 💅. A link can get dropped either because its timer expires (like in section 7) or because L_link_quality falls below HYST_THRESHOLD_LOW 😭.
Also, even when the link hysteresis says a link is NOT established yet, the link tuples still get updated for every HELLO message received (as in section 7) 🌈. What that means is that, no matter what hysteresis thinks about "established", tuples in the link set don't expire except through the L_time field of the link tuples. ✨
As a basic implementation requirement, an estimate of the link quality must be kept around and stored in the L_link_quality field 🎀. If you've got some measure of the signal/noise level on a received message (say, from a link layer notification), you can use that as the estimate after normalization 💖.
If there's no signal/noise info or any other link quality info from the link layer, you can use an algorithm like this one. It's an exponentially smoothed moving average of the transmission success rate 🧚. It's parameterized by a scaling parameter HYST_SCALING, a number fixed between 0 and 1. For each neighbor interface NI heard by interface I, the very first time NI is heard by I, L_link_quality gets set to HYST_SCALING (with L_link_pending set to true and L_LOST_LINK_time set to current time - 1) 🍓.
A tuple gets updated by two rules. Every time an OLSR packet sent by NI is received by I, the stability rule kicks in:
L_link_quality = (1-HYST_SCALING)*L_link_quality
+ HYST_SCALING.And when an OLSR packet sent by NI is lost by I, the instability rule applies:
L_link_quality = (1-HYST_SCALING)*L_link_quality.Packet loss gets detected in two ways: by tracking the missing Packet Sequence Numbers on a per-interface basis, and by a "long period of silence" from a node 🙈. A "long period of silence" can be detected like this: if no OLSR packet has been received on interface I from interface NI during the HELLO emission interval of interface NI (worked out from the Htime field in the last HELLO message received from NI), then a loss of an OLSR packet is detected 👑.
14.4. Interoperability Considerations
ngl this one's simple 🌸. Link hysteresis is what decides, for a node, the criteria for accepting or rejecting a link to a neighbor node. Nodes in a network can have different criteria, depending on the kind of media they're talking over 🍓. Once a link gets accepted, it gets advertised, following the rules in the earlier sections of this spec 💜.
15. Redundant Topology Information 🌈
Okay, redundancy time! 💅 To give the topology information base some backup, the advertised link set of a node MAY contain links to neighbor nodes that are NOT in its MPR selector set. The advertised link set MAY also contain links to the whole neighbor set of the node. The absolute minimum that any node MUST advertise in its TC messages is the links to its MPR selectors 🔥. The advertised link set can be built with the following rule, based on a local parameter called TC_REDUNDANCY.
Quick correction on that last sentence, because I typed it too fast: the MPR selector set is what I mean, and the two lines above say the same thing. Moving on 🫶.
15.1. TC_REDUNDANCY Parameter
The TC_REDUNDANCY parameter tells the local node how much information MAY be included in the TC messages 🦋. The parameter SHOULD be read like this:
- if the TC_REDUNDANCY parameter of the node is 0, then the advertised link set of the node is limited to the MPR selector set (as described in section 8.3),
- if the TC_REDUNDANCY parameter of the node is 1, then the advertised link set of the node is the union of its MPR set and its MPR selector set,
- if the TC_REDUNDANCY parameter of the node is 2, then the advertised link set of the node is the full neighbor link set.
A node with willingness equal to WILL_NEVER SHOULD also have TC_REDUNDANCY equal to zero 🙅♀️.
15.2. Interoperability Considerations
A TC message is how a node in the network declares a set of links, called the advertised link set 🎀. That set MUST include at least the links to all nodes of its MPR Selector set, meaning the neighbors that have picked the sender node as an MPR. That's enough info to make sure routes can be computed according to section 10 ✨.
This section explains how extra info can be declared through the TC_REDUNDANCY parameter 💖. TC_REDUNDANCY = 0 means the info declared is exactly the MPR Selector set, same as section 9. Other values of TC_REDUNDANCY declare additional info, but the contents of the MPR Selector set are always declared anyway 🌷. So nodes with different TC_REDUNDANCY values can coexist in a network: control messages are carried by all nodes according to section 3, and every node still receives at least the link-state info it needs to build routes as described in section 10 🧚.
16. MPR Redundancy 👑
MPR redundancy is about a node's ability to select redundant MPRs 💅. Section 4.5 says a node should select its MPR set to be as small as possible, to cut down on protocol overhead. The rule for picking MPRs is that all strict 2-hop nodes must be reachable through at least one MPR node 🌈. MPR set redundancy affects overhead by changing how many links get advertised, how many nodes advertise links, and how efficient MPR flooding is. On the flip side, redundancy in the MPR set means a node's reachability gets advertised by more nodes, so extra links spread around the network 🦋.
Generally a minimal MPR set gives the least overhead 🍓, but sometimes it's worth trading some overhead for other benefits. For example, a node may decide to boost its MPR coverage if it notices lots of changes in its neighbor information base caused by mobility, and otherwise keep MPR coverage low 🙈.
16.1. MPR_COVERAGE Parameter
One single local parameter, MPR_COVERAGE, defines the MPR coverage. It says how many MPR nodes any strict 2-hop node should be covered by 🎀. MPR_COVERAGE=1 keeps protocol overhead at a minimum and makes MPR selection work as described in section 8.3.1. MPR_COVERAGE=m makes sure that, if possible, a node selects its MPR set so that every strict 2-hop node for an interface is reachable through at least m MPR nodes on that interface ✨. MPR_COVERAGE can be any integer value > 0. The heuristic MUST be applied per interface, I. The MPR set for a node is the union of the MPR sets found for each interface 💜.
MPR_COVERAGE can be tuned locally without messing up the consistency of the protocol 💖. For example, nodes in a network can run with different MPR_COVERAGE values 🌸.
16.2. MPR Computation
Using MPR coverage, the MPR selection heuristics get extended from the one in section 8.3.1 by one new definition 🧚:
Poorly covered node: A poorly covered node is a node in N2 which is covered by less than MPR_COVERAGE nodes in N.
Here's the proposed heuristic for selecting MPRs 🔥:
1 Start with an MPR set made of all members of N with
willingness equal to WILL_ALWAYS
2 Calculate D(y), where y is a member of N, for all nodes in N.
3 Select as MPRs those nodes in N which cover the poorly covered
nodes in N2. The nodes are then removed from N2 for the rest
of the computation.
4 While there exist nodes in N2 which are not covered by at
least MPR_COVERAGE nodes in the MPR set:
4.1 For each node in N, calculate the reachability, i.e.,
the number of nodes in N2 which are not yet covered
by at least MPR_COVERAGE nodes in the MPR set, and
which are reachable through this 1-hop neighbor;
4.2 Select as a MPR the node with highest willingness among
the nodes in N with non-zero reachability. In case of
multiple choice select the node which provides
reachability to the maximum number of nodes in N2. In
case of multiple nodes providing the same amount of
reachability, select the node as MPR whose D(y) is
greater. Remove the nodes from N2 which are now covered
by MPR_COVERAGE nodes in the MPR set.
5 A node's MPR set is generated from the union of the MPR sets
for each interface. As an optimization, process each node, y,
in the MPR set in increasing order of N_willingness. If all
nodes in N2 are still covered by at least MPR_COVERAGE nodes
in the MPR set excluding node y, and if N_willingness of node
y is smaller than WILL_ALWAYS, then node y MAY be removed from
the MPR set.Once the MPR set has been computed, all the matching main addresses get stored in the MPR Set 🌈.
16.3. Interoperability Considerations
The MPR set of a node MUST, according to section 8.3, be calculated so that, through the neighbors in the MPR-set, it can reach all symmetric strict 2-hop neighbors 🦋. The heuristics in this section achieve that for all values of MPR_COVERAGE > 0 🍓. MPR_COVERAGE is a local parameter for each node, and setting it only affects how much redundancy shows up in part of the network 🙈.
Notice that for MPR_COVERAGE=1, the heuristics in this section are identical to the ones in section 8.3.1 🎀.
Nodes with different MPR_COVERAGE values may coexist in a network: control messages are carried by all nodes according to section 3, and all nodes will still receive at least the link-state info they need to build routes, as described in sections 9 and 10 ✨.
17. IPv6 Considerations ✨
okay so good news bestie 🦋 everything in this doc that OLSR uses for IPv4 works exactly the same for IPv6. 💅 the only thing you have to change is swapping the IPv4 addresses for IPv6 addresses. that's it!! 😭
the one thing to keep in mind is the minimum packet and message sizes. the ones that cause a rejection need adjusting, because IPv6 addresses are way bigger 🧚 so the limits have to account for that 🌸
18. Proposed Values for Constants 🎀
this section is the cheat sheet 📝 it lists the values for all the constants used in the protocol description, so you can look everything up in one place 💜
18.1. Setting emission intervals and holding times ⏰
first up, the proposed value for C:
C = 1/16 seconds (equal to 0.0625 seconds)C is a scaling factor for the "validity time" calculation ("Vtime" and "Htime" fields in message headers, see section 18.3). the whole point of validity time is that nodes can have different emission intervals and tune them individually 🌈 and they can still interoperate fully. slay, right? 👑 for protocol functioning and interoperability to work:
- the advertised holding time MUST always be greater than the refresh interval of the advertised information. also, it is recommended that the relation between the interval (from section 18.2) and the hold time is kept as specified in section 18.3, so there's room for reasonable packet loss 🫶
- the constant C SHOULD be set to the suggested value. to get interoperability, C MUST be the same on all nodes 💖
- the emission intervals (section 18.2), along with the advertised holding times (subject to the constraints above), MAY be picked on a per node basis ✨
note 🙈 a given implementation's timer resolution might not be precise enough to wake the system up right on the refresh times or the expire times. so the implementation SHOULD round up the 'validity time' ("Vtime" and "Htime" of packets) to make up for the coarser timer. this matters most when the validity time could end up shorter than emission interval plus the biggest expected timer error. 😭
18.2. Emission Intervals 📡
HELLO_INTERVAL = 2 seconds
REFRESH_INTERVAL = 2 seconds
TC_INTERVAL = 5 seconds
MID_INTERVAL = TC_INTERVAL
HNA_INTERVAL = TC_INTERVAL18.3. Holding Time 🕰️
NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL
TOP_HOLD_TIME = 3 x TC_INTERVAL
DUP_HOLD_TIME = 30 seconds
MID_HOLD_TIME = 3 x MID_INTERVAL
HNA_HOLD_TIME = 3 x HNA_INTERVALthe Vtime in the message header (see section 3.3.2) and the Htime in the HELLO message (see section 6.1) are the fields that carry these values, in mantissa and exponent format, rounded up 🧁 the math is:
value = C*(1+a/16)*2^b [in seconds]where a is the integer in the four highest bits of the field, and b is the integer in the four lowest bits 🔢
bestie, this part is so clever 🤌 for the previous proposed value of C (1/16 seconds), every value that formula can produce is stored with zero loss of precision, as long as you use binary fixed point or floating point numbers with at least 8 bits of fractional part. that lines up with NTP time-stamps and single precision IEEE Standard 754 floating point numbers. iconic 🥹
to turn a number T (of seconds) into the mantissa/exponent form, you do this:
- find the largest integer 'b' such that T/C >= 2^b
- compute 16*(T/(C*(2^b))-1), which might not be an integer, and round it up. that gives you the value for 'a'
- if 'a' is equal to 16, increment 'b' by one and set 'a' to 0
- now 'a' and 'b' should be integers between 0 and 15, and the field is a byte holding the value a*16+b
for example, 2 seconds, 6 seconds, 15 seconds and 30 seconds come out as (a=0,b=5), (a=8,b=6), (a=14,b=7) and (a=14,b=8) respectively 🎀
18.4. Message Types 💌
HELLO_MESSAGE = 1
TC_MESSAGE = 2
MID_MESSAGE = 3
HNA_MESSAGE = 418.5. Link Types 🔗
UNSPEC_LINK = 0
ASYM_LINK = 1
SYM_LINK = 2
LOST_LINK = 318.6. Neighbor Types 👯
NOT_NEIGH = 0
SYM_NEIGH = 1
MPR_NEIGH = 218.7. Link Hysteresis 🌊
HYST_THRESHOLD_HIGH = 0.8
HYST_THRESHOLD_LOW = 0.3
HYST_SCALING = 0.518.8. Willingness 🫧
WILL_NEVER = 0
WILL_LOW = 1
WILL_DEFAULT = 3
WILL_HIGH = 6
WILL_ALWAYS = 7okay so willingness is basically how much a node is up for carrying traffic for everybody else 🚚 it can be any integer from 0 to 7. every node starts out at WILL_DEFAULT. WILL_NEVER means "not carrying anyone's stuff rn" (think low battery or limited resources 🔋). WILL_ALWAYS means "pick me, always" (think permanent power and beefy connections ⚡).
a node can change its willingness whenever its conditions change 💅
one example that's giving me life: a node plugged into permanent power with a full battery advertises WILL_ALWAYS. the second it gets unplugged (a PDA yanked out of its charging cradle, for instance), it drops to WILL_DEFAULT. as the battery drains, the willingness keeps dropping: first to the value between WILL_DEFAULT and WILL_LOW, then to WILL_LOW, and finally to WILL_NEVER once the battery can no longer support carrying foreign traffic 🥀
18.9. Misc. Constants 🧩
TC_REDUNDANCY = 0
MPR COVERAGE = 1
MAXJITTER = HELLO_INTERVAL / 419. Sequence Numbers 🔢
sequence numbers are how OLSR throws out "old" info, like messages that show up out of order 🙃 the catch is that they only have a limited number of bits, so eventually they wrap around (going from the max value back to zero). to stop that from messing with the protocol, the following MUST be observed. 😤
MAXVALUE is the biggest possible value a sequence number can have.
sequence number S1 counts as "greater than" sequence number S2 if:
S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR
S2 > S1 AND S2 - S1 > MAXVALUE/2so even with wrap-around, you can still tell which message has the most recent info 🦋 the math is slightly chef's kiss 👌
20. Security Considerations 🛡️
bestie, real talk 🥺 OLSR does not specify any special security measures right now. as a proactive routing protocol, it's basically a big target for all kinds of attacks 💀 this section goes through the possible vulnerabilities, so grab a snack and pay attention.
20.1. Confidentiality 🔐
OLSR is proactive, which means it keeps spreading topology info on a schedule. so if it runs on an unprotected wireless network, the network topology is out there for anyone who's listening to OLSR control messages 👀 not great!!
if keeping the topology private matters to you, regular cryptography can help. you can encrypt the OLSR control traffic with PGP [9], or with some shared secret key, so only authorized people can read and interpret it 🔒
20.2. Integrity 🧱
in OLSR, every node is injecting topology info into the network by sending HELLO messages and, for some nodes, TC messages. if some nodes inject invalid control traffic, whether on purpose (malicious) or by accident (malfunction), the network's integrity can be compromised 😱 so message authentication is recommended.
there are a bunch of ways this can go sideways, for example:
- a node generates TC (or HNA) messages, advertising links to non-neighbor nodes
- a node generates TC (or HNA) messages, pretending to be another node
- a node generates HELLO messages, advertising non-neighbor nodes
- a node generates HELLO messages, pretending to be another node
- a node forwards altered control messages
- a node does not broadcast control messages
- a node does not select multipoint relays correctly
- a node forwards broadcast control messages unaltered, but does not forward unicast data traffic
- a node "replays" previously recorded control traffic from another node
authenticating the originator of control messages helps with situations 2, 4 and 5. authenticating the individual links announced in control messages helps with situations 1 and 3. 🫶 but to stop nodes from repeating old (and correctly authenticated) info (situation 9), you also need temporal information, so a node can positively identify delayed messages ⏳
another move 💡 digital signatures and other security info can go in a separate OLSR message type. that way "secured" and "unsecured" nodes can coexist in the same network, if that's what you want 🌈
specifically, you can establish the authenticity of entire OLSR control messages by using IPsec authentication headers. authenticity of individual links (situations 1 and 3) needs extra security info to be distributed, though 🧐
here's the big thing to remember ✨ every control message in OLSR is sent either to all nodes in the neighborhood (HELLO messages) or broadcast to all nodes in the network (for example, TC messages). so a control message is always a point-to-multipoint transmission. that means the authentication mechanism has to let any receiving node check that a message is authentic 💜 the analogy is a block of text signed with a PGP private key: anyone with the matching public key can verify it. periodt 🎀
20.3. Interaction with External Routing Domains ✨
okay so OLSR has a basic way to bring outside routing info into the OLSR domain, and it's done through the HNA messages in section 12 🦋. Section 12 also says routing info can be pulled out of the OLSR topology table or routing table and, maybe, pushed into an external domain, but only if that outside routing protocol allows it 💅.
Other than as described in the section 20.2, when you're running nodes that connect OLSR to an external routing domain, you MUST be careful not to let sketchy, untrustworthy info leak from the OLSR domain into the external ones 🙈. You also MUST check that info is correct before it gets injected, so you don't pollute anyone's routing tables with junk 💀.
the recommended move for extending an existing routing domain out to an OLSR routed MANET is to give the OLSR MANET area its own IP prefix, exclusively, under the authority of the nodes/gateways that connect the MANET to the existing domain 🌸. Then you configure those gateways statically so they advertise routes to that prefix to nodes in the existing domain 🫶.
20.4. Node Identity
OLSR doesn't assume anything about node addresses, except that every node has a unique IP address 🧚.
21. Flow and congestion control
okay this part is so pretty ✨. Because OLSR is proactive, it has natural control over how much control traffic flows around 🌈. Nodes send control messages at predetermined rates, set by predefined refresh intervals ⏰.
The MPR optimization is a whole queen move 👑 because it saves control overhead in two ways. First, the packets that advertise the topology are way shorter, since only MPR selectors can get advertised 💜. Second, flooding that info costs way less, because only MPR nodes forward the broadcast packets 🔥. In dense networks, the control traffic reduction can be several orders of magnitude compared to routing protocols that use classic flooding, like OSPF [10] 😭. That leaves more bandwidth for actual useful data and pushes the congestion frontier further out 🎀.
Since control traffic is continuous and periodic, it keeps link quality more stable for the links used in routing 🦋. Reactive protocols are different: their bursty floodings for route discoveries and repairs can wreck link quality for short periods by causing lots of collisions on those links, which can even set off route repair cascades 💀. Pretty chaotic, ngl.
Now, in certain OLSR options, some control messages may be intentionally sent before their deadline (TC or Hello messages) so the protocol reacts faster to topology changes ⚡. This can cause a small, temporary, and local increase in control traffic, which is a fair trade in my book 🍓.
22. IANA Considerations
OLSR defines a "Message Type" field for control messages 📮. A new registry was created for the values of this field, and these values got assigned:
Message Type Value
-------------------- -----
HELLO_MESSAGE 1
TC_MESSAGE 2
MID_MESSAGE 3
HNA_MESSAGE 4Future values in the range 5-127 of the Message Type can be allocated using standards action [7] 🧚♀️. Values in the range 128-255 are reserved for private/local use 🔒.
23. Acknowledgments
The authors wanna thank Joseph Macker <macker@itd.nrl.navy.mil> and his team, including Justin Dean <jdean@itd.nrl.navy.mil>, for their awesome suggestions on the advanced neighbor sensing mechanism and other aspects of the protocol, plus careful review of the spec 🫶💖.
The authors also wanna thank Christopher Dearlove <chris.dearlove@baesystems.com> for valuable input on the MPR selection heuristics and for careful reviews of the protocol specification 👑✨.
24. Contributors
During the development of this specification, the following people contributed 🌸. They're listed alphabetically, bestie 💅.
Cedric Adjih Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5215 EMail: Cedric.Adjih@inria.fr
Thomas Heide Clausen Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5133 EMail: T.Clausen@computer.org
Philippe Jacquet Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5263 EMail: Philippe.Jacquet@inria.fr
Anis Laouiti Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5088 EMail: Anis.Laouiti@inria.fr
Pascale Minet Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5233 EMail: Pascale.Minet@inria.fr
Paul Muhlethaler Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5278 EMail: Paul.Muhlethaler@inria.fr
Amir Qayyum Center for Advanced Research in Engineering Pvt. Ltd. 19 Ataturk Avenue Islamabad, Pakistan
Phone: +92-51-2874115 EMail: amir@carepvtltd.com
Laurent Viennot Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5225 EMail: Laurent.Viennot@inria.fr
25. References
25.1. Normative References
- [5] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
- [7] T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum and L. Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan 2001.
25.2. Informative References
- [1] P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing reliability in cable free radio LANs: Low level forwarding in HIPERLAN. Wireless Personal Communications, 1996.
- [2] A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. 35th Annual Hawaii International Conference on System Sciences (HICSS'2001).
- [3] ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 1, functional specifications ETS 300-652, ETSI, June 1996.
- [4] P. Jacquet and L. Viennot, Overhead in Mobile Ad-hoc Network Protocols, INRIA research report RR-3965, 2000.
- [6] T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The Optimized Link State Routing Protocol, Evaluation through Experiments and Simulation. IEEE Symposium on "Wireless Personal Mobile Communications", September 2001.
- [8] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
- [9] Atkins, D., Stallings, W. and P. Zimmermann, "PGP Message Exchange Formats", RFC 1991, August 1996.
- [10] P. Jacquet, A. Laouiti, P. Minet, L. Viennot. Performance analysis of OLSR multipoint relay flooding in two ad hoc wireless network models, INRIA research report RR-4260, 2001.
26. Authors' Addresses
Thomas Heide Clausen Project HIPERCOM INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5133 EMail: T.Clausen@computer.org
Philippe Jacquet, Project HIPERCOM, INRIA Rocquencourt, BP 105 78153 Le Chesnay Cedex, France
Phone: +33 1 3963 5263, EMail: Philippe.Jacquet@inria.fr
27. Full Copyright Statement
this part is legal stuff, so I'm keeping it word for word 🙏⚖️
Copyright (C) The Internet Society (2003). All Rights Reserved.
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assignees.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the Internet Society. 🌈💖
📦 where this page comes from
- ietf: rfc3626 2003-10
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms