idnits 2.17.1 draft-ietf-manet-olsr-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack an Authors' Addresses Section. ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The abstract seems to contain references ([2], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 312: '... OLSR MAY optimize the reactivity to...' RFC 2119 keyword, line 463: '...eason, each node MUST choose one of it...' RFC 2119 keyword, line 466: '... MUST be used in OLSR control traffi...' RFC 2119 keyword, line 515: '... MUST be set to "000000000000...' RFC 2119 keyword, line 532: '... MUST be set to "00000000" to...' (56 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- -- 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 (31 October 2001) is 8211 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? '1' on line 1375 looks like a reference -- Missing reference section? '2' on line 1130 looks like a reference -- Missing reference section? '3' on line 149 looks like a reference -- Missing reference section? '5' on line 203 looks like a reference -- Missing reference section? '4' on line 291 looks like a reference -- Missing reference section? '-MAXJITTER' on line 722 looks like a reference -- Missing reference section? '0' on line 722 looks like a reference Summary: 7 errors (**), 0 flaws (~~), 1 warning (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT Thomas Clausen 3 IETF MANET Working Group Philippe Jacquet 4 Expiration: 30 April 2002 Anis Laouiti 5 Pascale Minet 6 Paul Muhlethaler 7 Amir Qayyum 8 Laurent Viennot 9 INRIA Rocquencourt, France 10 31 October 2001 12 Optimized Link State Routing Protocol 14 draft-ietf-manet-olsr-05.txt 16 Status of this Memo 18 This document is a submission by the Mobile Ad Hoc Networking Working 19 Group of the Internet Engineering Task Force (IETF). Comments should 20 be submitted to the manet@itd.nrl.navy.mil mailing list. 22 Distribution of this memo is unlimited. 24 This document is an Internet-Draft and is in full conformance with 25 all provisions of Section 10 of RFC 2026. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF), its areas, and its working groups. Note that other 29 groups may also distribute working documents as Internet-Drafts. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 The list of current Internet-Drafts can be accessed at 37 http://www.ietf.org/ietf/1id-abstracts.txt 39 The list of Internet-Draft Shadow Directories can be accessed at 40 http://www.ietf.org/shadow.html. 42 Abstract 44 This document describes the Optimized Link State Routing (OLSR) 45 protocol for mobile ad hoc networks. The protocol is an optimization 46 of the pure link state algorithm tailored to the requirements of a 47 mobile wireless LAN. The key concept used in the protocol is that of 48 multipoint relays (MPRs) [1], [2]. MPRs are selected nodes which 49 forward broadcast messages during the flooding process. This 50 technique substantially reduces the message overhead as compared to a 51 pure flooding mechanism, where every node retransmits each message 52 when it receives the first copy of the message. In OLSR, information 53 flooded in the network "through" these MPRs is also "about" the MPRs. 54 Thus, a second optimization is achieved by minimizing the "contents" 55 of the control messages flooded in the network. Hence, as contrary to 56 the classic link state algorithm, a node declares only a small subset 57 of links to its neighbor nodes, rather than all links to all 58 neighbors. This information is then used by the OLSR protocol for 59 route calculation. As a consequence hereof, the routes contain only 60 the MPRs as intermediate nodes from a Source to a Destination. OLSR 61 provides optimal routes (in terms of number of hops). The protocol is 62 particularly suitable for large and dense networks as the technique 63 of MPRs works well in this context. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 68 1.1. Changes . . . . . . . . . . . . . . . . . . . . . . . . . 4 69 1.2. OLSR Terminology . . . . . . . . . . . . . . . . . . . . . 5 70 1.3. Applicability Section . . . . . . . . . . . . . . . . . . 7 71 1.4. Protocol Overview . . . . . . . . . . . . . . . . . . . . 7 72 1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . 8 74 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 9 75 2.1. Packet Format and Forwarding . . . . . . . . . . . . . . . 10 76 2.1.1. Protocol and Port Number . . . . . . . . . . . . . . . . 11 77 2.1.2. Multiple Interfaces and Main Address . . . . . . . . . . 11 78 2.1.3. Packet Format . . . . . . . . . . . . . . . . . . . . . 11 79 2.1.3.1. Packet Header . . . . . . . . . . . . . . . . . . . . 12 80 2.1.3.2. Message Header . . . . . . . . . . . . . . . . . . . . 12 81 2.1.4. Packet Processing and Message Flooding . . . . . . . . . 13 82 2.1.5. Message Emission and Jitter . . . . . . . . . . . . . . 16 84 2.2. Neighbor Sensing . . . . . . . . . . . . . . . . . . . . . 17 85 2.2.1. HELLO Message Format . . . . . . . . . . . . . . . . . . 18 86 2.2.2. Neighbor Sensing Information Base . . . . . . . . . . . 20 87 2.2.2.1. Neighbor Set . . . . . . . . . . . . . . . . . . . . . 20 88 2.2.2.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 20 89 2.2.2.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 21 90 2.2.2.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . 21 91 2.2.3. HELLO Message Generation . . . . . . . . . . . . . . . . 21 92 2.2.4. HELLO Message Processing . . . . . . . . . . . . . . . . 22 93 2.2.5. Multipoint Relay Selection . . . . . . . . . . . . . . . 25 94 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes . . . . . 27 95 2.2.6. Advanced Neighbor Sensing Functioning . . . . . . . . . 27 96 2.2.6.1. Link Hysteresis . . . . . . . . . . . . . . . . . . . 28 97 2.2.6.2. Optional Link layer notification . . . . . . . . . . . 29 98 2.3. Topology Discovery . . . . . . . . . . . . . . . . . . . . 30 99 2.3.1. Multipoint Relay Information Declaration . . . . . . . . 30 100 2.3.1.1. Topology Information Base . . . . . . . . . . . . . . 30 101 2.3.1.2. TC Message Generation . . . . . . . . . . . . . . . . 31 102 2.3.1.3. TC Message Processing . . . . . . . . . . . . . . . . 32 103 2.3.2. Multiple Interface Association . . . . . . . . . . . . . 34 104 2.3.2.1. Interface Association Information Base . . . . . . . . 34 105 2.3.2.2. MID Broadcast . . . . . . . . . . . . . . . . . . . . 35 106 2.3.2.3. MID Message Processing . . . . . . . . . . . . . . . . 36 107 2.3.3. Associated Networks and Hosts . . . . . . . . . . . . . 37 108 2.3.3.1. Host and Network Association Information Base . . . . 38 109 2.3.3.2. Host and Network Association Message Broadcast . . . . 38 110 2.3.3.3. HNA Message Processing . . . . . . . . . . . . . . . . 39 111 2.3.3.4. Optional Link layer notification . . . . . . . . . . . 40 112 2.3.4. Routing Table Calculation . . . . . . . . . . . . . . . 41 114 3. Node Configuration . . . . . . . . . . . . . . . . . . . . . 43 115 3.1. Address Assignment . . . . . . . . . . . . . . . . . . . . 43 116 3.2. Routing Configuration . . . . . . . . . . . . . . . . . . 43 117 3.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . 44 118 3.4. Control Message Forwarding . . . . . . . . . . . . . . . . 44 120 4. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . 44 121 5. Proposed Values for the Constants . . . . . . . . . . . . . 44 122 6. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . 45 123 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 46 125 1. Introduction 127 The Optimized Link State Routing Protocol (OLSR) is developed for 128 mobile ad hoc networks. It operates as a table driven and proactive 129 protocol, thus exchanges topology information with other nodes of the 130 network regularly. The nodes which are selected as a multipoint relay 131 by some neighbor nodes announce this information periodically in 132 their control messages. Thereby, a node announces to the network, 133 that it has reachability to the nodes which have selected it as MPR. 134 In route calculation, the MPRs are used to form the route from a 135 given node to any destination in the network. The protocol uses the 136 MPRs to facilitate efficient flooding of control messages in the net- 137 work. 139 MPRs are selected by a node among its one hop neighbors with "symmet- 140 ric", i.e. bi-directional, link. Therefore, selecting the route 141 through MPRs automatically avoids the problems associated with data 142 packet transfer over uni-directional links (such as the problem of 143 not getting link-layer acknowledgments for data packets at each hop) 145 OLSR is developed to work independently from other protocols. Like- 146 wise, OLSR makes no assumptions about the underlying link-layer. 148 OLSR inherits the concept of forwarding and relaying from HIPERLAN (a 149 MAC layer protocol) which is standardized by ETSI [3]. The protocol 150 is developed in the IPANEMA project (part of the Euclid program) and 151 in the PRIMA project (part of the RNRT program). 153 1.1. Changes 155 Major changes from version 04 to version 05 157 - Introduction of support for multiple interfaces 159 - Introduction of support for associated hosts and networks. 161 - Introduction of support for advanced neighbor sensing through 162 hysteresis. 164 - Modularity between neighbor sensing and topology discovery 165 emphasized. 167 Major changes from version 03 to version 04 169 - Finalized the generic packet/message format to include fea- 170 tures for scope-limited (diameter-bound) flooding of messages 171 and to handle duplicate messages. 173 - Editorial changes towards language consistency. 175 Major changes from version 02 to version 03 177 - Introduction of assigned port number for use with OLSR. 179 - The packet format now uses "message length" rather than an 180 offset to the next message. 182 - Optional section describing how link-layer notifications can 183 be utilized included. 185 Major changes from version 01 to version 02 187 - Introduction of a unified packet format for encapsulation of 188 all messages being exchanged between nodes. This also serves 189 to facilitate extensions in future versions of the protocol 190 (i.e. introduction of new protocol messages) without breaking 191 backwards compatibility. 193 - Removal of "Power Conservation" from this draft. Power Conser- 194 vation may be considered as an extension to the basic routing 195 capabilities. 197 1.2. OLSR Terminology 199 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 200 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 201 document are to be interpreted as described in RFC2119 [5]. The OLSR 202 protocol uses the following terminology: 204 multipoint relay (MPR) 206 A node which is selected by its one-hop neighbor, node X, to 207 "re-transmit" all the broadcast messages that it receives from 208 X, provided that the same message is not already received, and 209 the time to live field of the message is greater than one. 211 multipoint relay selector (MPR selector, MS) 213 A node which has selected its one-hop neighbor, node X, as its 214 multipoint relay, will be called a multipoint relay selector 215 of node X. 217 node 219 A MANET router which implements this Optimized Link State 220 Routing protocol. 222 interface 224 A network device participating in the MANET (it is usually 225 wireless). A node may have several interfaces, each one pos- 226 sessing its own IP address. 228 link 230 A link is a pair of interfaces (from two different nodes) sus- 231 ceptible to hear one another (i.e. one may be able to receive 232 traffic from the other). A node is said to have a link to 233 another node when one of its interface has a link to one of 234 the interfaces of the other node. 236 neighbor interface 238 An interface I is a neighbor interface of an interface J if J 239 can hear I (i.e. it is possible to send traffic from I to J). 241 sender interface 243 The sender interface of a control message is the neighbor 244 interface over which the message has been transmitted. 246 receiver interface 248 The reciever interface of a control message is the (local) 249 interface, over which a control message has been recieved. 251 neighbor node 253 A node X is a neighbor node of node Y if node Y can hear node 254 X (i.e. one of X interfaces is a neighbor interface of some 255 interface of Y). 257 symmetric link 259 A bi-directional link between two interfaces, i.e. interface I 260 and interface J where both can hear each other. 262 symmetric neighborhood 263 The symmetric neighborhood of any node X is the set of nodes 264 which have at least one symmetric link to X. 266 symmetric 2-hop neighborhood 267 The symmetric 2-hop neighborhood of X is the set of nodes 268 which don't have a symmetric link to X but have a symmetric 269 link to the symmetric neighborhood of X. 271 main address 273 The main address of a node, which will be used in OLSR control 274 traffic as the "originator address" of all messages emitted by 275 this node. It is the address of one of its interfaces. 277 1.3. Applicability Section 279 OLSR is a proactive routing protocol for mobile ad-hoc networks 280 (MANETs). It is well suited to large and dense mobile networks, as 281 the optimization achieved using the MPRs works well in this context. 282 The larger and more dense a network, the more optimization can be 283 achieved as compared to the classic link state algorithm. OLSR uses 284 hop-by-hop routing, i.e. each node uses its local information to 285 route packets. 287 OLSR is well suited for networks, where the traffic is random and 288 sporadic between "several" nodes rather than being almost exclusively 289 between a small specific set of nodes. The performance of the proto- 290 col, compared to a reactive protocol, is even better if these 291 [source, destination] pairs change with time [4]. Such changes may 292 initiate substantial traffic (query flooding) in case of a reactive 293 protocol, but nothing in OLSR, as the routes are maintained for each 294 known destination all the time. 296 1.4. Protocol Overview 298 OLSR is a proactive routing protocol for mobile ad hoc networks. The 299 protocol inherits the stability of a link state algorithm and has the 300 advantage of having routes immediately available when needed due to 301 its proactive nature. OLSR is an optimization over the pure link 302 state protocol, tailored for mobile ad hoc networks. 304 Firstly, it reduces the size of the control messages: rather than 305 declaring all links, a node declares only a subset of links with its 306 neighbors, namely the links to those nodes which are its MPR selec- 307 tors. Secondly, OLSR minimizes flooding of control traffic by using 308 only selected nodes, called MPRs, to diffuse its control messages. 309 This technique significantly reduces the number of retransmissions in 310 a flooding or broadcast procedure. 312 OLSR MAY optimize the reactivity to topological changes by reducing 313 the maximum time interval for periodic control message transmission. 314 Furthermore, as OLSR continuously maintains routes for all destina- 315 tions in the network, the protocol is beneficial for traffic patterns 316 where a large subset of nodes are communicating with another large 317 subset of nodes, and where the [source,destination] pairs are chang- 318 ing over time. The protocol is particularly suited for large and 319 dense networks, as the optimization done using MPRs works well in 320 this context. The larger and more dense a network, the more optimiza- 321 tion can be achieved as compared to the classic link state algorithm. 323 OLSR is designed to work in a completely distributed manner and does 324 thus not depend on any central entity. The protocol does NOT REQUIRE 325 reliable transmission of control messages: each node sends control 326 messages periodically, and can therefore sustain an occasional loss 327 of some such messages. Such losses occur frequently in radio networks 328 due to collisions or other transmission problems. 330 Also, OLSR does not require sequenced delivery of messages. Each con- 331 trol message contains a sequence number which is incremented for each 332 message. Thus the recipient of a control message can easily identify 333 which information is newer - even if messages have been re-ordered 334 while in transmission. 336 Furthermore, OLSR provides support for protocol extensions such as 337 sleep mode operation, multicast-routing etc. Such extensions may be 338 introduced as additions to the protocol without breaking backwards 339 compatibility with earlier versions. 341 OLSR performs hop by hop routing, i.e. each node uses its most recent 342 local information to route a packet. Hence, for OLSR to be able to 343 route packets, the frequency of control messages should be tuned to 344 the speed of the mobile nodes such that their movements can be 345 tracked by their neighborhood. 347 OLSR does not require any changes to the format of IP packets. Thus 348 any existing IP stack can be used as is: the protocol only interacts 349 with routing table management. 351 1.5. Multipoint Relays 353 The idea of multipoint relays is to minimize the overhead of flooding 354 messages in the network by reducing duplicate retransmissions in the 355 same region. Each node in the network selects a set of nodes in its 356 symmetric neighborhood which may retransmit its messages. This set of 357 selected neighbor nodes is called the "Multipoint Relay" (MPR) set of 358 that node. The neighbors of node N which are *NOT* in its MPR set, 359 receive and process broadcast messages but do not retransmit broad- 360 cast messages received from node N. 362 Each node selects its MPR set among its one hop symmetric neighbors. 363 This set is selected such that it covers (in terms of radio range) 364 all nodes that are two hops away. The MPR set of N, denoted as 365 MPR(N), is then an arbitrary subset of the symmetric neighborhood of 366 N which satisfies the following condition: every node in the symmet- 367 ric 2-hop neighborhood of N must have a symmetric link towards 368 MPR(N). The smaller the MPR set is, the more optimal is the routing 369 protocol. [2] gives an analysis and example of MPR selection algo- 370 rithms. 372 Each node maintains information about the neighbors that have 373 selected it as MPR. This set is called the "Multipoint Relay Selector 374 set" (MPR selector set) of a node. A node obtains this information 375 from periodic HELLO messages received from the neighbors. 377 A broadcast message, intended to be diffused in the whole network, 378 coming from these MPR selectors is assumed to be retransmitted by the 379 node. This set can change over time (i.e. when a node selects another 380 MPR-set) and is indicated by the selector nodes in their HELLO mes- 381 sages. Each node has a specific "Multipoint relay Selector Sequence 382 Number" (MSSN) associated with this set. Whenever the MPR selector 383 set is updated, the node also increments its MSSN. 385 OLSR relies on selection of MPRs, and calculates routes through these 386 nodes. I.e., the path is made of links between MPR and MPR selector. 387 To enable this, each node in the network periodically floods informa- 388 tion describing which neighbors have selected it as a MPR. Upon 389 receipt of this "MPR Selector" information, each node calculates or 390 updates the route to each known destination. So principally, the 391 route is a sequence of hops through the MPRs from source to the des- 392 tination. 394 MPRs are selected among the symmetric neighborhood. Therefore, 395 selecting the route through MPRs automatically avoids the problems 396 associated with data packet transfer over uni-directional links such 397 as the problem of not getting an acknowledgment for the data packets 398 at each hop. 400 2. Protocol Functioning 402 This section describes the details of the protocol functioning. This 403 includes descriptions of the format and contents of the packets being 404 exchanged by routers, the algorithms (e.g. for packet handling and 405 routing table calculation) and suggested data structures internally 406 kept in each router. 408 The "Packet Forwarding" and "Neighbor Sensing" mechanisms may be seen 409 as a transfer layer for the routing protocol. This provides nodes 410 with information about their neighbors and offer an optimized mecha- 411 nism for flooding messages through the concept of MPRs. It completely 412 relies on the exchange of HELLO messages. 414 The "Topoly Discovery" mechanism relies on the "Packet Forwarding" 415 and "Neighbor Sensing" mechanisms. Neighbor and MPR information from 416 the "Neighbor Sensing" mechanism is utilized by a node for diffusing 417 local topology information to the whole network. Topology information 418 is diffused through the "Packet Forwarding" mechanism, and relies on 419 TC, MID and HNA messages. Resulting from the "Topology Discovery" 420 mechanism is information which allows routing table calculation. 422 The key notion in these modules is the MPR relationship. 424 2.1. Packet Format and Forwarding 426 OLSR communicates using an unified packet format for all data related 427 to the protocol. The purpose of this is to facilitate extensibility 428 of the protocol without breaking backwards compatibility, as well as 429 to provide an easy way of piggybacking different "types" of informa- 430 tion into a single transmission. These packets are embedded in UDP 431 datagrams for transmission over the network. The present draft is 432 presented with IPv4 addresses. Considerations regarding IPv6 are 433 given in section 4. 435 Each packet encapsulates one or more messages. The messages share a 436 common header format, which enables nodes to correctly accept and (if 437 applicable) retransmit messages of an unknown type. 439 Messages can be flooded onto the entire network, or flooding can be 440 limited to nodes within a diameter (in terms of number of hops) from 441 the originator of the message. Thus, broadcasting a message to the 442 neighborhood of a node is just a special case of flooding. When 443 flooding any control message, duplicate retransmissions will be elim- 444 inated locally (i.e. each node maintains a duplicate table to prevent 445 transmitting the same message twice) and minimized in the entire net- 446 work through the usage of MPRs as described in later sections. 448 Furthermore, a node can examine the header of a message to obtain 449 information on the distance (in terms of number of hops) to the orig- 450 inator of the message. This feature may be useful in situations 451 where, e.g., the time information from a received control messages 452 stored in a node depends on the distance to the originator. 454 2.1.1. Protocol and Port Number 456 Packets in OLSR are communicated using UDP. Port 698 has been 457 assigned by IANA for exclusive usage by the OLSR protocol. 459 2.1.2. Multiple Interfaces and Main Address 461 A node may have several wireless interfaces, each of them having a 462 distinct IP address. OLSR supports such nodes with multiple inter- 463 faces. For this reason, each node MUST choose one of its interface 464 addresses as its "main address". For example, the smallest interface 465 address may be the chosen as the main interface. The main address 466 MUST be used in OLSR control traffic as the "originator address" of 467 all messages emitted by a node. 469 A node must transmit and retransmit all control messages on all 470 interfaces. The source address in the IP header must contain the IP- 471 address of the interface where the message is transmitted. This 472 address will be denoted the "sender interface address". 474 2.1.3. Packet Format 476 The basic layout of any packet in OLSR is as follows (omitting the IP 477 and UDP headers): 479 0 1 2 3 480 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 481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 482 | Packet Length | Reserved | 483 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 484 | Message Type | Reserved | Message Size | 485 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 486 | Originator Address | 487 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 488 | Time To Live | Hop Count | Message Sequence Number | 489 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 490 | | 491 : MESSAGE : 492 | | 493 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 494 | Message Type | Reserved | Message Size | 495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 496 | Originator Address | 497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 498 | Time To Live | Hop Count | Message Sequence Number | 499 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 500 | | 501 : MESSAGE : 502 | | 503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 504 : : 505 (etc) 507 2.1.3.1. Packet Header 509 Packet Length 511 The length (in bytes) of the packet 513 Reserved 515 MUST be set to "0000000000000000" to be in compliance with 516 this version of the draft. 518 The sender information for a packet is obtainable from the UDP 519 header. 521 2.1.3.2. Message Header 523 Message Type 525 This field indicates which type of message are to be found in 526 the "MESSAGE" partition. Message types in the range of 0-127 527 are reserved for messages in this draft and in extension 528 drafts. 530 Reserved 532 MUST be set to "00000000" to be in compliance with this ver- 533 sion of the draft. 535 Message Size 537 This field gives the size of this message, counted in bytes 538 and measured from the beginning of the "Message Type" field 539 and until the beginning of the next "Message Type" field (or - 540 if there are no following messages - the end of the packet). 542 Originator Address 543 This field contains the main address of the node, which has 544 originally generated this message. This field SHOULD NOT be 545 confused with the source address from the UDP header, which is 546 changed each time to the address of the intermediate interface 547 which is "re-transmitting" this message. The Originator 548 Address field MUST *NEVER* be changed in retransmissions. 550 Time To Live 552 This field contains the maximum number of hops a message will 553 be transmitted. Before a message is retransmitted, the Time To 554 Live MUST be decremented by 1. When a node receives a message 555 with a Time To Live equal to 0 or 1, the message MUST NOT be 556 retransmitted under any circumstances. Normally, a node would 557 not receive a message with a TTL of zero. 559 Thus, by setting this field, the originator of a message can 560 limit the flooding radius. 562 Hop Count 564 This field contains the number of hops a message has attained. 565 Before a message is retransmitted, the Hop Count MUST be 566 incremented by 1. 568 Initially, this is set to '0' by the originator of the mes- 569 sage. 571 Message Sequence Number 573 While generating a message, the "originator" node will assign 574 a unique identification number to each message. This number is 575 inserted into the Sequence Number field of the message. The 576 sequence number is increased by 1 (one) for each message orig- 577 inating from the node - "wrap-arounds" are handled as 578 described in a later section. Message sequence numbers are 579 used to ensure that a given message is not retransmitted more 580 than once by any node. 582 2.1.4. Packet Processing and Message Flooding 584 Upon receiving a basic packet, the protocol parser examines each of 585 the "message headers". Based on the value of the "Message Type" 586 field, the parser can determine the fate of the message. A node may 587 receive the same message several times. This can happen only if the 588 message is retransmitted by two interfaces in the receivers neighbor- 589 hood and the "Time To Live" and the "Hop Count" fields in the message 590 satisfy the following condition: 592 Time To Live + Hop Count > 1 594 Thus, to avoid re-processing of a message which was already received 595 and processed, each node maintains a Duplicate table. In this table, 596 the node records information about the most recently received mes- 597 sages where the above condition holds. For each message, satisfying 598 the above condition, a node records a "Duplicate Tuple" (D_addr, 599 D_seq_num, D_time), where D_addr is the originator address of the 600 message, D_seq_num is the message sequence number of the message and 601 D_time specifies the time at which a tuple expires and *MUST* be 602 removed. 604 In a node, the set of Duplicate Tuples are denoted the "Duplicate 605 set". 607 Thus, upon receiving a basic packet, a node performs the following 608 tasks for each encapsulated message: 610 1 If the time to live of the message is less than or equal to 611 '0' (zero), the message MUST silently be dropped. 613 2 If there exists a tuple in the duplicate set, where: 615 D_addr == Originator Address, AND 617 D_seq_num == Message Sequence Number 619 then the message has already been completely processed and 620 MUST silently be ignored. 622 3 Otherwise, if the Message Type of the message is known to the 623 node, the message MUST be processed according to the specifi- 624 cations of such message type. 626 4 Otherwise, If the Message Type of the message is not known to 627 the node, the message SHOULD be processed according to the 628 following algorithm: 630 4.1 If the sender of the message is not detected to be in the 631 symmetric neighborhood of the node, the message MUST 632 silently be dropped. 634 4.2 If the sender of the message is detected to be in the 635 symmetric neighborhood of the node, an entry in the 636 duplicate set is recorded with: 638 D_addr = originator address 640 D_seq_num = Message Sequence Number 642 D_time = current time + D_HOLD_TIME. 644 4.3 If the sender address is the link interface address of a 645 MPR selector of this node and if the time to live of the 646 message is greater than '1', the message MUST be for- 647 warded according to the following: 649 4.3.1 650 The TTL of the message is reduced by one. 652 4.3.2 653 The hop-count of the message is increased by one 655 4.3.3 656 The message is broadcasted on all interfaces 657 (Notice: The remaining fields of the message header 658 SHOULD be left unmodified.) 660 Notice: known message types are *not* forwarded "blindly" by this 661 algorithm. Forwarding (and setting the correct message header in the 662 forwarded, known, message) is the responsibility of the algorithm 663 specifying how the message is to be handled. This enables, e.g., a 664 message type to be specified such that the message can be modified 665 while in transit (e.g. to reflect the route the message has taken). 666 Further, it enables that the optimization through the MPRs can be 667 bypassed: if for some reason pure flooding of a message type is 668 required (e.g. to transmit control information over unidirectional 669 links), the algorithm which specifies how such messages should be 670 handled will simply rebroadcast the message, regardless of MPRs. 672 Finally, notice that a message, which is to be broadcasted in the 673 neighborhood but not flooded into the entire network, (e.g. a HELLO- 674 message) is simply specified by setting the time to live to 1 (one) 675 and the hop count to 0 (zero), and that no duplicate tuples are 676 recorded for such messages. 678 By defining a set of message types, which MUST be recognized by all 679 implementations of OLSR, it will be possible to extend the protocol 680 through introduction of additional message types, while still be able 681 to maintain compatibility with older implementations. The REQUIRED 682 message types for OLSR are: 684 - HELLO-messages, performing the task of neighbor sensing. 686 - TC-messages, performing the task of MPR information declara- 687 tion (OLSR topology declaration). 689 - MID-messages, performing the task of multiple interface decla- 690 ration. 692 - HNA-messages, performing the task of associated host and/or 693 network declaration 695 Extensions may for example be messages enabling power conservation / 696 sleep mode, multicast routing, support for unidirectional links, 697 auto-configuration/address assignment etc. 699 2.1.5. Message Emission and Jitter 701 As a basic implementation requirement, synchronization of control 702 messages SHOULD be avoided. As a consequence, periodic OLSR messages 703 should be emitted such that they avoid synchronization. 705 Emission of control traffic from neighboring nodes may, for various 706 reasons (mainly timer interactions with packet processing), become 707 synchronized such that several neighbor nodes attempt to transmit 708 control traffic simultaneously. Depending on the nature of the under- 709 lying link-layer, this may or may not lead to collisions and hence 710 message loss - possibly loss of several subsequent messages of the 711 same type. 713 To counter such synchronizations, the following simple strategy for 714 emitting control messages is proposed. A node may add an amount of 715 jitter to the interval at which messages are generated. The jitter 716 must be a random value for each message generated. Thus, for a node 717 utilizing jitter: 719 Actual message interval = MESSAGE_INTERVAL + jitter 721 Where jitter is a value, randomly selected from the interval 722 [-MAXJITTER,0] and MESSAGE_INTERVAL is the value of the message 723 interval specified for the message being emitted (e.g. HELLO_INTERVAL 724 for HELLO messages, TC_INTERVAL for TC-messages etc.). 726 It should be noticed that the present draft imposes a minimal rate of 727 control message emission. However a node MAY send control messages at 728 a higher rate (e.g. for better reacting to high mobility). It is an 729 implementation issue to optimize the rate of control packet emission. 730 If all nodes use the same constant base rate, introducing some jitter 731 as described above may be desirable. 733 2.2. Neighbor Sensing 735 Each node should detect the neighbor interfaces with which it has a 736 direct and symmetric link. Uncertainties over radio propagation may 737 make some links unidirectional. Consequently, all links MUST be 738 checked in both directions in order to be considered valid. 740 To perform neighbor detection, each node broadcasts HELLO messages, 741 containing information about heard neighbor interfaces and their link 742 status. The link status may either be "symmetric", "heard" (asymmet- 743 ric), "MPR" or "lost". "Symmetric" indicates, that the link has been 744 verified to be bi-directional, i.e. it is possible to transmit data 745 in both directions. "Heard" indicates that the node can hear HELLO 746 messages from a neighbor interface, but it is not confirmed that this 747 neighbor interface is also able to receive messages from the node. 748 "MPR" indicates, that a node is selected by the sender as a MPR. A 749 status of MPR further implies that the link is symmetric. "Lost" 750 indicates that the link with this neighbor interface is now lost. 752 HELLO messages are broadcasted to all one-hop neighbors and are emit- 753 ted on each MANET interface of the node. They are *not relayed* to 754 further nodes. 756 More precisely, a HELLO message contains for each interface I: 758 - a list of neighbor interface addresses, having a symmetric 759 link to interface I; 761 - a list of neighbor interface addresses, which are "heard" by 762 interface I (for historical reasons, the term "heard" is used 763 for "asymmetric"); 765 - a list of neighbor interface addresses of neighbors selected 766 as MPRs, AND having a symmetric link to interface I; 768 - a list of neighbor interface addresses, which have been lost. 770 These lists are computed as described in the HELLO message generation 771 section. 773 2.2.1. HELLO Message Format 775 To accommodate the above requirements, as well as to accommodate for 776 future extensions, an approach similar to the overall packet format 777 is taken. Thus the proposed format of a HELLO message is: 779 0 1 2 3 780 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 782 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 783 | Reserved | # Interfaces | 784 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 785 | Interface Address | 786 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 787 | Interface Address | 788 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 789 : . . . : 790 : : 791 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 792 | Link Type | Interface # | Link Message Size | 793 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 794 | Neighbor Interface Address | 795 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 796 | Neighbor Interface Address | 797 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 798 : . . . : 799 : : 800 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 801 | Link Type | Interface # | Link Message Size | 802 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 803 | Neighbor Interface Address | 804 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 805 | Neighbor Interface Address | 806 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 807 : : 808 : : 809 (etc) 811 This is sent as the data-portion of the general packet format 812 described in the Packet Format and Forwarding section, with the "Mes- 813 sage Type" set to HELLO_MESSAGE and the TTL field set to 1 (one). 815 Description of the fields 816 Reserved 818 This field is reserved for future usage, and MUST be set to 819 "000000000000000000000000" for compliance with this draft. 821 # Interfaces 823 This field indicates the number of additional MANET interfaces 824 (excluding the main interface) possessed by the node. If the 825 node has only one interface, this number is 0. 827 Interface Address 829 This field indicates the addresses of additional MANET inter- 830 faces. The first one will be referenced as interface address 831 number 1, the second as interface address number 2, and so on. 832 The main address of the node (whose address is given in the 833 originator field of the message header) will be referenced as 834 interface address number 0. 836 Link Message Size 838 The size of the link message, counted in bytes and measured 839 from the beginning of the "Link Type" field and until the next 840 "Link Type" field (or - if there are no more link types - the 841 end of the message). 843 Interface # 845 This field indicates the number of the interface to which the 846 following list of neighbor interfaces corresponds. Number 0 847 indicates the main interface (whose address is the main 848 address). 850 Link Type 852 This field specifies the type of the link between the inter- 853 face of the sender, as identified by the interface number, and 854 the following list of neighbor interfaces. As a minimum, the 855 following four link types are REQUIRED by OLSR: 857 - ASYM_LINK - indicating that the links are asymmetric 858 (i.e. the neighbor interface is "heard"). 860 - SYM_LINK - indicating that the links are symmetric. 862 - MPR_LINK - indicating, that the links are symmetric AND 863 that the neighbors have been selected as MPR by the 864 sender. 866 - LOST_LINK - indicating that the links have been lost. 868 Neighbor Interface Address 870 An interface address of a neighbor. 872 Neighbor sensing is performed using HELLO message exchange, updating 873 the neighbor sensing information base in each node. 875 2.2.2. Neighbor Sensing Information Base 877 The neighbor sensing information base stores information about neigh- 878 bor interfaces, 2-hop neighbors, MPRs and MPR selectors. 880 2.2.2.1. Neighbor Set 882 For each of its interface I and for each neighbor interface NI, heard 883 by I, a node records a "Neighbor Tuple" (N_if_id, N_if_addr, 884 N_main_addr, N_SYM_time, N_ASYM_time, N_time) where N_if_id is the 885 identification number of I, N_if_addr is the address of the neighbor 886 interface NI, N_main_addr is the main address of the neighbor pos- 887 sessing NI, N_SYM_time is the time until which the link is considered 888 symmetric, N_ASYM_time is the time until which the neighbor interface 889 is considered heard, and N_time specifies the time at which this 890 record expires and *MUST* be removed. When N_SYM_time and 891 N_ASYM_time are expired, the link is considered lost. 893 This information is used when declaring the neighbor interfaces in 894 the HELLO messages. N_SYM_time and N_ASYM_time are used to decide the 895 Link Type declared for the neighbor interface. If N_SYM_time is not 896 expired, the link is declared symmetric. If N_SYM_time is expired but 897 N_ASYM_time is not, the link is declared heard. If both N_SYM_time 898 and N_ASYM_time are expired, the link is declared lost. 900 In a node, the set of Neighbor Tuples are denoted the "Neighbor Set". 902 2.2.2.2. 2-hop Neighbor Set 904 A node records a set of "2-hop tuples" (N_main_addr, N_if_addr, 905 N_2hop_addr, N_time), describing symmetric or MPR links between its 906 neighbors and the 2-hop symmetric neighborhood. N_main_addr and 907 N_if_addr are the main address and an interface address of a 908 neighbor, N_2hop_addr is an interface address of a 2-hop neighbor 909 with a symmetric or MPR link to interface N_if_addr and N_time speci- 910 fies the time at which the tuple expires and *MUST* be removed. 912 This information is gathered from the HELLO messages received by a 913 node from its neighbor nodes. 915 In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor 916 Set". 918 2.2.2.3. MPR Set 920 A node maintains a set of neighbors which are elected as MPR. Their 921 main addresses are listed in the so-called MPR Set. The Multipoint 922 relay selection section describes how MPRs are elected. 924 2.2.2.4. MPR Selector Set 926 A node maintains information (obtained from the HELLO messages) about 927 the neighbors which have selected this node as a MPR. 929 Thus, a node records a MPR-selector tuple (MS_if_addr, MS_main_addr, 930 MS_time), for interfaces of a neighbor which has selected the node as 931 MPR. MS_if_addr is the address of an interface of a node which has 932 selected the node as MPR for that interface, MS_main_addr is the main 933 address of the MPR selector and MS_time specifies the time at which a 934 tuple expires and *MUST* be removed. 936 In a node, the set of MPR-selector tuples are denoted the "MPR Selec- 937 tor Set". A sequence number, MSSN, is associated with this set. When- 938 ever a tuple is added to or removed from this set, the MSSN is incre- 939 mented by 1. 941 2.2.3. HELLO Message Generation 943 The lists of addresses declared in a HELLO message are computed from 944 the Neighbor Set as follows: 946 - for each tuple where N_SYM_time and N_ASYM_time are expired, 947 the N_if_addr is declared with LOST_LINK Link Type for inter- 948 face N_if_id; 950 - for each tuple where N_SYM_time is not expired, the N_if_addr 951 is declared with MPR_LINK Link Type if N_main_addr is in the 952 MPR set and SYM_LINK Link Type otherwise; 954 - for each tuple where N_SYM_time is expired but N_ASYM_time is 955 not expired, the N_if_addr is declared with ASYM_LINK Link 956 Type. 958 The list of neighbor interfaces in a HELLO message can be partial 959 (e.g. due to message size limitations, imposed by the network), the 960 rule being the following: for each interface a neighbor interface is 961 heard on, its address is cited with corresponding interface id at 962 least once within a predetermined refreshing period (HELLO_INTERVAL). 964 Notice that for limiting the impact from loss of control messages, it 965 is desirable that a message fits in a single MAC packet. 967 Each HELLO message generated is broadcasted on each MANET interface 968 of the node. 970 2.2.4. HELLO Message Processing 972 Upon receiving a HELLO message, the node SHOULD update the neighbor 973 information corresponding to the sender node address (a node may - 974 e.g. for security reasons - wish to restrict updating the neighbor- 975 table, i.e. ignoring HELLO messages from some nodes). 977 In this section, the term "Originator Address" will be used for the 978 main address of the node which sent the HELLO-message. The term 979 "Sender Interface Address" will be used for the sender address (given 980 in the IP header of the packet containing the message) of the inter- 981 face which sent the HELLO message. The term "Receiver Interface" will 982 be used for the interface which received the HELLO message. The term 983 "link interface addresses" will be used for the own interface 984 addresses of the sender listed in the HELLO message. 986 The Neighbor Set should be updated as follows: 988 1 Upon receiving a HELLO message, if there exists no neighbor 989 tuple with 991 N_if_addr == Sender Interface Address 993 and 995 N_if_id == identifier of the Receiver Interface, 997 a new tuple is created with 998 N_if_addr = Sender Interface Address 1000 N_if_id = identifier of the Receiver Interface 1002 N_SYM_time = current time - 1 (expired time) 1004 N_time = current time + NEIGHB_HOLD_TIME 1006 2 The tuple is then modified as follows: 1008 2.1 N_main_addr = Originator Address. 1010 2.3 N_time = max (N_time, current time + 1011 NEIGHB_HOLD_TIME); 1013 2.4 N_ASYM_time = current time + NEIGHB_HOLD_TIME; 1015 2.5 if the node finds the receiver interface address among 1016 the addresses listed in the HELLO with: 1018 Link Interface Address == Sender Interface Address, 1020 then, the tuple is modified as follows: 1022 if Link Type == LOST_LINK then 1024 N_SYM_time = current time - 1 (expired time) 1026 else: 1028 N_SYM_time = current time + NEIGHB_HOLD_TIME, 1030 N_time = current time + 2 * 1031 NEIGHB_HOLD_TIME. 1033 The rule for setting N_time is the following: a link loosing its sym- 1034 metricity should still be advertised at least NEIGHB_HOLD_TIME. This 1035 allows neighbors to detect the link breakage. 1037 The 2-hop Neighbor Set is updated as follows: 1039 1 for each 2-hop interface address listed in the HELLO message 1040 with Link Type SYM_LINK or MPR_LINK, a 2-hop tuple is created 1041 with: 1043 N_main_addr = Originator Address; 1044 N_if_addr = Link Interface Address corresponding to the 1045 2-hop interface address; 1047 N_2hop_addr = the interface address of the 2-hop neigh- 1048 bor; 1050 N_time = current time + NEIGHB_HOLD_TIME. 1052 This tuple may replaces an older similar tuple with same 1053 N_if_addr and N_2hop_addr values. 1055 2 For each 2-hop interface address listed in the HELLO message 1056 with Link Type LOST_LINK or ASYM_LINK, all the 2-hop tuples 1057 where: 1059 N_if_addr == Link Interface Address corresponding to the 1060 2-hop interface address, 1062 and 1064 N_2hop_addr == the 2-hop interface address 1066 are deleted. 1068 Based on the information obtained from the HELLO messages, each node 1069 constructs its MPR selector set. 1071 Thus, upon receiving a HELLO message, if a node finds one of its 1072 interface addresses in a list with a link type of "MPR", it MUST 1073 update the MPR selector set to contain updated information about the 1074 sender of the HELLO message: 1076 1 If there exists no MPR selector tuple with: 1078 MS_if_addr == Link Interface Address 1080 and 1082 MS_main_addr == Originator Address 1084 then MSSN is incremented to indicate that the MPR selector 1085 table is going to change. 1087 2 If there exists no MPR selector tuple with: 1089 MS_if_addr == Link Interface Address 1091 then a new tuple is created with: 1093 MS_if_addr = Link Interface Address 1095 3 The tuple is then modified as follows: 1097 MS_main_addr = Originator Address, 1099 MS_time = current time + NEIGHB_HOLD_TIME. 1101 Deletion of MPR selector tuples occurs in case of expiration of the 1102 timer or in case of link breakage as described in the neighborhood 1103 and 2-hop neighborhood changes section. 1105 2.2.5. Multipoint Relay Selection 1107 Each node in the network selects, independently, its own set of MPRs 1108 among its symmetric neighborhood. The symmetric links with MPRs are 1109 advertised with Link Type MPR_LINK instead of SYM_LINK in HELLO mes- 1110 sages. 1112 MPRs are used to flood control messages from that node into the net- 1113 work while reducing the number of retransmissions that will occur in 1114 a region. Thus, the concept of MPR is an optimization of a pure 1115 flooding mechanism. 1117 The MPR set must be calculated by a node in such a way that it, 1118 through the neighbors in the MPR-set, can reach all symmetric 2-hop 1119 neighbors which are not at the same time symmetric neighbors of the 1120 node. This means that the union of the symmetric neighborhoods of 1121 the MPR nodes contains the symmetric 2-hop neighborhood. While it is 1122 not essential that the MPR set is minimal, it is essential that all 1123 2-hop neighbors can be reached through the selected MPR nodes. The 1124 smaller a MPR-set, however, the more optimization is achieved. 1126 By default, the MPR set can coincide with the entire symmetric neigh- 1127 bor set. This will be the case at network initialization. 1129 The following specifies a proposed heuristic for selection of MPRs 1130 [2] adapted for multiple interfaces support. It constructs a MPR-set 1131 that allows to reach any symmetric 2-hop interface (i.e. any inter- 1132 face of a 2-hop neighbor having a symmetric link with a neighbor). 1133 The following terminology will be used in describing this algorithm 1134 (neighbors are identified by their main address and 2-hop interfaces 1135 by their address): 1137 N: The set of neighbors with which there exists a symmetric link. 1139 N2: The set made of the symmetric 2-hop interfaces excluding all 1140 the interfaces of members of N and the interfaces of the node 1141 performing the computation. 1143 D(y): 1144 Degree of one hop neighbor node y (where y is a member of N), 1145 defined as the number of symmetric neighbor interfaces of node 1146 y, EXCLUDING all the interfaces of members of N and the inter- 1147 faces of the node performing the computation. 1149 The proposed heuristic is as follows: 1151 1 Start with an empty MPR set 1153 2 Calculate D(y), where y is a member of N, for all nodes in N. 1155 3 Select as MPRs those nodes in N which provide the "only path" 1156 to some interfaces in N2. 1158 4 While there exist interfaces in N2 which are not covered by 1159 the MPR set: 1161 4.1 For each node in N, calculate the number of interfaces in 1162 N2 which are not yet covered by the MPR set and are 1163 reachable through this one hop neighbor; 1165 4.2 Select as a MPR the node from N which provides reachabil- 1166 ity to the maximum number of uncovered interfaces in N2. 1167 In case of a tie, select that node as MPR whose D(y) is 1168 greater. 1170 5 As an optimization, process each node y in the MPR set. If the 1171 MPR set excluding y still covers all interfaces in N2, node y 1172 is removed from the MPR set. 1174 When the MPR set has been computed, all the corresponding main 1175 addresses are stored in the MPR Set. 1177 Some processing such as MPR set re-calculation should occur when 1178 changes are detected in the neighborhood or the 2-hop neighborhood. 1180 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes 1182 A change in the neighborhood is detected when: 1184 - The N_SYM_time field of a neighbor tuple expires. This is con- 1185 sidered as a neighbor loss if it was the last link with a 1186 neighbor node (on the contrary, a link with an interface may 1187 break while a link with another interface of the neighbor node 1188 is still alive). 1190 - The N_ASYM_time field of a neighbor tuple expires and 1191 N_SYM_time is expired. The link is then considered lost. 1193 - A new neighbor tuple is inserted in the Neighbor Set with a 1194 valid N_SYM_time or a tuple with expired N_SYM_time is modi- 1195 fied so that N_SYM_time becomes valid. This is considered as a 1196 neighbor appearance if there was previously no link with the 1197 corresponding neighbor node. 1199 A change in the 2-hop neighborhood is detected when a 2-hop neighbor 1200 tuple expires or is deleted according to the HELLO message processing 1201 section. 1203 The following processing should occur when changes in the neighbor- 1204 hood or the 2-hop neighborhood are detected: 1206 - In case of neighbor loss, all the 2-hop tuples with 1207 N_main_addr == Main Address of the neighbor are deleted. 1209 - In case of neighbor loss, all the MPR selector tuples with 1210 MS_main_addr == Main Address of the neighbor are deleted 1212 - The MPR set is re-calculated when a neighbor appearance or 1213 loss is detected, or when a change in the 2-hop neighborhood 1214 is detected. 1216 - An additional HELLO message may be sent when the MPR set 1217 changes. 1219 2.2.6. Advanced Neighbor Sensing Functioning 1221 Established links should be as reliable as possible to avoid data 1222 packet loss. To enhance the reliability of the neighbor sensing mech- 1223 anism, the following implementation recomendations should be consid- 1224 ered. 1226 Each neighbor tuple in the neighbor set SHOULD, in addition to what 1227 is described in section 2.2.2.1, include a N_pending field, a N_qual- 1228 ity field, and a N_LOST_time. N_pending is a boolean value specify- 1229 ing if the link is considered pending (i.e. the link is not consid- 1230 ered established). N_quality is a dimensionless number between 0 and 1231 1 describing the quality of the link. N_LOST_time is a timer for 1232 declaring a link as lost when an established link becomes pending. 1234 HELLO message generation should consider those new fields as follows. 1236 1 If N_LOST_time is not expired, the link is advertised with a 1237 link type of LOST_LINK; 1239 2 otherwise, if N_LOST_time is expired and N_pending is set to 1240 "true", the link SHOULD NOT be advertised at all; 1242 3 otherwise, if N_LOST_time is expired and N_pending is set to 1243 "false", the link is advertised as described in the HELLO mes- 1244 sage generation section. 1246 A node considers it has a symmetric link for each neighbor tuple such 1247 that N_LOST_time is expired, N_pending is "false" and N_SYM_time is 1248 not expired. This should be taken as definition for computing the 1249 symmetric neighborhood when computing the MPR set. 1251 Apart from the above points, what has been previously describe do not 1252 interfere with this newly introduced fields. The N_quality, N_pending 1253 and N_LOST_time fields are updated according to the present section 1254 and nowhere else. The other fields are not modified by the advanced 1255 neighbor sensing functioning. 1257 This advanced functioning is described as separately as possible to 1258 increase readability. 1260 2.2.6.1. Link Hysteresis 1262 The link between a node and some of its neighbor interfaces might be 1263 "bad", i.e. from time to time let HELLOs pass through only to fade 1264 out immediately after. In this case, the neighbor information base 1265 would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of 1266 link layer notification, such a bad link would spoil routing. To cope 1267 with such unstable links, the following hysteresis strategy SHOULD be 1268 adopted. 1270 For each neighbor interface NI heard by interface I, the N_quality 1271 field of the corresponding Neighbor Tuple determines the establish- 1272 ment of the link. Its value is compared to two thresholds 1273 HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW which are fixed between 0 and 1274 1 and such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. When 1275 N_quality becomes higher than HYST_THRESHOLD_HIGH, the N_pending 1276 field is set to false. When N_quality goes below HYST_THRESHOLD_LOW, 1277 the N_pending field is set to true and N_LOST_time is set to min 1278 (N_time, current time + NEIGHB_HOLD_TIME) (the link is then consid- 1279 ered as lost according to the Neighborhood and 2-hop neighborhood 1280 changes section and this may produce a neighbor loss). The condition 1281 for considering a link established is thus stricter than the condi- 1282 tion for loosing it. 1284 As a basic implementation requirement, an estimation of the link 1285 quality must be maintained and stored in the N_quality field. If some 1286 measure of the signal/noise level on a received message is available 1287 (e.g. as a link layer notification), then it can be used as estima- 1288 tion after normalization. 1290 If no signal/noise information is available from the link layer, an 1291 algorithm such the following can be utilized. The algorithm is 1292 parametrized by a scaling parameter HYST_SCALING which is a number 1293 fixed between 0 and 1. For each neighbor interface NI heard by inter- 1294 face I, the first time NI is heard by I, N_quality is set to 1295 HYST_SCALING (and N_pending is set to true). 1297 A tuple is updated according to two rules. Every time an OLSR mes- 1298 sage emitted by NI is received by I, the stability rule is applied: 1300 N_quality = (1-HYST_SCALING)*N_quality + HYST_SCALING. 1302 When an OLSR message emitted by NI is lost by I, the instability 1303 rule is applied: 1305 N_quality = (1-HYST_SCALING)*N_quality. 1307 The loss of OLSR messages is detected by tracking the missing Message 1308 Sequence Numbers and by long period of silence. If no HELLO message 1309 has been received for a HELLO_INTERVAL period, a loss of HELLO mes- 1310 sage is detected. 1312 2.2.6.2. Optional Link layer notification 1314 OLSR is designed not to impose or expect any specific information 1315 from the link layer. However, if information from the link-layer is 1316 available, a node MAY use this as described in this section. 1318 If link layer information describing connectivity to neighboring 1319 nodes is available (i.e. loss of connectivity such as through absence 1320 of a link layer acknowledgment), this information is used in addition 1321 to the information from the HELLO-messages to maintain the neighbor 1322 information base and the MPR selector set. 1324 Thus, upon receiving a link-layer notification that the link between 1325 a node and a neighbor interface is broken, the following actions are 1326 taken: 1328 1 if the link is broken to either a symmetric or asymmetric 1329 neighbor interface, the corresponding neighbor tuple is modi- 1330 fied: N_LOST_time and N_time are set to current time + 1331 NEIGHB_HOLD_TIME. 1333 2 this is considred as a link loss and the appropriate process- 1334 ing described in the neighborhood and 2-hop neighborhood 1335 changes section should be performed. 1337 2.3. Topology Discovery 1339 The Neighbor Sensing part of the protocol basically offers to each 1340 node a list of neighbors with which it can communicate directly and 1341 an optimized flooding mechanism through MPRs. Based on this mecha- 1342 nism, topology information is disseminated through the network. The 1343 present section describes what part of the information given by the 1344 Neighbor Sensing is disseminated and how it is used to construct 1345 routes. 1347 Routes are constructed through MPR-links and links with neighbors. A 1348 node thus basically disseminates its MPR-selector set. If a node has 1349 multiple interfaces, it must also disseminate the list of its inter- 1350 face addresses. 1352 2.3.1. Multipoint Relay Information Declaration 1354 2.3.1.1. Topology Information Base 1356 Each node in the network maintains topological information about the 1357 network. This information is acquired from TC-messages and is used 1358 for routing table calculations. 1360 Thus, for each destination in the network, a "Topology Tuple" 1361 (T_dest, T_last, T_seq, T_time) is recorded. T_dest is the main 1362 address of a node, which may be reached in one hop from the node with 1363 the main address T_last. Typically, T_last is a MPR of T_dest. T_seq 1364 is a sequence number, and T_time specifies the time at which this 1365 tuple expires and *MUST* be removed. 1367 In a node, the set of Topology Tuples are denoted the "Topology Set". 1369 2.3.1.2. TC Message Generation 1371 In order to build the topology information base needed, each node, 1372 which has been selected as MPR, broadcasts Topology Control (TC) mes- 1373 sages. TC messages are flooded to all nodes in the network and take 1374 advantage of MPRs. MPRs enable a better scalability in the distribu- 1375 tion of topology information [1]. 1377 A TC message is sent by a node in the network to declare its MPR 1378 Selector set. I.e., the TC message contains the list of neighbors 1379 which have selected the sender node as a MPR. The sequence number 1380 (MSSN) associated with this MPR selector set is also sent with the 1381 list. The list of addresses can be partial in each TC message (e.g. 1382 due to message size limitations, imposed by the network), but parsing 1383 of all TC messages describing the MPR selector set of a node MUST be 1384 complete within a certain refreshing period (TC_INTERVAL). The infor- 1385 mation diffused in the network by these TC messages will help each 1386 node calculate its routing table. A node which has an empty MPR 1387 selector set, i.e. nobody has selected it as a MPR, SHOULD NOT gener- 1388 ate any TC message. 1390 A node MAY transmit additional TC-messages to increase its reactive- 1391 ness to link failures. I.e. when a change to the MPR selector set is 1392 detected and this change can be attributed to a link failure, a TC- 1393 message SHOULD be transmitted after a shorter interval than TC_INTER- 1394 VAL. 1396 The proposed format of a TC message is 1398 0 1 2 3 1399 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 1400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1401 | MSSN | Reserved | 1402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1403 | Multipoint Relay Selector Main Address | 1404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1405 | Multipoint Relay Selector Main Address | 1406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1407 | ... | 1408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1410 This is sent as the data-portion of the general message format with 1411 the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set 1412 to 255 (maximum value) to diffuse the message into the entire net- 1413 work. 1415 Description of the fields 1417 MPR Selector Sequence Number (MSSN) 1419 A sequence number is associated with the MPR selector set. 1420 Every time a node detects a change in its MPR selector set, it 1421 increments this sequence number. This number is sent in this 1422 MSSN field of the TC message to keep track of the most recent 1423 information. When a node receives a TC message, it can decide 1424 on the basis of this MPR Sequence Number, whether or not the 1425 received information about the MPR selectors of the originator 1426 node is more recent than what it already has. 1428 Multipoint Relay Selector Main Address 1430 This field contains the main address of a node, which has 1431 selected the Originator node (of the TC message) as a MPR. 1432 All addresses of the MPR selectors of the Originator node are 1433 put in the TC message. If the maximum allowed message size (as 1434 imposed by the network) is reached while there are still MPR 1435 selector addresses which which have not been inserted into the 1436 TC-message, more TC messages will be generated until the 1437 entire MPR selector set has been sent. 1439 Reserved 1441 This field is reserved for future usage, and MUST be set to 1442 "0000000000000000" for compliance with this draft. 1444 2.3.1.3. TC Message Processing 1446 TC messages are broadcasted and retransmitted by the MPRs in order to 1447 diffuse the messages in the entire network. 1449 In this section, the term "originator" is used to designate the node 1450 from which the message originally originated, while the term "sender" 1451 is used to designate the node from which the message was received 1452 (i.e. the "last hop" of the message). 1454 The tuples in the topology set are recorded with the topology infor- 1455 mation that is exchanged through TC messages, according to the 1456 following algorithm: 1458 1 If the sender interface (NB: not originator) of this message 1459 is not in the symmetric neighborhood of this node, the message 1460 is discarded. 1462 2 A tuple is inserted into the duplicate table to prevent it 1463 from being processed again with: 1465 D_addr = originator address 1467 D_seq_num = Message Sequence 1469 D_time = current time + D_HOLD_TIME. 1471 3 If there exist some tuple in the topology set where: 1473 T_last == originator address AND 1475 T_seq > MSSN, 1477 then no further processing of this TC message is performed and 1478 the message is silently discarded (case: message received out 1479 of order). 1481 4 All tuples in the topology set where: 1483 T_last == originator address AND 1485 T_seq < MSSN 1487 are removed from the topology set. 1489 5 For each of the MPR selector address received in the TC mes- 1490 sage: 1492 5.1 If there exist some tuple in the topology set where: 1494 T_dest == MPR selector address, AND 1496 T_last == originator address, 1498 then the holding time of that tuple is set to: 1500 T_time = current time + TOP_HOLD_TIME. 1502 5.2 Otherwise, a new tuple is recorded in the topology set 1503 where: 1505 T_dest = MPR selector address, 1507 T_last = originator address, 1509 T_seq = MSSN, 1511 T_time = current time + TOP_HOLD_TIME. 1513 6 If the sender address is the link interface address of a MPR 1514 selector of this node and if the time to live of the message 1515 is greater than '1', the message MUST be forwarded according 1516 to the following: 1518 6.1 The TTL of the message is reduced by one. 1520 6.2 The hop-count of the message is increased by one 1522 6.3 The message is broadcasted on all interfaces (Notice: The 1523 remaining fields of the message header SHOULD be left 1524 unmodified.) 1526 2.3.2. Multiple Interface Association 1528 Each node in the network maintains interface information about the other 1529 nodes in the network. This information acquired from MID-messages, emit- 1530 ted by nodes with multiple interfaces participating in the MANET, and is 1531 used for routing table calculations. 1533 2.3.2.1. Interface Association Information Base 1535 For each destination in the network, "Interface association Tuples" 1536 (I_if_addr, I_main_addr, I_time) are recorded. I_if_addr is an inter- 1537 face address of a node, I_main_addr is the main address of this node. 1538 I_time specifies the time at which this tuple expires and *MUST* be 1539 removed. 1541 In a node, the set of Interface association Tuples is denoted the 1542 "Interface association Set". 1544 2.3.2.2. MID Message Broadcast 1546 In order to build the interface association information base, each 1547 node with multiple interfaces broadcast Multiple Interface Declara- 1548 tion (MID) messages. MID messages are flooded to all nodes in the 1549 network and take advantage of MPRs. 1551 A MID message is sent by a node in the network to declare its multi- 1552 ple interfaces (if any). I.e., the MID message contains the list of 1553 interface addresses which are associated to its main address. The 1554 list of addresses can be partial in each TC message (e.g. due to mes- 1555 sage size limitations, imposed by the network), but parsing of all 1556 MID messages describing a nodes interface set MUST be complete within 1557 a certain refreshing period (MID_INTERVAL). The information diffused 1558 in the network by these MID messages will help each node to calculate 1559 its routing table. A node which has only a single interface address 1560 participating in the MANET (i.e. running OLSR), MUST NOT generate any 1561 MID message. 1563 A node with more interfaces, where only one is participating in the 1564 MANET and running OLSR (e.g. a node is connected to a wired network 1565 as well as to a MANET) MUST NOT generate any MID messages. 1567 The proposed format of a MID message is 1569 0 1 2 3 1570 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 1571 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1572 | Interface Address | 1573 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1574 | Interface Address | 1575 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1576 | ... | 1577 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1579 This is sent as the data-portion of the general message format with 1580 the "Message Type" set to MID_MESSAGE. The time to live SHOULD be 1581 set to 255 (maximum value) to diffuse the message into the entire 1582 network. 1584 Description of the fields 1586 Interface Address 1587 This field contains the address of an interface of the node 1588 other than its main address (already indicated in the origina- 1589 tor address). All interface addresses other than the main 1590 address of the Originator node are put in the MID message. If 1591 the maximum allowed message size (as imposed by the network) 1592 is reached while there are still interface addresses which 1593 have not been inserted into the MID-message, more MID messages 1594 are generated until the entire interface addresses set has 1595 been sent. 1597 2.3.2.3. MID Message Processing 1599 MID messages are broadcasted and retransmitted by the MPRs in order 1600 to diffuse the messages in the entire network. 1602 In this section, the term "originator" is used to designate the node 1603 from which the message originally originated, while the term "sender" 1604 is used to designate the node from which the message was received 1605 (i.e. the "last hop" of the message). 1607 The tuples in the multiple interface association set are recorded 1608 with the information that is exchanged through MID messages, follow- 1609 ing the following algorithm: 1611 1 If the sender (NB: not originator) of this message is not in 1612 the symmetric neighborhood of this node, the message is dis- 1613 carded. 1615 2 A tuple is inserted into the duplicate table to prevent it 1616 from being processed again with: 1618 D_addr = originator address 1620 D_seq_num = Message Sequence 1622 D_time = current time + D_HOLD_TIME. 1624 3 For each of the interface address received in the MID message: 1626 3.1 If there exist some tuple in the interface association 1627 set where: 1629 I_if_addr == interface address, AND 1630 I_main_addr == originator address, 1632 then the holding time of that tuple is set to: 1634 I_time = current time + MID_HOLD_TIME. 1636 3.2 Otherwise, a new tuple is recorded in the interface asso- 1637 ciation set where: 1639 I_if_addr = interface address, 1641 I_main_addr = originator address, 1643 I_time = current time + MID_HOLD_TIME. 1645 4 If the sender address is the link interface address of a MPR 1646 selector of this node and if the time to live of the message 1647 is greater than '1', the message MUST be forwarded according 1648 to the following: 1650 4.1 The TTL of the message is reduced by one. 1652 4.2 The hop-count of the message is increased by one 1654 4.3 The message is broadcasted on all interfaces (Notice: The 1655 remaining fields of the message header SHOULD be left 1656 unmodified.) 1658 2.3.3. Associated Networks and Hosts 1660 A node MAY provide access to a set of associated hosts. I.e., a node 1661 may act as a "gateway" between the MANET and a number of associated 1662 hosts and/or subnets, not running OLSR and thus not participating in 1663 the MANET. Thus, a node SHOULD be able to inject routing information 1664 describing these associated hosts or networks into MANET, as SHOULD 1665 all nodes be capable of interpreting such information. 1667 Notice, that this is a different case from that of "multiple inter- 1668 faces", described previously. Where, in the "Multiple Interface Asso- 1669 ciations", all the described interfaces were participating in the 1670 MANET through running the OLSR protocol, this section addresses the 1671 interfaces which do not participate. This is, e.g., the case where a 1672 node has both a wireless interface (participating in the MANET) and a 1673 wired interface, through which a number of hosts statically connect 1674 (to the nodes in the MANET). 1676 To accomplish this, a node, to which there are associated hosts 1677 and/or networks, periodically issues an Host and Network Association 1678 (HNA) message, containing sufficient information for the recipients 1679 to construct an appropriate routing table. 1681 2.3.3.1. Host and Network Association Information Base 1683 Each node maintains information concerning which nodes may act as 1684 "gateways" to associated hosts and networks by recording "association 1685 tuples" (GW_main_addr, NET_addr, NET_mask, GS_time), where 1686 GW_main_addr is the main address of the gateway, NET_addr and 1687 NET_mask specifies the network address and netmask of a network, 1688 reachable through this gateway, and GS_time specifies the time at 1689 which this tuple expires and hence *MUST* be removed. 1691 The set of all association tuples in a node is called the "associa- 1692 tion set". 1694 2.3.3.2. Host and Network Association Message Broadcast 1696 A node with associated hosts and/or networks SHOULD periodically gen- 1697 erate a Host and Network Association (HNA) message, containing pairs 1698 of (network address, netmask) corresponding to the connected hosts and 1699 networks. HNA-messages SHOULD be transmitted periodically every 1700 HNA_INTERVAL. 1702 A node without any associated hosts and/or networks SHOULD NOT gener- 1703 ate HNA-messages. 1705 The proposed format of an HNA-message is: 1707 0 1 2 3 1708 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 1709 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1710 | Network Address | 1711 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1712 | Netmask | 1713 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1714 | Network Address | 1715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1716 | Netmask | 1717 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1718 | ... | 1719 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1721 This is sent as the data part of the general packet format with the 1722 "Message Type" set to HNA and the TTL field set to 255. 1724 It should be noticed, that the HNA-message can be considered as a 1725 "generalized version" of the TC-message: the originator of both the 1726 HNA and TC messages announce "reachability" to some other host(s). In 1727 the TC-message, no netmask is required, since all reachability is 1728 announced on a per-host basis. In HNA-messages, announcing reachabil- 1729 ity to an address sequence through a network- and netmask address is 1730 typically preferred over announcing reachability to individual host 1731 addresses. 1733 Description of the fields 1735 Network Address 1737 The network address of the associated network 1739 Netmask 1741 The netmask, corresponding to the network address immediately 1742 above. 1744 2.3.3.3. HNA Message Processing 1746 In this section, the term "originator address" is used to designate 1747 the main address of the node which originally issued the HNA-message. 1749 Upon receiving a HNA-message, the node performs the following: 1751 1 An entry in the duplicate set is recorded for this message 1752 with: 1754 D_addr = originator address 1756 D_seq_num = Message Sequence Number 1758 D_time = current time + D_HOLD_TIME. 1760 2 For each (network address, netmask) pair in the message: 1762 2.1 if an entry in the association set already exists, where: 1764 GW_main_addr == originator address 1766 NET_addr == network address 1767 NET_mask == netmask 1769 then the holding time for that tuple is set to: 1771 GW_time = current time + GW_HOLDING_TIME 1773 2.2 otherwise, a new tuple is recorded with: 1775 GW_main_addr == originator address 1777 NET_addr == network address 1779 NET_mask == netmask 1781 GW_time = current time + GW_HOLDING_TIME 1783 3 If the sender address is the link interface address of a MPR 1784 selector of this node and if the time to live of the message 1785 is greater than '1', the message MUST be forwarded according 1786 to the following: 1788 3.1 The TTL of the message is reduced by one. 1790 3.2 The hop-count of the message is increased by one 1792 3.3 The message is broadcasted on all interfaces (Notice: The 1793 remaining fields of the message header SHOULD be left 1794 unmodified.) 1796 2.3.3.4. Optional Link layer notification 1798 Detection of a link failure between a node and one of its MPR selec- 1799 tors through a link-layer notification may trigger additional TC-mes- 1800 sages to increase the protocols reactiveness to link failures. I.e. 1801 when a change to the MPR selector set is detected and this change can 1802 be attributed to a link failure, an additional TC-message SHOULD be 1803 transmitted. 1805 Thus, if a link failure appears to be a neighbor loss with a neigh- 1806 bor, which has selected this node as MPR, the MPR selector set is 1807 updated (MSSN is thus incremented) and a TC message SHOULD be gener- 1808 ated. 1810 2.3.4. Routing Table Calculation 1812 Each node maintains a routing table which allows it to route data, 1813 destined for the other nodes in the network. The routing table is 1814 based on the information contained in the neighbor sensing informa- 1815 tion base, the interface association set and the topology set. There- 1816 fore, if any of these tables are changed, the routing table is re- 1817 calculated to update the route information about each destination in 1818 the network. The route entries are recorded in the routing table in 1819 the following format: 1821 1. R_dest R_next R_dist R_if_id 1822 2. R_dest R_next R_dist R_if_id 1823 3. ,, ,, ,, 1825 Each entry in the table consists of R_dest, R_next, R_dist, and 1826 R_if_id which specifies that the node identified by R_dest is esti- 1827 mated to be R_dist hops away from the local node, and that the sym- 1828 metric neighbor node with interface address R_next is the next hop 1829 node in the route to R_dest, and this one hop is reachable through 1830 the local interface 1831 R_if_id. Entries are recorded in the table for each destination in 1832 the network for which the route is known. All the destinations for 1833 which the route is broken or partially known are not entered in the 1834 table. 1836 This routing table is updated when a change is detected in the neigh- 1837 bor information base, or the topology set. More precisely, it is re- 1838 calculated in case of neighbor appearance or loss, or when a topology 1839 tuple is created or removed. The update of this routing information 1840 does not generate or trigger any messages to be transmitted, neither 1841 in the network, nor in the one-hop neighborhood. 1843 To construct the routing table of node X, a shortest path algorithm 1844 is run on the directed graph containing the arcs X -> Y where Y is 1845 any symmetric neighbor of X (with Link Type SYM_LINK or MPR_LINK) and 1846 the arcs U -> V where there exists an entry in the topology set with 1847 V as T_dest and U as T_last. 1849 The following procedure is given as an example to calculate (or re- 1850 calculate) the routing table : 1852 1 All the entries from the routing table are removed. 1854 2 The new routing entries are added starting with the symmetric 1855 neighbors (h=1) as the destination nodes. For each neighbor 1856 tuple in the neighbor set, corresponding to a symmetric link 1857 (i.e. N_LOST_time is expired, N_pending == false and 1858 N_SYM_time is not expired), 1859 a new routing entry is recorded in the routing table where 1860 R_dest is set to the main address N_main_addr of the neighbor, 1861 R_next is set to the interface address N_if_addr of the neigh- 1862 bor interface, R_dist is set to 1, and R_if_id is set to the 1863 value field N_if_id of the entry. If N_if_addr is distinct of 1864 N_main_addr, another new routing entry with R_dest = 1865 N_main_addr, R_next = N_if_addr, R_if_id = N_if_id and R_dist 1866 = 1 is added. 1868 3 The new route entries for the destination nodes h+1 hops away 1869 are recorded in the routing table. The following procedure is 1870 executed for each value of h, starting with h=1 and increment- 1871 ing it by 1 each time. The execution will stop if no new entry 1872 is recorded in an iteration. 1874 3.1 For each topology entry in the topology table, if its 1875 T_dest does not correspond to R_dest of any route entry 1876 in the routing table AND its T_last corresponds to R_dest 1877 of a route entry whose R_dist is equal to h, then a new 1878 route entry is recorded in the routing table (if it does 1879 not already exist) where: 1881 R_dest is set to T_dest; 1883 R_next is set to R_next of the recorded route entry 1884 whose R_dest is equal to T_last 1886 R_dist is set to h+1; and 1888 R_if_id is set to the value of the R_if_id of the 1889 recorded route entry whose R_dest is equal to 1890 T_last. 1892 The routing table is further completed by using the multiple inter- 1893 face association set: 1895 1 For each entry in the multiple interface association where 1896 there exists a routing entry such that: 1898 R_dest == I_main_addr (of the multiple interface inter- 1899 face association entry) 1901 a route entry is created in the routing table with: 1903 R_dest = I_if_addr (of the multiple interface associa- 1904 tion entry) 1906 R_next = R_next (of the recorded route entry) 1908 R_dist = R_dist (of the recorded route entry) 1910 R_if_id = R_if_id (of the recorded route entry). 1912 The routing table is finally completed by using the host and network 1913 association set: 1915 1 For each tuple in the routing set, record an entry in the 1916 routing table, with: 1918 R_dest = NET_addr/NET_mask 1920 R_next = the next hop on the path from the node to 1921 GW_main_addr 1923 R_dist = dist to GW_main_addr 1925 R_next and R_if_id are set to the same values as the 1926 tuple from the routing set with R_dest == GW_main_addr. 1928 3. Node Configuration 1930 3.1. Address Assignment 1932 The nodes in the MANET network SHOULD be assigned addresses within a 1933 defined address sequence. I.e., the nodes in the MANET SHOULD be 1934 addressable through a network address and a netmask. 1936 Likewise, the nodes in each associated network SHOULD be assigned 1937 addresses from a defined address sequence, distinct from that being 1938 used in the MANET. 1940 3.2. Routing Configuration 1942 MANET nodes MUST be configured such that they have a network route 1943 set up on one of the interfaces participating in the MANET. I.e., in 1944 lack of other routing information, any incoming datagrams, destined 1945 for a node in the MANET address sequence, is transmitted onto this 1946 interface (efficiently: incoming data to a MANET node, which the node 1947 cannot find an exact match for, is broadcast to all neighbors) 1949 Any node with associated networks or hosts SHOULD, in addition to the 1950 configuration described above, be configured such that it has routes 1951 set up to the interfaces with associated hosts or network. 1953 3.3. Data Packet Forwarding 1955 OLSR itself does not perform packet forwarding. Rather, it maintains 1956 the routing table in the underlying operating system, which is 1957 assumed to be forwarding packets as specified in RFC1812. 1959 3.4. Control Message Forwarding 1961 Control messages, destined for flooding into the entire network, 1962 SHOULD be relayed by the MPR via the following rule: 1964 A node retransmits a message only when it is received from one 1965 of its MPR selector AND it is not before registered in the 1966 duplicate table AND the time to live is greater than 1 (one). 1968 Before retransmitting, the hop count is incremented by one and the 1969 time to live is decremented by one. 1971 4. IPv6 Considerations 1973 All the operations and parameters described in this document used by 1974 OLSR for IP version 4 are the same as those used by OLSR for IP ver- 1975 sion 6. However, with IP version 6, we only need to replace all the 1976 4 bytes Ipv4 address field in different messages with 16 bytes Ipv6 1977 address format. 1979 5. Proposed Values for the Constants 1981 This section list the values for the constants used in the descrip- 1982 tion of the protocol. 1984 HELLO_INTERVAL = 2 seconds 1986 TC_INTERVAL = 5 seconds 1987 MID_INTERVAL = TC_INTERVAL 1989 HNA_INTERVAL = TC_INTERVAL 1991 NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL 1993 TOP_HOLD_TIME = 3 x TC_INTERVAL 1995 D_TIME = 30 seconds 1997 I_TIME = 3 x MID_INTERVAL 1999 GW_TIME = 3 x HNA_INTERVAL 2001 HELLO_MESSAGE = 1 2003 TC_MESSAGE = 2 2005 MID_MESSAGE = 3 2007 HNA_MESSAGE = 4 2009 ASYM_LINK = 1 2011 SYM_LINK = 2 2013 MPR_LINK = 3 2015 LOST_LINK = 4 2017 HYST_THRESHOLD_HIGH = 0.8 2019 HYST_THRESHOLD_LOW = 0.3 2021 HYST_SCALING = 0.5 2023 MAXJITTER = 0.5 2025 6. Sequence Numbers 2027 Sequence numbers are used in OLSR with the purpose of discarding 2028 "old" information, i.e. messages received out of order. However with 2029 a limited number of bits for representing sequence numbers, wrap- 2030 arounds (that the sequence number is incremented from the maximum 2031 possible value to zero) will occur. To prevent this from interfering 2032 with the operation of the protocol, the following MUST be observed. 2034 The term MAXVALUE designates in the following the largest possible 2035 value for a sequence number. 2037 The sequence number S1 is said to be "greater than" the sequence num- 2038 ber S2 iff: 2040 S1-S2 < MAXVALUE/2 OR 2042 S1 < MAXVALUE/2 AND S2 > S1 + MAXVALUE/2 2044 Thus when comparing two messages, it is possible - even in the pres- 2045 ence of wrap-around - to determine which message contains the most 2046 recent information. 2048 7. Acknowledgments 2049 The authors would like to thank Joseph Macker and his team 2050 for their valuable suggestions on the 2051 advanced neighbor sensing mechanism. 2053 8. References 2055 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia- 2056 bility in cable free radio LANs: Low level forwarding in HIPERLAN. 2057 Wireless Personal Communications, 1996 2059 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient 2060 technique for flooding in mobile wireless networks. INRIA research 2061 report RR-3898, 2000 2063 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 2064 1, functional specifications ETS 300-652, ETSI, June 1996 2066 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net- 2067 work Protocols, INRIA research report RR-3965, 2000 2069 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- 2070 els. Request for Comments (Best Current Practice) 2119, Internet 2071 Engineering Task Force, March 1997.