idnits 2.17.1 draft-ietf-manet-olsr-10.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([2], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 248: '...formation from these interfaces MAY be...' RFC 2119 keyword, line 268: '...R interface node MUST use the address ...' RFC 2119 keyword, line 271: '...R interface node MUST choose one of it...' RFC 2119 keyword, line 274: '..., however a node SHOULD always use the...' RFC 2119 keyword, line 373: '...elected as MPRs, MUST declare the link...' (153 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 331 has weird spacing: '..., which have ...' == Line 2785 has weird spacing: '...limited to th...' == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: then the message has already been completely processed and MUST not be processed again. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (02 May 2003) is 7664 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 2091 looks like a reference -- Missing reference section? '2' on line 429 looks like a reference -- Missing reference section? '3' on line 212 looks like a reference -- Missing reference section? '5' on line 3349 looks like a reference -- Missing reference section? '0' on line 998 looks like a reference -- Missing reference section? 'MAXJITTER' on line 998 looks like a reference -- Missing reference section? '7' on line 3349 looks like a reference Summary: 4 errors (**), 0 flaws (~~), 4 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT Thomas Clausen, Editor 3 IETF MANET Working Group Philippe Jacquet, Editor 4 Expiration: 02 November 2003 Project Hipercom 5 INRIA Rocquencourt, France 6 02 May 2003 8 Optimized Link State Routing Protocol 10 draft-ietf-manet-olsr-10.txt 12 Status of this Memo 14 This document is a submission by the Mobile Ad Hoc Networking Working 15 Group of the Internet Engineering Task Force (IETF). Comments should 16 be submitted to the manet@itd.nrl.navy.mil mailing list. 18 Distribution of this memo is unlimited. 20 This document is an Internet-Draft and is in full conformance with 21 all provisions of Section 10 of RFC 2026. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note that 25 other groups may also distribute working documents as Internet- 26 Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 Abstract 41 This document describes the Optimized Link State Routing (OLSR) 42 protocol for mobile ad hoc networks. The protocol is an optimization 43 of the classical link state algorithm tailored to the requirements of 44 a mobile wireless LAN. The key concept used in the protocol is that 45 of multipoint relays (MPRs) [1], [2]. MPRs are selected nodes which 46 forward broadcast messages during the flooding process. This 47 technique substantially reduces the message overhead as compared to a 48 classical flooding mechanism, where every node retransmits each 49 message when it receives the first copy of the message. In OLSR, 50 link state information is generated only by nodes elected as MPRs. 51 Thus, a second optimization is achieved by minimizing the number of 52 control messages flooded in the network. As a third optimization, an 53 MPR node may chose to report only links between itself and its MPR 54 selectors. Hence, as contrary to the classic link state algorithm, 55 partial link state information is distributed in the network. This 56 information is then used by for route calculation. OLSR provides 57 optimal routes (in terms of number of hops). The protocol is 58 particularly suitable for large and dense networks as the technique 59 of MPRs works well in this context. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 6 64 1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 65 1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . . . 7 66 1.3. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 9 67 1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 10 68 1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . . . . 11 69 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . . . 12 70 2.1. Core Functioning . . . . . . . . . . . . . . . . . . . . . . . 12 71 2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . . . . . 14 72 3. Packet Format and Forwarding . . . . . . . . . . . . . . . . . . 15 73 3.1. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 16 74 3.2. Main Address . . . . . . . . . . . . . . . . . . . . . . . . . 16 75 3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . . . . . 16 76 3.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . . . . . 17 77 3.3.2. Message Header . . . . . . . . . . . . . . . . . . . . . . . 17 78 3.4. Packet Processing and Message Flooding . . . . . . . . . . . . 19 79 3.4.1. Default Forwarding Algorithm . . . . . . . . . . . . . . . . 21 80 3.4.2. Considerations on Processing and Forwarding . . . . . . . . . 22 81 3.5. Message Emission and Jitter . . . . . . . . . . . . . . . . . . 23 82 4. Information Repositories . . . . . . . . . . . . . . . . . . . . 24 83 4.1. Multiple Interface Association Information Base . . . . . . . . 24 84 4.2. Link sensing: Local Link Information Base . . . . . . . . . . . 25 85 4.2.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . . 25 86 4.3. Neighbor Detection: Neighborhood Information Base . . . . . . . 25 87 4.3.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . . 25 88 4.3.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . . . . 26 89 4.3.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 90 4.3.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . . . . 26 91 4.4. Topology Information Base . . . . . . . . . . . . . . . . . . . 26 92 5. Main Addresses and Multiple Interfaces . . . . . . . . . . . . . 27 93 5.1. MID Message Format . . . . . . . . . . . . . . . . . . . . . . 27 94 5.2. MID Message Generation . . . . . . . . . . . . . . . . . . . . 28 95 5.3. MID Message Forwarding . . . . . . . . . . . . . . . . . . . . 28 96 5.4. MID Message Processing . . . . . . . . . . . . . . . . . . . . 29 97 5.5. Resolving a Main Address from an Interface Address . . . . . . 29 98 6. HELLO Message Format and Generation . . . . . . . . . . . . . . . 30 99 6.1. HELLO Message Format . . . . . . . . . . . . . . . . . . . . . 30 100 6.1.1. Link Code as Link Type and Neighbor Type . . . . . . . . . . 33 101 6.2. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 34 102 6.3. HELLO Message Forwarding . . . . . . . . . . . . . . . . . . . 36 103 6.4. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 36 104 7. Link Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . 36 105 7.1. Populating the Link Set . . . . . . . . . . . . . . . . . . . . 37 106 7.1.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 37 107 8. Neighbor Detection . . . . . . . . . . . . . . . . . . . . . . . 39 108 8.1. Populating the Neighbor Set . . . . . . . . . . . . . . . . . . 39 109 8.1.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 40 110 8.2. Populating the 2-hop Neighbor Set . . . . . . . . . . . . . . . 41 111 8.2.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 41 112 8.3. Populating the MPR set . . . . . . . . . . . . . . . . . . . . 42 113 8.3.1. MPR Computation . . . . . . . . . . . . . . . . . . . . . . . 43 114 8.4. Populating the MPR Selector Set . . . . . . . . . . . . . . . . 45 115 8.4.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 45 116 8.5. Neighborhood and 2-hop Neighborhood Changes . . . . . . . . . . 46 117 9. Topology Discovery . . . . . . . . . . . . . . . . . . . . . . . 47 118 9.1. TC Message Format . . . . . . . . . . . . . . . . . . . . . . . 47 119 9.2. Advertised Neighbor Set . . . . . . . . . . . . . . . . . . . . 48 120 9.3. TC Message Generation . . . . . . . . . . . . . . . . . . . . . 49 121 9.4. TC Message Forwarding. . . . . . . . . . . . . . . . . . . . . 49 122 9.5. TC Message Processing . . . . . . . . . . . . . . . . . . . . . 49 123 10. Routing Table Calculation . . . . . . . . . . . . . . . . . . . 51 124 11. Node Configuration . . . . . . . . . . . . . . . . . . . . . . . 54 125 11.1. Address Assignment . . . . . . . . . . . . . . . . . . . . . . 54 126 11.2. Routing Configuration . . . . . . . . . . . . . . . . . . . . 55 127 11.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 55 128 12. Non OLSR Interfaces . . . . . . . . . . . . . . . . . . . . . . 55 129 12.1. HNA Message Format . . . . . . . . . . . . . . . . . . . . . . 56 130 12.2. Host and Network Association Information Base . . . . . . . . 56 131 12.3. HNA Message Generation . . . . . . . . . . . . . . . . . . . . 57 132 12.4. HNA Message Forwarding . . . . . . . . . . . . . . . . . . . . 57 133 12.5. HNA Message Processing . . . . . . . . . . . . . . . . . . . . 57 134 12.6. Routing Table Calculation . . . . . . . . . . . . . . . . . . 58 135 12.7. Interoperability Considerations . . . . . . . . . . . . . . . 59 136 13. Link Layer Notification . . . . . . . . . . . . . . . . . . . . 59 137 13.1. Interoperability Considerations . . . . . . . . . . . . . . . 60 138 14. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . . 60 139 14.1. Local Link Set . . . . . . . . . . . . . . . . . . . . . . . . 61 140 14.2. Hello Message Generation . . . . . . . . . . . . . . . . . . . 61 141 14.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . . . . . 62 142 14.4. Interoperability Considerations . . . . . . . . . . . . . . . 64 143 15. Redundant Topology Information . . . . . . . . . . . . . . . . . 64 144 15.1. TC_REDUNDANCY Parameter . . . . . . . . . . . . . . . . . . . 64 145 15.2. Interoperability Considerations . . . . . . . . . . . . . . . 65 146 16. MPR Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . 65 147 16.1. MPR_COVERAGE Parameter . . . . . . . . . . . . . . . . . . . . 66 148 16.2. MPR Computation . . . . . . . . . . . . . . . . . . . . . . . 66 149 16.3. Interoperability Considerations . . . . . . . . . . . . . . . 67 150 17. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . . 67 151 18. Proposed Values for Constants . . . . . . . . . . . . . . . . . 68 152 18.1. Setting emission interval and holding times . . . . . . . . . 68 153 18.2. Emission Interval . . . . . . . . . . . . . . . . . . . . . . 68 154 18.3. Holding time . . . . . . . . . . . . . . . . . . . . . . . . . 69 155 18.4. Message Types . . . . . . . . . . . . . . . . . . . . . . . . 70 156 18.5. Link Types . . . . . . . . . . . . . . . . . . . . . . . . . . 70 157 18.6. Neighbor Types . . . . . . . . . . . . . . . . . . . . . . . . 70 158 18.7. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 71 159 18.8. Willingness . . . . . . . . . . . . . . . . . . . . . . . . . 71 160 18.9. Misc. Constants . . . . . . . . . . . . . . . . . . . . . . . 72 161 19. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . . 72 162 20. Security Considerations . . . . . . . . . . . . . . . . . . . . 72 163 20.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . . . 73 164 20.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . . . 73 165 20.3. Interaction with External Routing Domains . . . . . . . . . . 74 166 20.4. Node Identity . . . . . . . . . . . . . . . . . . . . . . . . 74 167 21. Flow and congestion control . . . . . . . . . . . . . . . . . . 75 168 22. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 75 169 23. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 75 170 24. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . 76 171 25. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 77 172 26. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 173 1. Introduction 175 The Optimized Link State Routing Protocol (OLSR) is developed for 176 mobile ad hoc networks. It operates as a table driven, proactive 177 protocol, i.e exchanges topology information with other nodes of the 178 network regularly. Each node selects a set of its neighbor nodes as 179 "multipoint relays" (MPR). In OLSR, only nodes, selected as such 180 MPRs, are responsible for forwarding control traffic, intended for 181 diffusion into the entire network. MPRs provide an efficient mecha- 182 nism for flooding control traffic by reducing the number of transmis- 183 sions required. 185 Nodes, selected as MPRs, also have a special responsibility when 186 declaring link state information in the network. Indeed, the only 187 requirement for OLSR to provide shortest path routes to all destina- 188 tions is that MPR nodes declare link-state information for their MPR 189 selectors. Additional available link-state information may be uti- 190 lized, e.g. for redundancy. 192 Nodes which have been selected as multipoint relays by some neighbor 193 node(s) announce this information periodically in their control mes- 194 sages. Thereby a node announces to the network, that it has reacha- 195 bility to the nodes which have selected it as an MPR. In route cal- 196 culation, the MPRs are used to form the route from a given node to 197 any destination in the network. Furthermore, the protocol uses the 198 MPRs to facilitate efficient flooding of control messages in the net- 199 work. 201 A node selects MPRs from among its one hop neighbors with "symmetri- 202 cal", i.e. bi-directional, linkages. Therefore, selecting the route 203 through MPRs automatically avoids the problems associated with data 204 packet transfer over uni-directional links (such as the problem of 205 not getting link-layer acknowledgments for data packets at each hop, 206 for link-layers employing this technique for unicast traffic). 208 OLSR is developed to work independently from other protocols. Like- 209 wise, OLSR makes no assumptions about the underlying link-layer. 211 OLSR inherits the concept of forwarding and relaying from HIPERLAN (a 212 MAC layer protocol) which is standardized by ETSI [3]. The protocol 213 is developed in the IPANEMA project (part of the Euclid program) and 214 in the PRIMA project (part of the RNRT program). 216 1.1. Changes 218 Major changes from version 09 to version 10 220 - Designated editors included 222 - Flow-control section added 224 - Misc. editorial changes. 226 1.2. OLSR Terminology 228 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 229 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 230 document are to be interpreted as described in RFC2119 [5]. Addi- 231 tionally, this document uses the following terminology: 233 node 235 A MANET router which implements the Optimized Link State Rout- 236 ing protocol as specified in this document. 238 OLSR interface 240 A network device participating in a MANET running OLSR. A 241 node may have several OLSR interfaces, each interface assigned 242 an unique IP address. 244 non OLSR interface 246 A network device, not participating in a MANET running OLSR. 247 A node may have several non OLSR interfaces (wireless and/or 248 wired). Routing information from these interfaces MAY be 249 injected into the OLSR routing domain. 251 single OLSR interface node 253 A node which has a single OLSR interface, participating in an 254 OLSR routing domain. 256 multiple OLSR interface node 258 A node which has multiple OLSR interfaces, participating in an 259 OLSR routing domain. 261 main address 263 The main address of a node, which will be used in OLSR control 264 traffic as the "originator address" of all messages emitted by 265 this node. It is the address of one of the OLSR interfaces of 266 the node. 268 A single OLSR interface node MUST use the address of its only 269 OLSR interface as the main address. 271 A multiple OLSR interface node MUST choose one of its OLSR 272 interface addresses as its "main address" (equivalent of 273 "router ID" or "node identifier"). It is of no importance 274 which address is chosen, however a node SHOULD always use the 275 same address as its main address. 277 neighbor node 279 A node X is a neighbor node of node Y if node Y can hear node 280 X (i.e. a bidirectional link exists between an OLSR inter- 281 faces on node X and an OLSR interface on Y). 283 2-hop neighbor 285 A node heard by a neighbor. 287 strict 2-hop neighbor 289 a 2-hop neighbor which is not the node itself or a neighbor of 290 the node, and in addition is a neighbor of a neighbor, with 291 willingness different from WILL_NEVER, of the node. 293 multipoint relay (MPR) 295 A node which is selected by its one-hop neighbor, node X, to 296 "re-transmit" all the broadcast messages that it receives from 297 X, provided that the message is not a duplicate, and that the 298 time to live field of the message is greater than one. 300 multipoint relay selector (MPR selector, MS) 302 A node which has selected its one-hop neighbor, node X, as its 303 multipoint relay, will be called a multipoint relay selector 304 of node X. 306 link 308 A link is a pair of OLSR interfaces (from two different nodes) 309 susceptible to hear one another (i.e. one may be able to 310 receive traffic from the other). A node is said to have a 311 link to another node when one of its interface has a link to 312 one of the interfaces of the other node. 314 symmetric link 316 A verified bi-directional link between two OLSR interfaces. 318 asymmetric link 320 A link between two OLSR interfaces, verified in only one 321 direction. 323 symmetric 1-hop neighborhood 325 The symmetric 1-hop neighborhood of any node X is the set of 326 nodes which have at least one symmetric link to X. 328 symmetric 2-hop neighborhood 330 The symmetric 2-hop neighborhood of X is the set of nodes, 331 excluding X itself, which have a symmetric link to the sym- 332 metric 1-hop neighborhood of X. 334 symmetric strict 2-hop neighborhood 336 The symmetric 2-hop neighborhood of X is the set of nodes, 337 excluding X itself and its neighbors, which have a symmetric 338 link to some symmetric 1-hop neighbor, with willingness dif- 339 ferent of WILL_NEVER, of X. 341 1.3. Applicability 343 OLSR is a proactive routing protocol for mobile ad-hoc networks 344 (MANETs). It is well suited to large and dense mobile networks, as 345 the optimization achieved using the MPRs works well in this context. 346 The larger and more dense a network, the more optimization can be 347 achieved as compared to the classic link state algorithm. OLSR uses 348 hop-by-hop routing, i.e. each node uses its local information to 349 route packets. 351 OLSR is well suited for networks, where the traffic is random and 352 sporadic between a larger set of nodes rather than being almost 353 exclusively between a small specific set of nodes. As a proactive 354 protocol, OLSR is also suitable for scenarios where the communicating 355 pairs change over time: no additional control traffic is generated in 356 this situation since routes are maintained for all known destinations 357 at all times. 359 1.4. Protocol Overview 361 OLSR is a proactive routing protocol for mobile ad hoc networks. The 362 protocol inherits the stability of a link state algorithm and has the 363 advantage of having routes immediately available when needed due to 364 its proactive nature. OLSR is an optimization over the classical 365 link state protocol, tailored for mobile ad hoc networks. 367 OLSR minimizes the overhead from flooding of control traffic by using 368 only selected nodes, called MPRs, to retransmit control messages. 369 This technique significantly reduces the number of retransmissions 370 required to flood a message to all nodes in the network. Secondly, 371 OLSR requires only partial link state to be flooded in order to pro- 372 vide shortest path routes. The minimal set of link state information 373 required is, that all nodes, selected as MPRs, MUST declare the links 374 to their MPR selectors. Additional topological information, if 375 present, MAY be utilized e.g. for redundancy purposes. 377 OLSR MAY optimize the reactivity to topological changes by reducing 378 the maximum time interval for periodic control message transmission. 379 Furthermore, as OLSR continuously maintains routes to all destina- 380 tions in the network, the protocol is beneficial for traffic patterns 381 where a large subset of nodes are communicating with another large 382 subset of nodes, and where the [source, destination] pairs are chang- 383 ing over time. The protocol is particularly suited for large and 384 dense networks, as the optimization done using MPRs works well in 385 this context. The larger and more dense a network, the more opti- 386 mization can be achieved as compared to the classic link state algo- 387 rithm. 389 OLSR is designed to work in a completely distributed manner and does 390 not depend on any central entity. The protocol does NOT REQUIRE 391 reliable transmission of control messages: each node sends control 392 messages periodically, and can therefore sustain a reasonable loss of 393 some such messages. Such losses occur frequently in radio networks 394 due to collisions or other transmission problems. 396 Also, OLSR does not require sequenced delivery of messages. Each 397 control message contains a sequence number which is incremented for 398 each message. Thus the recipient of a control message can, if 399 required, easily identify which information is more recent - even if 400 messages have been re-ordered while in transmission. 402 Furthermore, OLSR provides support for protocol extensions such as 403 sleep mode operation, multicast-routing etc. Such extensions may be 404 introduced as additions to the protocol without breaking backwards 405 compatibility with earlier versions. 407 OLSR does not require any changes to the format of IP packets. Thus 408 any existing IP stack can be used as is: the protocol only interacts 409 with routing table management. 411 1.5. Multipoint Relays 413 The idea of multipoint relays is to minimize the overhead of flooding 414 messages in the network by reducing redundant retransmissions in the 415 same region. Each node in the network selects a set of nodes in its 416 symmetric 1-hop neighborhood which may retransmit its messages. This 417 set of selected neighbor nodes is called the "Multipoint Relay" (MPR) 418 set of that node. The neighbors of node N which are *NOT* in its MPR 419 set, receive and process broadcast messages but do not retransmit 420 broadcast messages received from node N. 422 Each node selects its MPR set from among its one hop symmetric neigh- 423 bors. This set is selected such that it covers (in terms of radio 424 range) all symmetric strict 2-hop nodes. The MPR set of N, denoted 425 as MPR(N), is then an arbitrary subset of the symmetric 1-hop neigh- 426 borhood of N which satisfies the following condition: every node in 427 the symmetric strict 2-hop neighborhood of N must have a symmetric 428 link towards MPR(N). The smaller a MPR set, the less control traffic 429 overhead results from the routing protocol. [2] gives an analysis 430 and example of MPR selection algorithms. 432 Each node maintains information about the set of neighbors that have 433 selected it as MPR. This set is called the "Multipoint Relay Selec- 434 tor set" (MPR selector set) of a node. A node obtains this informa- 435 tion from periodic HELLO messages received from the neighbors. 437 A broadcast message, intended to be diffused in the whole network, 438 coming from any of the MPR selectors of node N is assumed to be 439 retransmitted by node N, if N has not received it yet. This set can 440 change over time (i.e. when a node selects another MPR-set) and is 441 indicated by the selector nodes in their HELLO messages. 443 2. Protocol Functioning 445 This section outlines the overall protocol functioning. 447 OLSR is modularized into a "core" of functionality, which is always 448 required for the protocol to operate, and a set of auxiliary func- 449 tions. 451 The core specifies, in its own right, a protocol able to provide 452 routing in a stand-alone MANET. 454 Each auxiliary function provides additional functionality, which may 455 be applicable in specific scenarios. E.g. in case a node is provid- 456 ing connectivity between the MANET and another routing domain. 458 All auxiliary functions are compatible, to the extent where any 459 (sub)set of auxiliary functions may be implemented with the core. 460 Furthermore, the protocol allows heterogeneous nodes, i.e. nodes 461 which implement different subsets of the auxiliary functions, to 462 coexist in the network. 464 The purpose of dividing the functioning of OLSR into a core function- 465 ality and a set of auxiliary functions is to provide a simple and 466 easy-to-comprehend protocol, and to provide a way of only adding com- 467 plexity where specific additional functionality is required. 469 2.1. Core Functioning 471 The core functionality of OLSR specifies the behavior of a node, 472 equipped with OLSR interfaces participating in the MANET and running 473 OLSR as routing protocol. This includes a universal specification of 474 OLSR protocol messages and their transmission through the network, as 475 well as link sensing, topology diffusion and route calculation. 477 Specifically, the core is made up from the following components: 479 Packet Format and Forwarding 481 An universal specification of the packet format and an opti- 482 mized flooding mechanism serves as the transport mechanism for 483 all OLSR control traffic. 485 Link Sensing 486 Link Sensing is accomplished through periodic emission of 487 HELLO messages over the interfaces through which connectivity 488 is checked. A separate HELLO message is generated for each 489 interface and emitted in correspondence with the provisions in 490 section 7. 492 Resulting from Link Sensing is a local link set, describing 493 links between "local interfaces" and "remote interfaces" - 494 i.e. interfaces on neighbor nodes. 496 If sufficient information is provided by the link-layer, this 497 may be utilized to populate the local link set instead of 498 HELLO message exchange. 500 Neighbor detection 502 Given a network with only single interface nodes, a node may 503 deduct the neighbor set directly from the information 504 exchanged as part of link sensing: the "main address" of a 505 single interface node is, by definition, the address of the 506 only interface on that node. 508 In a network with multiple interface nodes, additional infor- 509 mation is required in order to map interface addresses to main 510 addresses (and, thereby, to nodes). This additional informa- 511 tion is acquired through multiple interface declaration (MID) 512 messages, described in section 5. 514 MPR Selection and MPR Signaling 516 The objective of MPR selection is for a node to select a sub- 517 set of its neighbors such that a broadcast message, retrans- 518 mitted by these selected neighbors, will be received by all 519 nodes 2 hops away. The MPR set of a node is computed such 520 that it, for each interface, satisfies this condition. The 521 information required to perform this calculation is acquired 522 throuth the periodic exchange of HELLO messages, as described 523 in section 6. MPR selection procedures are 524 detailed in section 8.3. 526 MPR signaling is provided in correspondence with the provi- 527 sions in the section 6. 529 Topology Control Message Diffusion 530 Topology Control messages are diffused with the purpose of 531 providing each node in the network with sufficient link-state 532 information to allow route calculation. Topology Control mes- 533 sages are diffused in correspondence with the provisions in 534 section 9. 536 Route Calculation 538 Given the link state information acquired through periodic 539 message exchange, as well as the interface configuration of 540 the nodes, the routing table for each node can be computed. 541 This is detailed in section 10 543 The key notion for these mechanisms is the MPR relationship. 545 The following table specifies the component of the core functionality 546 of OLSR, as well as their relations to this document. 548 Feature | Section 549 ------------------------------+-------------- 550 Packet format and forwarding | 3 551 Information repositories | 4 552 Main addr and multiple if. | 5 553 Hello messages | 6 554 Link sensing | 7 555 Neighbor detection | 8 556 Topology discovery | 9 557 Routing table computation | 10 558 Node configuration | 11 560 2.2. Auxiliary Functioning 562 In addition to the core functioning of OLSR, there are situations 563 where additional functionality is desired. This includes situations 564 where a node has multiple interfaces, some of which participate in 565 another routing domain, where the programming interface to the net- 566 working hardware provides additional information in form of link- 567 layer notifications and where it is desired to provide redundant 568 topological information to the network on expense of protocol over- 569 head. 571 The following table specifies auxiliary functions and their relation 572 to this document. 574 Feature | Section 575 ------------------------------+-------------- 576 Non-OLSR interfaces | 12 577 Link-layer notifications | 13 578 Advanced link sensing | 14 579 Redundant topology | 15 580 Redundant MPR flooding | 16 582 The interpretation of the above table is as follows: if the feature 583 listed is required, it SHOULD be provided as specified in the corre- 584 sponding section. 586 3. Packet Format and Forwarding 588 OLSR communicates using a unified packet format for all data related 589 to the protocol. The purpose of this is to facilitate extensibility 590 of the protocol without breaking backwards compatibility. This also 591 provides an easy way of piggybacking different "types" of information 592 into a single transmission, and thus for a given implementation to 593 optimize towards utilizing the maximal frame-size, provided by the 594 network. These packets are embedded in UDP datagrams for transmis- 595 sion over the network. The present draft is presented with IPv4 596 addresses. Considerations regarding IPv6 are given in section 597 17. 599 Each packet encapsulates one or more messages. The messages share a 600 common header format, which enables nodes to correctly accept and (if 601 applicable) retransmit messages of an unknown type. 603 Messages can be flooded onto the entire network, or flooding can be 604 limited to nodes within a diameter (in terms of number of hops) from 605 the originator of the message. Thus transmitting a message to the 606 neighborhood of a node is just a special case of flooding. When 607 flooding any control message, duplicate retransmissions will be elim- 608 inated locally (i.e. each node maintains a duplicate set to prevent 609 transmitting the same OLSR control message twice) and minimized in 610 the entire network through the usage of MPRs as described in later 611 sections. 613 Furthermore, a node can examine the header of a message to obtain 614 information on the distance (in terms of number of hops) to the orig- 615 inator of the message. This feature may be useful in situations 616 where, e.g., the time information from a received control messages 617 stored in a node depends on the distance to the originator. 619 3.1. Protocol and Port Number 621 Packets in OLSR are communicated using UDP. Port 698 has been 622 assigned by IANA for exclusive usage by the OLSR protocol. 624 3.2. Main Address 626 For a node with one interface, the main address of a node, as defined 627 in "OLSR Terminology", MUST be set to the address of that interface. 629 3.3. Packet Format 631 The basic layout of any packet in OLSR is as follows (omitting IP and 632 UDP headers): 634 0 1 2 3 635 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 636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 637 | Packet Length | Packet Sequence Number | 638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 639 | Message Type | Vtime | Message Size | 640 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 641 | Originator Address | 642 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 643 | Time To Live | Hop Count | Message Sequence Number | 644 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 645 | | 646 : MESSAGE : 647 | | 648 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 649 | Message Type | Vtime | Message Size | 650 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 651 | Originator Address | 652 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 653 | Time To Live | Hop Count | Message Sequence Number | 654 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 655 | | 656 : MESSAGE : 657 | | 658 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 659 : : 660 (etc) 662 3.3.1. Packet Header 664 Packet Length 666 The length (in bytes) of the packet 668 Packet Sequence Number 670 The Packet Sequence Number (PSN) MUST be incremented by one 671 each time a new OLSR packet is transmitted. "Wrap-around" is 672 handled as described in section 19. A separate Packet 673 Sequence Number is maintained for each interface such that 674 packets transmitted over an interface are sequentially enumer- 675 ated. 677 The IP address of the interface over which a packet was transmitted 678 is obtainable from the IP header of the packet. 680 If the packet contains no messages (i.e. the Packet Length is less 681 than or equal to the size of the packet header), the packet MUST 682 silently be discarded. 684 For IPv4 addresses, this implies that packets, where the Packet 685 Length < 16 MUST silently be discarded. 687 3.3.2. Message Header 689 Message Type 691 This field indicates which type of message is to be found in 692 the "MESSAGE" part. Message types in the range of 0-127 are 693 reserved for messages in this document and in possible exten- 694 sions. 696 Vtime 698 This field indicates for how long time after reception a node 699 MUST consider the information contained in the message as 700 valid, unless a more recent update to the information is 701 received. The validity time is represented by its mantissa 702 (four highest bits of Vtime field) and by its exponent (four 703 lowest bits of Vtime field). In other words: 705 validity time = C*(1+a/16)* 2^b [in seconds] 707 where a is the integer represented by the four highest bits of 708 Vtime field and b the integer represented by the four lowest 709 bits of Vtime field. The proposed value of the scaling factor 710 C is specified in section 18. 712 Message Size 714 This field gives the size of this message, counted in bytes 715 and measured from the beginning of the "Message Type" field 716 and until the beginning of the next "Message Type" field (or - 717 if there are no following messages - until the end of the 718 packet). 720 Originator Address 722 This field contains the main address of the node, which has 723 originally generated this message. This field SHOULD NOT be 724 confused with the source address from the IP header, which is 725 changed each time to the address of the intermediate interface 726 which is re-transmitting this message. The Originator Address 727 field MUST *NEVER* be changed in retransmissions. 729 Time To Live 731 This field contains the maximum number of hops a message will 732 be transmitted. Before a message is retransmitted, the Time 733 To Live MUST be decremented by 1. When a node receives a mes- 734 sage with a Time To Live equal to 0 or 1, the message MUST NOT 735 be retransmitted under any circumstances. Normally, a node 736 would not receive a message with a TTL of zero. 738 Thus, by setting this field, the originator of a message can 739 limit the flooding radius. 741 Hop Count 743 This field contains the number of hops a message has attained. 744 Before a message is retransmitted, the Hop Count MUST be 745 incremented by 1. 747 Initially, this is set to '0' by the originator of the mes- 748 sage. 750 Message Sequence Number 752 While generating a message, the "originator" node will assign 753 a unique identification number to each message. This number 754 is inserted into the Sequence Number field of the message. 755 The sequence number is increased by 1 (one) for each message 756 originating from the node. "Wrap-around" is handled as 757 described in section 19. Message sequence numbers are 758 used to ensure that a given message is not retransmitted more 759 than once by any node. 761 3.4. Packet Processing and Message Flooding 763 Upon receiving a basic packet, a node examines each of the "message 764 headers". Based on the value of the "Message Type" field, the node 765 can determine the fate of the message. A node may receive the same 766 message several times. Thus, to avoid re-processing of some messages 767 which were already received and processed, each node maintains a 768 Duplicate Set. In this set, the node records information about the 769 most recently received messages where duplicate processing of a mes- 770 sage is to be avoided. For such a message, a node records a "Dupli- 771 cate Tuple" (D_addr, D_seq_num, D_retransmitted, D_iface_list, 772 D_time), where D_addr is the originator address of the message, 773 D_seq_num is the message sequence number of the message, D_retrans- 774 mitted is a boolean indicating whether the message has been already 775 retransmitted, D_iface_list is a list of the addresses of the inter- 776 faces on which the message has been received and D_time specifies the 777 time at which a tuple expires and *MUST* be removed. 779 In a node, the set of Duplicate Tuples are denoted the "Duplicate 780 set". 782 In this section, the term "Originator Address" will be used for the 783 main address of the node which sent the message. The term "Sender 784 Interface Address" will be used for the sender address (given in the 785 IP header of the packet containing the message) of the interface 786 which sent the message. The term "Receiving Interface Address" will 787 be used for the address of the interface of the node which received 788 the message. 790 Thus, upon receiving a basic packet, a node MUST perform the follow- 791 ing tasks for each encapsulated message: 793 1 If the packet contains no messages (i.e. the Packet Length is 794 less than or equal to the size of the packet header), the 795 packet MUST silently be discarded. 797 For IPv4 addresses, this implies that packets, where the 798 Packet Length < 16 MUST silently be discarded. 800 2 If the time to live of the message is less than or equal to 801 '0' (zero), or if the message was sent by the receiving node 802 (i.e. the Originator Address of the message is the main 803 address of the receiving node): the message MUST silently be 804 dropped. 806 3 Processing condition: 808 3.1 if there exists a tuple in the duplicate set, where: 810 D_addr == Originator Address, AND 812 D_seq_num == Message Sequence Number 814 then the message has already been completely processed 815 and MUST not be processed again. 817 3.2 Otherwise, if the node implements the Message Type of the 818 message, the message MUST be processed according to the 819 specifications for the message type. 821 4 Forwarding condition: 823 4.1 if there exists a tuple in the duplicate set, where: 825 D_addr == Originator Address, AND 827 D_seq_num == Message Sequence Number, 828 AND 830 the receiving interface (address) is 831 in D_iface_list 833 then the message has already been considered for forward- 834 ing and SHOULD NOT be retransmitted again. 836 4.2 Otherwise: 838 4.2.1 839 If the node implements the Message Type of the 840 message, the message MUST be considered for 841 forwarding according to the specifications for 842 the message type. 844 4.2.2 845 Otherwise, if the node does not implement the 846 Message Type of the message, the message SHOULD 847 be processed according to the default forward- 848 ing algorithm described below. 850 3.4.1. Default Forwarding Algorithm 852 The default forwarding algorithm is the following: 854 1 If the sender interface address of the message is not detected 855 to be in the symmetric 1-hop neighborhood of the node, the 856 forwarding algorithm MUST silently stop here (and the message 857 MUST NOT be forwarded). 859 2 If there exists a tuple in the duplicate set where: 861 D_addr == Originator Address 863 D_seq_num == Message Sequence Number 865 Then the message will be further considered for forwarding if 866 and only if: 868 D_retransmitted is false, AND 870 the (address of the) interface which received the message 871 is not included among the addresses in D_iface_list 873 3 Otherwise, if such an entry doesn't exist, the message is fur- 874 ther considered for forwarding. 876 If after those steps, the message is not considered for forwarding, 877 then the processing of this section stops (i.e. steps 4 to 8 are 878 ignored), otherwise, if it is still considered for forwarding then 879 the following algorithm is used: 881 4 If the sender interface address is an interface address of a 882 MPR selector of this node and if the time to live of the mes- 883 sage is greater than '1', the message MUST be retransmitted 884 (as described later in steps 6 to 8). 886 5 If an entry in the duplicate set exists, with same Originator 887 Address, and same Message Sequence Number, the entry is 888 updated as follows: 890 D_time = current time + DUP_HOLD_TIME. 892 The receiving interface (address) is added to 893 D_iface_list. 895 D_retransmitted is set to true if and only if the message 896 will be retransmitted according to step 4. 898 Otherwise an entry in the duplicate set is recorded with: 900 D_addr = Originator Address 902 D_seq_num = Message Sequence Number 904 D_time = current time + DUP_HOLD_TIME. 906 D_iface_list contains the receiving interface address. 908 D_retransmitted is set to true if and only if the message 909 will be retransmitted according to step 4. 911 If, and only if, according to step 4, the message must be retransmit- 912 ted then: 914 6 The TTL of the message is reduced by one. 916 7 The hop-count of the message is increased by one 918 8 The message is broadcast on all interfaces (Notice: The 919 remaining fields of the message header SHOULD be left unmodi- 920 fied.) 922 3.4.2. Considerations on Processing and Forwarding 924 It should be noted that processing and forwarding messages are two 925 different actions, conditioned by different rules. Processing 926 relates to using the content of the messages, while forwarding is 927 related to retransmitting the same message for other nodes of the 928 network. 930 Notice that this specification includes a description for both the 931 forwarding and the processing of each known message type. Messages 932 with known message types MUST *NOT* be forwarded "blindly" by this 933 algorithm. Forwarding (and setting the correct message header in the 934 forwarded, known, message) is the responsibility of the algorithm 935 specifying how the message is to be handled and, if necessary, 936 retransmitted. This enables a message type to be specified such that 937 the message can be modified while in transit (e.g. to reflect the 938 route the message has taken). It also enables bypassing of the MPR 939 flooding mechanism if for some reason classical flooding of a message 940 type is required, the algorithm which specifies how such messages 941 should be handled will simply rebroadcast the message, regardless of 942 MPRs. 944 By defining a set of message types, which MUST be recognized by all 945 implementations of OLSR, it will be possible to extend the protocol 946 through introduction of additional message types, while still being 947 able to maintain compatibility with older implementations. The 948 REQUIRED message types for the core functionality of OLSR are: 950 - HELLO-messages, performing the task of link sensing, neighbor 951 detection and MPR signaling, 953 - TC-messages, performing the task of topology declaration 954 (advertisement of link states). 956 - MID-messages, performing the task of declaring the presence of 957 multiple interfaces on a node. 959 Other message types include those specified in later sections, as 960 well as possible future extensions such as messages enabling power 961 conservation / sleep mode, multicast routing, support for unidirec- 962 tional links, auto-configuration/address assignment etc. 964 3.5. Message Emission and Jitter 966 As a basic implementation requirement, synchronization of control 967 messages SHOULD be avoided. As a consequence, OLSR control messages 968 SHOULD be emitted such that they avoid synchronization. 970 Emission of control traffic from neighboring nodes may, for various 971 reasons (mainly timer interactions with packet processing), become 972 synchronized such that several neighbor nodes attempt to transmit 973 control traffic simultaneously. Depending on the nature of the 974 underlying link-layer, this may or may not lead to collisions and 975 hence message loss - possibly loss of several subsequent messages of 976 the same type. 978 To avoid such synchronizations, the following simple strategy for 979 emitting control messages is proposed. A node MAY add an amount of 980 jitter to the interval at which messages are generated. The jitter 981 must be a random value for each message generated. Thus, for a node 982 utilizing jitter: 984 Actual message interval = MESSAGE_INTERVAL - jitter 986 Where jitter is a value, randomly selected from the interval 987 [0,MAXJITTER] and MESSAGE_INTERVAL is the value of the message inter- 988 val specified for the message being emitted (e.g. HELLO_INTERVAL for 989 HELLO messages, TC_INTERVAL for TC-messages etc.). 991 Jitter MAY also be introduced when forwarding messages. The follow- 992 ing simple strategy may be adopted: when a message is to be forwarded 993 by a node, it should be kept in the node during a short period of 994 time : 996 Keep message period = jitter 998 Where jitter is a random value in [0,MAXJITTER]. 1000 Notice that when the node sends a control message, the opportunity to 1001 piggyback other messages (before their keeping period is expired) may 1002 be taken to reduce the number of packet transmissions. 1004 Notice, that a minimal rate of control messages is imposed. A node 1005 MAY send control messages at a higher rate, if beneficial for a spe- 1006 cific deployment. 1008 4. Information Repositories 1010 Through the exchange of OLSR control messages, each node accumulates 1011 information about the network. This information is stored according 1012 to the descriptions in this section. 1014 4.1. Multiple Interface Association Information Base 1016 For each destination in the network, "Interface Association Tuples" 1017 (I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an 1018 interface address of a node, I_main_addr is the main address of this 1019 node. I_time specifies the time at which this tuple expires and 1020 *MUST* be removed. 1022 In a node, the set of Interface Association Tuples is denoted the 1023 "Interface Association Set". 1025 4.2. Link Sensing: Local Link Information Base 1027 The local link information base stores information about links to 1028 neighbors. 1030 4.2.1. Link Set 1032 A node records a set of "Link Tuples" (L_local_iface_addr, L_neigh- 1033 bor_iface_addr, L_SYM_time, L_ASYM_time, L_time). L_local_iface_addr 1034 is the interface address of the local node (i.e. one endpoint of the 1035 link), L_neighbor_iface_addr is the interface address of the neighbor 1036 node (i.e. the other endpoint of the link), L_SYM_time is the time 1037 until which the link is considered symmetric, L_ASYM_time is the time 1038 until which the neighbor interface is considered heard, and L_time 1039 specifies the time at which this record expires and *MUST* be 1040 removed. When L_SYM_time and L_ASYM_time are expired, the link is 1041 considered lost. 1043 This information is used when declaring the neighbor interfaces in 1044 the HELLO messages. 1046 L_SYM_time is used to decide the Link Type declared for the neighbor 1047 interface. If L_SYM_time is not expired, the link MUST be declared 1048 symmetric. If L_SYM_time is expired, the link MUST be declared asym- 1049 metric. If both L_SYM_time and L_ASYM_time are expired, the link 1050 MUST be declared lost. 1052 In a node, the set of Link Tuples are denoted the "Link Set". 1054 4.3. Neighbor Detection: Neighborhood Information Base 1056 The neighborhood information base stores information about neighbors, 1057 2-hop neighbors, MPRs and MPR selectors. 1059 4.3.1. Neighbor Set 1061 A node records a set of "neighbor tuples" (N_neighbor_main_addr, 1062 N_status, N_willingness), describing symmetric neighbors. N_neigh- 1063 bor_main_addr is the main address of a neighbor, N_status specifies 1064 if the node is NOT_SYM or SYM. N_willingness in an integer between 0 1065 and 7, and specifies a nodes willingness to carry traffic on behalf 1066 of other nodes. 1068 4.3.2. 2-hop Neighbor Set 1070 A node records a set of "2-hop tuples" (N_neighbor_main_addr, 1071 N_2hop_addr, N_time), describing symmetric (and, since MPR links by 1072 definition are also symmetric, thereby also MPR) links between its 1073 neighbors and the symmetric 2-hop neighborhood. N_neighbor_main_addr 1074 is the main address of a neighbor, N_2hop_addr is the main address of 1075 a 2-hop neighbor with a symmetric link to N_neighbor_main_addr, and 1076 N_time specifies the time at which the tuple expires and *MUST* be 1077 removed. 1079 In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor 1080 Set". 1082 4.3.3. MPR Set 1084 A node maintains a set of neighbors which are selected as MPR. Their 1085 main addresses are listed in the MPR Set. 1087 4.3.4. MPR Selector Set 1089 A node records a set of MPR-selector tuples (MS_main_addr, MS_time), 1090 describing the neighbors which have selected this node as a MPR. 1091 MS_main_addr is the main address of a node, which has selected this 1092 node as MPR. MS_time specifies the time at which a tuple expires and 1093 *MUST* be removed. 1095 In a node, the set of MPR-selector tuples are denoted the "MPR Selec- 1096 tor Set". 1098 4.4. Topology Information Base 1100 Each node in the network maintains topology information about the 1101 network. This information is acquired from TC-messages and is used 1102 for routing table calculations. 1104 Thus, for each destination in the network, at least one "Topology 1105 Tuple" (T_dest_addr, T_last_addr, T_seq, T_time) is recorded. 1106 T_dest_addr is the main address of a node, which may be reached in 1107 one hop from the node with the main address T_last_addr. Typically, 1108 T_last_addr is a MPR of T_dest_addr. T_seq is a sequence number, and 1109 T_time specifies the time at which this tuple expires and *MUST* be 1110 removed. 1112 In a node, the set of Topology Tuples are denoted the "Topology Set". 1114 5. Main Addresses and Multiple Interfaces 1116 For single OLSR interface nodes, the relationship between an OLSR 1117 interface address and the corresponding main address is trivial: the 1118 main address is the OLSR interface address. For multiple OLSR inter- 1119 face nodes, the relationship between OLSR interface addresses and 1120 main addresses is defined through the exchange of Multiple Interface 1121 Declaration (MID) messages. This section describes how MID messages 1122 are exchanged and processed. 1124 Each node with multiple interfaces MUST announce, periodically, 1125 information describing its interface configuration to other nodes in 1126 the network. This is accomplished through flooding a Multiple Inter- 1127 face Declaration message to all nodes in the network through the MPR 1128 flooding mechanism. 1130 Each node in the network maintains interface information about the 1131 other nodes in the network. This information acquired from MID-mes- 1132 sages, emitted by nodes with multiple interfaces participating in the 1133 MANET, and is used for routing table calculations. 1135 Specifically, multiple interface declaration associates multiple 1136 interfaces to a node (and to a main address) through populating the 1137 multiple interface association base in each node. 1139 5.1. MID Message Format 1141 The proposed format of a MID message is as follows: 1143 0 1 2 3 1144 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 1145 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1146 | OLSR Interface Address | 1147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1148 | OLSR Interface Address | 1149 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1150 | ... | 1151 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1153 This is sent as the data-portion of the general packet format 1154 described in section 3.4, with the "Message Type" set to 1155 MID_MESSAGE. The time to live SHOULD be set to 255 (maximum value) 1156 to diffuse the message into the entire network and Vtime set accord- 1157 ingly to the value of MID_HOLD_TIME, as specified in section 1158 18.3. 1160 OLSR Interface Address 1162 This field contains the address of an OLSR interface of the 1163 node, excluding the nodes main address (which already indi- 1164 cated in the originator address). 1166 All interface addresses other than the main address of the originator 1167 node are put in the MID message. If the maximum allowed message size 1168 (as imposed by the network) is reached while there are still inter- 1169 face addresses which have not been inserted into the MID-message, 1170 more MID messages are generated until the entire interface addresses 1171 set has been sent. 1173 5.2. MID Message Generation 1175 A MID message is sent by a node in the network to declare its multi- 1176 ple interfaces (if any). I.e., the MID message contains the list of 1177 interface addresses which are associated to its main address. The 1178 list of addresses can be partial in each MID message (e.g. due to 1179 message size limitations, imposed by the network), but parsing of all 1180 MID messages describing the interface set from a node MUST be com- 1181 plete within a certain refreshing period (MID_INTERVAL). The infor- 1182 mation diffused in the network by these MID messages will help each 1183 node to calculate its routing table. A node which has only a single 1184 interface address participating in the MANET (i.e. running OLSR), 1185 MUST NOT generate any MID message. 1187 A node with more interfaces, where only one is participating in the 1188 MANET and running OLSR (e.g. a node is connected to a wired network 1189 as well as to a MANET) MUST NOT generate any MID messages. 1191 A node with more interfaces, where more than one is participating in 1192 the MANET and running OLSR MUST generate MID messages as specified. 1194 5.3. MID Message Forwarding 1196 MID messages are broadcast and retransmitted by the MPRs in order to 1197 diffuse the messages in the entire network. The "default forwarding 1198 algorithm" (described in section 3.4) MUST be used for for- 1199 warding of MID messages. 1201 5.4. MID Message Processing 1203 The tuples in the multiple interface association set are recorded 1204 with the information that is exchanged through MID messages. 1206 Upon receiving a MID message, the "validity time" MUST be computed 1207 from the Vtime field of the message header (as described in section 1208 3.3.2). The Multiple Interface Association Information Base 1209 SHOULD then be updated as follows: 1211 1 If the sender interface (NB: not originator) of this message 1212 is not in the symmetric 1-hop neighborhood of this node, the 1213 message MUST be discarded. 1215 2 For each interface address listed in the MID message: 1217 2.1 If there exist some tuple in the interface association 1218 set where: 1220 I_iface_addr == interface address, AND 1222 I_main_addr == originator address, 1224 then the holding time of that tuple is set to: 1226 I_time = current time + validity time. 1228 2.2 Otherwise, a new tuple is recorded in the interface asso- 1229 ciation set where: 1231 I_iface_addr = interface address, 1233 I_main_addr = originator address, 1235 I_time = current time + validity time. 1237 5.5. Resolving a Main Address from an Interface Address 1239 In general, the only part of OLSR requiring use of "interface 1240 addresses" is link sensing. The remaining parts of OLSR operate on 1241 nodes, uniquely identified by their "main addresses" (effectively, 1242 the main address of a node is its "node id" - which for convenience 1243 corresponds to the address of one of its interfaces). In a network 1244 with only single interface nodes, the main address of a node will, by 1245 definition, be equal to the interface address of the node. In net- 1246 works with multiple interface nodes operating within a common OLSR 1247 area, it is required to be able to map any interface address to the 1248 corresponding main address. 1250 The exchange of MID messages provides a way in which interface infor- 1251 mation is acquired by nodes in the network. This permits identifica- 1252 tion of a nodes "main address", given one of its interface addresses. 1254 Given an interface address: 1256 1 if there exists some tuple in the interface association set 1257 where: 1259 I_iface_addr == interface address 1261 then the result of the main address search is the originator 1262 address I_main_addr of the tuple. 1264 2 Otherwise, the result of the main address search is the inter- 1265 face address itself. 1267 6. HELLO Message Format and Generation 1269 A common mechanism is employed for populating the local link informa- 1270 tion base and the neighborhood information base, namely periodic 1271 exchange of HELLO messages. Thus this section describes the general 1272 HELLO message mechanism, followed by a description of link sensing 1273 and topology detection, respectively. 1275 6.1. HELLO Message Format 1277 To accommodate for link sensing, neighborhood detection and MPR 1278 selection signalling, as well as to accommodate for future exten- 1279 sions, an approach similar to the overall packet format is taken. 1280 Thus the proposed format of a HELLO message is as follows: 1282 0 1 2 3 1283 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 1285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1286 | Reserved | Htime | Willingness | 1287 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1288 | Link Code | Reserved | Link Message Size | 1289 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1290 | Neighbor Interface Address | 1291 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1292 | Neighbor Interface Address | 1293 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1294 : . . . 1295 : 1296 : : 1297 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1298 | Link Code | Reserved | Link Message Size | 1299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1300 | Neighbor Interface Address | 1301 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1302 | Neighbor Interface Address | 1303 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1304 : : 1305 : : 1306 (etc) 1308 This is sent as the data-portion of the general packet format 1309 described in section 3.4, with the "Message Type" set to 1310 HELLO_MESSAGE, the TTL field set to 1 (one) and Vtime set accordingly 1311 to the value of NEIGHB_HOLD_TIME, specified in section 18.3. 1313 Reserved 1315 This field must be set to "0000000000000" to be in compliance 1316 with this specification. 1318 HTime 1320 This field specifies the HELLO emission interval used by the 1321 node on this particular interface, i.e. the time before the 1322 transmission of the next HELLO (this information may be used 1323 in advanced link sensing, see section 14). The 1324 HELLO emission interval is represented by its mantissa (four 1325 highest bits of Htime field) and by its exponent (four lowest 1326 bits of Htime field). In other words: 1328 HELLO emission interval=C*(1+a/16)*2^b [in seconds] 1330 where a is the integer represented by the four highest bits of 1331 Htime field and b the integer represented by the four lowest 1332 bits of Htime field. The proposed value of the scaling factor 1333 C is specified in section 18. 1335 Willingness 1337 This field specifies the willingness of a node to carry and 1338 forward traffic for other nodes. 1340 A node with willingness WILL_NEVER (see section 18.8, for 1341 willingness constants) MUST never be selected as MPR by any 1342 node. A node with willingness WILL_ALWAYS MUST always be 1343 selected as MPR. By default, a node SHOULD advertise a will- 1344 ingness of WILL_DEFAULT. 1346 Link Code 1348 This field specifies informations about the link between the 1349 interface of the sender and the following list of neighbor 1350 interfaces. It also specifies informations about the status 1351 of the neighbor. 1353 Link codes, not known by a node, are silently discarded. 1355 Link Message Size 1357 The size of the link message, counted in bytes and measured 1358 from the beginning of the "Link Code" field and until the next 1359 "Link Code" field (or - if there are no more link types - the 1360 end of the message). 1362 Neighbor Interface Address 1364 An address of the interface of a neighbor node. 1366 6.1.1. Link Code as Link Type and Neighbor Type 1368 This document only specifies processing of Link Codes < 16. 1370 If the Link Code value is less or equal to 15, then it MUST be inter- 1371 preted as holding two different fields, of two bits each: 1373 7 6 5 4 3 2 1 0 1374 +-------+-------+-------+-------+-------+-------+-------+-------+ 1375 | 0 | 0 | 0 | 0 | Neighbor Type | Link Type | 1376 +-------+-------+-------+-------+-------+-------+-------+-------+ 1378 The following four "Link Types" are REQUIRED by OLSR: 1380 - UNSPEC_LINK - indicating that no specific information about 1381 the links is given. 1383 - ASYM_LINK - indicating that the links are asymmetric (i.e. 1384 the neighbor interface is "heard"). 1386 - SYM_LINK - indicating that the links are symmetric with the 1387 interface. 1389 - LOST_LINK - indicating that the links have been lost. 1391 The following three "Neighbor Types" are REQUIRED by OLSR: 1393 - SYM_NEIGH - indicating that the neighbors have at least one 1394 symmetrical link with this node. 1396 - MPR_NEIGH - indicating that the neighbors have at least one 1397 symmetrical link AND have been been selected as MPR by the 1398 sender. 1400 - NOT_NEIGH - indicating that the nodes are either no longer or 1401 have not yet become symmetrical neighbors. 1403 Note that an implementation should be careful in not confusing Link 1404 Type with Neighbor Type nor the constants (confusing SYM_NEIGH with 1405 SYM_LINK for instance). 1407 A link code advertising: 1409 Link Type == SYM_LINK AND 1411 Neighbor Type == NOT_NEIGH 1413 is invalid, and any links adverticed as such MUST be silently dis- 1414 carded without any processing. 1416 Likewise a Neighbor Type field advertising a numerical value which is 1417 not one of the constants SYM_NEIGH, MPR_NEIGH, NOT_NEIGH, is invalid, 1418 and any links adverticed as such MUST be silently discarded without 1419 any processing. 1421 6.2. HELLO Message Generation 1423 This involves transmitting the Link Set, the Neighbor Set and the MPR 1424 Set. In principle, a HELLO message serves three independent tasks: 1426 - link sensing 1428 - neighbor detection 1430 - MPR selection signaling 1432 Three tasks are all are based on periodic information exchange within 1433 a nodes neighborhood, and serve the common purpose of "local topology 1434 discovery". A HELLO message is therefore generated based on the 1435 information stored in the Local Link Set, the Neighbor Set and the 1436 MPR Set from the local link information base. 1438 A node must perform link sensing on each interface, in order to 1439 detect links between the interface and neighbor interfaces. Further- 1440 more, a node must advertise its entire symmetric 1-hop neighborhood 1441 on each interface in order to perform neighbor detection. Hence, for 1442 a given interface, a HELLO message will contain a list of links on 1443 that interface (with associated link types), as well as a list of the 1444 entire neighborhood (with an associated neighbor types). 1446 The Vtime field is set such that it corresponds to the value of the 1447 node's NEIGHB_HOLD_TIME parameter. The Htime field is set such that 1448 it corresponds to the value of the node's HELLO_INTERVAL parameter 1449 (see section 18.3). 1451 The Willingness field is set such that it corresponds to the node's 1452 willingness to forward traffic on behalf of other nodes (see section 1453 18.8). A node MUST advertise the same willingness on all 1454 interfaces. 1456 The lists of addresses declared in a HELLO message is a list of 1457 neighbor interface addresses computed as follows: 1459 For each tuple in the Link Set, where L_local_iface_addr is the 1460 interface where the HELLO is to be transmitted, and where L_time >= 1461 current time (i.e. not expired), L_neighbor_iface_addr is advertised 1462 with: 1464 1 The Link Type set according to the following: 1466 1.1 if L_SYM_time >= current time (not expired) 1468 Link Type = SYM_LINK 1470 1.2 Otherwise, if L_ASYM_time >= current time (not expired) 1471 AND 1473 L_SYM_time < current time (expired) 1475 Link Type = ASYM_LINK 1477 1.3 Otherwise, if L_ASYM_time < current time (expired) AND 1479 L_SYM_time < current time (expired) 1481 Link Type = LOST_LINK 1483 2 The Neighbor Type is set according to the following: 1485 2.1 If the main address, corresponding to L_neigh- 1486 bor_iface_addr, is included in the MPR set: 1488 Neighbor Type = MPR_NEIGH 1490 2.2 Otherwise, if the main address, corresponding to L_neigh- 1491 bor_iface_addr, is included in the neighbor set: 1493 2.2.1 1494 if N_status == SYM 1496 Neighbor Type = SYM_NEIGH 1498 2.2.2 1499 Otherwise, if N_status == NOT_SYM 1500 Neighbor Type = NOT_NEIGH 1502 For each tuple in the Neighbor Set, for which no L_neigh- 1503 bor_iface_addr from an associated link tuple has been advertised by 1504 the previous algorithm, N_neighbor_main_addr is advertised with: 1506 - Link Type = UNSPEC_LINK, 1508 - Neighbor Type set as described in step 2 above 1510 For a node with a single OLSR interface, the main address is simply 1511 the address of the OLSR interface. I.e. for a node with a single 1512 OLSR interface, the main address, corresponding to L_neigh- 1513 bor_iface_addr is simply L_neighbor_iface_addr. 1515 A HELLO message can be partial (e.g. due to message size limita- 1516 tions, imposed by the network), the rule being the following, on each 1517 interface: each link and each neighbor node MUST be cited at least 1518 once within a predetermined refreshing period, REFRESH_INTERVAL. To 1519 keep track of fast connectivity changes, a HELLO message must be sent 1520 at least every HELLO_INTERVAL period, smaller than or equal to 1521 REFRESH_INTERVAL. 1523 Notice that for limiting the impact from loss of control messages, it 1524 is desirable that a message (plus the generic packet header) can fit 1525 into a single MAC frame. 1527 6.3. HELLO Message Forwarding 1529 Each HELLO message generated is broadcast by the node on one inter- 1530 face to its neighbors. HELLO messages MUST never be forwarded. 1532 6.4. HELLO Message Processing 1534 A node processes incoming HELLO messages for the purpose of conduct- 1535 ing link sensing (detailed in section 7), neighbor detection 1536 and MPR selector set population (detailed in section 8) 1538 7. Link Sensing 1540 Link sensing populates the local link information base. Link sensing 1541 is exclusively concerned with OLSR interface addresses and the abil- 1542 ity to exchange packets between such OLSR interfaces. 1544 The mechanism for link sensing is the periodic exchange of HELLO 1545 messages. 1547 7.1. Populating the Link Set 1549 The Link Set is populated with information on links to neighbor 1550 nodes. The process of populating this set is denoted "link sensing" 1551 and is performed using HELLO message exchange, updating a local link 1552 information base in each node. 1554 Each node should detect the links between itself and neighbor nodes. 1555 Uncertainties over radio propagation may make some links unidirec- 1556 tional. Consequently, all links MUST be checked in both directions 1557 in order to be considered valid. 1559 A "link" is described by a pair of interfaces: a local and a remote 1560 interface. 1562 For the purpose of link sensing, each neighbor node (more specifi- 1563 cally, the link to each neighbor) has an associated status of either 1564 "symmetric" or "asymmetric". "Symmetric" indicates, that the link to 1565 that neighbor node has been verified to be bi-directional, i.e. it 1566 is possible to transmit data in both directions. "Asymmetric" indi- 1567 cates that HELLO messages from the node have been heard (i.e. commu- 1568 nication from the neighbor node is possible), however it is not con- 1569 firmed that this node is also able to receive messages (i.e. commu- 1570 nication to the neighbor node is not confirmed). 1572 The information, acquired through and used by the link sensing, is 1573 accumulated in the link set. 1575 7.1.1. HELLO Message Processing 1577 The "Originator Address" of a HELLO message is the main address of 1578 the node, which has emitted the message. 1580 Upon receiving a HELLO message, a node SHOULD update its Link Set. 1581 Notice, that a HELLO message MUST neither be forwarded nor be 1582 recorded in the duplicate set. 1584 Upon receiving a HELLO message, the "validity time" MUST be computed 1585 from the Vtime field of the message header (see section 3.3.2). 1586 Then, the Link Set SHOULD be updated as follows: 1588 1 Upon receiving a HELLO message, if there exists no link tuple 1589 with 1591 L_neighbor_iface_addr == Source Address 1593 a new tuple is created with 1595 L_neighbor_iface_addr = Source Address 1597 L_local_iface_addr = Address of the interface 1598 which received the 1599 HELLO message 1601 L_SYM_time = current time - 1 (expired) 1603 L_time = current time + validity time 1605 2 The tuple (existing or new) with: 1607 L_neighbor_iface_addr == Source Address 1609 is then modified as follows: 1611 2.1 L_ASYM_time = current time + validity time; 1613 2.2 if the node finds the address of the interface which 1614 received the HELLO message among the addresses listed in 1615 the link message then the tuple is modified as follows: 1617 2.2.1 1618 if Link Type is equal to LOST_LINK then 1620 L_SYM_time = current time - 1 (i.e. expired) 1622 2.2.2 1623 else if Link Type is equal to SYM_LINK or ASYM_LINK 1624 then 1626 L_SYM_time = current time + validity time, 1628 L_time = L_SYM_time + NEIGHB_HOLD_TIME 1630 2.3 L_time = max(L_time, L_ASYM_time) 1632 The above rule for setting L_time is the following: a link losing its 1633 symmetry SHOULD still be advertised during at least the duration of 1634 the "validity time" advertised in the generated HELLO. This allows 1635 neighbors to detect the link breakage. 1637 8. Neighbor Detection 1639 Neighbor detection populates the neighborhood information base and 1640 concerns itself with nodes and node main addresses. The relationship 1641 between OLSR interface addresses and main addresses is described in 1642 section 5. 1644 The mechanism for neighbor detection is the periodic exchange of 1645 HELLO messages. 1647 8.1. Populating the Neighbor Set 1649 A node maintains a set of neighbor tuples, based on the link tuples. 1650 This information is updated according to changes in the Link Set. 1652 The Link Set keeps the information about the links, while the Neigh- 1653 bor Set keeps the information about the neighbors. There is a clear 1654 association between those two sets, since a node is a neighbor of 1655 another node if and only if there is at least one link between the 1656 two nodes. 1658 In any case, the formal correspondence between links and neighbors is 1659 defined as follows: 1661 The "associated neighbor tuple" of a link tuple, is, if it 1662 exists, the neighbor tuple where: 1664 N_neighbor_main_addr == main address of 1665 L_neighbor_iface_addr 1667 The "associated link tuples" of a neighbor tuple, are all the 1668 link tuples, where: 1670 N_neighbor_main_addr == main address of 1671 L_neighbor_iface_addr 1673 The Neighbor Set MUST be populated by maintaining the proper corre- 1674 spondence between link tuples and associated neighbor tuples, as fol- 1675 lows: 1677 Creation 1679 Each time a link appears, that is, each time a link tuple is 1680 created, the associated neighbor tuple MUST be created, if it 1681 doesn't already exist, with the following values: 1683 N_neighbor_main_addr = main address of 1684 L_neighbor_iface_addr 1685 (from the link tuple) 1687 In any case, the N_status MUST then be computed as described 1688 in the next step 1690 Update 1692 Each time a link changes, that is, each time the information 1693 of a link tuple is modified, the node MUST ensure that the 1694 N_status of the associated neighbor tuple respects the prop- 1695 erty: 1697 If the neighbor has any associated link tuple which indi- 1698 cates a symmetrical link (i.e. with L_SYM_time >= cur- 1699 rent time), then 1701 N_status is set to SYM 1703 else N_status is set to NOT_SYM 1705 Removal 1707 Each time a link is deleted, that is, each time a link tuple 1708 is removed, the associated neighbor tuple MUST be removed if 1709 it has no longer any associated link tuples. 1711 These rules ensure that there is exactly one associated neighbor 1712 tuple for a link tuple, and that every neighbor tuple has at least 1713 one associated link tuple. 1715 8.1.1. HELLO Message Processing 1717 The "Originator Address" of a HELLO message is the main address of 1718 the node, which has emitted the message. Likewise, the "willingness" 1719 MUST be computed from the Willingness field of the HELLO message (see 1720 section 6.1). 1722 Upon receiving a HELLO message, a node SHOULD first update its Link 1723 Set as described before. It SHOULD then update its Neighbor Set as 1724 follows: 1726 - if the Originator Address is the N_neighbor_main_addr from a 1727 neighbor tuple included in the Neighbor Set: 1729 then, the neighbor tuple SHOULD be updated as follows: 1731 N_willingness = willingness from the HELLO message 1733 8.2. Populating the 2-hop Neighbor Set 1735 The 2-hop neighbor set describes the set of nodes which have a sym- 1736 metric link to a symmetric neighbor. This information set is main- 1737 tained through periodic exchange of HELLO messages as described in 1738 this section. 1740 8.2.1. HELLO Message Processing 1742 The "Originator Address" of a HELLO message is the main address of 1743 the node, which has emitted the message. 1745 Upon receiving a HELLO message from a symmetric neighbor, a node 1746 SHOULD update its 2-hop Neighbor Set. Notice, that a HELLO message 1747 MUST neither be forwarded nor be recorded in the duplicate set. 1749 Upon receiving a HELLO message, the "validity time" MUST be computed 1750 from the Vtime field of the message header (see section 3.3.2). 1752 If the Originator Address is the main address of a L_neigh- 1753 bor_iface_addr from a link tuple included in the Link Set with 1755 L_SYM_time >= current time (not expired) 1757 (in other words: if the Originator Address is a symmetric neighbor) 1758 then the 2-hop Neighbor Set SHOULD be updated as follows: 1760 1 for each address (henceforth: 2-hop neighbor address), listed 1761 in the HELLO message with Neighbor Type equal to SYM_NEIGH or 1762 MPR_NEIGH: 1764 1.1 if the main address of the 2-hop neighbor address = main 1765 address of receiving node: 1767 silently discard the 2-hop neighbor address. 1769 (in other words: a node is not its own 2-hop neighbor). 1771 1.2 Otherwise, a 2-hop tuple is created with: 1773 N_neighbor_main_addr = Originator Address; 1775 N_2hop_addr = main address of the 1776 2-hop neighbor; 1778 N_time = current time 1779 + validity time. 1781 This tuple may replace an older similar tuple with same 1782 N_neighbor_main_addr and N_2hop_addr values. 1784 2 For each 2-hop node listed in the HELLO message with Neighbor 1785 Type equal to NOT_NEIGH, all 2-hop tuples where: 1787 N_neighbor_main_addr == Originator Address AND 1789 N_2hop_addr == main address of the 1790 2-hop neighbor 1792 are deleted. 1794 8.3. Populating the MPR set 1796 MPRs are used to flood control messages from a node into the network 1797 while reducing the number of retransmissions that will occur in a 1798 region. Thus, the concept of MPR is an optimization of a classical 1799 flooding mechanism. 1801 Each node in the network selects, independently, its own set of MPRs 1802 among its symmetric 1-hop neighborhood. The symmetric links with 1803 MPRs are advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in 1804 HELLO messages. 1806 The MPR set MUST be calculated by a node in such a way that it, 1807 through the neighbors in the MPR-set, can reach all symmetric strict 1808 2-hop neighbors. (Notice that a node, a, which is a direct neighbor 1809 of another node, b, is not also a strict 2-hop neighbor of node b). 1810 This means that the union of the symmetric 1-hop neighborhoods of the 1811 MPR nodes contains the symmetric strict 2-hop neighborhood. MPR set 1812 recalculation should occur when changes are detected in the neighbor- 1813 hood or in the 2-hop neighborhood. 1815 MPRs are computed per interface, the union of the MPR sets of each 1816 interface make up the MPR set for the node. 1818 While it is not essential that the MPR set is minimal, it is 1819 essential that all strict 2-hop neighbors can be reached through the 1820 selected MPR nodes. A node SHOULD select an MPR set such that any 1821 strict 2-hop neighbor is covered by at least one MPR node. This 1822 ensures that the overhead of the protocol is kept at a minimum. 1824 The MPR set can coincide with the entire symmetric neighbor set. 1825 This could be the case at network initialization (and will correspond 1826 to classic link-state routing). 1828 8.3.1. MPR Computation 1830 The following specifies a proposed heuristic for selection of MPRs. 1831 It constructs an MPR-set that enables a node to reach any node in the 1832 symmetrical strict 2-hop neighborhood through relaying by one MPR 1833 node with willingness different from WILL_NEVER. The heuristic MUST 1834 be applied per interface, I. The MPR set for a node is the union of 1835 the MPR sets found for each interface. The following terminology 1836 will be used in describing the heuristics: 1838 neighbor of an interface 1840 a node is a "neighbor of an interface" if the interface 1841 (on the local node) has a link to any one interface of 1842 the neighbor node. 1844 2-hop neighbors reachable from an interface 1846 the list of 2-hop neighbors of the node that can be 1847 reached from neighbors of this interface. 1849 MPR set of an interface 1851 a (sub)set of the neighbors of an interface with a will- 1852 ingness different from WILL_NEVER, selected such that 1853 through these selected nodes, all strict 2-hop neighbors 1854 reachable from that interface are reachable. 1856 N: 1858 N is the subset of neighbors of the node, which are 1859 neighbor of the interface I. 1861 N2: 1863 The set of two-hop neighbors reachable from the interface 1864 I, excluding: 1866 (i) the nodes only reachable by members of N with will- 1867 ingness WILL_NEVER 1869 (ii) the node performing the computation 1871 (iii) 1872 all the symmetric neighbors: the nodes for which 1873 there exists a symmetric link to this node on some 1874 interface. 1876 D(y): 1878 The degree of an one hop neighbor node y (where y is a 1879 member of N), is defined as the number of symmetric 1880 neighbors of node y, EXCLUDING all the members of N and 1881 EXCLUDING the node performing the computation. 1883 The proposed heuristic is as follows: 1885 1 Start with an MPR set made of all members of N with N_willing- 1886 ness equal to WILL_ALWAYS 1888 2 Calculate D(y), where y is a member of N, for all nodes in N. 1890 3 Add to the MPR set those nodes in N, which are the *only* 1891 nodes to provide reachability to a node in N2. I.e. if node 1892 b in N2 can be reached only through a symmetric link to node a 1893 in N, then add node a to the MPR set. Remove the nodes from 1894 N2 which are now covered by a node in the MPR set. 1896 4 While there exist nodes in N2 which are not covered by at 1897 least one node in the MPR set: 1899 4.1 For each node in N, calculate the reachability, i.e. the 1900 number of nodes in N2 which are not yet covered by at 1901 least one node in the MPR set, and which are reachable 1902 through this one hop neighbor; 1904 4.2 Select as a MPR the node with highest N_willingness among 1905 the nodes in N with non-zero reachability. In case of 1906 multiple choice select the node which provides 1907 reachability to the maximum number of nodes in N2. In 1908 case of multiple nodes providing the same amount of 1909 reachability, select the node as MPR whose D(y) is 1910 greater. Remove the nodes from N2 which are now covered 1911 by a node in the MPR set. 1913 5 A node's MPR set is generated from the union of the MPR sets 1914 for each interface. As an optimization, process each node, y, 1915 in the MPR set in increasing order of N_willingness. If all 1916 nodes in N2 are still covered by at least one node in the MPR 1917 set excluding node y, and if N_willingness of node y is 1918 smaller than WILL_ALWAYS, then node y MAY be removed from the 1919 MPR set. 1921 Other algorithms, as well as improvements over this algorithm, are 1922 possible. For example, assume that in a multiple-interface scenario 1923 there exists more than one link between nodes 'a' and 'b'. If node 1924 'a' has selected node 'b' as MPR for one of its interfaces, then node 1925 'b' can be selected as MPR without additional performance loss by any 1926 other interfaces on node 'a'. 1928 8.4. Populating the MPR Selector Set 1930 The MPR selector set of a node, n, is populated by the main addresses 1931 of the nodes which have selected n as MPR. MPR selection is signaled 1932 through HELLO messages. 1934 8.4.1. HELLO Message Processing 1936 Upon receiving a HELLO message, if a node finds one of its own inter- 1937 face addresses in the list with a Neighbor Type equal to MPR_NEIGH, 1938 information from the HELLO message must be recorded in the MPR Selec- 1939 tor Set. 1941 The "validity time" MUST be computed from the Vtime field of the mes- 1942 sage header (see section 3.3.2). The MPR Selector Set SHOULD 1943 then be updated as follows: 1945 1 If there exists no MPR selector tuple with: 1947 MS_main_addr == Originator Address 1949 then a new tuple is created with: 1951 MS_main_addr = Originator Address 1953 2 The tuple (new or otherwise) with 1955 MS_main_addr == Originator Address 1957 is then modified as follows: 1959 MS_time = current time + validity time. 1961 Deletion of MPR selector tuples occurs in case of expiration of the 1962 timer or in case of link breakage as described in the "Neighborhood 1963 and 2-hop Neighborhood Changes". 1965 8.5. Neighborhood and 2-hop Neighborhood Changes 1967 A change in the neighborhood is detected when: 1969 - The L_SYM_time field of a link tuple expires. This is consid- 1970 ered as a neighbor loss if the link described by the expired 1971 tuple was the last link with a neighbor node (on the contrary, 1972 a link with an interface may break while a link with another 1973 interface of the neighbor node remains without being observed 1974 as a neighborhood change). 1976 - A new link tuple is inserted in the Link Set with a non- 1977 expired L_SYM_time or a tuple with expired L_SYM_time is modi- 1978 fied so that L_SYM_time becomes non-expired. This is consid- 1979 ered as a neighbor appearance if there was previously no link 1980 tuple describing a link with the corresponding neighbor node. 1982 A change in the 2-hop neighborhood is detected when a 2-hop neighbor 1983 tuple expires or is deleted according to section 8.2. 1985 The following processing occurs when changes in the neighborhood or 1986 the 2-hop neighborhood are detected: 1988 - In case of neighbor loss, all 2-hop tuples with N_neigh- 1989 bor_main_addr == Main Address of the neighbor MUST be deleted. 1991 - In case of neighbor loss, all MPR selector tuples with 1992 MS_main_addr == Main Address of the neighbor MUST be deleted 1994 - The MPR set MUST be re-calculated when a neighbor appearance 1995 or loss is detected, or when a change in the 2-hop neighbor- 1996 hood is detected. 1998 - An additional HELLO message MAY be sent when the MPR set 1999 changes. 2001 9. Topology Discovery 2003 The link sensing and neighbor detection part of the protocol basi- 2004 cally offers, to each node, a list of neighbors with which it can 2005 communicate directly and, in combination with the Packet Format and 2006 Forwarding part, an optimized flooding mechanism through MPRs. Based 2007 on this, topology information is disseminated through the network. 2008 The present section describes what part of the information given by 2009 the link sensing and neighbor detection is disseminated to the entire 2010 network and how it is used to construct routes. 2012 Routes are constructed through advertised links and links with neigh- 2013 bors. A node must at least disseminate links between itself and the 2014 nodes in its MPR-selector set, in order to provide sufficient infor- 2015 mation to enable routing. 2017 9.1. TC Message Format 2019 The proposed format of a TC message is as follows: 2021 0 1 2 3 2022 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 2023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2024 | ANSN | Reserved | 2025 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2026 | Advertised Neighbor Main Address | 2027 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2028 | Advertised Neighbor Main Address | 2029 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2030 | ... | 2031 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2033 This is sent as the data-portion of the general message format with 2034 the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set 2035 to 255 (maximum value) to diffuse the message into the entire network 2036 and Vtime set accordingly to the value of TOP_HOLD_TIME, as specified 2037 in section 18.3. 2039 Advertised Neighbor Sequence Number (ANSN) 2041 A sequence number is associated with the advertised neighbor 2042 set. Every time a node detects a change in its advertised 2043 neighbor set, it increments this sequence number ("Wrap- 2044 around" is handled as described in section 19). This 2045 number is sent in this ANSN field of the TC message to keep 2046 track of the most recent information. When a node receives a 2047 TC message, it can decide on the basis of this Advertised 2048 Neighbor Sequence Number, whether or not the received informa- 2049 tion about the advertised neighbors of the originator node is 2050 more recent than what it already has. 2052 Advertised Neighbor Main Address 2054 This field contains the main address of a neighbor node. All 2055 main addresses of the advertised neighbors of the Originator 2056 node are put in the TC message. If the maximum allowed mes- 2057 sage size (as imposed by the network) is reached while there 2058 are still advertised neighbor addresses which have not been 2059 inserted into the TC-message, more TC messages will be gener- 2060 ated until the entire advertised neighbor set has been sent. 2061 Extra main addresses of neighbor nodes may be included, if 2062 redundancy is desired. 2064 Reserved 2066 This field is reserved, and MUST be set to "0000000000000000" 2067 for compliance with this document. 2069 9.2. Advertised Neighbor Set 2071 A TC message is sent by a node in the network to declare a set of 2072 links, called advertised link set which MUST include at least the 2073 links to all nodes of its MPR Selector set, i.e., the neighbors which 2074 have selected the sender node as a MPR. 2076 If, for some reason, it is required to distribute redundant TC infor- 2077 mation, refer to section 15. 2079 The sequence number (ANSN) associated with the advertised neighbor 2080 set is also sent with the list. The ANSN number MUST be incremented 2081 when links are removed from the advertised neighbor set; the ANSN 2082 number SHOULD be incremented when links are added to the advertised 2083 neighbor set. 2085 9.3. TC Message Generation 2087 In order to build the topology information base, each node, which has 2088 been selected as MPR, broadcasts Topology Control (TC) messages. TC 2089 messages are flooded to all nodes in the network and take advantage 2090 of MPRs. MPRs enable a better scalability in the distribution of 2091 topology information [1]. 2093 The list of addresses can be partial in each TC message (e.g. due to 2094 message size limitations, imposed by the network), but parsing of all 2095 TC messages describing the advertised link set of a node MUST be com- 2096 plete within a certain refreshing period (TC_INTERVAL). The informa- 2097 tion diffused in the network by these TC messages will help each node 2098 calculate its routing table. 2100 When the advertised link set of a node becomes empty, it SHOULD still 2101 send (empty) TC-messages during the a duration equal to the "validity 2102 time" (typically, this will be equal to TC_HOLD_TIME) of its previ- 2103 ously emitted TC-messages, in order to invalidate the previous TC- 2104 messages. It SHOULD then stop sending TC-messages until some node is 2105 inserted in its advertised link set. 2107 A node MAY transmit additional TC-messages to increase its reactive- 2108 ness to link failures. When a change to the MPR selector set is 2109 detected and this change can be attributed to a link failure, a TC- 2110 message SHOULD be transmitted after a shorter interval than TC_INTER- 2111 VAL. 2113 9.4. TC Message Forwarding 2115 TC messages are broadcast and retransmitted by the MPRs in order to 2116 diffuse the messages in the entire network. TC messages MUST be for- 2117 warded according to the "default forwarding algorithm". 2119 9.5. TC Message Processing 2121 Upon receiving a TC message, the "validity time" MUST be computed 2122 from the Vtime field of the message header (see section 3.3.2). 2123 The topology set SHOULD then be updated as follows (using section 2124 19 for comparison of ANSN): 2126 1 If the sender interface (NB: not originator) of this message 2127 is not in the symmetric 1-hop neighborhood of this node, the 2128 message MUST be discarded. 2130 2 If there exist some tuple in the topology set where: 2132 T_last_addr == originator address AND 2134 T_seq > ANSN, 2136 then further processing of this TC message MUST NOT be per- 2137 formed and the message MUST be silently discarded (case: mes- 2138 sage received out of order). 2140 3 All tuples in the topology set where: 2142 T_last_addr == originator address AND 2144 T_seq < ANSN 2146 MUST be removed from the topology set. 2148 4 For each of the advertised neighbor main address received in 2149 the TC message: 2151 4.1 If there exist some tuple in the topology set where: 2153 T_dest_addr == advertised neighbor main address, AND 2155 T_last_addr == originator address, 2157 then the holding time of that tuple MUST be set to: 2159 T_time = current time + validity time. 2161 4.2 Otherwise, a new tuple MUST be recorded in the topology 2162 set where: 2164 T_dest_addr = advertised neighbor main address, 2166 T_last_addr = originator address, 2168 T_seq = ANSN, 2170 T_time = current time + validity time. 2172 10. Routing Table Calculation 2174 Each node maintains a routing table which allows it to route data, 2175 destined for the other nodes in the network. The routing table is 2176 based on the information contained in the link set and the topology 2177 set. Therefore, if any of these sets are changed, the routing table 2178 is re-calculated to update the route information about each destina- 2179 tion in the network. The route entries are recorded in the routing 2180 table in the following format: 2182 1. R_dest_addr R_next_addr R_dist R_iface_addr 2183 2. R_dest_addr R_next_addr R_dist R_iface_addr 2184 3. ,, ,, ,, ,, 2186 Each entry in the table consists of R_dest_addr, R_next_addr, R_dist, 2187 and R_iface_addr. Such entry specifies that the node identified by 2188 R_dest_addr is estimated to be R_dist hops away from the local node, 2189 that the symmetric neighbor node with interface address R_next_addr 2190 is the next hop node in the route to R_dest_addr, and that this sym- 2191 metric neighbor node is reachable through the local interface with 2192 the address R_iface_addr. Entries are recorded in the routing table 2193 for each destination in the network for which a route is known. All 2194 the destinations, for which a route is broken or only partially 2195 known, are not recorded in the table. 2197 The routing table is updated when a change is detected in either: 2199 - the link set, 2201 - the neighbor set, 2203 - the 2-hop neighbor set, 2205 - the topology set, 2207 - the Multiple Interface Association Information Base, 2209 More precisely, the routing table is re-calculated in case of neigh- 2210 bor appearance or loss, when a 2-hop tuple is created or removed,when 2211 a topology tuple is created or removed or when multiple interface 2212 association information changes. The update of this routing informa- 2213 tion does not generate or trigger any messages to be transmitted, 2214 neither in the network, nor in the 1-hop neighborhood. 2216 To construct the routing table of node X, a shortest path algorithm 2217 is run on the directed graph containing the arcs X -> Y where Y is 2218 any symmetric neighbor of X (with Neighbor Type equal to SYM), the 2219 arcs Y -> Z where Y is a neighbor node with willingness different of 2220 WILL_NEVER and there exists an entry in the 2-hop Neighbor set with Y 2221 as N_neighbor_main_addr and Z as N_2hop_addr, and the arcs U -> V, 2222 where there exists an entry in the topology set with V as T_dest_addr 2223 and U as T_last_addr. 2225 The following procedure is given as an example to calculate (or re- 2226 calculate) the routing table : 2228 1 All the entries from the routing table are removed. 2230 2 The new routing entries are added starting with the symmetric 2231 neighbors (h=1) as the destination nodes. I.e. for each 2232 neighbor tuple in the neighbor set where: 2234 N_status = SYM 2236 (there is a symmetric link to the neighbor), and for each 2237 associated link tuple of the neighbor node such that L_time >= 2238 current time, a new routing entry is recorded in the routing 2239 table with: 2241 R_dest_addr = L_neighbor_iface_addr, of the 2242 associated link tuple; 2244 R_next_addr = L_neighbor_iface_addr, of the 2245 associated link tuple; 2247 R_dist = 1; 2249 R_iface_addr = L_local_iface_addr of the 2250 associated link tuple. 2252 If in the above, no R_dest_addr is equal to the main address 2253 of the neighbor, then another new routing entry with MUST be 2254 added, with: 2256 R_dest_addr = main address of the neighbor; 2258 R_next_addr = L_neighbor_iface_addr of one of the 2259 associated link tuple with L_time >= cur- 2260 rent time; 2262 R_dist = 1; 2264 R_iface_addr = L_local_iface_addr of the 2265 associated link tuple. 2267 3 for each node in N2, i.e a 2-hop neighbor which is not a 2268 neighbor node or the node itself, and such that there exist at 2269 least one entry in the 2-hop neighbor set where N_neigh- 2270 bor_main_addr correspond to a neighbor node with willingness 2271 different of WILL_NEVER, one selects one 2-hop tuple and cre- 2272 ates one entry in the routing table with: 2274 R_dest_addr = the main address of the two hop neighbor; 2276 R_next_addr = the R_next_addr of the entry in the 2277 routing table with: 2279 R_dest_addr == N_neighbor_main_addr 2280 of the 2-hop tuple; 2282 R_dist = 2; 2284 R_iface_addr = the R_iface_addr of the entry in the 2285 routing table with: 2287 R_dest_addr == N_neighbor_main_addr 2288 of the 2-hop tuple; 2290 3 The new route entries for the destination nodes h+1 hops away 2291 are recorded in the routing table. The following procedure 2292 MUST be executed for each value of h, starting with h=2 and 2293 incrementing it by 1 each time. The execution will stop if no 2294 new entry is recorded in an iteration. 2296 3.1 For each topology entry in the topology table, if its 2297 T_dest_addr does not correspond to R_dest_addr of any 2298 route entry in the routing table AND its T_last_addr cor- 2299 responds to R_dest_addr of a route entry whose R_dist is 2300 equal to h, then a new route entry MUST be recorded in 2301 the routing table (if it does not already exist) where: 2303 R_dest_addr = T_dest_addr; 2305 R_next_addr = R_next_addr of the recorded 2306 route entry where: 2308 R_dest_addr == T_last_addr 2310 R_dist = h+1; and 2311 R_iface_addr = R_iface_addr of the recorded 2312 route entry where: 2314 R_dest_addr == T_last_addr. 2316 3.2 Several topology entries may be used to select a next hop 2317 R_next_addr for reaching the node R_dest_addr. When h=1, 2318 ties should be broken such that nodes with highest will- 2319 ingness and MPR selectors are preferred as next hop. 2321 4 For each entry in the multiple interface association base 2322 where there exists a routing entry such that: 2324 R_dest_addr == I_main_addr (of the multiple interface 2325 association entry) 2327 AND there is no routing entry such that: 2329 R_dest_addr == I_iface_addr 2331 then a route entry is created in the routing table with: 2333 R_dest_addr = I_iface_addr (of the multiple interface 2334 association entry) 2336 R_next_addr = R_next_addr (of the recorded 2337 route entry) 2339 R_dist = R_dist (of the recorded 2340 route entry) 2342 R_iface_addr = R_iface_addr (of the recorded 2343 route entry). 2345 11. Node Configuration 2347 This section outlines how a node should be configured, in order to 2348 operate in an OLSR MANET. 2350 11.1. Address Assignment 2352 The nodes in the MANET network SHOULD be assigned addresses within a 2353 defined address sequence. I.e., the nodes in the MANET SHOULD be 2354 addressable through a network address and a netmask. 2356 Likewise, the nodes in each associated network SHOULD be assigned 2357 addresses from a defined address sequence, distinct from that being 2358 used in the MANET. 2360 11.2. Routing Configuration 2362 Any MANET node with associated networks or hosts SHOULD be configured 2363 such that it has routes set up to the interfaces with associated 2364 hosts or network. 2366 11.3. Data Packet Forwarding 2368 OLSR itself does not perform packet forwarding. Rather, it maintains 2369 the routing table in the underlying operating system, which is 2370 assumed to be forwarding packets as specified in RFC1812. 2372 12. Non OLSR Interfaces 2374 A node MAY be equipped with multiple interfaces, some of which do not 2375 participate in the OLSR MANET. These non-OLSR interfaces may be 2376 point to point connections to other singular hosts or may connect to 2377 separate networks. 2379 In order to provide connectivity from the OLSR MANET interface(s) to 2380 these non-OLSR interface(s), a node SHOULD be able to inject external 2381 route information to the OLSR MANET. 2383 Injecting routing information from the OLSR MANET to non-OLSR inter- 2384 faces is outside the scope of this specification. It should be 2385 clear, however, that the routing information for the OLSR MANET can 2386 be extracted from the topology table (see section 4.4) or 2387 directly from the routing table of OLSR, and SHOULD be injected onto 2388 the non-OLSR interfaces following whatever mechanism (routing proto- 2389 col, static configuration etc.) is provided on these interfaces. 2391 An example of such a situation could be where a node is equipped with 2392 a fixed network (e.g. an Ethernet) connecting to a larger network 2393 running, as well as a wireless network interface running OLSR. 2395 Notice that this is a different case from that of "multiple inter- 2396 faces", where all the interfaces are participating in the MANET 2397 through running the OLSR protocol. 2399 In order to provide this capability of injecting external routing 2400 information into an OLSR MANET, a node with such non-MANET interfaces 2401 periodically issues a Host and Network Association (HNA) message, 2402 containing sufficient information for the recipients to construct an 2403 appropriate routing table. 2405 12.1. HNA Message Format 2407 The proposed format of an HNA-message is: 2409 0 1 2 3 2410 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 2411 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2412 | Network Address | 2413 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2414 | Netmask | 2415 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2416 | Network Address | 2417 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2418 | Netmask | 2419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2420 | ... | 2421 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2423 This is sent as the data part of the general packet format with the 2424 "Message Type" set to HNA_MESSAGE, the TTL field set to 255 and Vtime 2425 set accordingly to the value of HNA_HOLD_TIME, as specified in sec- 2426 tion 18.3. 2428 Network Address 2430 The network address of the associated network 2432 Netmask 2434 The netmask, corresponding to the network address immediately 2435 above. 2437 12.2. Host and Network Association Information Base 2439 Each node maintains information concerning which nodes may act as 2440 "gateways" to associated hosts and networks by recording "association 2441 tuples" (A_gateway_addr, A_network_addr, A_netmask, A_time), where 2442 A_gateway_addr is the address of a OLSR interface of the gateway, 2443 A_network_addr and A_netmask specify the network address and netmask 2444 of a network, reachable through this gateway, and A_time specifies 2445 the time at which this tuple expires and hence *MUST* be removed. 2447 The set of all association tuples in a node is called the "associa- 2448 tion set". 2450 It should be noticed, that the HNA-message can be considered as a 2451 "generalized version" of the TC-message: the originator of both the 2452 HNA- and TC-messages announce "reachability" to some other host(s). 2453 In the TC-message, no netmask is required, since all reachability is 2454 announced on a per-host basis. In HNA-messages, announcing reacha- 2455 bility to an address sequence through a network- and netmask address 2456 is typically preferred over announcing reachability to individual 2457 host addresses. 2459 An important difference between TC- and HNA-messages is, that a TC 2460 message may have a canceling effect on previous information (if the 2461 ANSN is incremented), whereas information in HNA-messages is removed 2462 only upon expiration. 2464 12.3. HNA Message Generation 2466 A node with associated hosts and/or networks SHOULD periodically gen- 2467 erate a Host and Network Association (HNA) message, containing pairs 2468 of (network address, netmask) corresponding to the connected hosts 2469 and networks. HNA-messages SHOULD be transmitted periodically every 2470 HNA_INTERVAL. The Vtime is set accordingly to the value of 2471 HNA_HOLD_TIME, as specified in section 18.3. 2473 A node without any associated hosts and/or networks SHOULD NOT gener- 2474 ate HNA-messages. 2476 12.4. HNA Message Forwarding 2478 Upon receiving a HNA message, and thus following the rules of section 2479 3, in this version of the specification, the message MUST be 2480 forwarded according to section 3.4. 2482 12.5. HNA Message Processing 2484 In this section, the term "originator address" is used to designate 2485 the main address on the OLSR MANET of the node which originally 2486 issued the HNA-message. 2488 Upon processing a HNA-message, the "validity time" MUST be computed 2489 from the Vtime field of the message header (see section 3.3.2). 2490 The association base SHOULD then be updated as follows: 2492 1 If the sender interface (NB: not originator) of this message 2493 is not in the symmetric 1-hop neighborhood of this node, the 2494 message MUST be discarded. 2496 2 Otherwise, for each (network address, netmask) pair in the 2497 message: 2499 2.1 if an entry in the association set already exists, where: 2501 A_gateway_addr == originator address 2503 A_network_addr == network address 2505 A_netmask == netmask 2507 then the holding time for that tuple MUST be set to: 2509 A_time = current time + validity time 2511 2.2 otherwise, a new tuple MUST be recorded with: 2513 A_gateway_addr = originator address 2515 A_network_addr = network address 2517 A_netmask = netmask 2519 A_time = current time + validity time 2521 12.6. Routing Table Calculation 2523 In addition to the routing table computation as described in section 2524 10, the host and network association set MUST be added as 2525 follows: 2527 For each tuple in the association set, 2529 1 If there is no entry in the routing table with: 2531 R_dest_addr == A_network_addr/A_netmask 2533 then a new routing entry is created is created. 2535 2 If a new routing entry was created at the previous step, or 2536 else if there existed one with: 2538 R_dest_addr == A_network_addr/A_netmask 2540 R_dist > dist to A_gateway_addr of 2541 current association set tuple, 2543 then the routing entry is modified as follows: 2545 R_dest_addr = A_network_addr/A_netmask 2547 R_next_addr = the next hop on the path 2548 from the node to A_gateway_addr 2550 R_dist = dist to A_gateway_addr 2552 R_next_addr and R_iface_addr MUST be set to the same val- 2553 ues as the tuple from the routing set with R_dest_addr == 2554 A_gateway_addr. 2556 12.7. Interoperability Considerations 2558 Nodes, which do not implement support for non-OLSR interfaces, can 2559 coexist in a network with nodes which do implement support for non- 2560 OLSR interfaces: the generic packet format and message forwarding 2561 (section 3) ensures that HNA messages are correctly for- 2562 warded by all nodes . Nodes which implement support for non-OLSR 2563 interfaces may thus transmit and process HNA messages according to 2564 this section. 2566 Nodes, which do not implement support for non-OLSR interfaces can not 2567 take advantage of the functionality specified in this section, how- 2568 ever will forward HNA messages correctly, as specified in section 2569 3. 2571 13. Link Layer Notification 2573 OLSR is designed not to impose or expect any specific information 2574 from the link layer. However, if information from the link-layer 2575 describing link breakage is available, a node MAY use this as 2576 described in this section. 2578 If link layer information describing connectivity to neighboring 2579 nodes is available (i.e. loss of connectivity such as through 2580 absence of a link layer acknowledgment), this information is used in 2581 addition to the information from the HELLO-messages to maintain the 2582 neighbor information base and the MPR selector set. 2584 Thus, upon receiving a link-layer notification that the link between 2585 a node and a neighbor interface is broken, the following actions are 2586 taken with respect to link sensing: 2588 Each link tuple in the local link set SHOULD, in addition to what is 2589 described in section 4.2, include a L_LOST_LINK_time field. 2590 L_LOST_LINK_time is a timer for declaring a link as lost when an 2591 established link becomes pending. (Notice, that this is a subset of 2592 what is recommended in section 14, thus link hysteresis 2593 and link layer notifications can coexist). 2595 HELLO message generation should consider those new fields as follows: 2597 1 if L_LOST_LINK_time is not expired, the link is advertised 2598 with a link type of LOST_LINK. In addition, it is not consid- 2599 ered as a symmetrical link in the updates of the associated 2600 neighbor tuple (see section 8.1). 2602 2 if the link to a neighboring symmetric or asymmetric interface 2603 is broken, the corresponding link tuple is modified: 2604 L_LOST_LINK_time and L_time are set to current time + 2605 NEIGHB_HOLD_TIME. 2607 3 this is considered as a link loss and the appropriate process- 2608 ing described in section 8.5 should be performed. 2610 13.1. Interoperability Considerations 2612 Link layer notifications provide, for a node, an additional criterion 2613 by which a node may determine if a link to a neighbor node is lost. 2614 Once a link is detected as lost, it is advertised, in accordance with 2615 the provisions described in the previous sections of this specifica- 2616 tion. 2618 14. Link Hysteresis 2620 Established links should be as reliable as possible to avoid data 2621 packet loss. This implies that link sensing should be robust against 2622 bursty loss or transient connectivity between nodes. Hence, to 2623 enhance the robustness of the link sensing mechanism, the following 2624 implementation recommendations SHOULD be considered. 2626 14.1. Local Link Set 2628 Each link tuple in the local link set SHOULD, in addition to what is 2629 described in section 4.2, include a L_link_pending field, a 2630 L_link_quality field, and a L_LOST_LINK_time field. L_link_pending 2631 is a boolean value specifying if the link is considered pending (i.e. 2632 the link is not considered established). L_link_quality is a dimen- 2633 sionless number between 0 and 1 describing the quality of the link. 2634 L_LOST_LINK_time is a timer for declaring a link as lost when an 2635 established link becomes pending. 2637 14.2. Hello Message Generation 2639 HELLO message generation should consider those new fields as follows: 2641 1 if L_LOST_LINK_time is not expired, the link is advertised 2642 with a link type of LOST_LINK. 2644 2 otherwise, if L_LOST_LINK_time is expired and L_link_pending 2645 is set to "true", the link SHOULD NOT be advertised at all; 2647 3 otherwise, if L_LOST_LINK_time is expired and L_link_pending 2648 is set to "false", the link is advertised as described previ- 2649 ously in section 6. 2651 A node considers that it has a symmetric link for each link tuple 2652 where: 2654 1 L_LOST_LINK_time is expired, AND 2656 2 L_link_pending is "false", AND 2658 3 L_SYM_time is not expired. 2660 This definition for "symmetric link" SHOULD be used the updates of 2661 the associated neighbor tuple (see section 8.1) for computing 2662 the N_status of a neighbor node. This definition SHOULD thereby also 2663 be used as basis for the symmetric neighborhood when computing the 2664 MPR set, as well as for "the symmetric neighbors" in the first steps 2665 of the routing table calculation. 2667 Apart from the above, what has been described previously does not 2668 interfere with the advanced link sensing fields in the link tuples. 2669 The L_link_quality, L_link_pending and L_LOST_LINK_time fields are 2670 exclusively updated according to the present section. This section 2671 does not modify the function of any other fields in the link tuples. 2673 14.3. Hysteresis Strategy 2675 The link between a node and some of its neighbor interfaces might be 2676 "bad", i.e. from time to time let HELLOs pass through only to fade 2677 out immediately after. In this case, the neighbor information base 2678 would contain a bad link for at least "validity time". The following 2679 hysteresis strategy SHOULD be adopted to counter this situation. 2681 For each neighbor interface NI heard by interface I, the L_link_qual- 2682 ity field of the corresponding Link Tuple determines the establish- 2683 ment of the link. The value of L_link_quality is compared to two 2684 thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed between 0 2685 and 1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. 2687 The L_link_pending field is set according to the following: 2689 1 if L_link_quality > HYST_THRESHOLD_HIGH: 2691 L_link_pending = false 2693 L_LOST_LINK_time = current time - 1 (expired) 2695 2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW: 2697 L_link_pending = true 2699 L_LOST_LINK_time = min (L_time, current time + 2700 NEIGHB_HOLD_TIME) 2702 (the link is then considered as lost according to section 2703 8.5 and this may produce a neighbor loss). 2705 3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality 2706 <= HYST_THRESHOLD_HIGH: 2708 L_link_pending and L_LOST_LINK_time remain unchanged. 2710 The condition for considering a link established is thus stricter 2711 than the condition for dropping a link. Notice thus, that a link can 2712 be dropped based on either timer expiration (as described in section 2713 7) or on L_link_quality dropping below HYST_THRESHOLD_LOW. 2715 Also notice, that even if a link is not considered as established by 2716 the link hysteresis, the link tuples are still updated for each 2717 received HELLO message (as described in section 7). Specif- 2718 ically, this implies that, regardless of whether or not the link hys- 2719 teresis considers a link as "established", tuples in the link set do 2720 not expire except as determined by the L_time field of the link 2721 tuples. 2723 As a basic implementation requirement, an estimation of the link 2724 quality must be maintained and stored in the L_link_quality field. 2725 If some measure of the signal/noise level on a received message is 2726 available (e.g. as a link layer notification), then it can be used 2727 as estimation after normalization. 2729 If no signal/noise information or other link quality information is 2730 available from the link layer, an algorithm such as the following can 2731 be utilized (it is an exponentially smoothed moving average of the 2732 transmission success rate). The algorithm is parameterized by a 2733 scaling parameter HYST_SCALING which is a number fixed between 0 and 2734 1. For each neighbor interface NI heard by interface I, the first 2735 time NI is heard by I, L_link_quality is set to HYST_SCALING 2736 (L_link_pending is set to true and L_LOST_LINK_time to current time - 2737 1). 2739 A tuple is updated according to two rules. Every time an OLSR packet 2740 emitted by NI is received by I, the stability rule is applied: 2742 L_link_quality = (1-HYST_SCALING)*L_link_quality 2743 + HYST_SCALING. 2745 When an OLSR packet emitted by NI is lost by I, the instability 2746 rule is applied: 2748 L_link_quality = (1-HYST_SCALING)*L_link_quality. 2750 The loss of OLSR packet is detected by tracking the missing Packet 2751 Sequence Numbers on a per interface basis and by "long period of 2752 silence" from a node. A "long period of silence may be detected 2753 thus: if no OLSR packet has been received on interface I from inter- 2754 face NI during HELLO emission interval of interface NI (computed from 2755 the Htime field in the last HELLO message received from NI), a loss 2756 of an OLSR packet is detected. 2758 14.4. Interoperability Considerations 2760 Link hysteresis determines, for a node, the criteria at which a link 2761 to a neighbor node is accepted or rejected. Nodes in a network may 2762 have different criteria, according to e.g. the nature of the media 2763 over which they are communicating. Once a link is accepted, it is 2764 advertised, in accordance with the provisions described in the previ- 2765 ous sections of this specification. 2767 15. Redundant Topology Information 2769 In order to provide redundancy to topology information base, the 2770 advertised link set of a node MAY contain links to neighbor nodes 2771 which are not in MPR selector set of the node. The advertised link 2772 set MAY contain links to the whole neighbor set of the node. The 2773 minimal set of links that any node MUST advertise in its TC messages 2774 is the links to the nodes MPR selectors. The advertised link set can 2775 be built according to the following rule based on a local parameter 2776 called TC_REDUNDANCY parameter. 2778 15.1. TC_REDUNDANCY Parameter 2780 The parameter TC_REDUNDANCY specifies, for the local node, the amount 2781 of information that MAY be included in the TC messages. The parame- 2782 ter SHOULD be interpreted as follows: 2784 - if the TC_REDUNDANCY parameter of the node is 0, then the 2785 advertised link set of the node set is limited to the MPR 2786 selector set (as described in section 8.3), 2788 - if the TC_REDUNDANCY parameter of the node is 1, then the 2789 advertised link set of the node is the union of its MPR set 2790 and its MPR selector set, 2792 - if the TC_REDUNDANCY parameter of the node is 2, then the 2793 advertised link set of the node is the full neighbor link set. 2795 A node with willingness equal to WILL_NEVER SHOULD have TC_REDUNDANCY 2796 also equal to zero. 2798 15.2. Interoperability Considerations 2800 A TC message is sent by a node in the network to declare a set of 2801 links, called advertised link set which MUST include at least the 2802 links to all nodes of its MPR Selector set, i.e., the neighbors which 2803 have selected the sender node as a MPR. This is sufficient informa- 2804 tion to ensure that routes can be computed in accordance with section 2805 10. 2807 The provisions in this section specifies how additional information 2808 may be declared, as specified through a TC_REDUNDANCY parameter. 2809 TC_REDUNDANCY = 0 implies that the information declared corresponds 2810 exactly to the MPR Selector set, identical to section 9. Other 2811 values of TC_REDUNDANCY specifies additional information to be 2812 declared, i.e. the contents of the MPR Selector set is always 2813 declared. Thus, nodes with different values of TC_REDUNDANCY may 2814 coexist in a network: control messages are carried by all nodes in 2815 accordance with section 3, and all nodes will receive at 2816 least the link-state information required to construct routes as 2817 described in section 10. 2819 16. MPR Redundancy 2821 MPR redundancy specifies the ability for a node to select redundant 2822 MPRs. Section 4.5 specifies that a node should select its MPR set to 2823 be as small as possible, in order to reduce protocol overhead. The 2824 criteria for selecting MPRs is, that all strict 2-hop nodes must be 2825 reachable through, at least, one MPR node. Redundancy of the MPR set 2826 affects the overhead through affecting the amount of links being 2827 advertised, the amount of nodes advertising links and the efficiency 2828 of the MPR flooding mechanism. On the other hand, redundancy in the 2829 MPR set ensures that reachability for a node is advertised by more 2830 nodes, thus additional links are diffused to the network. 2832 While, in general, a minimal MPR set provides the least overhead, 2833 there are situations in which overhead can be traded off for other 2834 benefits. E.g. a node can may decide to increase its MPR coverage 2835 if it observes many changes in its neighbor information base caused 2836 by mobility, while otherwise keeping a low MPR coverage. 2838 16.1. MPR_COVERAGE Parameter 2840 The MPR coverage is defined by a single local parameter, MPR_COVER- 2841 AGE, specifying by how many MPR nodes any strict 2-hop node should be 2842 covered. MPR_COVERAGE=1 specifies that the overhead of the protocol 2843 is kept at a minimum and causes the MPR selection to operate as 2844 described in section 8.3.1. MPR_COVERAGE=m ensures that, if 2845 possible, a node selects its MPR set such that all strict 2-hop nodes 2846 for an interface are reachable through at least m MPR nodes on that 2847 interface. MPR_COVERAGE can assume any integer value > 0. The 2848 heuristic MUST be applied per interface, I. The MPR set for a node 2849 is the union of the MPR sets found for each interface. 2851 Notice that MPR_COVERAGE can be tuned locally without affecting the 2852 consistency of the protocol. I.e. nodes in a network may operate 2853 with different values of MPR_COVERAGE. 2855 16.2. MPR Computation 2857 Using MPR coverage, the MPR selection heuristics is extended from 2858 that described in the section 8.3.1 by one definition: 2860 Poorly covered node: 2862 A poorly covered node is a node in N2 which is covered by less 2863 than MPR_COVERAGE nodes in N. 2865 The proposed heuristic for selecting MPRs is then as follows: 2867 1 Start with an MPR set made of all members of N with willing- 2868 ness equal to WILL_ALWAYS 2870 2 Calculate D(y), where y is a member of N, for all nodes in N. 2872 3 Select as MPRs those nodes in N which cover the poorly covered 2873 nodes in N2. The nodes are then removed from N2 for the rest 2874 of the computation. 2876 4 While there exist nodes in N2 which are not covered by at 2877 least MPR_COVERAGE nodes in the MPR set: 2879 4.1 For each node in N, calculate the reachability, i.e. the 2880 number of nodes in N2 which are not yet covered by at 2881 least MPR_COVERAGE nodes in the MPR set, and which are 2882 reachable through this one hop neighbor; 2884 4.2 Select as a MPR the node with highest willingness among 2885 the nodes in N with non-zero reachability. In case of 2886 multiple choice select the node which provides reachabil- 2887 ity to the maximum number of nodes in N2. In case of 2888 multiple nodes providing the same amount of reachability, 2889 select the node as MPR whose D(y) is greater. Remove the 2890 nodes from N2 which are now covered by MPR_COVERAGE nodes 2891 in the MPR set. 2893 5 A node's MPR set is generated from the union of the MPR sets 2894 for each interface. As an optimization, process each node, y, 2895 in the MPR set in increasing order of N_willingness. If all 2896 nodes in N2 are still covered by at least MPR_COVERAGE nodes 2897 in the MPR set excluding node y, and if N_willingness of node 2898 y is smaller than WILL_ALWAYS, then node y MAY be removed from 2899 the MPR set. 2901 When the MPR set has been computed, all the corresponding main 2902 addresses are stored in the MPR Set. 2904 16.3. Interoperability Considerations 2906 The MPR set of a node MUST, according to section 8.3, be cal- 2907 culated by a node in such a way that it, through the neighbors in the 2908 MPR-set, can reach all symmetric strict 2-hop neighbors. This is 2909 achieved by the heuristics in this section, for all values of 2910 MPR_COVERAGE > 0. MPR_COVERAGE is a local parameter for each node. 2911 Setting this parameter affects only the amount of redundancy in part 2912 of the network. 2914 Notice that for MPR_COVERAGE=1, the heuristics in this section is 2915 identical to the heuristics specified in the section 8.3.1. 2917 Nodes with different values of MPR_COVERAGE may coexist in a network: 2918 control messages are carried by all nodes in accordance with section 2919 3, and all nodes will receive at least the link-state infor- 2920 mation required to construct routes as described in sections 9 2921 and 10. 2923 17. IPv6 Considerations 2925 All the operations and parameters described in this document used by 2926 OLSR for IP version 4 are the same as those used by OLSR for IP ver- 2927 sion 6. To operate with IP version 6, the only required change is to 2928 replace the IPv4 addresses with IPv6 address. The minimum packet and 2929 message sizes (under which there is rejection) should be adjusted 2930 accordingly, considering the greater size of IPv6 addresses. 2932 18. Proposed Values for Constants 2934 This section list the values for the constants used in the descrip- 2935 tion of the protocol. 2937 18.1. Setting emission intervals and holding times 2939 The proposed constant for C is the following: 2941 C = 1/16 seconds (equal to 0.0625 seconds) 2943 C is a scaling factor for the "validity time" calculation ("Vtime" 2944 and "Htime" fields in message headers, see section 18.3). 2945 The "validity time" advertisement is designed such that nodes in a 2946 network may have different and individually tuneable emission inter- 2947 vals, while still interoperate fully. For protocol functioning and 2948 interoperability to work: 2950 - the advertised holding time MUST always be greater than the 2951 refresh interval of the advertised information. Moreover, it 2952 is recommended that the relation between the interval (from 2953 section 18.2), and the hold time is kept as specified 2954 in section 18.3, to allow for reasonable packet loss. 2956 - the constant C SHOULD be set to the suggested value. In order 2957 to achieve interoperability, C MUST be the same on all nodes. 2959 - the emission intervals (section 18.2), along with the 2960 advertised holding times (subject to the above constraints) 2961 MAY be selected on a per node basis. 2963 Note that the timer resolution of a given implementation might not be 2964 sufficient to wake up the system on precise refresh times or on pre- 2965 cise expire times: the implementation SHOULD round up the 'validity 2966 time' ("Vtime" and "Htime" of packets) to compensate for coarser 2967 timer resolution, at least in the case where "validity time" could be 2968 shorter than the sum of emission interval and maximum expected timer 2969 error. 2971 18.2. Emission Intervals 2972 HELLO_INTERVAL = 2 seconds 2974 REFRESH_INTERVAL = 2 seconds 2976 TC_INTERVAL = 5 seconds 2978 MID_INTERVAL = TC_INTERVAL 2980 HNA_INTERVAL = TC_INTERVAL 2982 18.3. Holding Time 2984 NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL 2986 TOP_HOLD_TIME = 3 x TC_INTERVAL 2988 DUP_HOLD_TIME = 30 seconds 2990 MID_HOLD_TIME = 3 x MID_INTERVAL 2992 HNA_HOLD_TIME = 3 x HNA_INTERVAL 2994 The Vtime in the message header (see section 3.3.2), and the 2995 Htime in the HELLO message (see section 6.1) are the 2996 fields which hold information about the above values in mantissa and 2997 exponent format (rounded up). In other words: 2999 value = C*(1+a/16)*2^b [in seconds] 3001 where a is the integer represented by the four highest bits of the 3002 field and b the integer represented by the four lowest bits of the 3003 field. 3005 Notice, that for the previous proposed value of C, (1/16 seconds), 3006 the values, in seconds, expressed by the formula above can be stored, 3007 without loss of precision, in binary fixed point or floating point 3008 numbers with at least 8 bits of fractional part. This corresponds 3009 with NTP time-stamps and single precision IEEE Standard 754 floating 3010 point numbers. 3012 Given one of the above holding times, a way of computing the man- 3013 tissa/exponent representation of a number T (of seconds) is the fol- 3014 lowing: 3016 - find the largest integer 'b' such that: T/C >= 2^b 3017 - compute the expression 16*(T/(C*(2^b))-1), which may not be a 3018 integer, and round it up. This results in the value for 'a' 3020 - if 'a' is equal to 16: increment 'b' by one, and set 'a' to 0 3022 - now, 'a' and 'b' should be integers between 0 and 15, and the 3023 field will be a byte holding the value a*16+b 3025 For instance, for values of 2 seconds, 6 seconds, 15 seconds, and 30 3026 seconds respectively, a and b would be: (a=0,b=5), (a=8,b=6), 3027 (a=14,b=7) and (a=14,b=8) respectively. 3029 18.4. Message Types 3031 HELLO_MESSAGE = 1 3033 TC_MESSAGE = 2 3035 MID_MESSAGE = 3 3037 HNA_MESSAGE = 4 3039 18.5. Link Types 3041 UNSPEC_LINK = 0 3043 ASYM_LINK = 1 3045 SYM_LINK = 2 3047 LOST_LINK = 3 3049 18.6. Neighbor Types 3051 NOT_NEIGH = 0 3053 SYM_NEIGH = 1 3055 MPR_NEIGH = 2 3057 18.7. Link Hysteresis 3059 HYST_THRESHOLD_HIGH = 0.8 3061 HYST_THRESHOLD_LOW = 0.3 3063 HYST_SCALING = 0.5 3065 18.8. Willingness 3067 WILL_NEVER = 0 3069 WILL_LOW = 1 3071 WILL_DEFAULT = 3 3073 WILL_HIGH = 6 3075 WILL_ALWAYS = 7 3077 The willingness of a node may be set to any integer value from 0 to 3078 7, and specifies how willing a node is to be forwarding traffic on 3079 behalf of other nodes. Nodes will, by default, have a willingness 3080 WILL_DEFAULT. WILL_NEVER indicates a node which does not wish to 3081 carry traffic for other nodes, e.g. due to resource constraints 3082 (e.g. low on battery). WILL_ALWAYS indicates that a node always 3083 should be selected to carry traffic on behalf of other nodes, e.g. 3084 due to resource abundance (e.g. permanent power supply, high-capac- 3085 ity interfaces to other nodes). 3087 A node may dynamically change its willingness as its conditions 3088 change. 3090 One possible application would, for example, be for a node, connected 3091 to a permanent power supply and with fully charged batteries, to 3092 advertise a willingness of WILL_ALWAYS. Upon being disconnected from 3093 the permanent power supply (e.g. a PDA being taken out of its charg- 3094 ing cradle), a willingness of WILL_DEFAULT is advertised. As battery 3095 capacity is drained, the willingness would be further reduced. First 3096 to the intermediate value between WILL_DEFAULT and WILL_LOW, then to 3097 WILL_LOW and finally to WILL_NEVER, when the battery capacity of the 3098 node does no longer support carrying foreign traffic. 3100 18.9. Misc. Constants 3102 TC_REDUNDANCY = 0 3104 MPR COVERAGE = 1 3106 MAXJITTER = HELLO_INTERVAL / 4 3108 19. Sequence Numbers 3110 Sequence numbers are used in OLSR with the purpose of discarding 3111 "old" information, i.e. messages received out of order. However 3112 with a limited number of bits for representing sequence numbers, 3113 wrap-around (that the sequence number is incremented from the maximum 3114 possible value to zero) will occur. To prevent this from interfering 3115 with the operation of the protocol, the following MUST be observed. 3117 The term MAXVALUE designates in the following the largest possible 3118 value for a sequence number. 3120 The sequence number S1 is said to be "greater than" the sequence num- 3121 ber S2 iff: 3123 S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR 3125 S2 > S1 AND S2 - S1 > MAXVALUE/2 3127 Thus when comparing two messages, it is possible - even in the pres- 3128 ence of wrap-around - to determine which message contains the most 3129 recent information. 3131 20. Security Considerations 3133 Currently, OLSR does does not specify any special security measures. 3134 As a proactive routing protocol, OLSR makes a target for various 3135 attacks. The various possible vulnerability are discussed in this 3136 section. 3138 20.1. Confidentiality 3140 Being a proactive protocol, OLSR periodically diffuses topological 3141 information. Hence, if used in an unprotected wireless network, the 3142 network topology is revealed to anyone who listens to OLSR control 3143 messages. 3145 In situations where the confidentiality of the network topology is of 3146 importance, regular cryptographic techniques can be applied to ensure 3147 that control traffic can be read and interpreted by only those autho- 3148 rized to do so. 3150 20.2. Integrity 3152 In OLSR, each node is injecting topological information into the net- 3153 work through transmitting HELLO messages and, for some nodes, TC mes- 3154 sages. If some nodes for some reason, malicious or malfunction, 3155 inject invalid control traffic, network integrity may be compromised. 3156 Therefore, message authentication is recommended. 3158 Different such situations may occur, for instance: 3160 1 a node generates TC (or HNA) messages, advertising links to 3161 non-neighbor nodes: 3163 2 a node generates TC (or HNA) messages, pretending to be 3164 another node, 3166 3 a node generates HELLO messages, advertising non-neighbor 3167 nodes, 3169 4 a node generates HELLO messages, pretending to be another 3170 node. 3172 5 a node forwards altered control messages, 3174 6 a node does not broadcast control messages, 3176 7 a node does not select multipoint relays correctly. 3178 8 a node forwards broadcast control messages unaltered, but does 3179 not forward unicast data traffic; 3181 9 a node "replays" previously recorded control traffic from 3182 another node. 3184 Authenticated signatures on control messages (for situation 2, 4 and 3185 5) and on the individual links announced in the control messages (for 3186 situation 1 and 3) may be used as a countermeasure. However to pre- 3187 vent nodes from repeating old (and correctly authenticated) informa- 3188 tion (situation 9) temporal information is required, allowing a node 3189 to positively identify such delayed messages. 3191 Signatures and other required security information may be transmitted 3192 as a separate OLSR message type, thereby allowing that "secured" and 3193 "unsecured" nodes can coexist in the same network, if desired. 3195 20.3. Interaction with External Routing Domains 3197 OLSR does, through the HNA messages specified in section 12, 3198 provide a basic mechanism for injecting external routing information 3199 to the OLSR domain. Section 12 also specifies that routing 3200 information can be extracted from the topology table or the routing 3201 table of OLSR and, potentially, injected into an external domain if 3202 the routing protocol governing that domain permits. 3204 Other than as described in the section 20.2, when operating 3205 nodes, connecting OLSR to an external routing domain, care MUST be 3206 taken not to allow potentially insecure and un-trustworthy informa- 3207 tion to be injected from the OLSR domain to external routing domains. 3208 Care MUST be taken to validate the correctness of information prior 3209 to it being injected as to avoid polluting routing tables with 3210 invalid information. 3212 A recommended way of extending connectivity from an existing routing 3213 domain to an OLSR routed MANET is to assign an IP prefix (under the 3214 authority of the nodes/gateways connecting the MANET with the exiting 3215 routing domain) exclusively to the OLSR MANET area, and to configure 3216 the gateways statically to advertise routes to that IP sequence to 3217 nodes in the existing routing domain. 3219 20.4. Node Identity 3221 OLSR does not make any assumption about node addresses, other than 3222 that each node is assumed to have an unique IP addresses. Therefore, 3223 no special considerations can be made about the applicability of 3224 IPsec authentication headers or key exchange mechanisms. 3226 21. Flow and congestion control 3228 Due to its proactive nature, the OLSR protocol has a natural control 3229 over the flow of its control traffic. Nodes transmits control mes- 3230 sage at predetermined rates fixed by predefined refresh intervals. 3231 In certain options some control messages may be intentionnaly sent in 3232 advance of their deadline(TC or Hello messages) in order to increase 3233 the reactiveness of the protocol against certain events. This may 3234 cause a small, temporary and local increase of control traffic. 3236 22. IANA Considerations 3238 OLSR defines a "Message Type" field for control messages. A new reg- 3239 istry is to be created for the values for this Message Type field, 3240 and the following values assigned: 3242 Message Type Value 3243 -------------------- ----- 3244 HELLO_MESSAGE 1 3245 TC_MESSAGE 2 3246 MID_MESSAGE 3 3247 HNA_MESSAGE 4 3249 Future values in the range 5-127 of the Message Type can be allocated 3250 using standards action [7]. 3252 Additionally, values in the range 128-255 are reserved for pri- 3253 vate/local use. 3255 23. Acknowledgments 3257 The authors would like to thank Joseph Macker 3258 and his team, including Justin Dean 3259 , for their valuable suggestions on the 3260 advanced neighbor sensing mechanism and other various aspects of the 3261 protocol, including careful review of the protocol specification. 3263 The authors would also like to thank Christopher Dearlove 3264 for valuable input on the MPR selec- 3265 tion heuristics and for careful reviews of the protocol specifica- 3266 tion. 3268 24. Contributors 3270 During the development of this specification, the following list of 3271 people contributed. The contributors are listed alphabetically. 3273 Cedric Adjih, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le 3274 Chesnay Cedex, France, Phone: +33 1 3963 5215, Email: 3275 Cedric.Adjih@inria.fr 3277 Thomas Heide Clausen, Project HIPERCOM, INRIA Rocquencourt, BP 105, 3278 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5133, Email: 3279 Thomas.Clausen@inria.fr 3281 Philippe Jacquet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3282 Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email: 3283 Philippe.Jacquet@inria.fr 3285 Anis Laouiti, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le 3286 Chesnay Cedex, France, Phone: +33 1 3963 508832, Email: 3287 Anis.Laouiti@inria.fr 3289 Pascale Minet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le 3290 Chesnay Cedex, France, Phone: +33 1 3963 508832, Email: Pas- 3291 cale.Minet@inria.fr 3293 Paul Muhlethaler, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3294 Le Chesnay Cedex, France, Phone: +33 1 3963 5278, Email: Paul.Muh- 3295 lethaler@inria.fr 3297 Amir Qayyum, Center for Advanced Research in Engineering Pvt. Ltd., 3298 19, Ataturk Avenue, Islamabad, Pakistan, Phone: +92-51-2874115, 3299 Email: amir@carepvtltd.com 3301 Laurent Viennot, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3302 Le Chesnay Cedex, France, Phone: +33 1 3963 5225, Email: Lau- 3303 rent.Viennot@inria.fr 3305 25. Authors' Addresses 3307 Thomas Heide Clausen, Project HIPERCOM, INRIA Rocquencourt, BP 105, 3308 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5133, Email: 3309 Thomas.Clausen@inria.fr 3311 Philippe Jacquet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3312 Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email: 3313 Philippe.Jacquet@inria.fr 3315 26. References 3317 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing 3318 reliability in cable free radio LANs: Low level forwarding in 3319 HIPERLAN. Wireless Personal Communications, 1996 3321 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An effi- 3322 cient technique for flooding in mobile wireless networks. 35th 3323 Annual Hawaii International Conference on System Sciences 3324 (HICSS'2001). 3326 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN 3327 type 1, functional specifications ETS 300-652, ETSI, June 1996 3329 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net- 3330 work Protocols, INRIA research report RR-3965, 2000 3332 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- 3333 els. Request for Comments (Best Current Practice) 2119, Internet 3334 Engineering Task Force, March 1997. 3336 6. T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The 3337 Optimized Link State Routing Protocol, Evaluation through Experi- 3338 ments and Simulation. IEEE Symposium on "Wireless Personal Mobile 3339 Communications", September 2001. 3341 7. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum 3342 and L. Viennot. Optimized Link State Routing Protocol. IEEE 3343 INMIC Pakistan 2001. 3345 8. T. Narten and H. Alvestrand. Guidelines for Writing an IANA Con- 3346 siderations Section in RFCs. Request for Comments (Best Current 3347 Practice) 2434, Internet Engineering Task Force, October 1998. 3349 Reference [5] and [7] are normative; all others are informative.