idnits 2.17.1 draft-ietf-manet-olsr-11.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: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == 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 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 238: '...formation from these interfaces MAY be...' RFC 2119 keyword, line 258: '...R interface node MUST use the address ...' RFC 2119 keyword, line 261: '...R interface node MUST choose one of it...' RFC 2119 keyword, line 264: '..., however a node SHOULD always use the...' RFC 2119 keyword, line 363: '...that all nodes, selected as MPRs, MUST...' (153 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 321 has weird spacing: '..., which have ...' == Line 2784 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 (03 July 2003) is 7602 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. 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? '3' on line 212 looks like a reference -- Missing reference section? '5' on line 3381 looks like a reference -- Missing reference section? '1' on line 2088 looks like a reference -- Missing reference section? '2' on line 420 looks like a reference -- Missing reference section? '0' on line 989 looks like a reference -- Missing reference section? 'MAXJITTER' on line 989 looks like a reference -- Missing reference section? '9' on line 3147 looks like a reference -- Missing reference section? '10' on line 3250 looks like a reference -- Missing reference section? '7' on line 3381 looks like a reference Summary: 7 errors (**), 0 flaws (~~), 4 warnings (==), 12 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: 03 Janyary 2003 Project Hipercom 5 INRIA Rocquencourt, France 6 03 July 2003 8 Optimized Link State Routing Protocol 10 draft-ietf-manet-olsr-11.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). MPRs are selected nodes which forward 46 broadcast messages during the flooding process. This technique 47 substantially reduces the message overhead as compared to a classical 48 flooding mechanism, where every node retransmits each message when it 49 receives the first copy of the message. In OLSR, link state 50 information is generated only by nodes elected as MPRs. Thus, a 51 second optimization is achieved by minimizing the number of control 52 messages flooded in the network. As a third optimization, an MPR 53 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. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . . . 7 65 1.2. Applicability . . . . . . . . . . . . . . . . . . . . . . . . . 9 66 1.3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 10 67 1.4. Multipoint Relays . . . . . . . . . . . . . . . . . . . . . . . 11 68 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . . . 12 69 2.1. Core Functioning . . . . . . . . . . . . . . . . . . . . . . . 12 70 2.2. Auxiliary Functioning . . . . . . . . . . . . . . . . . . . . . 14 71 3. Packet Format and Forwarding . . . . . . . . . . . . . . . . . . 15 72 3.1. Protocol and Port Number . . . . . . . . . . . . . . . . . . . 16 73 3.2. Main Address . . . . . . . . . . . . . . . . . . . . . . . . . 16 74 3.3. Packet Format . . . . . . . . . . . . . . . . . . . . . . . . . 16 75 3.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . . . . . 17 76 3.3.2. Message Header . . . . . . . . . . . . . . . . . . . . . . . 17 77 3.4. Packet Processing and Message Flooding . . . . . . . . . . . . 19 78 3.4.1. Default Forwarding Algorithm . . . . . . . . . . . . . . . . 21 79 3.4.2. Considerations on Processing and Forwarding . . . . . . . . . 22 80 3.5. Message Emission and Jitter . . . . . . . . . . . . . . . . . . 23 81 4. Information Repositories . . . . . . . . . . . . . . . . . . . . 24 82 4.1. Multiple Interface Association Information Base . . . . . . . . 24 83 4.2. Link sensing: Local Link Information Base . . . . . . . . . . . 25 84 4.2.1. Link Set . . . . . . . . . . . . . . . . . . . . . . . . . . 25 85 4.3. Neighbor Detection: Neighborhood Information Base . . . . . . . 25 86 4.3.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . . . . 25 87 4.3.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . . . . 26 88 4.3.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 89 4.3.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . . . . 26 90 4.4. Topology Information Base . . . . . . . . . . . . . . . . . . . 26 91 5. Main Addresses and Multiple Interfaces . . . . . . . . . . . . . 27 92 5.1. MID Message Format . . . . . . . . . . . . . . . . . . . . . . 27 93 5.2. MID Message Generation . . . . . . . . . . . . . . . . . . . . 28 94 5.3. MID Message Forwarding . . . . . . . . . . . . . . . . . . . . 28 95 5.4. MID Message Processing . . . . . . . . . . . . . . . . . . . . 29 96 5.5. Resolving a Main Address from an Interface Address . . . . . . 29 97 6. HELLO Message Format and Generation . . . . . . . . . . . . . . . 30 98 6.1. HELLO Message Format . . . . . . . . . . . . . . . . . . . . . 30 99 6.1.1. Link Code as Link Type and Neighbor Type . . . . . . . . . . 33 100 6.2. HELLO Message Generation . . . . . . . . . . . . . . . . . . . 34 101 6.3. HELLO Message Forwarding . . . . . . . . . . . . . . . . . . . 36 102 6.4. HELLO Message Processing . . . . . . . . . . . . . . . . . . . 36 103 7. Link Sensing . . . . . . . . . . . . . . . . . . . . . . . . . . 36 104 7.1. Populating the Link Set . . . . . . . . . . . . . . . . . . . . 37 105 7.1.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 37 106 8. Neighbor Detection . . . . . . . . . . . . . . . . . . . . . . . 39 107 8.1. Populating the Neighbor Set . . . . . . . . . . . . . . . . . . 39 108 8.1.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 40 109 8.2. Populating the 2-hop Neighbor Set . . . . . . . . . . . . . . . 41 110 8.2.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 41 111 8.3. Populating the MPR set . . . . . . . . . . . . . . . . . . . . 42 112 8.3.1. MPR Computation . . . . . . . . . . . . . . . . . . . . . . . 43 113 8.4. Populating the MPR Selector Set . . . . . . . . . . . . . . . . 45 114 8.4.1. HELLO Message Processing . . . . . . . . . . . . . . . . . . 45 115 8.5. Neighborhood and 2-hop Neighborhood Changes . . . . . . . . . . 46 116 9. Topology Discovery . . . . . . . . . . . . . . . . . . . . . . . 47 117 9.1. TC Message Format . . . . . . . . . . . . . . . . . . . . . . . 47 118 9.2. Advertised Neighbor Set . . . . . . . . . . . . . . . . . . . . 48 119 9.3. TC Message Generation . . . . . . . . . . . . . . . . . . . . . 49 120 9.4. TC Message Forwarding. . . . . . . . . . . . . . . . . . . . . 49 121 9.5. TC Message Processing . . . . . . . . . . . . . . . . . . . . . 49 122 10. Routing Table Calculation . . . . . . . . . . . . . . . . . . . 51 123 11. Node Configuration . . . . . . . . . . . . . . . . . . . . . . . 54 124 11.1. Address Assignment . . . . . . . . . . . . . . . . . . . . . . 54 125 11.2. Routing Configuration . . . . . . . . . . . . . . . . . . . . 55 126 11.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . . . 55 127 12. Non OLSR Interfaces . . . . . . . . . . . . . . . . . . . . . . 55 128 12.1. HNA Message Format . . . . . . . . . . . . . . . . . . . . . . 56 129 12.2. Host and Network Association Information Base . . . . . . . . 56 130 12.3. HNA Message Generation . . . . . . . . . . . . . . . . . . . . 57 131 12.4. HNA Message Forwarding . . . . . . . . . . . . . . . . . . . . 57 132 12.5. HNA Message Processing . . . . . . . . . . . . . . . . . . . . 57 133 12.6. Routing Table Calculation . . . . . . . . . . . . . . . . . . 58 134 12.7. Interoperability Considerations . . . . . . . . . . . . . . . 59 135 13. Link Layer Notification . . . . . . . . . . . . . . . . . . . . 59 136 13.1. Interoperability Considerations . . . . . . . . . . . . . . . 60 137 14. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . . 60 138 14.1. Local Link Set . . . . . . . . . . . . . . . . . . . . . . . . 61 139 14.2. Hello Message Generation . . . . . . . . . . . . . . . . . . . 61 140 14.3. Hysteresis Strategy . . . . . . . . . . . . . . . . . . . . . 62 141 14.4. Interoperability Considerations . . . . . . . . . . . . . . . 64 142 15. Redundant Topology Information . . . . . . . . . . . . . . . . . 64 143 15.1. TC_REDUNDANCY Parameter . . . . . . . . . . . . . . . . . . . 64 144 15.2. Interoperability Considerations . . . . . . . . . . . . . . . 65 145 16. MPR Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . 65 146 16.1. MPR_COVERAGE Parameter . . . . . . . . . . . . . . . . . . . . 65 147 16.2. MPR Computation . . . . . . . . . . . . . . . . . . . . . . . 66 148 16.3. Interoperability Considerations . . . . . . . . . . . . . . . 67 149 17. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . . . 67 150 18. Proposed Values for Constants . . . . . . . . . . . . . . . . . 68 151 18.1. Setting emission interval and holding times . . . . . . . . . 68 152 18.2. Emission Interval . . . . . . . . . . . . . . . . . . . . . . 68 153 18.3. Holding time . . . . . . . . . . . . . . . . . . . . . . . . . 69 154 18.4. Message Types . . . . . . . . . . . . . . . . . . . . . . . . 70 155 18.5. Link Types . . . . . . . . . . . . . . . . . . . . . . . . . . 70 156 18.6. Neighbor Types . . . . . . . . . . . . . . . . . . . . . . . . 70 157 18.7. Link Hysteresis . . . . . . . . . . . . . . . . . . . . . . . 70 158 18.8. Willingness . . . . . . . . . . . . . . . . . . . . . . . . . 71 159 18.9. Misc. Constants . . . . . . . . . . . . . . . . . . . . . . . 72 160 19. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . . 72 161 20. Security Considerations . . . . . . . . . . . . . . . . . . . . 72 162 20.1. Confidentiality . . . . . . . . . . . . . . . . . . . . . . . 72 163 20.2. Integrity . . . . . . . . . . . . . . . . . . . . . . . . . . 73 164 20.3. Interaction with External Routing Domains . . . . . . . . . . 74 165 20.4. Node Identity . . . . . . . . . . . . . . . . . . . . . . . . 75 166 21. Flow and congestion control . . . . . . . . . . . . . . . . . . 75 167 22. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 75 168 23. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 76 169 24. Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . 76 170 25. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 77 171 26. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 172 1. Introduction 174 The Optimized Link State Routing Protocol (OLSR) is developed for 175 mobile ad hoc networks. It operates as a table driven, proactive 176 protocol, i.e exchanges topology information with other nodes of the 177 network regularly. Each node selects a set of its neighbor nodes as 178 "multipoint relays" (MPR). In OLSR, only nodes, selected as such 179 MPRs, are responsible for forwarding control traffic, intended for 180 diffusion into the entire network. MPRs provide an efficient 181 mechanism for flooding control traffic by reducing the number of 182 transmissions required. 184 Nodes, selected as MPRs, also have a special responsibility when 185 declaring link state information in the network. Indeed, the only 186 requirement for OLSR to provide shortest path routes to all 187 destinations is that MPR nodes declare link-state information for 188 their MPR selectors. Additional available link-state information may 189 be utilized, e.g. for redundancy. 191 Nodes which have been selected as multipoint relays by some neighbor 192 node(s) announce this information periodically in their control 193 messages. Thereby a node announces to the network, that it has 194 reachability to the nodes which have selected it as an MPR. In route 195 calculation, the MPRs are used to form the route from a given node to 196 any destination in the network. Furthermore, the protocol uses the 197 MPRs to facilitate efficient flooding of control messages in the 198 network. 200 A node selects MPRs from among its one hop neighbors with 201 "symmetrical", i.e. bi-directional, linkages. Therefore, selecting 202 the route through MPRs automatically avoids the problems associated 203 with data packet transfer over uni-directional links (such as the 204 problem of not getting link-layer acknowledgments for data packets at 205 each hop, for link-layers employing this technique for unicast 206 traffic). 208 OLSR is developed to work independently from other protocols. 209 Likewise, 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. OLSR Terminology 218 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 219 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 220 document are to be interpreted as described in RFC2119 [5]. 221 Additionally, this document uses the following terminology: 223 node 225 A MANET router which implements the Optimized Link State 226 Routing protocol as specified in this document. 228 OLSR interface 230 A network device participating in a MANET running OLSR. A 231 node may have several OLSR interfaces, each interface assigned 232 an unique IP address. 234 non OLSR interface 236 A network device, not participating in a MANET running OLSR. 237 A node may have several non OLSR interfaces (wireless and/or 238 wired). Routing information from these interfaces MAY be 239 injected into the OLSR routing domain. 241 single OLSR interface node 243 A node which has a single OLSR interface, participating in an 244 OLSR routing domain. 246 multiple OLSR interface node 248 A node which has multiple OLSR interfaces, participating in an 249 OLSR routing domain. 251 main address 253 The main address of a node, which will be used in OLSR control 254 traffic as the "originator address" of all messages emitted by 255 this node. It is the address of one of the OLSR interfaces of 256 the node. 258 A single OLSR interface node MUST use the address of its only 259 OLSR interface as the main address. 261 A multiple OLSR interface node MUST choose one of its OLSR 262 interface addresses as its "main address" (equivalent of 263 "router ID" or "node identifier"). It is of no importance 264 which address is chosen, however a node SHOULD always use the 265 same address as its main address. 267 neighbor node 269 A node X is a neighbor node of node Y if node Y can hear node 270 X (i.e. a bidirectional link exists between an OLSR 271 interfaces on node X and an OLSR interface on Y). 273 2-hop neighbor 275 A node heard by a neighbor. 277 strict 2-hop neighbor 279 a 2-hop neighbor which is not the node itself or a neighbor of 280 the node, and in addition is a neighbor of a neighbor, with 281 willingness different from WILL_NEVER, of the node. 283 multipoint relay (MPR) 285 A node which is selected by its one-hop neighbor, node X, to 286 "re-transmit" all the broadcast messages that it receives from 287 X, provided that the message is not a duplicate, and that the 288 time to live field of the message is greater than one. 290 multipoint relay selector (MPR selector, MS) 292 A node which has selected its one-hop neighbor, node X, as its 293 multipoint relay, will be called a multipoint relay selector 294 of node X. 296 link 298 A link is a pair of OLSR interfaces (from two different nodes) 299 susceptible to hear one another (i.e. one may be able to 300 receive traffic from the other). A node is said to have a 301 link to another node when one of its interface has a link to 302 one of the interfaces of the other node. 304 symmetric link 306 A verified bi-directional link between two OLSR interfaces. 308 asymmetric link 310 A link between two OLSR interfaces, verified in only one 311 direction. 313 symmetric 1-hop neighborhood 315 The symmetric 1-hop neighborhood of any node X is the set of 316 nodes which have at least one symmetric link to X. 318 symmetric 2-hop neighborhood 320 The symmetric 2-hop neighborhood of X is the set of nodes, 321 excluding X itself, which have a symmetric link to the 322 symmetric 1-hop neighborhood of X. 324 symmetric strict 2-hop neighborhood 326 The symmetric 2-hop neighborhood of X is the set of nodes, 327 excluding X itself and its neighbors, which have a symmetric 328 link to some symmetric 1-hop neighbor, with willingness 329 different of WILL_NEVER, of X. 331 1.2. Applicability 333 OLSR is a proactive routing protocol for mobile ad-hoc networks 334 (MANETs) [1], [2]. It is well suited to large and dense mobile 335 networks, as the optimization achieved using the MPRs works well in 336 this context. The larger and more dense a network, the more 337 optimization can be achieved as compared to the classic link state 338 algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its 339 local information to route packets. 341 OLSR is well suited for networks, where the traffic is random and 342 sporadic between a larger set of nodes rather than being almost 343 exclusively between a small specific set of nodes. As a proactive 344 protocol, OLSR is also suitable for scenarios where the communicating 345 pairs change over time: no additional control traffic is generated in 346 this situation since routes are maintained for all known destinations 347 at all times. 349 1.3. Protocol Overview 351 OLSR is a proactive routing protocol for mobile ad hoc networks. The 352 protocol inherits the stability of a link state algorithm and has the 353 advantage of having routes immediately available when needed due to 354 its proactive nature. OLSR is an optimization over the classical 355 link state protocol, tailored for mobile ad hoc networks. 357 OLSR minimizes the overhead from flooding of control traffic by using 358 only selected nodes, called MPRs, to retransmit control messages. 359 This technique significantly reduces the number of retransmissions 360 required to flood a message to all nodes in the network. Secondly, 361 OLSR requires only partial link state to be flooded in order to 362 provide shortest path routes. The minimal set of link state 363 information required is, that all nodes, selected as MPRs, MUST 364 declare the links to their MPR selectors. Additional topological 365 information, if present, MAY be utilized e.g. for redundancy 366 purposes. 368 OLSR MAY optimize the reactivity to topological changes by reducing 369 the maximum time interval for periodic control message transmission. 370 Furthermore, as OLSR continuously maintains routes to all 371 destinations in the network, the protocol is beneficial for traffic 372 patterns where a large subset of nodes are communicating with another 373 large subset of nodes, and where the [source, destination] pairs are 374 changing over time. The protocol is particularly suited for large 375 and dense networks, as the optimization done using MPRs works well in 376 this context. The larger and more dense a network, the more 377 optimization can be achieved as compared to the classic link state 378 algorithm. 380 OLSR is designed to work in a completely distributed manner and does 381 not depend on any central entity. The protocol does NOT REQUIRE 382 reliable transmission of control messages: each node sends control 383 messages periodically, and can therefore sustain a reasonable loss of 384 some such messages. Such losses occur frequently in radio networks 385 due to collisions or other transmission problems. 387 Also, OLSR does not require sequenced delivery of messages. Each 388 control message contains a sequence number which is incremented for 389 each message. Thus the recipient of a control message can, if 390 required, easily identify which information is more recent - even if 391 messages have been re-ordered while in transmission. 393 Furthermore, OLSR provides support for protocol extensions such as 394 sleep mode operation, multicast-routing etc. Such extensions may be 395 introduced as additions to the protocol without breaking backwards 396 compatibility with earlier versions. 398 OLSR does not require any changes to the format of IP packets. Thus 399 any existing IP stack can be used as is: the protocol only interacts 400 with routing table management. 402 1.4. Multipoint Relays 404 The idea of multipoint relays is to minimize the overhead of flooding 405 messages in the network by reducing redundant retransmissions in the 406 same region. Each node in the network selects a set of nodes in its 407 symmetric 1-hop neighborhood which may retransmit its messages. This 408 set of selected neighbor nodes is called the "Multipoint Relay" (MPR) 409 set of that node. The neighbors of node N which are *NOT* in its MPR 410 set, receive and process broadcast messages but do not retransmit 411 broadcast messages received from node N. 413 Each node selects its MPR set from among its one hop symmetric 414 neighbors. This set is selected such that it covers (in terms of 415 radio range) all symmetric strict 2-hop nodes. The MPR set of N, 416 denoted as MPR(N), is then an arbitrary subset of the symmetric 1-hop 417 neighborhood of N which satisfies the following condition: every node 418 in the symmetric strict 2-hop neighborhood of N must have a symmetric 419 link towards MPR(N). The smaller a MPR set, the less control traffic 420 overhead results from the routing protocol. [2] gives an analysis 421 and example of MPR selection algorithms. 423 Each node maintains information about the set of neighbors that have 424 selected it as MPR. This set is called the "Multipoint Relay 425 Selector set" (MPR selector set) of a node. A node obtains this 426 information from periodic HELLO messages received from the neighbors. 428 A broadcast message, intended to be diffused in the whole network, 429 coming from any of the MPR selectors of node N is assumed to be 430 retransmitted by node N, if N has not received it yet. This set can 431 change over time (i.e. when a node selects another MPR-set) and is 432 indicated by the selector nodes in their HELLO messages. 434 2. Protocol Functioning 436 This section outlines the overall protocol functioning. 438 OLSR is modularized into a "core" of functionality, which is always 439 required for the protocol to operate, and a set of auxiliary 440 functions. 442 The core specifies, in its own right, a protocol able to provide 443 routing in a stand-alone MANET. 445 Each auxiliary function provides additional functionality, which may 446 be applicable in specific scenarios. E.g. in case a node is 447 providing connectivity between the MANET and another routing domain. 449 All auxiliary functions are compatible, to the extent where any 450 (sub)set of auxiliary functions may be implemented with the core. 451 Furthermore, the protocol allows heterogeneous nodes, i.e. nodes 452 which implement different subsets of the auxiliary functions, to 453 coexist in the network. 455 The purpose of dividing the functioning of OLSR into a core 456 functionality and a set of auxiliary functions is to provide a simple 457 and easy-to-comprehend protocol, and to provide a way of only adding 458 complexity where specific additional functionality is required. 460 2.1. Core Functioning 462 The core functionality of OLSR specifies the behavior of a node, 463 equipped with OLSR interfaces participating in the MANET and running 464 OLSR as routing protocol. This includes a universal specification of 465 OLSR protocol messages and their transmission through the network, as 466 well as link sensing, topology diffusion and route calculation. 468 Specifically, the core is made up from the following components: 470 Packet Format and Forwarding 472 An universal specification of the packet format and an 473 optimized flooding mechanism serves as the transport mechanism 474 for all OLSR control traffic. 476 Link Sensing 477 Link Sensing is accomplished through periodic emission of 478 HELLO messages over the interfaces through which connectivity 479 is checked. A separate HELLO message is generated for each 480 interface and emitted in correspondence with the provisions in 481 section 7. 483 Resulting from Link Sensing is a local link set, describing 484 links between "local interfaces" and "remote interfaces" - 485 i.e. interfaces on neighbor nodes. 487 If sufficient information is provided by the link-layer, this 488 may be utilized to populate the local link set instead of 489 HELLO message exchange. 491 Neighbor detection 493 Given a network with only single interface nodes, a node may 494 deduct the neighbor set directly from the information 495 exchanged as part of link sensing: the "main address" of a 496 single interface node is, by definition, the address of the 497 only interface on that node. 499 In a network with multiple interface nodes, additional 500 information is required in order to map interface addresses to 501 main addresses (and, thereby, to nodes). This additional 502 information is acquired through multiple interface declaration 503 (MID) messages, described in section 5. 505 MPR Selection and MPR Signaling 507 The objective of MPR selection is for a node to select a 508 subset of its neighbors such that a broadcast message, 509 retransmitted by these selected neighbors, will be received by 510 all nodes 2 hops away. The MPR set of a node is computed such 511 that it, for each interface, satisfies this condition. The 512 information required to perform this calculation is acquired 513 throuth the periodic exchange of HELLO messages, as described 514 in section 6. MPR selection procedures are 515 detailed in section 8.3. 517 MPR signaling is provided in correspondence with the 518 provisions in the section 6. 520 Topology Control Message Diffusion 521 Topology Control messages are diffused with the purpose of 522 providing each node in the network with sufficient link-state 523 information to allow route calculation. Topology Control 524 messages are diffused in correspondence with the provisions in 525 section 9. 527 Route Calculation 529 Given the link state information acquired through periodic 530 message exchange, as well as the interface configuration of 531 the nodes, the routing table for each node can be computed. 532 This is detailed in section 10 534 The key notion for these mechanisms is the MPR relationship. 536 The following table specifies the component of the core functionality 537 of OLSR, as well as their relations to this document. 539 Feature | Section 540 ------------------------------+-------------- 541 Packet format and forwarding | 3 542 Information repositories | 4 543 Main addr and multiple if. | 5 544 Hello messages | 6 545 Link sensing | 7 546 Neighbor detection | 8 547 Topology discovery | 9 548 Routing table computation | 10 549 Node configuration | 11 551 2.2. Auxiliary Functioning 553 In addition to the core functioning of OLSR, there are situations 554 where additional functionality is desired. This includes situations 555 where a node has multiple interfaces, some of which participate in 556 another routing domain, where the programming interface to the 557 networking hardware provides additional information in form of link 558 layer notifications and where it is desired to provide redundant 559 topological information to the network on expense of protocol 560 overhead. 562 The following table specifies auxiliary functions and their relation 563 to this document. 565 Feature | Section 566 ------------------------------+-------------- 567 Non-OLSR interfaces | 12 568 Link-layer notifications | 13 569 Advanced link sensing | 14 570 Redundant topology | 15 571 Redundant MPR flooding | 16 573 The interpretation of the above table is as follows: if the feature 574 listed is required, it SHOULD be provided as specified in the 575 corresponding section. 577 3. Packet Format and Forwarding 579 OLSR communicates using a unified packet format for all data related 580 to the protocol. The purpose of this is to facilitate extensibility 581 of the protocol without breaking backwards compatibility. This also 582 provides an easy way of piggybacking different "types" of information 583 into a single transmission, and thus for a given implementation to 584 optimize towards utilizing the maximal frame-size, provided by the 585 network. These packets are embedded in UDP datagrams for 586 transmission over the network. The present draft is presented with 587 IPv4 addresses. Considerations regarding IPv6 are given in section 588 17. 590 Each packet encapsulates one or more messages. The messages share a 591 common header format, which enables nodes to correctly accept and (if 592 applicable) retransmit messages of an unknown type. 594 Messages can be flooded onto the entire network, or flooding can be 595 limited to nodes within a diameter (in terms of number of hops) from 596 the originator of the message. Thus transmitting a message to the 597 neighborhood of a node is just a special case of flooding. When 598 flooding any control message, duplicate retransmissions will be 599 eliminated locally (i.e. each node maintains a duplicate set to 600 prevent transmitting the same OLSR control message twice) and 601 minimized in the entire network through the usage of MPRs as 602 described in later sections. 604 Furthermore, a node can examine the header of a message to obtain 605 information on the distance (in terms of number of hops) to the 606 originator of the message. This feature may be useful in situations 607 where, e.g., the time information from a received control messages 608 stored in a node depends on the distance to the originator. 610 3.1. Protocol and Port Number 612 Packets in OLSR are communicated using UDP. Port 698 has been 613 assigned by IANA for exclusive usage by the OLSR protocol. 615 3.2. Main Address 617 For a node with one interface, the main address of a node, as defined 618 in "OLSR Terminology", MUST be set to the address of that interface. 620 3.3. Packet Format 622 The basic layout of any packet in OLSR is as follows (omitting IP and 623 UDP headers): 625 0 1 2 3 626 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 627 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 628 | Packet Length | Packet Sequence Number | 629 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 630 | Message Type | Vtime | Message Size | 631 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 632 | Originator Address | 633 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 634 | Time To Live | Hop Count | Message Sequence Number | 635 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 636 | | 637 : MESSAGE : 638 | | 639 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 640 | Message Type | Vtime | Message Size | 641 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 642 | Originator Address | 643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 644 | Time To Live | Hop Count | Message Sequence Number | 645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 646 | | 647 : MESSAGE : 648 | | 649 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 650 : : 651 (etc) 653 3.3.1. Packet Header 655 Packet Length 657 The length (in bytes) of the packet 659 Packet Sequence Number 661 The Packet Sequence Number (PSN) MUST be incremented by one 662 each time a new OLSR packet is transmitted. "Wrap-around" is 663 handled as described in section 19. A separate Packet 664 Sequence Number is maintained for each interface such that 665 packets transmitted over an interface are sequentially 666 enumerated. 668 The IP address of the interface over which a packet was transmitted 669 is obtainable from the IP header of the packet. 671 If the packet contains no messages (i.e. the Packet Length is less 672 than or equal to the size of the packet header), the packet MUST 673 silently be discarded. 675 For IPv4 addresses, this implies that packets, where the Packet 676 Length < 16 MUST silently be discarded. 678 3.3.2. Message Header 680 Message Type 682 This field indicates which type of message is to be found in 683 the "MESSAGE" part. Message types in the range of 0-127 are 684 reserved for messages in this document and in possible 685 extensions. 687 Vtime 689 This field indicates for how long time after reception a node 690 MUST consider the information contained in the message as 691 valid, unless a more recent update to the information is 692 received. The validity time is represented by its mantissa 693 (four highest bits of Vtime field) and by its exponent (four 694 lowest bits of Vtime field). In other words: 696 validity time = C*(1+a/16)* 2^b [in seconds] 698 where a is the integer represented by the four highest bits of 699 Vtime field and b the integer represented by the four lowest 700 bits of Vtime field. The proposed value of the scaling factor 701 C is specified in section 18. 703 Message Size 705 This field gives the size of this message, counted in bytes 706 and measured from the beginning of the "Message Type" field 707 and until the beginning of the next "Message Type" field (or - 708 if there are no following messages - until the end of the 709 packet). 711 Originator Address 713 This field contains the main address of the node, which has 714 originally generated this message. This field SHOULD NOT be 715 confused with the source address from the IP header, which is 716 changed each time to the address of the intermediate interface 717 which is re-transmitting this message. The Originator Address 718 field MUST *NEVER* be changed in retransmissions. 720 Time To Live 722 This field contains the maximum number of hops a message will 723 be transmitted. Before a message is retransmitted, the Time 724 To Live MUST be decremented by 1. When a node receives a 725 message with a Time To Live equal to 0 or 1, the message MUST 726 NOT be retransmitted under any circumstances. Normally, a 727 node would not receive a message with a TTL of zero. 729 Thus, by setting this field, the originator of a message can 730 limit the flooding radius. 732 Hop Count 734 This field contains the number of hops a message has attained. 735 Before a message is retransmitted, the Hop Count MUST be 736 incremented by 1. 738 Initially, this is set to '0' by the originator of the 739 message. 741 Message Sequence Number 743 While generating a message, the "originator" node will assign 744 a unique identification number to each message. This number 745 is inserted into the Sequence Number field of the message. 746 The sequence number is increased by 1 (one) for each message 747 originating from the node. "Wrap-around" is handled as 748 described in section 19. Message sequence numbers are 749 used to ensure that a given message is not retransmitted more 750 than once by any node. 752 3.4. Packet Processing and Message Flooding 754 Upon receiving a basic packet, a node examines each of the "message 755 headers". Based on the value of the "Message Type" field, the node 756 can determine the fate of the message. A node may receive the same 757 message several times. Thus, to avoid re-processing of some messages 758 which were already received and processed, each node maintains a 759 Duplicate Set. In this set, the node records information about the 760 most recently received messages where duplicate processing of a 761 message is to be avoided. For such a message, a node records a 762 "Duplicate Tuple" (D_addr, D_seq_num, D_retransmitted, D_iface_list, 763 D_time), where D_addr is the originator address of the message, 764 D_seq_num is the message sequence number of the message, 765 D_retransmitted is a boolean indicating whether the message has been 766 already retransmitted, D_iface_list is a list of the addresses of the 767 interfaces on which the message has been received and D_time 768 specifies the time at which a tuple expires and *MUST* be removed. 770 In a node, the set of Duplicate Tuples are denoted the "Duplicate 771 set". 773 In this section, the term "Originator Address" will be used for the 774 main address of the node which sent the message. The term "Sender 775 Interface Address" will be used for the sender address (given in the 776 IP header of the packet containing the message) of the interface 777 which sent the message. The term "Receiving Interface Address" will 778 be used for the address of the interface of the node which received 779 the message. 781 Thus, upon receiving a basic packet, a node MUST perform the 782 following tasks for each encapsulated message: 784 1 If the packet contains no messages (i.e. the Packet Length is 785 less than or equal to the size of the packet header), the 786 packet MUST silently be discarded. 788 For IPv4 addresses, this implies that packets, where the 789 Packet Length < 16 MUST silently be discarded. 791 2 If the time to live of the message is less than or equal to 792 '0' (zero), or if the message was sent by the receiving node 793 (i.e. the Originator Address of the message is the main 794 address of the receiving node): the message MUST silently be 795 dropped. 797 3 Processing condition: 799 3.1 if there exists a tuple in the duplicate set, where: 801 D_addr == Originator Address, AND 803 D_seq_num == Message Sequence Number 805 then the message has already been completely processed 806 and MUST not be processed again. 808 3.2 Otherwise, if the node implements the Message Type of the 809 message, the message MUST be processed according to the 810 specifications for the message type. 812 4 Forwarding condition: 814 4.1 if there exists a tuple in the duplicate set, where: 816 D_addr == Originator Address, AND 818 D_seq_num == Message Sequence Number, 819 AND 821 the receiving interface (address) is 822 in D_iface_list 824 then the message has already been considered for 825 forwarding and SHOULD NOT be retransmitted again. 827 4.2 Otherwise: 829 4.2.1 830 If the node implements the Message Type of the 831 message, the message MUST be considered for 832 forwarding according to the specifications for 833 the message type. 835 4.2.2 836 Otherwise, if the node does not implement the 837 Message Type of the message, the message SHOULD 838 be processed according to the default 839 forwarding algorithm described below. 841 3.4.1. Default Forwarding Algorithm 843 The default forwarding algorithm is the following: 845 1 If the sender interface address of the message is not detected 846 to be in the symmetric 1-hop neighborhood of the node, the 847 forwarding algorithm MUST silently stop here (and the message 848 MUST NOT be forwarded). 850 2 If there exists a tuple in the duplicate set where: 852 D_addr == Originator Address 854 D_seq_num == Message Sequence Number 856 Then the message will be further considered for forwarding if 857 and only if: 859 D_retransmitted is false, AND 861 the (address of the) interface which received the message 862 is not included among the addresses in D_iface_list 864 3 Otherwise, if such an entry doesn't exist, the message is 865 further considered for forwarding. 867 If after those steps, the message is not considered for forwarding, 868 then the processing of this section stops (i.e. steps 4 to 8 are 869 ignored), otherwise, if it is still considered for forwarding then 870 the following algorithm is used: 872 4 If the sender interface address is an interface address of a 873 MPR selector of this node and if the time to live of the 874 message is greater than '1', the message MUST be retransmitted 875 (as described later in steps 6 to 8). 877 5 If an entry in the duplicate set exists, with same Originator 878 Address, and same Message Sequence Number, the entry is 879 updated as follows: 881 D_time = current time + DUP_HOLD_TIME. 883 The receiving interface (address) is added to 884 D_iface_list. 886 D_retransmitted is set to true if and only if the message 887 will be retransmitted according to step 4. 889 Otherwise an entry in the duplicate set is recorded with: 891 D_addr = Originator Address 893 D_seq_num = Message Sequence Number 895 D_time = current time + DUP_HOLD_TIME. 897 D_iface_list contains the receiving interface address. 899 D_retransmitted is set to true if and only if the message 900 will be retransmitted according to step 4. 902 If, and only if, according to step 4, the message must be 903 retransmitted then: 905 6 The TTL of the message is reduced by one. 907 7 The hop-count of the message is increased by one 909 8 The message is broadcast on all interfaces (Notice: The 910 remaining fields of the message header SHOULD be left 911 unmodified.) 913 3.4.2. Considerations on Processing and Forwarding 915 It should be noted that processing and forwarding messages are two 916 different actions, conditioned by different rules. Processing 917 relates to using the content of the messages, while forwarding is 918 related to retransmitting the same message for other nodes of the 919 network. 921 Notice that this specification includes a description for both the 922 forwarding and the processing of each known message type. Messages 923 with known message types MUST *NOT* be forwarded "blindly" by this 924 algorithm. Forwarding (and setting the correct message header in the 925 forwarded, known, message) is the responsibility of the algorithm 926 specifying how the message is to be handled and, if necessary, 927 retransmitted. This enables a message type to be specified such that 928 the message can be modified while in transit (e.g. to reflect the 929 route the message has taken). It also enables bypassing of the MPR 930 flooding mechanism if for some reason classical flooding of a message 931 type is required, the algorithm which specifies how such messages 932 should be handled will simply rebroadcast the message, regardless of 933 MPRs. 935 By defining a set of message types, which MUST be recognized by all 936 implementations of OLSR, it will be possible to extend the protocol 937 through introduction of additional message types, while still being 938 able to maintain compatibility with older implementations. The 939 REQUIRED message types for the core functionality of OLSR are: 941 - HELLO-messages, performing the task of link sensing, neighbor 942 detection and MPR signaling, 944 - TC-messages, performing the task of topology declaration 945 (advertisement of link states). 947 - MID-messages, performing the task of declaring the presence of 948 multiple interfaces on a node. 950 Other message types include those specified in later sections, as 951 well as possible future extensions such as messages enabling power 952 conservation / sleep mode, multicast routing, support for 953 unidirectional links, auto-configuration/address assignment etc. 955 3.5. Message Emission and Jitter 957 As a basic implementation requirement, synchronization of control 958 messages SHOULD be avoided. As a consequence, OLSR control messages 959 SHOULD be emitted such that they avoid synchronization. 961 Emission of control traffic from neighboring nodes may, for various 962 reasons (mainly timer interactions with packet processing), become 963 synchronized such that several neighbor nodes attempt to transmit 964 control traffic simultaneously. Depending on the nature of the 965 underlying link-layer, this may or may not lead to collisions and 966 hence message loss - possibly loss of several subsequent messages of 967 the same type. 969 To avoid such synchronizations, the following simple strategy for 970 emitting control messages is proposed. A node SHOULD add an amount 971 of jitter to the interval at which messages are generated. The 972 jitter must be a random value for each message generated. Thus, for 973 a node utilizing jitter: 975 Actual message interval = MESSAGE_INTERVAL - jitter 977 Where jitter is a value, randomly selected from the interval 978 [0,MAXJITTER] and MESSAGE_INTERVAL is the value of the message 979 interval specified for the message being emitted (e.g. 980 HELLO_INTERVAL for HELLO messages, TC_INTERVAL for TC-messages etc.). 982 Jitter SHOULD also be introduced when forwarding messages. The 983 following simple strategy may be adopted: when a message is to be 984 forwarded by a node, it should be kept in the node during a short 985 period of time : 987 Keep message period = jitter 989 Where jitter is a random value in [0,MAXJITTER]. 991 Notice that when the node sends a control message, the opportunity to 992 piggyback other messages (before their keeping period is expired) may 993 be taken to reduce the number of packet transmissions. 995 Notice, that a minimal rate of control messages is imposed. A node 996 MAY send control messages at a higher rate, if beneficial for a 997 specific deployment. 999 4. Information Repositories 1001 Through the exchange of OLSR control messages, each node accumulates 1002 information about the network. This information is stored according 1003 to the descriptions in this section. 1005 4.1. Multiple Interface Association Information Base 1007 For each destination in the network, "Interface Association Tuples" 1008 (I_iface_addr, I_main_addr, I_time) are recorded. I_iface_addr is an 1009 interface address of a node, I_main_addr is the main address of this 1010 node. I_time specifies the time at which this tuple expires and 1011 *MUST* be removed. 1013 In a node, the set of Interface Association Tuples is denoted the 1014 "Interface Association Set". 1016 4.2. Link Sensing: Local Link Information Base 1018 The local link information base stores information about links to 1019 neighbors. 1021 4.2.1. Link Set 1023 A node records a set of "Link Tuples" (L_local_iface_addr, 1024 L_neighbor_iface_addr, L_SYM_time, L_ASYM_time, L_time). 1025 L_local_iface_addr is the interface address of the local node (i.e. 1026 one endpoint of the link), L_neighbor_iface_addr is the interface 1027 address of the neighbor node (i.e. the other endpoint of the link), 1028 L_SYM_time is the time until which the link is considered symmetric, 1029 L_ASYM_time is the time until which the neighbor interface is 1030 considered heard, and L_time specifies the time at which this record 1031 expires and *MUST* be removed. When L_SYM_time and L_ASYM_time are 1032 expired, the link is considered lost. 1034 This information is used when declaring the neighbor interfaces in 1035 the HELLO messages. 1037 L_SYM_time is used to decide the Link Type declared for the neighbor 1038 interface. If L_SYM_time is not expired, the link MUST be declared 1039 symmetric. If L_SYM_time is expired, the link MUST be declared 1040 asymmetric. If both L_SYM_time and L_ASYM_time are expired, the link 1041 MUST be declared lost. 1043 In a node, the set of Link Tuples are denoted the "Link Set". 1045 4.3. Neighbor Detection: Neighborhood Information Base 1047 The neighborhood information base stores information about neighbors, 1048 2-hop neighbors, MPRs and MPR selectors. 1050 4.3.1. Neighbor Set 1052 A node records a set of "neighbor tuples" (N_neighbor_main_addr, 1053 N_status, N_willingness), describing symmetric neighbors. 1054 N_neighbor_main_addr is the main address of a neighbor, N_status 1055 specifies if the node is NOT_SYM or SYM. N_willingness in an integer 1056 between 0 and 7, and specifies a nodes willingness to carry traffic 1057 on behalf of other nodes. 1059 4.3.2. 2-hop Neighbor Set 1061 A node records a set of "2-hop tuples" (N_neighbor_main_addr, 1062 N_2hop_addr, N_time), describing symmetric (and, since MPR links by 1063 definition are also symmetric, thereby also MPR) links between its 1064 neighbors and the symmetric 2-hop neighborhood. N_neighbor_main_addr 1065 is the main address of a neighbor, N_2hop_addr is the main address of 1066 a 2-hop neighbor with a symmetric link to N_neighbor_main_addr, and 1067 N_time specifies the time at which the tuple expires and *MUST* be 1068 removed. 1070 In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor 1071 Set". 1073 4.3.3. MPR Set 1075 A node maintains a set of neighbors which are selected as MPR. Their 1076 main addresses are listed in the MPR Set. 1078 4.3.4. MPR Selector Set 1080 A node records a set of MPR-selector tuples (MS_main_addr, MS_time), 1081 describing the neighbors which have selected this node as a MPR. 1082 MS_main_addr is the main address of a node, which has selected this 1083 node as MPR. MS_time specifies the time at which a tuple expires and 1084 *MUST* be removed. 1086 In a node, the set of MPR-selector tuples are denoted the "MPR 1087 Selector Set". 1089 4.4. Topology Information Base 1091 Each node in the network maintains topology information about the 1092 network. This information is acquired from TC-messages and is used 1093 for routing table calculations. 1095 Thus, for each destination in the network, at least one "Topology 1096 Tuple" (T_dest_addr, T_last_addr, T_seq, T_time) is recorded. 1097 T_dest_addr is the main address of a node, which may be reached in 1098 one hop from the node with the main address T_last_addr. Typically, 1099 T_last_addr is a MPR of T_dest_addr. T_seq is a sequence number, and 1100 T_time specifies the time at which this tuple expires and *MUST* be 1101 removed. 1103 In a node, the set of Topology Tuples are denoted the "Topology Set". 1105 5. Main Addresses and Multiple Interfaces 1107 For single OLSR interface nodes, the relationship between an OLSR 1108 interface address and the corresponding main address is trivial: the 1109 main address is the OLSR interface address. For multiple OLSR 1110 interface nodes, the relationship between OLSR interface addresses 1111 and main addresses is defined through the exchange of Multiple 1112 Interface Declaration (MID) messages. This section describes how MID 1113 messages are exchanged and processed. 1115 Each node with multiple interfaces MUST announce, periodically, 1116 information describing its interface configuration to other nodes in 1117 the network. This is accomplished through flooding a Multiple 1118 Interface Declaration message to all nodes in the network through the 1119 MPR flooding mechanism. 1121 Each node in the network maintains interface information about the 1122 other nodes in the network. This information acquired from MID 1123 messages, emitted by nodes with multiple interfaces participating in 1124 the MANET, and is used for routing table calculations. 1126 Specifically, multiple interface declaration associates multiple 1127 interfaces to a node (and to a main address) through populating the 1128 multiple interface association base in each node. 1130 5.1. MID Message Format 1132 The proposed format of a MID message is as follows: 1134 0 1 2 3 1135 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 1136 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1137 | OLSR Interface Address | 1138 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1139 | OLSR Interface Address | 1140 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1141 | ... | 1142 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1144 This is sent as the data-portion of the general packet format 1145 described in section 3.4, with the "Message Type" set to 1146 MID_MESSAGE. The time to live SHOULD be set to 255 (maximum value) 1147 to diffuse the message into the entire network and Vtime set 1148 accordingly to the value of MID_HOLD_TIME, as specified in section 1149 18.3. 1151 OLSR Interface Address 1153 This field contains the address of an OLSR interface of the 1154 node, excluding the nodes main address (which already 1155 indicated in the originator address). 1157 All interface addresses other than the main address of the originator 1158 node are put in the MID message. If the maximum allowed message size 1159 (as imposed by the network) is reached while there are still 1160 interface addresses which have not been inserted into the MIDmessage, 1161 more MID messages are generated until the entire interface addresses 1162 set has been sent. 1164 5.2. MID Message Generation 1166 A MID message is sent by a node in the network to declare its 1167 multiple interfaces (if any). I.e., the MID message contains the 1168 list of interface addresses which are associated to its main address. 1169 The list of addresses can be partial in each MID message (e.g. due 1170 to message size limitations, imposed by the network), but parsing of 1171 all MID messages describing the interface set from a node MUST be 1172 complete within a certain refreshing period (MID_INTERVAL). The 1173 information diffused in the network by these MID messages will help 1174 each node to calculate its routing table. A node which has only a 1175 single interface address participating in the MANET (i.e. running 1176 OLSR), MUST NOT generate any MID message. 1178 A node with more interfaces, where only one is participating in the 1179 MANET and running OLSR (e.g. a node is connected to a wired network 1180 as well as to a MANET) MUST NOT generate any MID messages. 1182 A node with more interfaces, where more than one is participating in 1183 the MANET and running OLSR MUST generate MID messages as specified. 1185 5.3. MID Message Forwarding 1187 MID messages are broadcast and retransmitted by the MPRs in order to 1188 diffuse the messages in the entire network. The "default forwarding 1189 algorithm" (described in section 3.4) MUST be used for 1190 forwarding of MID messages. 1192 5.4. MID Message Processing 1194 The tuples in the multiple interface association set are recorded 1195 with the information that is exchanged through MID messages. 1197 Upon receiving a MID message, the "validity time" MUST be computed 1198 from the Vtime field of the message header (as described in section 1199 3.3.2). The Multiple Interface Association Information Base 1200 SHOULD then be updated as follows: 1202 1 If the sender interface (NB: not originator) of this message 1203 is not in the symmetric 1-hop neighborhood of this node, the 1204 message MUST be discarded. 1206 2 For each interface address listed in the MID message: 1208 2.1 If there exist some tuple in the interface association 1209 set where: 1211 I_iface_addr == interface address, AND 1213 I_main_addr == originator address, 1215 then the holding time of that tuple is set to: 1217 I_time = current time + validity time. 1219 2.2 Otherwise, a new tuple is recorded in the interface 1220 association set where: 1222 I_iface_addr = interface address, 1224 I_main_addr = originator address, 1226 I_time = current time + validity time. 1228 5.5. Resolving a Main Address from an Interface Address 1230 In general, the only part of OLSR requiring use of "interface 1231 addresses" is link sensing. The remaining parts of OLSR operate on 1232 nodes, uniquely identified by their "main addresses" (effectively, 1233 the main address of a node is its "node id" - which for convenience 1234 corresponds to the address of one of its interfaces). In a network 1235 with only single interface nodes, the main address of a node will, by 1236 definition, be equal to the interface address of the node. In 1237 networks with multiple interface nodes operating within a common OLSR 1238 area, it is required to be able to map any interface address to the 1239 corresponding main address. 1241 The exchange of MID messages provides a way in which interface 1242 information is acquired by nodes in the network. This permits 1243 identification of a nodes "main address", given one of its interface 1244 addresses. 1246 Given an interface address: 1248 1 if there exists some tuple in the interface association set 1249 where: 1251 I_iface_addr == interface address 1253 then the result of the main address search is the originator 1254 address I_main_addr of the tuple. 1256 2 Otherwise, the result of the main address search is the 1257 interface address itself. 1259 6. HELLO Message Format and Generation 1261 A common mechanism is employed for populating the local link 1262 information base and the neighborhood information base, namely 1263 periodic exchange of HELLO messages. Thus this section describes the 1264 general HELLO message mechanism, followed by a description of link 1265 sensing and topology detection, respectively. 1267 6.1. HELLO Message Format 1269 To accommodate for link sensing, neighborhood detection and MPR 1270 selection signalling, as well as to accommodate for future 1271 extensions, an approach similar to the overall packet format is 1272 taken. Thus the proposed format of a HELLO message is as follows: 1274 0 1 2 3 1275 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 1277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1278 | Reserved | Htime | Willingness | 1279 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1280 | Link Code | Reserved | Link Message Size | 1281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1282 | Neighbor Interface Address | 1283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1284 | Neighbor Interface Address | 1285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1286 : . . . 1287 : 1288 : : 1289 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1290 | Link Code | Reserved | Link Message Size | 1291 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1292 | Neighbor Interface Address | 1293 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1294 | Neighbor Interface Address | 1295 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1296 : : 1297 : : 1298 (etc) 1300 This is sent as the data-portion of the general packet format 1301 described in section 3.4, with the "Message Type" set to 1302 HELLO_MESSAGE, the TTL field set to 1 (one) and Vtime set accordingly 1303 to the value of NEIGHB_HOLD_TIME, specified in section 18.3. 1305 Reserved 1307 This field must be set to "0000000000000" to be in compliance 1308 with this specification. 1310 HTime 1312 This field specifies the HELLO emission interval used by the 1313 node on this particular interface, i.e. the time before the 1314 transmission of the next HELLO (this information may be used 1315 in advanced link sensing, see section 14). The 1316 HELLO emission interval is represented by its mantissa (four 1317 highest bits of Htime field) and by its exponent (four lowest 1318 bits of Htime field). In other words: 1320 HELLO emission interval=C*(1+a/16)*2^b [in seconds] 1322 where a is the integer represented by the four highest bits of 1323 Htime field and b the integer represented by the four lowest 1324 bits of Htime field. The proposed value of the scaling factor 1325 C is specified in section 18. 1327 Willingness 1329 This field specifies the willingness of a node to carry and 1330 forward traffic for other nodes. 1332 A node with willingness WILL_NEVER (see section 18.8, for 1333 willingness constants) MUST never be selected as MPR by any 1334 node. A node with willingness WILL_ALWAYS MUST always be 1335 selected as MPR. By default, a node SHOULD advertise a 1336 willingness of WILL_DEFAULT. 1338 Link Code 1340 This field specifies informations about the link between the 1341 interface of the sender and the following list of neighbor 1342 interfaces. It also specifies informations about the status 1343 of the neighbor. 1345 Link codes, not known by a node, are silently discarded. 1347 Link Message Size 1349 The size of the link message, counted in bytes and measured 1350 from the beginning of the "Link Code" field and until the next 1351 "Link Code" field (or - if there are no more link types - the 1352 end of the message). 1354 Neighbor Interface Address 1356 An address of the interface of a neighbor node. 1358 6.1.1. Link Code as Link Type and Neighbor Type 1360 This document only specifies processing of Link Codes < 16. 1362 If the Link Code value is less or equal to 15, then it MUST be 1363 interpreted as holding two different fields, of two bits each: 1365 7 6 5 4 3 2 1 0 1366 +-------+-------+-------+-------+-------+-------+-------+-------+ 1367 | 0 | 0 | 0 | 0 | Neighbor Type | Link Type | 1368 +-------+-------+-------+-------+-------+-------+-------+-------+ 1370 The following four "Link Types" are REQUIRED by OLSR: 1372 - UNSPEC_LINK - indicating that no specific information about 1373 the links is given. 1375 - ASYM_LINK - indicating that the links are asymmetric (i.e. 1376 the neighbor interface is "heard"). 1378 - SYM_LINK - indicating that the links are symmetric with the 1379 interface. 1381 - LOST_LINK - indicating that the links have been lost. 1383 The following three "Neighbor Types" are REQUIRED by OLSR: 1385 - SYM_NEIGH - indicating that the neighbors have at least one 1386 symmetrical link with this node. 1388 - MPR_NEIGH - indicating that the neighbors have at least one 1389 symmetrical link AND have been been selected as MPR by the 1390 sender. 1392 - NOT_NEIGH - indicating that the nodes are either no longer or 1393 have not yet become symmetrical neighbors. 1395 Note that an implementation should be careful in not confusing Link 1396 Type with Neighbor Type nor the constants (confusing SYM_NEIGH with 1397 SYM_LINK for instance). 1399 A link code advertising: 1401 Link Type == SYM_LINK AND 1403 Neighbor Type == NOT_NEIGH 1405 is invalid, and any links adverticed as such MUST be silently 1406 discarded without any processing. 1408 Likewise a Neighbor Type field advertising a numerical value which is 1409 not one of the constants SYM_NEIGH, MPR_NEIGH, NOT_NEIGH, is invalid, 1410 and any links adverticed as such MUST be silently discarded without 1411 any processing. 1413 6.2. HELLO Message Generation 1415 This involves transmitting the Link Set, the Neighbor Set and the MPR 1416 Set. In principle, a HELLO message serves three independent tasks: 1418 - link sensing 1420 - neighbor detection 1422 - MPR selection signaling 1424 Three tasks are all are based on periodic information exchange within 1425 a nodes neighborhood, and serve the common purpose of "local topology 1426 discovery". A HELLO message is therefore generated based on the 1427 information stored in the Local Link Set, the Neighbor Set and the 1428 MPR Set from the local link information base. 1430 A node must perform link sensing on each interface, in order to 1431 detect links between the interface and neighbor interfaces. 1432 Furthermore, a node must advertise its entire symmetric 1-hop 1433 neighborhood on each interface in order to perform neighbor 1434 detection. Hence, for a given interface, a HELLO message will 1435 contain a list of links on that interface (with associated link 1436 types), as well as a list of the entire neighborhood (with an 1437 associated neighbor types). 1439 The Vtime field is set such that it corresponds to the value of the 1440 node's NEIGHB_HOLD_TIME parameter. The Htime field is set such that 1441 it corresponds to the value of the node's HELLO_INTERVAL parameter 1442 (see section 18.3). 1444 The Willingness field is set such that it corresponds to the node's 1445 willingness to forward traffic on behalf of other nodes (see section 1446 18.8). A node MUST advertise the same willingness on all 1447 interfaces. 1449 The lists of addresses declared in a HELLO message is a list of 1450 neighbor interface addresses computed as follows: 1452 For each tuple in the Link Set, where L_local_iface_addr is the 1453 interface where the HELLO is to be transmitted, and where L_time >= 1454 current time (i.e. not expired), L_neighbor_iface_addr is advertised 1455 with: 1457 1 The Link Type set according to the following: 1459 1.1 if L_SYM_time >= current time (not expired) 1461 Link Type = SYM_LINK 1463 1.2 Otherwise, if L_ASYM_time >= current time (not expired) 1464 AND 1466 L_SYM_time < current time (expired) 1468 Link Type = ASYM_LINK 1470 1.3 Otherwise, if L_ASYM_time < current time (expired) AND 1472 L_SYM_time < current time (expired) 1474 Link Type = LOST_LINK 1476 2 The Neighbor Type is set according to the following: 1478 2.1 If the main address, corresponding to 1479 L_neighbor_iface_addr, is included in the MPR set: 1481 Neighbor Type = MPR_NEIGH 1483 2.2 Otherwise, if the main address, corresponding to 1484 L_neighbor_iface_addr, is included in the neighbor set: 1486 2.2.1 1487 if N_status == SYM 1489 Neighbor Type = SYM_NEIGH 1491 2.2.2 1492 Otherwise, if N_status == NOT_SYM 1493 Neighbor Type = NOT_NEIGH 1495 For each tuple in the Neighbor Set, for which no 1496 L_neighbor_iface_addr from an associated link tuple has been 1497 advertised by the previous algorithm, N_neighbor_main_addr is 1498 advertised with: 1500 - Link Type = UNSPEC_LINK, 1502 - Neighbor Type set as described in step 2 above 1504 For a node with a single OLSR interface, the main address is simply 1505 the address of the OLSR interface. I.e. for a node with a single 1506 OLSR interface, the main address, corresponding to 1507 L_neighbor_iface_addr is simply L_neighbor_iface_addr. 1509 A HELLO message can be partial (e.g. due to message size 1510 limitations, imposed by the network), the rule being the following, 1511 on each interface: each link and each neighbor node MUST be cited at 1512 least once within a predetermined refreshing period, 1513 REFRESH_INTERVAL. To keep track of fast connectivity changes, a 1514 HELLO message must be sent at least every HELLO_INTERVAL period, 1515 smaller than or equal to REFRESH_INTERVAL. 1517 Notice that for limiting the impact from loss of control messages, it 1518 is desirable that a message (plus the generic packet header) can fit 1519 into a single MAC frame. 1521 6.3. HELLO Message Forwarding 1523 Each HELLO message generated is broadcast by the node on one 1524 interface to its neighbors. HELLO messages MUST never be forwarded. 1526 6.4. HELLO Message Processing 1528 A node processes incoming HELLO messages for the purpose of 1529 conducting link sensing (detailed in section 7), neighbor 1530 detection and MPR selector set population (detailed in section 1531 8) 1533 7. Link Sensing 1535 Link sensing populates the local link information base. Link sensing 1536 is exclusively concerned with OLSR interface addresses and the 1537 ability to exchange packets between such OLSR interfaces. 1539 The mechanism for link sensing is the periodic exchange of HELLO 1540 messages. 1542 7.1. Populating the Link Set 1544 The Link Set is populated with information on links to neighbor 1545 nodes. The process of populating this set is denoted "link sensing" 1546 and is performed using HELLO message exchange, updating a local link 1547 information base in each node. 1549 Each node should detect the links between itself and neighbor nodes. 1550 Uncertainties over radio propagation may make some links 1551 unidirectional. Consequently, all links MUST be checked in both 1552 directions in order to be considered valid. 1554 A "link" is described by a pair of interfaces: a local and a remote 1555 interface. 1557 For the purpose of link sensing, each neighbor node (more 1558 specifically, the link to each neighbor) has an associated status of 1559 either "symmetric" or "asymmetric". "Symmetric" indicates, that the 1560 link to that neighbor node has been verified to be bi-directional, 1561 i.e. it is possible to transmit data in both directions. 1562 "Asymmetric" indicates that HELLO messages from the node have been 1563 heard (i.e. communication from the neighbor node is possible), 1564 however it is not confirmed that this node is also able to receive 1565 messages (i.e. communication to the neighbor node is not confirmed). 1567 The information, acquired through and used by the link sensing, is 1568 accumulated in the link set. 1570 7.1.1. HELLO Message Processing 1572 The "Originator Address" of a HELLO message is the main address of 1573 the node, which has emitted the message. 1575 Upon receiving a HELLO message, a node SHOULD update its Link Set. 1576 Notice, that a HELLO message MUST neither be forwarded nor be 1577 recorded in the duplicate set. 1579 Upon receiving a HELLO message, the "validity time" MUST be computed 1580 from the Vtime field of the message header (see section 3.3.2). 1581 Then, the Link Set SHOULD be updated as follows: 1583 1 Upon receiving a HELLO message, if there exists no link tuple 1584 with 1586 L_neighbor_iface_addr == Source Address 1588 a new tuple is created with 1590 L_neighbor_iface_addr = Source Address 1592 L_local_iface_addr = Address of the interface 1593 which received the 1594 HELLO message 1596 L_SYM_time = current time - 1 (expired) 1598 L_time = current time + validity time 1600 2 The tuple (existing or new) with: 1602 L_neighbor_iface_addr == Source Address 1604 is then modified as follows: 1606 2.1 L_ASYM_time = current time + validity time; 1608 2.2 if the node finds the address of the interface which 1609 received the HELLO message among the addresses listed in 1610 the link message then the tuple is modified as follows: 1612 2.2.1 1613 if Link Type is equal to LOST_LINK then 1615 L_SYM_time = current time - 1 (i.e. expired) 1617 2.2.2 1618 else if Link Type is equal to SYM_LINK or ASYM_LINK 1619 then 1621 L_SYM_time = current time + validity time, 1623 L_time = L_SYM_time + NEIGHB_HOLD_TIME 1625 2.3 L_time = max(L_time, L_ASYM_time) 1627 The above rule for setting L_time is the following: a link losing its 1628 symmetry SHOULD still be advertised during at least the duration of 1629 the "validity time" advertised in the generated HELLO. This allows 1630 neighbors to detect the link breakage. 1632 8. Neighbor Detection 1634 Neighbor detection populates the neighborhood information base and 1635 concerns itself with nodes and node main addresses. The relationship 1636 between OLSR interface addresses and main addresses is described in 1637 section 5. 1639 The mechanism for neighbor detection is the periodic exchange of 1640 HELLO messages. 1642 8.1. Populating the Neighbor Set 1644 A node maintains a set of neighbor tuples, based on the link tuples. 1645 This information is updated according to changes in the Link Set. 1647 The Link Set keeps the information about the links, while the 1648 Neighbor Set keeps the information about the neighbors. There is a 1649 clear association between those two sets, since a node is a neighbor 1650 of another node if and only if there is at least one link between the 1651 two nodes. 1653 In any case, the formal correspondence between links and neighbors is 1654 defined as follows: 1656 The "associated neighbor tuple" of a link tuple, is, if it 1657 exists, the neighbor tuple where: 1659 N_neighbor_main_addr == main address of 1660 L_neighbor_iface_addr 1662 The "associated link tuples" of a neighbor tuple, are all the 1663 link tuples, where: 1665 N_neighbor_main_addr == main address of 1666 L_neighbor_iface_addr 1668 The Neighbor Set MUST be populated by maintaining the proper 1669 correspondence between link tuples and associated neighbor tuples, as 1670 follows: 1672 Creation 1674 Each time a link appears, that is, each time a link tuple is 1675 created, the associated neighbor tuple MUST be created, if it 1676 doesn't already exist, with the following values: 1678 N_neighbor_main_addr = main address of 1679 L_neighbor_iface_addr 1680 (from the link tuple) 1682 In any case, the N_status MUST then be computed as described 1683 in the next step 1685 Update 1687 Each time a link changes, that is, each time the information 1688 of a link tuple is modified, the node MUST ensure that the 1689 N_status of the associated neighbor tuple respects the 1690 property: 1692 If the neighbor has any associated link tuple which 1693 indicates a symmetrical link (i.e. with L_SYM_time >= 1694 current time), then 1696 N_status is set to SYM 1698 else N_status is set to NOT_SYM 1700 Removal 1702 Each time a link is deleted, that is, each time a link tuple 1703 is removed, the associated neighbor tuple MUST be removed if 1704 it has no longer any associated link tuples. 1706 These rules ensure that there is exactly one associated neighbor 1707 tuple for a link tuple, and that every neighbor tuple has at least 1708 one associated link tuple. 1710 8.1.1. HELLO Message Processing 1712 The "Originator Address" of a HELLO message is the main address of 1713 the node, which has emitted the message. Likewise, the "willingness" 1714 MUST be computed from the Willingness field of the HELLO message (see 1715 section 6.1). 1717 Upon receiving a HELLO message, a node SHOULD first update its Link 1718 Set as described before. It SHOULD then update its Neighbor Set as 1719 follows: 1721 - if the Originator Address is the N_neighbor_main_addr from a 1722 neighbor tuple included in the Neighbor Set: 1724 then, the neighbor tuple SHOULD be updated as follows: 1726 N_willingness = willingness from the HELLO message 1728 8.2. Populating the 2-hop Neighbor Set 1730 The 2-hop neighbor set describes the set of nodes which have a 1731 symmetric link to a symmetric neighbor. This information set is 1732 maintained through periodic exchange of HELLO messages as described 1733 in this section. 1735 8.2.1. HELLO Message Processing 1737 The "Originator Address" of a HELLO message is the main address of 1738 the node, which has emitted the message. 1740 Upon receiving a HELLO message from a symmetric neighbor, a node 1741 SHOULD update its 2-hop Neighbor Set. Notice, that a HELLO message 1742 MUST neither be forwarded nor be recorded in the duplicate set. 1744 Upon receiving a HELLO message, the "validity time" MUST be computed 1745 from the Vtime field of the message header (see section 3.3.2). 1747 If the Originator Address is the main address of a 1748 L_neighbor_iface_addr from a link tuple included in the Link Set with 1750 L_SYM_time >= current time (not expired) 1752 (in other words: if the Originator Address is a symmetric neighbor) 1753 then the 2-hop Neighbor Set SHOULD be updated as follows: 1755 1 for each address (henceforth: 2-hop neighbor address), listed 1756 in the HELLO message with Neighbor Type equal to SYM_NEIGH or 1757 MPR_NEIGH: 1759 1.1 if the main address of the 2-hop neighbor address = main 1760 address of receiving node: 1762 silently discard the 2-hop neighbor address. 1764 (in other words: a node is not its own 2-hop neighbor). 1766 1.2 Otherwise, a 2-hop tuple is created with: 1768 N_neighbor_main_addr = Originator Address; 1770 N_2hop_addr = main address of the 1771 2-hop neighbor; 1773 N_time = current time 1774 + validity time. 1776 This tuple may replace an older similar tuple with same 1777 N_neighbor_main_addr and N_2hop_addr values. 1779 2 For each 2-hop node listed in the HELLO message with Neighbor 1780 Type equal to NOT_NEIGH, all 2-hop tuples where: 1782 N_neighbor_main_addr == Originator Address AND 1784 N_2hop_addr == main address of the 1785 2-hop neighbor 1787 are deleted. 1789 8.3. Populating the MPR set 1791 MPRs are used to flood control messages from a node into the network 1792 while reducing the number of retransmissions that will occur in a 1793 region. Thus, the concept of MPR is an optimization of a classical 1794 flooding mechanism. 1796 Each node in the network selects, independently, its own set of MPRs 1797 among its symmetric 1-hop neighborhood. The symmetric links with 1798 MPRs are advertised with Link Type MPR_NEIGH instead of SYM_NEIGH in 1799 HELLO messages. 1801 The MPR set MUST be calculated by a node in such a way that it, 1802 through the neighbors in the MPR-set, can reach all symmetric strict 1803 2-hop neighbors. (Notice that a node, a, which is a direct neighbor 1804 of another node, b, is not also a strict 2-hop neighbor of node b). 1805 This means that the union of the symmetric 1-hop neighborhoods of the 1806 MPR nodes contains the symmetric strict 2-hop neighborhood. MPR set 1807 recalculation should occur when changes are detected in the 1808 neighborhood or in the 2-hop neighborhood. 1810 MPRs are computed per interface, the union of the MPR sets of each 1811 interface make up the MPR set for the node. 1813 While it is not essential that the MPR set is minimal, it is 1814 essential that all strict 2-hop neighbors can be reached through the 1815 selected MPR nodes. A node SHOULD select an MPR set such that any 1816 strict 2-hop neighbor is covered by at least one MPR node. This 1817 ensures that the overhead of the protocol is kept at a minimum. 1819 The MPR set can coincide with the entire symmetric neighbor set. 1820 This could be the case at network initialization (and will correspond 1821 to classic link-state routing). 1823 8.3.1. MPR Computation 1825 The following specifies a proposed heuristic for selection of MPRs. 1826 It constructs an MPR-set that enables a node to reach any node in the 1827 symmetrical strict 2-hop neighborhood through relaying by one MPR 1828 node with willingness different from WILL_NEVER. The heuristic MUST 1829 be applied per interface, I. The MPR set for a node is the union of 1830 the MPR sets found for each interface. The following terminology 1831 will be used in describing the heuristics: 1833 neighbor of an interface 1835 a node is a "neighbor of an interface" if the interface 1836 (on the local node) has a link to any one interface of 1837 the neighbor node. 1839 2-hop neighbors reachable from an interface 1841 the list of 2-hop neighbors of the node that can be 1842 reached from neighbors of this interface. 1844 MPR set of an interface 1846 a (sub)set of the neighbors of an interface with a 1847 willingness different from WILL_NEVER, selected such that 1848 through these selected nodes, all strict 2-hop neighbors 1849 reachable from that interface are reachable. 1851 N: 1853 N is the subset of neighbors of the node, which are 1854 neighbor of the interface I. 1856 N2: 1858 The set of two-hop neighbors reachable from the interface 1859 I, excluding: 1861 (i) the nodes only reachable by members of N with 1862 willingness WILL_NEVER 1864 (ii) the node performing the computation 1866 (iii) 1867 all the symmetric neighbors: the nodes for which 1868 there exists a symmetric link to this node on some 1869 interface. 1871 D(y): 1873 The degree of an one hop neighbor node y (where y is a 1874 member of N), is defined as the number of symmetric 1875 neighbors of node y, EXCLUDING all the members of N and 1876 EXCLUDING the node performing the computation. 1878 The proposed heuristic is as follows: 1880 1 Start with an MPR set made of all members of N with 1881 N_willingness equal to WILL_ALWAYS 1883 2 Calculate D(y), where y is a member of N, for all nodes in N. 1885 3 Add to the MPR set those nodes in N, which are the *only* 1886 nodes to provide reachability to a node in N2. I.e. if node 1887 b in N2 can be reached only through a symmetric link to node a 1888 in N, then add node a to the MPR set. Remove the nodes from 1889 N2 which are now covered by a node in the MPR set. 1891 4 While there exist nodes in N2 which are not covered by at 1892 least one node in the MPR set: 1894 4.1 For each node in N, calculate the reachability, i.e. the 1895 number of nodes in N2 which are not yet covered by at 1896 least one node in the MPR set, and which are reachable 1897 through this one hop neighbor; 1899 4.2 Select as a MPR the node with highest N_willingness among 1900 the nodes in N with non-zero reachability. In case of 1901 multiple choice select the node which provides 1902 reachability to the maximum number of nodes in N2. In 1903 case of multiple nodes providing the same amount of 1904 reachability, select the node as MPR whose D(y) is 1905 greater. Remove the nodes from N2 which are now covered 1906 by a node in the MPR set. 1908 5 A node's MPR set is generated from the union of the MPR sets 1909 for each interface. As an optimization, process each node, y, 1910 in the MPR set in increasing order of N_willingness. If all 1911 nodes in N2 are still covered by at least one node in the MPR 1912 set excluding node y, and if N_willingness of node y is 1913 smaller than WILL_ALWAYS, then node y MAY be removed from the 1914 MPR set. 1916 Other algorithms, as well as improvements over this algorithm, are 1917 possible. For example, assume that in a multiple-interface scenario 1918 there exists more than one link between nodes 'a' and 'b'. If node 1919 'a' has selected node 'b' as MPR for one of its interfaces, then node 1920 'b' can be selected as MPR without additional performance loss by any 1921 other interfaces on node 'a'. 1923 8.4. Populating the MPR Selector Set 1925 The MPR selector set of a node, n, is populated by the main addresses 1926 of the nodes which have selected n as MPR. MPR selection is signaled 1927 through HELLO messages. 1929 8.4.1. HELLO Message Processing 1931 Upon receiving a HELLO message, if a node finds one of its own 1932 interface addresses in the list with a Neighbor Type equal to 1933 MPR_NEIGH, information from the HELLO message must be recorded in the 1934 MPR Selector Set. 1936 The "validity time" MUST be computed from the Vtime field of the 1937 message header (see section 3.3.2). The MPR Selector Set 1938 SHOULD then be updated as follows: 1940 1 If there exists no MPR selector tuple with: 1942 MS_main_addr == Originator Address 1944 then a new tuple is created with: 1946 MS_main_addr = Originator Address 1948 2 The tuple (new or otherwise) with 1950 MS_main_addr == Originator Address 1952 is then modified as follows: 1954 MS_time = current time + validity time. 1956 Deletion of MPR selector tuples occurs in case of expiration of the 1957 timer or in case of link breakage as described in the "Neighborhood 1958 and 2-hop Neighborhood Changes". 1960 8.5. Neighborhood and 2-hop Neighborhood Changes 1962 A change in the neighborhood is detected when: 1964 - The L_SYM_time field of a link tuple expires. This is 1965 considered as a neighbor loss if the link described by the 1966 expired tuple was the last link with a neighbor node (on the 1967 contrary, a link with an interface may break while a link with 1968 another interface of the neighbor node remains without being 1969 observed as a neighborhood change). 1971 - A new link tuple is inserted in the Link Set with a non 1972 expired L_SYM_time or a tuple with expired L_SYM_time is 1973 modified so that L_SYM_time becomes non-expired. This is 1974 considered as a neighbor appearance if there was previously no 1975 link tuple describing a link with the corresponding neighbor 1976 node. 1978 A change in the 2-hop neighborhood is detected when a 2-hop neighbor 1979 tuple expires or is deleted according to section 8.2. 1981 The following processing occurs when changes in the neighborhood or 1982 the 2-hop neighborhood are detected: 1984 - In case of neighbor loss, all 2-hop tuples with 1985 N_neighbor_main_addr == Main Address of the neighbor MUST be 1986 deleted. 1988 - In case of neighbor loss, all MPR selector tuples with 1989 MS_main_addr == Main Address of the neighbor MUST be deleted 1991 - The MPR set MUST be re-calculated when a neighbor appearance 1992 or loss is detected, or when a change in the 2-hop 1993 neighborhood is detected. 1995 - An additional HELLO message MAY be sent when the MPR set 1996 changes. 1998 9. Topology Discovery 2000 The link sensing and neighbor detection part of the protocol 2001 basically offers, to each node, a list of neighbors with which it can 2002 communicate directly and, in combination with the Packet Format and 2003 Forwarding part, an optimized flooding mechanism through MPRs. Based 2004 on this, topology information is disseminated through the network. 2005 The present section describes what part of the information given by 2006 the link sensing and neighbor detection is disseminated to the entire 2007 network and how it is used to construct routes. 2009 Routes are constructed through advertised links and links with 2010 neighbors. A node must at least disseminate links between itself and 2011 the nodes in its MPR-selector set, in order to provide sufficient 2012 information to enable routing. 2014 9.1. TC Message Format 2016 The proposed format of a TC message is as follows: 2018 0 1 2 3 2019 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 2020 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2021 | ANSN | Reserved | 2022 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2023 | Advertised Neighbor Main Address | 2024 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2025 | Advertised Neighbor Main Address | 2026 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2027 | ... | 2028 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2030 This is sent as the data-portion of the general message format with 2031 the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set 2032 to 255 (maximum value) to diffuse the message into the entire network 2033 and Vtime set accordingly to the value of TOP_HOLD_TIME, as specified 2034 in section 18.3. 2036 Advertised Neighbor Sequence Number (ANSN) 2038 A sequence number is associated with the advertised neighbor 2039 set. Every time a node detects a change in its advertised 2040 neighbor set, it increments this sequence number ("Wraparound" 2041 is handled as described in section 19). This number 2042 is sent in this ANSN field of the TC message to keep track of 2043 the most recent information. When a node receives a TC 2044 message, it can decide on the basis of this Advertised 2045 Neighbor Sequence Number, whether or not the received 2046 information about the advertised neighbors of the originator 2047 node is more recent than what it already has. 2049 Advertised Neighbor Main Address 2051 This field contains the main address of a neighbor node. All 2052 main addresses of the advertised neighbors of the Originator 2053 node are put in the TC message. If the maximum allowed 2054 message size (as imposed by the network) is reached while 2055 there are still advertised neighbor addresses which have not 2056 been inserted into the TC-message, more TC messages will be 2057 generated until the entire advertised neighbor set has been 2058 sent. Extra main addresses of neighbor nodes may be included, 2059 if redundancy is desired. 2061 Reserved 2063 This field is reserved, and MUST be set to "0000000000000000" 2064 for compliance with this document. 2066 9.2. Advertised Neighbor Set 2068 A TC message is sent by a node in the network to declare a set of 2069 links, called advertised link set which MUST include at least the 2070 links to all nodes of its MPR Selector set, i.e., the neighbors which 2071 have selected the sender node as a MPR. 2073 If, for some reason, it is required to distribute redundant TC 2074 information, refer to section 15. 2076 The sequence number (ANSN) associated with the advertised neighbor 2077 set is also sent with the list. The ANSN number MUST be incremented 2078 when links are removed from the advertised neighbor set; the ANSN 2079 number SHOULD be incremented when links are added to the advertised 2080 neighbor set. 2082 9.3. TC Message Generation 2084 In order to build the topology information base, each node, which has 2085 been selected as MPR, broadcasts Topology Control (TC) messages. TC 2086 messages are flooded to all nodes in the network and take advantage 2087 of MPRs. MPRs enable a better scalability in the distribution of 2088 topology information [1]. 2090 The list of addresses can be partial in each TC message (e.g. due to 2091 message size limitations, imposed by the network), but parsing of all 2092 TC messages describing the advertised link set of a node MUST be 2093 complete within a certain refreshing period (TC_INTERVAL). The 2094 information diffused in the network by these TC messages will help 2095 each node calculate its routing table. 2097 When the advertised link set of a node becomes empty, it SHOULD still 2098 send (empty) TC-messages during the a duration equal to the "validity 2099 time" (typically, this will be equal to TC_HOLD_TIME) of its 2100 previously emitted TC-messages, in order to invalidate the previous 2101 TC-messages. It SHOULD then stop sending TC-messages until some node 2102 is inserted in its advertised link set. 2104 A node MAY transmit additional TC-messages to increase its 2105 reactiveness to link failures. When a change to the MPR selector set 2106 is detected and this change can be attributed to a link failure, a 2107 TC-message SHOULD be transmitted after a shorter interval than 2108 TC_INTERVAL. 2110 9.4. TC Message Forwarding 2112 TC messages are broadcast and retransmitted by the MPRs in order to 2113 diffuse the messages in the entire network. TC messages MUST be 2114 forwarded according to the "default forwarding algorithm". 2116 9.5. TC Message Processing 2118 Upon receiving a TC message, the "validity time" MUST be computed 2119 from the Vtime field of the message header (see section 3.3.2). 2120 The topology set SHOULD then be updated as follows (using section 2121 19 for comparison of ANSN): 2123 1 If the sender interface (NB: not originator) of this message 2124 is not in the symmetric 1-hop neighborhood of this node, the 2125 message MUST be discarded. 2127 2 If there exist some tuple in the topology set where: 2129 T_last_addr == originator address AND 2131 T_seq > ANSN, 2133 then further processing of this TC message MUST NOT be 2134 performed and the message MUST be silently discarded (case: 2135 message received out of order). 2137 3 All tuples in the topology set where: 2139 T_last_addr == originator address AND 2141 T_seq < ANSN 2143 MUST be removed from the topology set. 2145 4 For each of the advertised neighbor main address received in 2146 the TC message: 2148 4.1 If there exist some tuple in the topology set where: 2150 T_dest_addr == advertised neighbor main address, AND 2152 T_last_addr == originator address, 2154 then the holding time of that tuple MUST be set to: 2156 T_time = current time + validity time. 2158 4.2 Otherwise, a new tuple MUST be recorded in the topology 2159 set where: 2161 T_dest_addr = advertised neighbor main address, 2163 T_last_addr = originator address, 2165 T_seq = ANSN, 2167 T_time = current time + validity time. 2169 10. Routing Table Calculation 2171 Each node maintains a routing table which allows it to route data, 2172 destined for the other nodes in the network. The routing table is 2173 based on the information contained in the link set and the topology 2174 set. Therefore, if any of these sets are changed, the routing table 2175 is recalculated to update the route information about each 2176 destination in the network. The route entries are recorded in the 2177 routing table in the following format: 2179 1. R_dest_addr R_next_addr R_dist R_iface_addr 2180 2. R_dest_addr R_next_addr R_dist R_iface_addr 2181 3. ,, ,, ,, ,, 2183 Each entry in the table consists of R_dest_addr, R_next_addr, R_dist, 2184 and R_iface_addr. Such entry specifies that the node identified by 2185 R_dest_addr is estimated to be R_dist hops away from the local node, 2186 that the symmetric neighbor node with interface address R_next_addr 2187 is the next hop node in the route to R_dest_addr, and that this 2188 symmetric neighbor node is reachable through the local interface with 2189 the address R_iface_addr. Entries are recorded in the routing table 2190 for each destination in the network for which a route is known. All 2191 the destinations, for which a route is broken or only partially 2192 known, are not recorded in the table. 2194 The routing table is updated when a change is detected in either: 2196 - the link set, 2198 - the neighbor set, 2200 - the 2-hop neighbor set, 2202 - the topology set, 2204 - the Multiple Interface Association Information Base, 2206 More precisely, the routing table is recalculated in case of neighbor 2207 appearance or loss, when a 2-hop tuple is created or removed,when a 2208 topology tuple is created or removed or when multiple interface 2209 association information changes. The update of this routing 2210 information does not generate or trigger any messages to be 2211 transmitted, neither in the network, nor in the 1-hop neighborhood. 2213 To construct the routing table of node X, a shortest path algorithm 2214 is run on the directed graph containing the arcs X -> Y where Y is 2215 any symmetric neighbor of X (with Neighbor Type equal to SYM), the 2216 arcs Y -> Z where Y is a neighbor node with willingness different of 2217 WILL_NEVER and there exists an entry in the 2-hop Neighbor set with Y 2218 as N_neighbor_main_addr and Z as N_2hop_addr, and the arcs U -> V, 2219 where there exists an entry in the topology set with V as T_dest_addr 2220 and U as T_last_addr. 2222 The following procedure is given as an example to calculate (or 2223 recalculate) the routing table : 2225 1 All the entries from the routing table are removed. 2227 2 The new routing entries are added starting with the symmetric 2228 neighbors (h=1) as the destination nodes. I.e. for each 2229 neighbor tuple in the neighbor set where: 2231 N_status = SYM 2233 (there is a symmetric link to the neighbor), and for each 2234 associated link tuple of the neighbor node such that L_time >= 2235 current time, a new routing entry is recorded in the routing 2236 table with: 2238 R_dest_addr = L_neighbor_iface_addr, of the 2239 associated link tuple; 2241 R_next_addr = L_neighbor_iface_addr, of the 2242 associated link tuple; 2244 R_dist = 1; 2246 R_iface_addr = L_local_iface_addr of the 2247 associated link tuple. 2249 If in the above, no R_dest_addr is equal to the main address 2250 of the neighbor, then another new routing entry with MUST be 2251 added, with: 2253 R_dest_addr = main address of the neighbor; 2255 R_next_addr = L_neighbor_iface_addr of one of the 2256 associated link tuple with L_time >= 2257 current time; 2259 R_dist = 1; 2261 R_iface_addr = L_local_iface_addr of the 2262 associated link tuple. 2264 3 for each node in N2, i.e a 2-hop neighbor which is not a 2265 neighbor node or the node itself, and such that there exist at 2266 least one entry in the 2-hop neighbor set where 2267 N_neighbor_main_addr correspond to a neighbor node with 2268 willingness different of WILL_NEVER, one selects one 2-hop 2269 tuple and creates one entry in the routing table with: 2271 R_dest_addr = the main address of the two hop neighbor; 2273 R_next_addr = the R_next_addr of the entry in the 2274 routing table with: 2276 R_dest_addr == N_neighbor_main_addr 2277 of the 2-hop tuple; 2279 R_dist = 2; 2281 R_iface_addr = the R_iface_addr of the entry in the 2282 routing table with: 2284 R_dest_addr == N_neighbor_main_addr 2285 of the 2-hop tuple; 2287 3 The new route entries for the destination nodes h+1 hops away 2288 are recorded in the routing table. The following procedure 2289 MUST be executed for each value of h, starting with h=2 and 2290 incrementing it by 1 each time. The execution will stop if no 2291 new entry is recorded in an iteration. 2293 3.1 For each topology entry in the topology table, if its 2294 T_dest_addr does not correspond to R_dest_addr of any 2295 route entry in the routing table AND its T_last_addr 2296 corresponds to R_dest_addr of a route entry whose R_dist 2297 is equal to h, then a new route entry MUST be recorded in 2298 the routing table (if it does not already exist) where: 2300 R_dest_addr = T_dest_addr; 2302 R_next_addr = R_next_addr of the recorded 2303 route entry where: 2305 R_dest_addr == T_last_addr 2307 R_dist = h+1; and 2308 R_iface_addr = R_iface_addr of the recorded 2309 route entry where: 2311 R_dest_addr == T_last_addr. 2313 3.2 Several topology entries may be used to select a next hop 2314 R_next_addr for reaching the node R_dest_addr. When h=1, 2315 ties should be broken such that nodes with highest 2316 willingness and MPR selectors are preferred as next hop. 2318 4 For each entry in the multiple interface association base 2319 where there exists a routing entry such that: 2321 R_dest_addr == I_main_addr (of the multiple interface 2322 association entry) 2324 AND there is no routing entry such that: 2326 R_dest_addr == I_iface_addr 2328 then a route entry is created in the routing table with: 2330 R_dest_addr = I_iface_addr (of the multiple interface 2331 association entry) 2333 R_next_addr = R_next_addr (of the recorded 2334 route entry) 2336 R_dist = R_dist (of the recorded 2337 route entry) 2339 R_iface_addr = R_iface_addr (of the recorded 2340 route entry). 2342 11. Node Configuration 2344 This section outlines how a node should be configured, in order to 2345 operate in an OLSR MANET. 2347 11.1. Address Assignment 2349 The nodes in the MANET network SHOULD be assigned addresses within a 2350 defined address sequence. I.e., the nodes in the MANET SHOULD be 2351 addressable through a network address and a netmask. 2353 Likewise, the nodes in each associated network SHOULD be assigned 2354 addresses from a defined address sequence, distinct from that being 2355 used in the MANET. 2357 11.2. Routing Configuration 2359 Any MANET node with associated networks or hosts SHOULD be configured 2360 such that it has routes set up to the interfaces with associated 2361 hosts or network. 2363 11.3. Data Packet Forwarding 2365 OLSR itself does not perform packet forwarding. Rather, it maintains 2366 the routing table in the underlying operating system, which is 2367 assumed to be forwarding packets as specified in RFC1812. 2369 12. Non OLSR Interfaces 2371 A node MAY be equipped with multiple interfaces, some of which do not 2372 participate in the OLSR MANET. These non OLSR interfaces may be 2373 point to point connections to other singular hosts or may connect to 2374 separate networks. 2376 In order to provide connectivity from the OLSR MANET interface(s) to 2377 these non OLSR interface(s), a node SHOULD be able to inject external 2378 route information to the OLSR MANET. 2380 Injecting routing information from the OLSR MANET to non OLSR 2381 interfaces is outside the scope of this specification. It should be 2382 clear, however, that the routing information for the OLSR MANET can 2383 be extracted from the topology table (see section 4.4) or 2384 directly from the routing table of OLSR, and SHOULD be injected onto 2385 the non OLSR interfaces following whatever mechanism (routing 2386 protocol, static configuration etc.) is provided on these interfaces. 2388 An example of such a situation could be where a node is equipped with 2389 a fixed network (e.g. an Ethernet) connecting to a larger network 2390 running, as well as a wireless network interface running OLSR. 2392 Notice that this is a different case from that of "multiple 2393 interfaces", where all the interfaces are participating in the MANET 2394 through running the OLSR protocol. 2396 In order to provide this capability of injecting external routing 2397 information into an OLSR MANET, a node with such non-MANET interfaces 2398 periodically issues a Host and Network Association (HNA) message, 2399 containing sufficient information for the recipients to construct an 2400 appropriate routing table. 2402 12.1. HNA Message Format 2404 The proposed format of an HNA-message is: 2406 0 1 2 3 2407 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 2408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2409 | Network Address | 2410 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2411 | Netmask | 2412 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2413 | Network Address | 2414 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2415 | Netmask | 2416 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2417 | ... | 2418 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2420 This is sent as the data part of the general packet format with the 2421 "Message Type" set to HNA_MESSAGE, the TTL field set to 255 and Vtime 2422 set accordingly to the value of HNA_HOLD_TIME, as specified in 2423 section 18.3. 2425 Network Address 2427 The network address of the associated network 2429 Netmask 2431 The netmask, corresponding to the network address immediately 2432 above. 2434 12.2. Host and Network Association Information Base 2436 Each node maintains information concerning which nodes may act as 2437 "gateways" to associated hosts and networks by recording "association 2438 tuples" (A_gateway_addr, A_network_addr, A_netmask, A_time), where 2439 A_gateway_addr is the address of a OLSR interface of the gateway, 2440 A_network_addr and A_netmask specify the network address and netmask 2441 of a network, reachable through this gateway, and A_time specifies 2442 the time at which this tuple expires and hence *MUST* be removed. 2444 The set of all association tuples in a node is called the 2445 "association set". 2447 It should be noticed, that the HNA-message can be considered as a 2448 "generalized version" of the TC-message: the originator of both the 2449 HNA- and TC-messages announce "reachability" to some other host(s). 2450 In the TC-message, no netmask is required, since all reachability is 2451 announced on a per-host basis. In HNA-messages, announcing 2452 reachability to an address sequence through a network- and netmask 2453 address is typically preferred over announcing reachability to 2454 individual host addresses. 2456 An important difference between TC- and HNA-messages is, that a TC 2457 message may have a canceling effect on previous information (if the 2458 ANSN is incremented), whereas information in HNA-messages is removed 2459 only upon expiration. 2461 12.3. HNA Message Generation 2463 A node with associated hosts and/or networks SHOULD periodically 2464 generate a Host and Network Association (HNA) message, containing 2465 pairs of (network address, netmask) corresponding to the connected 2466 hosts and networks. HNA-messages SHOULD be transmitted periodically 2467 every HNA_INTERVAL. The Vtime is set accordingly to the value of 2468 HNA_HOLD_TIME, as specified in section 18.3. 2470 A node without any associated hosts and/or networks SHOULD NOT 2471 generate HNA-messages. 2473 12.4. HNA Message Forwarding 2475 Upon receiving a HNA message, and thus following the rules of section 2476 3, in this version of the specification, the message MUST be 2477 forwarded according to section 3.4. 2479 12.5. HNA Message Processing 2481 In this section, the term "originator address" is used to designate 2482 the main address on the OLSR MANET of the node which originally 2483 issued the HNA-message. 2485 Upon processing a HNA-message, the "validity time" MUST be computed 2486 from the Vtime field of the message header (see section 3.3.2). 2487 The association base SHOULD then be updated as follows: 2489 1 If the sender interface (NB: not originator) of this message 2490 is not in the symmetric 1-hop neighborhood of this node, the 2491 message MUST be discarded. 2493 2 Otherwise, for each (network address, netmask) pair in the 2494 message: 2496 2.1 if an entry in the association set already exists, where: 2498 A_gateway_addr == originator address 2500 A_network_addr == network address 2502 A_netmask == netmask 2504 then the holding time for that tuple MUST be set to: 2506 A_time = current time + validity time 2508 2.2 otherwise, a new tuple MUST be recorded with: 2510 A_gateway_addr = originator address 2512 A_network_addr = network address 2514 A_netmask = netmask 2516 A_time = current time + validity time 2518 12.6. Routing Table Calculation 2520 In addition to the routing table computation as described in section 2521 10, the host and network association set MUST be added as 2522 follows: 2524 For each tuple in the association set, 2526 1 If there is no entry in the routing table with: 2528 R_dest_addr == A_network_addr/A_netmask 2530 then a new routing entry is created is created. 2532 2 If a new routing entry was created at the previous step, or 2533 else if there existed one with: 2535 R_dest_addr == A_network_addr/A_netmask 2537 R_dist > dist to A_gateway_addr of 2538 current association set tuple, 2540 then the routing entry is modified as follows: 2542 R_dest_addr = A_network_addr/A_netmask 2544 R_next_addr = the next hop on the path 2545 from the node to A_gateway_addr 2547 R_dist = dist to A_gateway_addr 2549 R_next_addr and R_iface_addr MUST be set to the same 2550 values as the tuple from the routing set with R_dest_addr 2551 == A_gateway_addr. 2553 12.7. Interoperability Considerations 2555 Nodes, which do not implement support for non OLSR interfaces, can 2556 coexist in a network with nodes which do implement support for non 2557 OLSR interfaces: the generic packet format and message forwarding 2558 (section 3) ensures that HNA messages are correctly 2559 forwarded by all nodes . Nodes which implement support for non OLSR 2560 interfaces may thus transmit and process HNA messages according to 2561 this section. 2563 Nodes, which do not implement support for non OLSR interfaces can not 2564 take advantage of the functionality specified in this section, 2565 however will forward HNA messages correctly, as specified in section 2566 3. 2568 13. Link Layer Notification 2570 OLSR is designed not to impose or expect any specific information 2571 from the link layer. However, if information from the link-layer 2572 describing link breakage is available, a node MAY use this as 2573 described in this section. 2575 If link layer information describing connectivity to neighboring 2576 nodes is available (i.e. loss of connectivity such as through 2577 absence of a link layer acknowledgment), this information is used in 2578 addition to the information from the HELLO-messages to maintain the 2579 neighbor information base and the MPR selector set. 2581 Thus, upon receiving a link-layer notification that the link between 2582 a node and a neighbor interface is broken, the following actions are 2583 taken with respect to link sensing: 2585 Each link tuple in the local link set SHOULD, in addition to what is 2586 described in section 4.2, include a L_LOST_LINK_time field. 2587 L_LOST_LINK_time is a timer for declaring a link as lost when an 2588 established link becomes pending. (Notice, that this is a subset of 2589 what is recommended in section 14, thus link hysteresis 2590 and link layer notifications can coexist). 2592 HELLO message generation should consider those new fields as follows: 2594 1 if L_LOST_LINK_time is not expired, the link is advertised 2595 with a link type of LOST_LINK. In addition, it is not 2596 considered as a symmetrical link in the updates of the 2597 associated neighbor tuple (see section 8.1). 2599 2 if the link to a neighboring symmetric or asymmetric interface 2600 is broken, the corresponding link tuple is modified: 2601 L_LOST_LINK_time and L_time are set to current time + 2602 NEIGHB_HOLD_TIME. 2604 3 this is considered as a link loss and the appropriate 2605 processing described in section 8.5 should be 2606 performed. 2608 13.1. Interoperability Considerations 2610 Link layer notifications provide, for a node, an additional criterion 2611 by which a node may determine if a link to a neighbor node is lost. 2612 Once a link is detected as lost, it is advertised, in accordance with 2613 the provisions described in the previous sections of this 2614 specification. 2616 14. Link Hysteresis 2618 Established links should be as reliable as possible to avoid data 2619 packet loss. This implies that link sensing should be robust against 2620 bursty loss or transient connectivity between nodes. Hence, to 2621 enhance the robustness of the link sensing mechanism, the following 2622 implementation recommendations SHOULD be considered. 2624 14.1. Local Link Set 2626 Each link tuple in the local link set SHOULD, in addition to what is 2627 described in section 4.2, include a L_link_pending field, a 2628 L_link_quality field, and a L_LOST_LINK_time field. L_link_pending 2629 is a boolean value specifying if the link is considered pending (i.e. 2630 the link is not considered established). L_link_quality is a 2631 dimensionless number between 0 and 1 describing the quality of the 2632 link. L_LOST_LINK_time is a timer for declaring a link as lost when 2633 an established link becomes pending. 2635 14.2. Hello Message Generation 2637 HELLO message generation should consider those new fields as follows: 2639 1 if L_LOST_LINK_time is not expired, the link is advertised 2640 with a link type of LOST_LINK. 2642 2 otherwise, if L_LOST_LINK_time is expired and L_link_pending 2643 is set to "true", the link SHOULD NOT be advertised at all; 2645 3 otherwise, if L_LOST_LINK_time is expired and L_link_pending 2646 is set to "false", the link is advertised as described 2647 previously in section 6. 2649 A node considers that it has a symmetric link for each link tuple 2650 where: 2652 1 L_LOST_LINK_time is expired, AND 2654 2 L_link_pending is "false", AND 2656 3 L_SYM_time is not expired. 2658 This definition for "symmetric link" SHOULD be used the updates of 2659 the associated neighbor tuple (see section 8.1) for computing 2660 the N_status of a neighbor node. This definition SHOULD thereby also 2661 be used as basis for the symmetric neighborhood when computing the 2662 MPR set, as well as for "the symmetric neighbors" in the first steps 2663 of the routing table calculation. 2665 Apart from the above, what has been described previously does not 2666 interfere with the advanced link sensing fields in the link tuples. 2667 The L_link_quality, L_link_pending and L_LOST_LINK_time fields are 2668 exclusively updated according to the present section. This section 2669 does not modify the function of any other fields in the link tuples. 2671 14.3. Hysteresis Strategy 2673 The link between a node and some of its neighbor interfaces might be 2674 "bad", i.e. from time to time let HELLOs pass through only to fade 2675 out immediately after. In this case, the neighbor information base 2676 would contain a bad link for at least "validity time". The following 2677 hysteresis strategy SHOULD be adopted to counter this situation. 2679 For each neighbor interface NI heard by interface I, the 2680 L_link_quality field of the corresponding Link Tuple determines the 2681 establishment of the link. The value of L_link_quality is compared 2682 to two thresholds HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed 2683 between 0 and 1 and such that HYST_THRESHOLD_HIGH >= 2684 HYST_THRESHOLD_LOW. 2686 The L_link_pending field is set according to the following: 2688 1 if L_link_quality > HYST_THRESHOLD_HIGH: 2690 L_link_pending = false 2692 L_LOST_LINK_time = current time - 1 (expired) 2694 2 otherwise, if L_link_quality < HYST_THRESHOLD_LOW: 2696 L_link_pending = true 2698 L_LOST_LINK_time = min (L_time, current time + 2699 NEIGHB_HOLD_TIME) 2701 (the link is then considered as lost according to section 2702 8.5 and this may produce a neighbor loss). 2704 3 otherwise, if HYST_THRESHOLD_LOW <= L_link_quality 2705 <= HYST_THRESHOLD_HIGH: 2707 L_link_pending and L_LOST_LINK_time remain unchanged. 2709 The condition for considering a link established is thus stricter 2710 than the condition for dropping a link. Notice thus, that a link can 2711 be dropped based on either timer expiration (as described in section 2712 7) or on L_link_quality dropping below HYST_THRESHOLD_LOW. 2714 Also notice, that even if a link is not considered as established by 2715 the link hysteresis, the link tuples are still updated for each 2716 received HELLO message (as described in section 7). 2717 Specifically, this implies that, regardless of whether or not the 2718 link hysteresis considers a link as "established", tuples in the link 2719 set do not expire except as determined by the L_time field of the 2720 link tuples. 2722 As a basic implementation requirement, an estimation of the link 2723 quality must be maintained and stored in the L_link_quality field. 2724 If some measure of the signal/noise level on a received message is 2725 available (e.g. as a link layer notification), then it can be used 2726 as estimation after normalization. 2728 If no signal/noise information or other link quality information is 2729 available from the link layer, an algorithm such as the following can 2730 be utilized (it is an exponentially smoothed moving average of the 2731 transmission success rate). The algorithm is parameterized by a 2732 scaling parameter HYST_SCALING which is a number fixed between 0 and 2733 1. For each neighbor interface NI heard by interface I, the first 2734 time NI is heard by I, L_link_quality is set to HYST_SCALING 2735 (L_link_pending is set to true and L_LOST_LINK_time to current time - 2736 1). 2738 A tuple is updated according to two rules. Every time an OLSR packet 2739 emitted by NI is received by I, the stability rule is applied: 2741 L_link_quality = (1-HYST_SCALING)*L_link_quality 2742 + HYST_SCALING. 2744 When an OLSR packet emitted by NI is lost by I, the instability 2745 rule is applied: 2747 L_link_quality = (1-HYST_SCALING)*L_link_quality. 2749 The loss of OLSR packet is detected by tracking the missing Packet 2750 Sequence Numbers on a per interface basis and by "long period of 2751 silence" from a node. A "long period of silence may be detected 2752 thus: if no OLSR packet has been received on interface I from 2753 interface NI during HELLO emission interval of interface NI (computed 2754 from the Htime field in the last HELLO message received from NI), a 2755 loss of an OLSR packet is detected. 2757 14.4. Interoperability Considerations 2759 Link hysteresis determines, for a node, the criteria at which a link 2760 to a neighbor node is accepted or rejected. Nodes in a network may 2761 have different criteria, according to e.g. the nature of the media 2762 over which they are communicating. Once a link is accepted, it is 2763 advertised, in accordance with the provisions described in the 2764 previous sections of this specification. 2766 15. Redundant Topology Information 2768 In order to provide redundancy to topology information base, the 2769 advertised link set of a node MAY contain links to neighbor nodes 2770 which are not in MPR selector set of the node. The advertised link 2771 set MAY contain links to the whole neighbor set of the node. The 2772 minimal set of links that any node MUST advertise in its TC messages 2773 is the links to the nodes MPR selectors. The advertised link set can 2774 be built according to the following rule based on a local parameter 2775 called TC_REDUNDANCY parameter. 2777 15.1. TC_REDUNDANCY Parameter 2779 The parameter TC_REDUNDANCY specifies, for the local node, the amount 2780 of information that MAY be included in the TC messages. The 2781 parameter SHOULD be interpreted as follows: 2783 - if the TC_REDUNDANCY parameter of the node is 0, then the 2784 advertised link set of the node set is limited to the MPR 2785 selector set (as described in section 8.3), 2787 - if the TC_REDUNDANCY parameter of the node is 1, then the 2788 advertised link set of the node is the union of its MPR set 2789 and its MPR selector set, 2791 - if the TC_REDUNDANCY parameter of the node is 2, then the 2792 advertised link set of the node is the full neighbor link set. 2794 A node with willingness equal to WILL_NEVER SHOULD have TC_REDUNDANCY 2795 also equal to zero. 2797 15.2. Interoperability Considerations 2799 A TC message is sent by a node in the network to declare a set of 2800 links, called advertised link set which MUST include at least the 2801 links to all nodes of its MPR Selector set, i.e., the neighbors which 2802 have selected the sender node as a MPR. This is sufficient 2803 information to ensure that routes can be computed in accordance with 2804 section 10. 2806 The provisions in this section specifies how additional information 2807 may be declared, as specified through a TC_REDUNDANCY parameter. 2808 TC_REDUNDANCY = 0 implies that the information declared corresponds 2809 exactly to the MPR Selector set, identical to section 9. Other 2810 values of TC_REDUNDANCY specifies additional information to be 2811 declared, i.e. the contents of the MPR Selector set is always 2812 declared. Thus, nodes with different values of TC_REDUNDANCY may 2813 coexist in a network: control messages are carried by all nodes in 2814 accordance with section 3, and all nodes will receive at 2815 least the link-state information required to construct routes as 2816 described in section 10. 2818 16. MPR Redundancy 2820 MPR redundancy specifies the ability for a node to select redundant 2821 MPRs. Section 4.5 specifies that a node should select its MPR set to 2822 be as small as possible, in order to reduce protocol overhead. The 2823 criteria for selecting MPRs is, that all strict 2-hop nodes must be 2824 reachable through, at least, one MPR node. Redundancy of the MPR set 2825 affects the overhead through affecting the amount of links being 2826 advertised, the amount of nodes advertising links and the efficiency 2827 of the MPR flooding mechanism. On the other hand, redundancy in the 2828 MPR set ensures that reachability for a node is advertised by more 2829 nodes, thus additional links are diffused to the network. 2831 While, in general, a minimal MPR set provides the least overhead, 2832 there are situations in which overhead can be traded off for other 2833 benefits. E.g. a node can may decide to increase its MPR coverage 2834 if it observes many changes in its neighbor information base caused 2835 by mobility, while otherwise keeping a low MPR coverage. 2837 16.1. MPR_COVERAGE Parameter 2839 The MPR coverage is defined by a single local parameter, 2840 MPR_COVERAGE, specifying by how many MPR nodes any strict 2-hop node 2841 should be covered. MPR_COVERAGE=1 specifies that the overhead of the 2842 protocol is kept at a minimum and causes the MPR selection to operate 2843 as described in section 8.3.1. MPR_COVERAGE=m ensures that, 2844 if possible, a node selects its MPR set such that all strict 2-hop 2845 nodes for an interface are reachable through at least m MPR nodes on 2846 that interface. MPR_COVERAGE can assume any integer value > 0. The 2847 heuristic MUST be applied per interface, I. The MPR set for a node 2848 is the union of the MPR sets found for each interface. 2850 Notice that MPR_COVERAGE can be tuned locally without affecting the 2851 consistency of the protocol. I.e. nodes in a network may operate 2852 with different values of MPR_COVERAGE. 2854 16.2. MPR Computation 2856 Using MPR coverage, the MPR selection heuristics is extended from 2857 that described in the section 8.3.1 by one definition: 2859 Poorly covered node: 2861 A poorly covered node is a node in N2 which is covered by less 2862 than MPR_COVERAGE nodes in N. 2864 The proposed heuristic for selecting MPRs is then as follows: 2866 1 Start with an MPR set made of all members of N with 2867 willingness equal to WILL_ALWAYS 2869 2 Calculate D(y), where y is a member of N, for all nodes in N. 2871 3 Select as MPRs those nodes in N which cover the poorly covered 2872 nodes in N2. The nodes are then removed from N2 for the rest 2873 of the computation. 2875 4 While there exist nodes in N2 which are not covered by at 2876 least MPR_COVERAGE nodes in the MPR set: 2878 4.1 For each node in N, calculate the reachability, i.e. the 2879 number of nodes in N2 which are not yet covered by at 2880 least MPR_COVERAGE nodes in the MPR set, and which are 2881 reachable through this one hop neighbor; 2883 4.2 Select as a MPR the node with highest willingness among 2884 the nodes in N with non-zero reachability. In case of 2885 multiple choice select the node which provides 2886 reachability to the maximum number of nodes in N2. In 2887 case of multiple nodes providing the same amount of 2888 reachability, select the node as MPR whose D(y) is 2889 greater. Remove the nodes from N2 which are now covered 2890 by MPR_COVERAGE nodes in the MPR set. 2892 5 A node's MPR set is generated from the union of the MPR sets 2893 for each interface. As an optimization, process each node, y, 2894 in the MPR set in increasing order of N_willingness. If all 2895 nodes in N2 are still covered by at least MPR_COVERAGE nodes 2896 in the MPR set excluding node y, and if N_willingness of node 2897 y is smaller than WILL_ALWAYS, then node y MAY be removed from 2898 the MPR set. 2900 When the MPR set has been computed, all the corresponding main 2901 addresses are stored in the MPR Set. 2903 16.3. Interoperability Considerations 2905 The MPR set of a node MUST, according to section 8.3, be 2906 calculated by a node in such a way that it, through the neighbors in 2907 the MPR-set, can reach all symmetric strict 2-hop neighbors. This is 2908 achieved by the heuristics in this section, for all values of 2909 MPR_COVERAGE > 0. MPR_COVERAGE is a local parameter for each node. 2910 Setting this parameter affects only the amount of redundancy in part 2911 of the network. 2913 Notice that for MPR_COVERAGE=1, the heuristics in this section is 2914 identical to the heuristics specified in the section 8.3.1. 2916 Nodes with different values of MPR_COVERAGE may coexist in a network: 2917 control messages are carried by all nodes in accordance with section 2918 3, and all nodes will receive at least the link-state 2919 information required to construct routes as described in sections 2920 #REF:td and 10. 2922 17. IPv6 Considerations 2924 All the operations and parameters described in this document used by 2925 OLSR for IP version 4 are the same as those used by OLSR for IP 2926 version 6. To operate with IP version 6, the only required change is 2927 to replace the IPv4 addresses with IPv6 address. The minimum packet 2928 and message sizes (under which there is rejection) should be adjusted 2929 accordingly, considering the greater size of IPv6 addresses. 2931 18. Proposed Values for Constants 2933 This section list the values for the constants used in the 2934 description of the protocol. 2936 18.1. Setting emission intervals and holding times 2938 The proposed constant for C is the following: 2940 C = 1/16 seconds (equal to 0.0625 seconds) 2942 C is a scaling factor for the "validity time" calculation ("Vtime" 2943 and "Htime" fields in message headers, see section 18.3). 2944 The "validity time" advertisement is designed such that nodes in a 2945 network may have different and individually tuneable emission 2946 intervals, while still interoperate fully. For protocol functioning 2947 and interoperability to work: 2949 - the advertised holding time MUST always be greater than the 2950 refresh interval of the advertised information. Moreover, it 2951 is recommended that the relation between the interval (from 2952 section 18.2), and the hold time is kept as specified 2953 in section 18.3, to allow for reasonable packet loss. 2955 - the constant C SHOULD be set to the suggested value. In order 2956 to achieve interoperability, C MUST be the same on all nodes. 2958 - the emission intervals (section 18.2), along with the 2959 advertised holding times (subject to the above constraints) 2960 MAY be selected on a per node basis. 2962 Note that the timer resolution of a given implementation might not be 2963 sufficient to wake up the system on precise refresh times or on 2964 precise expire times: the implementation SHOULD round up the 2965 'validity time' ("Vtime" and "Htime" of packets) to compensate for 2966 coarser timer resolution, at least in the case where "validity time" 2967 could be shorter than the sum of emission interval and maximum 2968 expected timer error. 2970 18.2. Emission Intervals 2972 HELLO_INTERVAL = 2 seconds 2973 REFRESH_INTERVAL = 2 seconds 2975 TC_INTERVAL = 5 seconds 2977 MID_INTERVAL = TC_INTERVAL 2979 HNA_INTERVAL = TC_INTERVAL 2981 18.3. Holding Time 2983 NEIGHB_HOLD_TIME = 3 x REFRESH_INTERVAL 2985 TOP_HOLD_TIME = 3 x TC_INTERVAL 2987 DUP_HOLD_TIME = 30 seconds 2989 MID_HOLD_TIME = 3 x MID_INTERVAL 2991 HNA_HOLD_TIME = 3 x HNA_INTERVAL 2993 The Vtime in the message header (see section 3.3.2), and the 2994 Htime in the HELLO message (see section 6.1) are the 2995 fields which hold information about the above values in mantissa and 2996 exponent format (rounded up). In other words: 2998 value = C*(1+a/16)*2^b [in seconds] 3000 where a is the integer represented by the four highest bits of the 3001 field and b the integer represented by the four lowest bits of the 3002 field. 3004 Notice, that for the previous proposed value of C, (1/16 seconds), 3005 the values, in seconds, expressed by the formula above can be stored, 3006 without loss of precision, in binary fixed point or floating point 3007 numbers with at least 8 bits of fractional part. This corresponds 3008 with NTP time-stamps and single precision IEEE Standard 754 floating 3009 point numbers. 3011 Given one of the above holding times, a way of computing the 3012 mantissa/exponent representation of a number T (of seconds) is the 3013 following: 3015 - 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 3058 HYST_THRESHOLD_HIGH = 0.8 3060 HYST_THRESHOLD_LOW = 0.3 3062 HYST_SCALING = 0.5 3064 18.8. Willingness 3066 WILL_NEVER = 0 3068 WILL_LOW = 1 3070 WILL_DEFAULT = 3 3072 WILL_HIGH = 6 3074 WILL_ALWAYS = 7 3076 The willingness of a node may be set to any integer value from 0 to 3077 7, and specifies how willing a node is to be forwarding traffic on 3078 behalf of other nodes. Nodes will, by default, have a willingness 3079 WILL_DEFAULT. WILL_NEVER indicates a node which does not wish to 3080 carry traffic for other nodes, e.g. due to resource constraints 3081 (e.g. low on battery). WILL_ALWAYS indicates that a node always 3082 should be selected to carry traffic on behalf of other nodes, e.g. 3083 due to resource abundance (e.g. permanent power supply, high 3084 capacity interfaces to other nodes). 3086 A node may dynamically change its willingness as its conditions 3087 change. 3089 One possible application would, for example, be for a node, connected 3090 to a permanent power supply and with fully charged batteries, to 3091 advertise a willingness of WILL_ALWAYS. Upon being disconnected from 3092 the permanent power supply (e.g. a PDA being taken out of its 3093 charging cradle), a willingness of WILL_DEFAULT is advertised. As 3094 battery capacity is drained, the willingness would be further 3095 reduced. First to the intermediate value between WILL_DEFAULT and 3096 WILL_LOW, then to WILL_LOW and finally to WILL_NEVER, when the 3097 battery capacity of the node does no longer support carrying foreign 3098 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 3121 number 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 3128 presence of wrap-around - to determine which message contains the 3129 most 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 such as exchange of OLSR 3147 control traffic messages encrypted by pgp [9] or by encrypted by some 3148 shared secret key can be applied to ensure that control traffic can 3149 be read and interpreted by only those authorized to do so. 3151 20.2. Integrity 3153 In OLSR, each node is injecting topological information into the 3154 network through transmitting HELLO messages and, for some nodes, TC 3155 messages. If some nodes for some reason, malicious or malfunction, 3156 inject invalid control traffic, network integrity may be compromised. 3157 Therefore, message authentication is recommended. 3159 Different such situations may occur, for instance: 3161 1 a node generates TC (or HNA) messages, advertising links to 3162 non-neighbor nodes: 3164 2 a node generates TC (or HNA) messages, pretending to be 3165 another node, 3167 3 a node generates HELLO messages, advertising non-neighbor 3168 nodes, 3170 4 a node generates HELLO messages, pretending to be another 3171 node. 3173 5 a node forwards altered control messages, 3175 6 a node does not broadcast control messages, 3177 7 a node does not select multipoint relays correctly. 3179 8 a node forwards broadcast control messages unaltered, but does 3180 not forward unicast data traffic; 3182 9 a node "replays" previously recorded control traffic from 3183 another node. 3185 Authentication of the originator node for control messages (for 3186 situation 2, 4 and 5) and on the individual links announced in the 3187 control messages (for situation 1 and 3) may be used as a 3188 countermeasure. However to prevent nodes from repeating old (and 3189 correctly authenticated) information (situation 9) temporal 3190 information is required, allowing a node to positively identify such 3191 delayed messages. 3193 Signatures and other required security information may be transmitted 3194 as a separate OLSR message type, thereby allowing that "secured" and 3195 "unsecured" nodes can coexist in the same network, if desired. 3197 An important consideration is, that all control messages in OLSR are 3198 transmitted either to all nodes in the neighborhood (HELLO messages) 3199 or broadcast to all nodes in the network (e.g. TC messages). I.e. 3200 a control message in OLSR is always a point-to-multipoint 3201 transmission. It is therefore important that the authentication 3202 mechanism employed permits that any receiving node can validate the 3203 authenticity of a message. As an analogy, given a block of text, 3204 signed by a PGP private key, then anyone with the corresponding 3205 public key can verify the authenticiy of the text. 3207 20.3. Interaction with External Routing Domains 3209 OLSR does, through the HNA messages specified in section 12, 3210 provide a basic mechanism for injecting external routing information 3211 to the OLSR domain. Section 12 also specifies that routing 3212 information can be extracted from the topology table or the routing 3213 table of OLSR and, potentially, injected into an external domain if 3214 the routing protocol governing that domain permits. 3216 Other than as described in the section 20.2, when operating 3217 nodes, connecting OLSR to an external routing domain, care MUST be 3218 taken not to allow potentially insecure and un-trustworthy 3219 information to be injected from the OLSR domain to external routing 3220 domains. Care MUST be taken to validate the correctness of 3221 information prior to it being injected as to avoid polluting routing 3222 tables with invalid information. 3224 A recommended way of extending connectivity from an existing routing 3225 domain to an OLSR routed MANET is to assign an IP prefix (under the 3226 authority of the nodes/gateways connecting the MANET with the exiting 3227 routing domain) exclusively to the OLSR MANET area, and to configure 3228 the gateways statically to advertise routes to that IP sequence to 3229 nodes in the existing routing domain. 3231 20.4. Node Identity 3233 OLSR does not make any assumption about node addresses, other than 3234 that each node is assumed to have an unique IP addresses. Therefore, 3235 no special considerations can be made about the applicability of 3236 IPsec authentication headers or key exchange mechanisms. 3238 21. Flow and congestion control 3240 Due to its proactive nature, the OLSR protocol has a natural control 3241 over the flow of its control traffic. Nodes transmits control 3242 message at predetermined rates fixed by predefined refresh intervals. 3243 Furthermore the MPR optimization greatly saves on control overhead, 3244 and this is done on two sides. First, the packets that advertize the 3245 topology are much shorter since only MPR selectors may be advertized. 3246 Second, the cost of flooding this information is greatly reduced 3247 since only MPR nodes forward the broadcast packets. In dense 3248 networks, the reduction of control traffic can be of several orders 3249 of magnitude compared to routing protocols using classical flooding 3250 (such as OSPF) [10]. This feature naturally provides more bandwidth 3251 for useful data traffic and pushes further the frontier of 3252 congestion. Since the control traffic is continuous and periodic, it 3253 keeps more stable the quality of the links used in routing, where 3254 reactive protocols, with bursty floodings for route discoveries and 3255 repairs, may damage the link qualities for short times by causing 3256 numerous collisions on those links, possibly provoking route repair 3257 cascades. However, in certain OLSR options, some control messages 3258 may be intentionnaly sent in advance of their deadline(TC or Hello 3259 messages) in order to increase the reactiveness of the protocol 3260 against topology changes. This may cause a small, temporary and 3261 local increase of control traffic. 3263 22. IANA Considerations 3265 OLSR defines a "Message Type" field for control messages. A new 3266 registry is to be created for the values for this Message Type field, 3267 and the following values assigned: 3269 Message Type Value 3270 -------------------- ----- 3271 HELLO_MESSAGE 1 3272 TC_MESSAGE 2 3273 MID_MESSAGE 3 3274 HNA_MESSAGE 4 3276 Future values in the range 5-127 of the Message Type can be allocated 3277 using standards action [7]. 3279 Additionally, values in the range 128-255 are reserved for 3280 private/local use. 3282 23. Acknowledgments 3283 The authors would like to thank Joseph Macker 3284 and his team, including Justin Dean 3285 , for their valuable suggestions on the 3286 advanced neighbor sensing mechanism and other various aspects of the 3287 protocol, including careful review of the protocol specification. 3289 The authors would also like to thank Christopher Dearlove 3290 for valuable input on the MPR 3291 selection heuristics and for careful reviews of the protocol 3292 specification. 3294 24. Contributors 3296 During the development of this specification, the following list of 3297 people contributed. The contributors are listed alphabetically. 3299 Cedric Adjih, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le 3300 Chesnay Cedex, France, Phone: +33 1 3963 5215, Email: 3301 Cedric.Adjih@inria.fr 3303 Thomas Heide Clausen, Project HIPERCOM, INRIA Rocquencourt, BP 105, 3304 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5133, Email: 3305 Thomas.Clausen@inria.fr 3307 Philippe Jacquet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3308 Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email: 3309 Philippe.Jacquet@inria.fr 3311 Anis Laouiti, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le 3312 Chesnay Cedex, France, Phone: +33 1 3963 508832, Email: 3313 Anis.Laouiti@inria.fr 3315 Pascale Minet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le 3316 Chesnay Cedex, France, Phone: +33 1 3963 508832, Email: 3317 Pascale.Minet@inria.fr 3318 Paul Muhlethaler, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3319 Le Chesnay Cedex, France, Phone: +33 1 3963 5278, Email: 3320 Paul.Muhlethaler@inria.fr 3322 Amir Qayyum, Center for Advanced Research in Engineering Pvt. Ltd., 3323 19, Ataturk Avenue, Islamabad, Pakistan, Phone: +92-51-2874115, 3324 Email: amir@carepvtltd.com 3326 Laurent Viennot, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3327 Le Chesnay Cedex, France, Phone: +33 1 3963 5225, Email: 3328 Laurent.Viennot@inria.fr 3330 25. Authors' Addresses 3332 Thomas Heide Clausen, Project HIPERCOM, INRIA Rocquencourt, BP 105, 3333 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5133, Email: 3334 Thomas.Clausen@inria.fr 3336 Philippe Jacquet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 3337 Le Chesnay Cedex, France, Phone: +33 1 3963 5263, Email: 3338 Philippe.Jacquet@inria.fr 3340 26. References 3342 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing 3343 reliability in cable free radio LANs: Low level forwarding in 3344 HIPERLAN. Wireless Personal Communications, 1996 3346 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An 3347 efficient technique for flooding in mobile wireless networks. 35th 3348 Annual Hawaii International Conference on System Sciences 3349 (HICSS'2001). 3351 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN 3352 type 1, functional specifications ETS 300-652, ETSI, June 1996 3354 4. P. Jacquet and L. Viennot, Overhead in Mobile Ad-hoc Network 3355 Protocols, INRIA research report RR-3965, 2000 3357 5. S. Bradner. Key words for use in RFCs to Indicate Requirement 3358 Levels. Request for Comments (Best Current Practice) 2119, 3359 Internet Engineering Task Force, March 1997. 3361 6. T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The 3362 Optimized Link State Routing Protocol, Evaluation through 3363 Experiments and Simulation. IEEE Symposium on "Wireless Personal 3364 Mobile Communications", September 2001. 3366 7. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum 3367 and L. Viennot. Optimized Link State Routing Protocol. IEEE 3368 INMIC Pakistan 2001. 3370 8. T. Narten and H. Alvestrand. Guidelines for Writing an IANA 3371 Considerations Section in RFCs. Request for Comments (Best Current 3372 Practice) 2434, Internet Engineering Task Force, October 1998. 3374 9. D. Atkins, W. Stallings and P. Zimmermann, PGP Message Exchange 3375 Formats. Request for Comments (Informational) 1991, August 1996. 3377 10. P. Jacquet, A. Laouiti, P. Minet, L. Viennot. Performance 3378 analysis of OLSR multipoint relay flooding in two ad hoc wireless 3379 network models, INRIA research report RR-4260, 2001. 3381 Reference [5] and [7] are normative; all others are informative.