idnits 2.17.1 draft-ietf-manet-olsr-06.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 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 332: '... OLSR MAY optimize the reactivity to...' RFC 2119 keyword, line 478: '...eason, each node MUST choose one of it...' RFC 2119 keyword, line 480: '..., however a node SHOULD always use the...' RFC 2119 keyword, line 482: '...The main address MUST be used in OLSR ...' RFC 2119 keyword, line 532: '... MUST be set to "000000000000...' (68 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 (1 September 2001) is 8244 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 1554 looks like a reference -- Missing reference section? '2' on line 1226 looks like a reference -- Missing reference section? '3' on line 158 looks like a reference -- Missing reference section? '5' on line 220 looks like a reference -- Missing reference section? '4' on line 310 looks like a reference -- Missing reference section? '0' on line 746 looks like a reference -- Missing reference section? 'MAXJITTER' on line 746 looks like a reference Summary: 6 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: 1 September 2002 Anis Laouiti 5 Pascale Minet 6 Paul Muhlethaler 7 Amir Qayyum 8 Laurent Viennot 9 INRIA Rocquencourt, France 10 1 September 2001 12 Optimized Link State Routing Protocol 14 draft-ietf-manet-olsr-06.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 classical link state algorithm tailored to the requirements of 47 a mobile wireless LAN. The key concept used in the protocol is that 48 of 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 classical flooding mechanism, where every node retransmits each 52 message when it receives the first copy of the message. In OLSR, 53 information flooded in the network "through" these MPRs is also 54 "about" the MPRs. Thus, a second optimization is achieved by 55 minimizing the "contents" of the control messages flooded in the 56 network. Hence, as contrary to the classic link state algorithm, a 57 node declares only a small subset of links to its neighbor nodes, 58 rather than all links to all neighbors. This information is then used 59 by the OLSR protocol for route calculation. As a consequence hereof, 60 routes contain only the MPRs as intermediate nodes from a Source to a 61 Destination. OLSR provides optimal routes (in terms of number of 62 hops). The protocol is particularly suitable for large and dense 63 networks as the technique 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 . . . . . . . . . . . . . . . . . . . . 8 72 1.5. Multipoint Relays . . . . . . . . . . . . . . . . . . . . 9 74 2. Protocol Functioning . . . . . . . . . . . . . . . . . . . . 10 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 . . . . . . . . . 14 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 . . . . . . . . . . . . . . . . . . 21 89 2.2.2.3. MPR Set . . . . . . . . . . . . . . . . . . . . . . . 21 90 2.2.2.4. MPR Selector Set . . . . . . . . . . . . . . . . . . . 21 91 2.2.3. HELLO Message Generation . . . . . . . . . . . . . . . . 22 92 2.2.4. HELLO Message Processing . . . . . . . . . . . . . . . . 23 93 2.2.5. Multipoint Relay Selection . . . . . . . . . . . . . . . 27 94 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes . . . . . 29 95 2.2.6. Advanced Neighbor Sensing Functioning . . . . . . . . . 30 96 2.2.6.1. Link Hysteresis . . . . . . . . . . . . . . . . . . . 31 97 2.2.6.2. Optional Link layer notification . . . . . . . . . . . 32 99 2.3. Topology Discovery . . . . . . . . . . . . . . . . . . . . 33 100 2.3.1. TC Message Format . . . . . . . . . . . . . . . . . . . 33 101 2.3.2. Topology Information Base . . . . . . . . . . . . . . . 34 102 2.3.3. TC Message Generation . . . . . . . . . . . . . . . . . 35 103 2.3.4. TC Message Processing . . . . . . . . . . . . . . . . . 35 104 2.3.5. Multiple Interface Association . . . . . . . . . . . . . 37 105 2.3.5.1. Multiple Interface Association Information Base . . . 37 106 2.3.5.2. MID Message Format . . . . . . . . . . . . . . . . . . 37 107 2.3.5.3. MID Message Generation . . . . . . . . . . . . . . . . 38 108 2.3.5.4. MID Message Processing . . . . . . . . . . . . . . . . 39 109 2.3.6. Associated Networks and Hosts . . . . . . . . . . . . . 40 110 2.3.6.1. HNA Message Format . . . . . . . . . . . . . . . . . . 41 111 2.3.6.2. Host and Network Association Information Base . . . . 41 112 2.3.6.3. HNA Message Generation . . . . . . . . . . . . . . . . 42 113 2.3.6.4. HNA Message Processing . . . . . . . . . . . . . . . . 42 114 2.3.7. Routing Table Calculation . . . . . . . . . . . . . . . 43 115 2.3.8. Advanced Topology Discovery Functioning . . . . . . . . 46 116 2.3.8.1. Reaction to Link Failure with a MPR Selector . . . . . 46 117 2.3.8.2. Advanced Fast Re-routing Mechanism . . . . . . . . . . 47 118 2.3.8.2.1. FRR Message Format . . . . . . . . . . . . . . . . . 48 119 2.3.8.2.2. FRR Message Generation . . . . . . . . . . . . . . . 48 120 2.3.8.2.3. FRR Message Processing . . . . . . . . . . . . . . . 49 122 3. Node Configuration . . . . . . . . . . . . . . . . . . . . . 49 123 3.1. Address Assignment . . . . . . . . . . . . . . . . . . . . 49 124 3.2. Routing Configuration . . . . . . . . . . . . . . . . . . 50 125 3.3. Data Packet Forwarding . . . . . . . . . . . . . . . . . . 50 127 4. IPv6 Considerations . . . . . . . . . . . . . . . . . . . . 50 128 5. Proposed Values for the Constants . . . . . . . . . . . . . 50 129 6. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . 51 130 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 52 131 8. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 52 133 1. Introduction 135 The Optimized Link State Routing Protocol (OLSR) is developed for 136 mobile ad hoc networks. It operates as a table driven, proactive pro- 137 tocol. I.e., exchanges topology information with other nodes of the 138 network regularly. Each node selects a set of its neighbor nodes as 139 "multipoint relays". These nodes which have been selected as a multi- 140 point relay by some neighbor nodes announce this information periodi- 141 cally in their control messages. Thereby, a node announces to the 142 network, that it has reachability to the nodes which have selected it 143 as MPR. In route calculation, the MPRs are used to form the route 144 from a given node to any destination in the network. Furthermore, the 145 protocol uses the MPRs to facilitate efficient flooding of control 146 messages in the network. 148 A node selects MPRs from among its one hop neighbors with "symmetri- 149 cal", i.e. bi-directional, linkages. Therefore, selecting the route 150 through MPRs automatically avoids the problems associated with data 151 packet transfer over uni-directional links (such as the problem of 152 not getting link-layer acknowledgments for data packets at each hop) 154 OLSR is developed to work independently from other protocols. Like- 155 wise, OLSR makes no assumptions about the underlying link-layer. 157 OLSR inherits the concept of forwarding and relaying from HIPERLAN (a 158 MAC layer protocol) which is standardized by ETSI [3]. The protocol 159 is developed in the IPANEMA project (part of the Euclid program) and 160 in the PRIMA project (part of the RNRT program). 162 1.1. Changes 164 Major changes from version 05 to version 06 166 - Clarification of the usage of link layer notification and fast 167 rerouting 169 - Clarification of MPR selection 171 - Clarification of multiple interfaces 173 Major changes from version 04 to version 05 175 - Introduction of support for multiple interfaces 176 - Introduction of support for associated hosts and networks. 178 - Introduction of support for advanced neighbor sensing through 179 hysteresis. 181 - Modularity between neighbor sensing and topology discovery 182 emphasized. 184 Major changes from version 03 to version 04 186 - Finalized the generic packet/message format to include fea- 187 tures for scope-limited (diameter-bound) flooding of messages 188 and to handle duplicate messages. 190 - Editorial changes towards language consistency. 192 Major changes from version 02 to version 03 194 - Introduction of assigned port number for use with OLSR. 196 - The packet format now uses "message length" rather than an 197 offset to the next message. 199 - Optional section describing how link-layer notifications can 200 be utilized included. 202 Major changes from version 01 to version 02 204 - Introduction of a unified packet format for encapsulation of 205 all messages being exchanged between nodes. This also serves 206 to facilitate extensions in future versions of the protocol 207 (i.e. introduction of new protocol messages) without breaking 208 backwards compatibility. 210 - Removal of "Power Conservation" from this draft. Power Conser- 211 vation may be considered as an extension to the basic routing 212 capabilities. 214 1.2. OLSR Terminology 216 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 217 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 218 document are to be interpreted as described in RFC2119 [5]. The OLSR 219 protocol uses the following terminology: 221 multipoint relay (MPR) 222 A node which is selected by its one-hop neighbor, node X, to 223 "re-transmit" all the broadcast messages that it receives from 224 X, provided that the same message is not already received, and 225 the time to live field of the message is greater than one. 227 multipoint relay selector (MPR selector, MS) 229 A node which has selected its one-hop neighbor, node X, as its 230 multipoint relay, will be called a multipoint relay selector 231 of node X. 233 node 235 A MANET router which implements this Optimized Link State 236 Routing protocol. 238 interface 240 A network device participating in the MANET (usually a wire- 241 less device). A node may have several interfaces, each inter- 242 face assigned an unique IP address. 244 link 246 A link is a pair of interfaces (from two different nodes) sus- 247 ceptible to hear one another (i.e. one may be able to receive 248 traffic from the other). A node is said to have a link to 249 another node when one of its interface has a link to one of 250 the interfaces of the other node. 252 neighbor interface 254 An interface I is a neighbor interface of an interface J if J 255 can hear I (i.e. it is possible to send traffic from I to J). 257 sender interface 259 The sender interface of a control message is the neighbor 260 interface over which the message has been transmitted. 262 receiver interface 264 The receiver interface of a control message is the (local) 265 interface, over which a control message has been received. 267 neighbor node 268 A node X is a neighbor node of node Y if node Y can hear node 269 X (i.e. one of X interfaces is a neighbor interface of some 270 interface of Y). 272 2-hop interface 274 An interface heard by a neighbor. 276 symmetric link 278 A bi-directional link between two interfaces, i.e. interface I 279 and interface J where both can hear each other. 281 symmetric neighborhood 282 The symmetric neighborhood of any node X is the set of nodes 283 which have at least one symmetric link to X. 285 symmetric 2-hop neighborhood 286 The symmetric 2-hop neighborhood of X is the set of nodes 287 which don't have a symmetric link to X but have a symmetric 288 link to the symmetric neighborhood of X. 290 main address 292 The main address of a node, which will be used in OLSR control 293 traffic as the "originator address" of all messages emitted by 294 this node. It is the address of one of its interfaces. 296 1.3. Applicability Section 298 OLSR is a proactive routing protocol for mobile ad-hoc networks 299 (MANETs). It is well suited to large and dense mobile networks, as 300 the optimization achieved using the MPRs works well in this context. 301 The larger and more dense a network, the more optimization can be 302 achieved as compared to the classic link state algorithm. OLSR uses 303 hop-by-hop routing, i.e. each node uses its local information to 304 route packets. 306 OLSR is well suited for networks, where the traffic is random and 307 sporadic between "several" nodes rather than being almost exclusively 308 between a small specific set of nodes. The performance of the proto- 309 col, compared to a reactive protocol, is even better if these 310 [source, destination] pairs change over time [4]. Such changes may 311 initiate substantial traffic (query flooding) in case of a reactive 312 protocol, but no additional traffic in OLSR, as the routes are main- 313 tained for each known destination all the time. 315 1.4. Protocol Overview 317 OLSR is a proactive routing protocol for mobile ad hoc networks. The 318 protocol inherits the stability of a link state algorithm and has the 319 advantage of having routes immediately available when needed due to 320 its proactive nature. OLSR is an optimization over the classical link 321 state protocol, tailored for mobile ad hoc networks. 323 First, it reduces the size of the control messages: rather than 324 declaring all links, a node declares only a subset of links with its 325 neighbors, namely the links to those nodes which are its MPR selec- 326 tors. Second, OLSR minimizes the overhead from flooding of control 327 traffic by using only selected nodes, called MPRs, to retransmit con- 328 trol messages. This technique significantly reduces the number of 329 retransmissions required to flood a message to all nodes in the net- 330 work. 332 OLSR MAY optimize the reactivity to topological changes by reducing 333 the maximum time interval for periodic control message transmission. 334 Furthermore, as OLSR continuously maintains routes to all destina- 335 tions in the network, the protocol is beneficial for traffic patterns 336 where a large subset of nodes are communicating with another large 337 subset of nodes, and where the [source, destination] pairs are chang- 338 ing over time. The protocol is particularly suited for large and 339 dense networks, as the optimization done using MPRs works well in 340 this context. The larger and more dense a network, the more optimiza- 341 tion can be achieved as compared to the classic link state algorithm. 343 OLSR is designed to work in a completely distributed manner and does 344 thus not depend on any central entity. The protocol does NOT REQUIRE 345 reliable transmission of control messages: each node sends control 346 messages periodically, and can therefore sustain an occasional loss 347 of some such messages. Such losses occur frequently in radio networks 348 due to collisions or other transmission problems. 350 Also, OLSR does not require sequenced delivery of messages. Each con- 351 trol message contains a sequence number which is incremented for each 352 message. Thus the recipient of a control message can, if required, 353 easily identify which information is newer - even if messages have 354 been re-ordered while in transmission. 356 Furthermore, OLSR provides support for protocol extensions such as 357 sleep mode operation, multicast-routing etc. Such extensions may be 358 introduced as additions to the protocol without breaking backwards 359 compatibility with earlier versions. 361 OLSR does not require any changes to the format of IP packets. Thus 362 any existing IP stack can be used as is: the protocol only interacts 363 with routing table management. 365 1.5. Multipoint Relays 367 The idea of multipoint relays is to minimize the overhead of flooding 368 messages in the network by reducing duplicate retransmissions in the 369 same region. Each node in the network selects a set of nodes in its 370 symmetric neighborhood which may retransmit its messages. This set of 371 selected neighbor nodes is called the "Multipoint Relay" (MPR) set of 372 that node. The neighbors of node N which are *NOT* in its MPR set, 373 receive and process broadcast messages but do not retransmit broad- 374 cast messages received from node N. 376 Each node selects its MPR set among its one hop symmetric neighbors. 377 This set is selected such that it covers (in terms of radio range) 378 all nodes that are two hops away. The MPR set of N, denoted as 379 MPR(N), is then an arbitrary subset of the symmetric neighborhood of 380 N which satisfies the following condition: every node in the symmet- 381 ric 2-hop neighborhood of N must have a symmetric link towards 382 MPR(N). The smaller the MPR set is, the more optimal is the routing 383 protocol. [2] gives an analysis and example of MPR selection algo- 384 rithms. 386 Each node maintains information about the set of neighbors that have 387 selected it as MPR. This set is called the "Multipoint Relay Selector 388 set" (MPR selector set) of a node. A node obtains this information 389 from periodic HELLO messages received from the neighbors. 391 A broadcast message, intended to be diffused in the whole network, 392 coming from any of the MPR selectors of node N is assumed to be 393 retransmitted by node N. This set can change over time (i.e. when a 394 node selects another MPR-set) and is indicated by the selector nodes 395 in their HELLO messages. Each node has a specific "Multipoint relay 396 Selector Sequence Number" (MSSN) associated with this set. Whenever 397 the MPR selector set is updated, the node also increments its MSSN. 399 OLSR relies on selection of MPRs, and calculates routes through these 400 nodes. I.e., the path is made of links between MPR and MPR selector. 401 To enable this, each node in the network periodically floods informa- 402 tion describing which neighbors have selected it as a MPR. Upon 403 receipt of this "MPR Selector" information, each node calculates or 404 updates the route to each known destination. So principally, the 405 route is a sequence of hops through the MPRs from source to the des- 406 tination. 408 A nodes MPRs are selected among its symmetric neighborhood. 410 Therefore, selecting the route through MPRs automatically avoids the 411 problems associated with data packet transfer over uni-directional 412 links such as the problem of not getting a link layer acknowledgment 413 for the data packets at each hop. 415 2. Protocol Functioning 417 This section describes the details of the protocol functioning. This 418 includes descriptions of the format and contents of the packets being 419 exchanged by routers and the algorithms (e.g. for packet handling and 420 routing table calculation). 422 The "Packet Forwarding" and "Neighbor Sensing" mechanisms may be seen 423 as a transfer layer for the routing protocol. This provides nodes 424 with information about their neighbors and offers an optimized mecha- 425 nism for flooding messages through the concept of MPRs. It completely 426 relies on the exchange of HELLO messages. 428 The "Topology Discovery" mechanism relies on the "Packet Forwarding" 429 and "Neighbor Sensing" mechanisms. A node uses neighbor and MPR 430 information from the "Neighbor Sensing" mechanism in diffusing local 431 topology information to the larger network. Topology information is 432 diffused through the "Packet Forwarding" mechanism, and relies on TC, 433 MID and HNA messages. Resulting from the "Topology Discovery" mecha- 434 nism is information which allows routing table calculation. 436 The key notion for these mechanisms is the MPR relationship. 438 2.1. Packet Format and Forwarding 440 OLSR communicates using a unified packet format for all data related 441 to the protocol. The purpose of this is to facilitate extensibility 442 of the protocol without breaking backwards compatibility. Also, this 443 provides an easy way of piggybacking different "types" of information 444 into a single transmission, and thus for a given implementation to 445 optimize towards utilizing the maximal frame-size, provided by the 446 network. These packets are embedded in UDP datagrams for transmission 447 over the network. The present draft is presented with IPv4 addresses. 448 Considerations regarding IPv6 are given in section 4. 450 Each packet encapsulates one or more messages. The messages share a 451 common header format, which enables nodes to correctly accept and (if 452 applicable) retransmit messages of an unknown type. 454 Messages can be flooded onto the entire network, or flooding can be 455 limited to nodes within a diameter (in terms of number of hops) from 456 the originator of the message. Thus transmitting a message to the 457 neighborhood of a node is just a special case of flooding. When 458 flooding any control message, duplicate retransmissions will be elim- 459 inated locally (i.e. each node maintains a duplicate table to prevent 460 transmitting the same message twice) and minimized in the entire net- 461 work through the usage of MPRs as described in later sections. 463 Furthermore, a node can examine the header of a message to obtain 464 information on the distance (in terms of number of hops) to the orig- 465 inator of the message. This feature may be useful in situations 466 where, e.g., the time information from a received control messages 467 stored in a node depends on the distance to the originator. 469 2.1.1. Protocol and Port Number 471 Packets in OLSR are communicated using UDP. Port 698 has been 472 assigned by IANA for exclusive usage by the OLSR protocol. 474 2.1.2. Multiple Interfaces and Main Address 476 A node may have several wireless interfaces, each of them having a 477 distinct IP address. OLSR supports such nodes with multiple inter- 478 faces. For this reason, each node MUST choose one of its interface 479 addresses as its "main address". It is of no importance which address 480 is chosen, however a node SHOULD always use the same address as its 481 main address. For example, the smallest interface address may be cho- 482 sen as the main interface. The main address MUST be used in OLSR con- 483 trol traffic as the "originator address" of all messages emitted by a 484 node. 486 A node must transmit and retransmit all control messages on all 487 interfaces. The source address in the IP header must contain the IP- 488 address of the interface where the message is transmitted. This 489 address will be denoted the "sender interface address". 491 2.1.3. Packet Format 493 The basic layout of any packet in OLSR is as follows (omitting the IP 494 and UDP headers): 496 0 1 2 3 497 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 498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 499 | Packet Length | Reserved | 500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 501 | Message Type | Reserved | Message Size | 502 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 503 | Originator Address | 504 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 505 | Time To Live | Hop Count | Message Sequence Number | 506 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 507 | | 508 : MESSAGE : 509 | | 510 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 511 | Message Type | Reserved | Message Size | 512 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 513 | Originator Address | 514 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 515 | Time To Live | Hop Count | Message Sequence Number | 516 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 517 | | 518 : MESSAGE : 519 | | 520 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 521 : : 522 (etc) 524 2.1.3.1. Packet Header 526 Packet Length 528 The length (in bytes) of the packet 530 Reserved 532 MUST be set to "0000000000000000" to be in compliance with 533 this version of the draft. 535 The sender information for a packet is obtainable from the UDP 536 header. 538 2.1.3.2. Message Header 540 Message Type 541 This field indicates which type of message is to be found in 542 the "MESSAGE" partition. Message types in the range of 0-127 543 are reserved for messages in this draft and in extension 544 drafts. 546 Reserved 548 MUST be set to "00000000" to be in compliance with this ver- 549 sion of the draft. 551 Message Size 553 This field gives the size of this message, counted in bytes 554 and measured from the beginning of the "Message Type" field 555 and until the beginning of the next "Message Type" field (or - 556 if there are no following messages - until the end of the 557 packet). 559 Originator Address 561 This field contains the main address of the node, which has 562 originally generated this message. This field SHOULD NOT be 563 confused with the source address from the UDP header, which is 564 changed each time to the address of the intermediate interface 565 which is re-transmitting this message. The Originator Address 566 field MUST *NEVER* be changed in retransmissions. 568 Time To Live 570 This field contains the maximum number of hops a message will 571 be transmitted. Before a message is retransmitted, the Time To 572 Live MUST be decremented by 1. When a node receives a message 573 with a Time To Live equal to 0 or 1, the message MUST NOT be 574 retransmitted under any circumstances. Normally, a node would 575 not receive a message with a TTL of zero. 577 Thus, by setting this field, the originator of a message can 578 limit the flooding radius. 580 Hop Count 582 This field contains the number of hops a message has attained. 583 Before a message is retransmitted, the Hop Count MUST be 584 incremented by 1. 586 Initially, this is set to '0' by the originator of the mes- 587 sage. 589 Message Sequence Number 591 While generating a message, the "originator" node will assign 592 a unique identification number to each message. This number is 593 inserted into the Sequence Number field of the message. The 594 sequence number is increased by 1 (one) for each message orig- 595 inating from the node - "wrap-arounds" are handled as 596 described in a later section. Message sequence numbers are 597 used to ensure that a given message is not retransmitted more 598 than once by any node. 600 2.1.4. Packet Processing and Message Flooding 602 Upon receiving a basic packet, the protocol parser examines each of 603 the "message headers". Based on the value of the "Message Type" 604 field, the parser can determine the fate of the message. A node may 605 receive the same message several times. Thus, to avoid re-processing 606 of a message which was already received and processed, each node 607 maintains a Duplicate table. In this table, the node records informa- 608 tion about the most recently received messages where the above condi- 609 tion holds. For each message, satisfying the above condition, a node 610 records a "Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr 611 is the originator address of the message, D_seq_num is the message 612 sequence number of the message and D_time specifies the time at which 613 a tuple expires and *MUST* be removed. 615 In a node, the set of Duplicate Tuples are denoted the "Duplicate 616 set". 618 In this section, the term "Originator Address" will be used for the 619 main address of the node which sent the message. The term "Sender 620 Interface Address" will be used for the sender address (given in the 621 IP header of the packet containing the message) of the interface 622 which sent the message. 624 Thus, upon receiving a basic packet, a node performs the following 625 tasks for each encapsulated message: 627 1 If the time to live of the message is less than or equal to 628 '0' (zero), the message MUST silently be dropped. 630 2 If there exists a tuple in the duplicate set, where: 632 D_addr == Originator Address, AND 633 D_seq_num == Message Sequence Number 635 then the message has already been completely processed and 636 MUST silently be ignored. 638 3 Otherwise, if the node implements the Message Type of the mes- 639 sage, the message MUST be processed according to the specifi- 640 cations for the message type. 642 4 Otherwise, if the node does not implement the Message Type of 643 the message the message SHOULD be processed according to the 644 following algorithm: 646 4.1 If the sender interface address of the message is not 647 detected to be in the symmetric neighborhood of the node, 648 the message MUST silently be dropped. 650 4.2 If the sender interface address of the message is 651 detected to be in the symmetric neighborhood of the node, 652 an entry in the duplicate set is recorded with: 654 D_addr = originator address 656 D_seq_num = Message Sequence Number 658 D_time = current time + D_HOLD_TIME. 660 4.3 If the sender interface address is an interface address 661 of a MPR selector of this node and if the time to live of 662 the message is greater than '1', the message MUST be for- 663 warded according to the following: 665 4.3.1 666 The TTL of the message is reduced by one. 668 4.3.2 669 The hop-count of the message is increased by one 671 4.3.3 672 The message is broadcasted on all interfaces 673 (Notice: The remaining fields of the message header 674 SHOULD be left unmodified.) 676 Notice: known message types are *not* forwarded "blindly" by this 677 algorithm. Forwarding (and setting the correct message header in the 678 forwarded, known, message) is the responsibility of the algorithm 679 specifying how the message is to be handled. This enables, e.g., a 680 message type to be specified such that the message can be modified 681 while in transit (e.g. to reflect the route the message has taken). 682 Further, it enables that the optimization through the MPRs can be 683 bypassed: if for some reason classical flooding of a message type is 684 required (e.g. to transmit control information over unidirectional 685 links), the algorithm which specifies how such messages should be 686 handled will simply rebroadcast the message, regardless of MPRs. 688 By defining a set of message types, which MUST be recognized by all 689 implementations of OLSR, it will be possible to extend the protocol 690 through introduction of additional message types, while still be able 691 to maintain compatibility with older implementations. The REQUIRED 692 message types for OLSR are: 694 - HELLO-messages, performing the task of neighbor sensing. 696 - TC-messages, performing the task of MPR information declara- 697 tion (OLSR topology declaration). 699 - MID-messages, performing the task of multiple interface decla- 700 ration. 702 - HNA-messages, performing the task of associated host and/or 703 network declaration. 705 - FRR-messages, performing the task of initiating fast rerouting 706 in case of link failure. 708 Extensions may for example be messages enabling power conservation / 709 sleep mode, multicast routing, support for unidirectional links, 710 auto-configuration/address assignment etc. 712 2.1.5. Message Emission and Jitter 714 As a basic implementation requirement, synchronization of control 715 messages SHOULD be avoided. As a consequence, periodic OLSR messages 716 SHOULD be emitted such that they avoid synchronization. 718 Emission of control traffic from neighboring nodes may, for various 719 reasons (mainly timer interactions with packet processing), become 720 synchronized such that several neighbor nodes attempt to transmit 721 control traffic simultaneously. Depending on the nature of the under- 722 lying link-layer, this may or may not lead to collisions and hence 723 message loss - possibly loss of several subsequent messages of the 724 same type. 726 To avoid such synchronizations, the following simple strategy for 727 emitting control messages is proposed. A node MAY add an amount of 728 jitter to the interval at which messages are generated. The jitter 729 must be a random value for each message generated. Thus, for a node 730 utilizing jitter: 732 Actual message interval = MESSAGE_INTERVAL - jitter 734 Where jitter is a value, randomly selected from the interval 735 [0,MAXJITTER] and MESSAGE_INTERVAL is the value of the message inter- 736 val specified for the message being emitted (e.g. HELLO_INTERVAL for 737 HELLO messages, TC_INTERVAL for TC-messages etc.). 739 Jitter MAY also be introduced when forwarding messages. The follow- 740 ing simple strategy may be adopted: when a message is to be forwarded 741 by a node, it should be kept in the node during a short period of 742 time : 744 Keep message period = jitter 746 Where jitter is a random value in [0,MAXJITTER]. 748 Notice that when the node sends a control message, the opportunity to 749 piggyback other messages (before their keeping period is expired) may 750 be taken to reduce the number of packet transmissions. 752 It should be noticed that the present draft imposes a minimal rate of 753 control message emission. However a node MAY send control messages at 754 a higher rate (e.g. for better reacting to high mobility). Tuning the 755 rate of control traffic to the actual conditions under which the pro- 756 tocol is to operate is an implementation issue. 758 2.2. Neighbor Sensing 760 Each node should detect the neighbor interfaces with which it has a 761 direct and symmetric link. Uncertainties over radio propagation may 762 make some links unidirectional. Consequently, all links MUST be 763 checked in both directions in order to be considered valid. 765 To perform neighbor detection, each node broadcasts HELLO messages, 766 containing information about heard neighbor interfaces and their link 767 status. The link status may either be "symmetric", "heard" (asymmet- 768 ric), "MPR" or "lost". "Symmetric" indicates, that the link has been 769 verified to be bi-directional, i.e. it is possible to transmit data 770 in both directions. "Heard" indicates that the node can hear HELLO 771 messages from a neighbor interface, but it is not confirmed that this 772 neighbor interface is also able to receive messages from the node. 773 MPR indicates that the sender has selected the node as MPR. A status 774 of MPR further implies that the link is symmetric. "Lost" indicates 775 that the link with this neighbor interface is now lost. 777 HELLO messages are broadcasted to all one-hop neighbors and are emit- 778 ted on each MANET interface of the node. They are *not relayed* to 779 further nodes. 781 More precisely, a HELLO message contains for each interface I: 783 - a list of neighbor interface addresses, having a symmetric 784 link to interface I; 786 - a list of neighbor interface addresses, which are "heard" by 787 interface I (for historical reasons, the term "asymmetric" is 788 used for "heard"); 790 - a list of neighbor interface addresses of neighbors selected 791 as MPRs, AND having a symmetric link to interface I; 793 - a list of neighbor interface addresses, which have been lost. 795 These lists are computed as described in the HELLO message generation 796 section. 798 2.2.1. HELLO Message Format 800 To accommodate the above requirements, as well as to accommodate for 801 future extensions, an approach similar to the overall packet format 802 is taken. Thus the proposed format of a HELLO message is: 804 0 1 2 3 805 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 807 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 808 | Reserved | # Interfaces | 809 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 810 | Interface Address | 811 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 812 | Interface Address | 813 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 814 : . . . : 815 : : 816 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 817 | Link Type | Interface # | Link Message Size | 818 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 819 | Neighbor Interface Address | 820 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 821 | Neighbor Interface Address | 822 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 823 : . . . : 824 : : 825 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 826 | Link Type | Interface # | Link Message Size | 827 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 828 | Neighbor Interface Address | 829 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 830 | Neighbor Interface Address | 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 : : 833 : : 834 (etc) 836 This is sent as the data-portion of the general packet format 837 described in the Packet Format and Forwarding section, with the "Mes- 838 sage Type" set to HELLO_MESSAGE and the TTL field set to 1 (one). 840 Reserved 842 This field is reserved for future usage, and MUST be set to 843 "000000000000000000000000" for compliance with this draft. 845 # Interfaces 847 This field indicates the number of additional MANET interfaces 848 (excluding the main interface) possessed by the node. If the 849 node has only one interface, this number is 0. 851 Interface Address 853 This field indicates the addresses of additional MANET inter- 854 faces. The first one will be referenced as interface address 855 number 1, the second as interface address number 2, and so on. 856 The main address of the node (whose address is given in the 857 originator field of the message header) will be referenced as 858 interface address number 0. 860 Link Message Size 861 The size of the link message, counted in bytes and measured 862 from the beginning of the "Link Type" field and until the next 863 "Link Type" field (or - if there are no more link types - the 864 end of the message). 866 Link Type 868 This field specifies the type of the link between the inter- 869 face of the sender, as identified by the interface number, and 870 the following list of neighbor interfaces. As a minimum, the 871 following four link types are REQUIRED by OLSR: 873 - ASYM_LINK - indicating that the links are asymmetric 874 (i.e. the neighbor interface is "heard"). 876 - SYM_LINK - indicating that the links are symmetric. 878 - MPR_LINK - indicating, that the links are symmetric AND 879 that the neighbors have been selected as MPR by the 880 sender. 882 - LOST_LINK - indicating that the links have been lost. 884 Interface # 886 This field indicates the number of the interface to which the 887 following list of neighbor interfaces corresponds. Number 0 888 indicates the main interface (whose address is the main 889 address). 891 Neighbor Interface Address 893 An address of a neighbor interface. 895 Neighbor sensing is performed using HELLO message exchange, updating 896 the neighbor sensing information base in each node. 898 2.2.2. Neighbor Sensing Information Base 900 The neighbor sensing information base stores information about neigh- 901 bor interfaces, 2-hop neighbors, MPRs and MPR selectors. 903 2.2.2.1. Neighbor Set 905 For each of its interface I and for each neighbor interface NI, heard 906 by I, a node records a "Neighbor Tuple" (N_if_id, N_if_addr, 907 N_main_addr, N_SYM_time, N_ASYM_time, N_time) where N_if_id is the 908 identifier number of the local interface I, N_if_addr is the address 909 of the neighbor interface NI, N_main_addr is the main address of the 910 neighbor possessing NI, N_SYM_time is the time until which the link 911 is considered symmetric, N_ASYM_time is the time until which the 912 neighbor interface is considered heard, and N_time specifies the time 913 at which this record expires and *MUST* be removed. When N_SYM_time 914 and N_ASYM_time are expired, the link is considered lost. 916 This information is used when declaring the neighbor interfaces in 917 the HELLO messages. 919 N_SYM_time and N_ASYM_time are used to decide the Link Type declared 920 for the neighbor interface. If N_SYM_time is not expired, the link is 921 declared symmetric. If N_SYM_time is expired but N_ASYM_time is not, 922 the link is declared heard. If both N_SYM_time and N_ASYM_time are 923 expired, the link is declared lost. 925 In a node, the set of Neighbor Tuples are denoted the "Neighbor Set". 927 2.2.2.2. 2-hop Neighbor Set 929 A node records a set of "2-hop tuples" (N_main_addr, N_if_addr, 930 N_2hop_addr, N_time), describing symmetric or MPR links between its 931 neighbors and the symmetric 2-hop neighborhood. N_main_addr and 932 N_if_addr are the main address and an interface address of a neigh- 933 bor, N_2hop_addr is an interface address of a 2-hop neighbor with a 934 symmetric or MPR link to interface N_if_addr and N_time specifies the 935 time at which the tuple expires and *MUST* be removed. 937 This information is gathered from the HELLO messages received by a 938 node from its neighbor nodes. 940 In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor 941 Set". 943 2.2.2.3. MPR Set 945 A node maintains a set of neighbors which are selected as MPR. Their 946 main addresses are listed in the so-called MPR Set. The Multipoint 947 relay selection section describes how MPRs are selected. 949 2.2.2.4. MPR Selector Set 951 A node maintains information (obtained from the HELLO messages) about 952 the neighbors which have selected this node as a MPR. 954 Thus, a node records an MPR-selector tuple (MS_if_addr, MS_main_addr, 955 MS_time), for interfaces of a neighbor which has selected the node as 956 MPR. MS_if_addr is the address of an interface of a node which has 957 selected the node as MPR for that interface, MS_main_addr is the main 958 address of the MPR selector and MS_time specifies the time at which a 959 tuple expires and *MUST* be removed. 961 In a node, the set of MPR-selector tuples are denoted the "MPR Selec- 962 tor Set". A sequence number, MSSN, is associated with this set. When- 963 ever a tuple is added to or removed from this set, the MSSN is incre- 964 mented by 1. 966 2.2.3. HELLO Message Generation 968 The lists of addresses declared in a HELLO message are computed from 969 the Neighbor Set as follows: 971 - for each tuple where: 973 N_SYM_time < current time (expired) AND 974 N_ASYM_time = current time (not expired) 983 N_if_addr is declared with MPR_LINK Link Type if N_main_addr 984 is in the MPR set and SYM_LINK Link Type otherwise; 986 - for each tuple where: 988 N_SYM_time < current time (expired) AND 989 N_ASYM_time >= current time (not expired), 991 N_if_addr is declared with ASYM_LINK Link Type. 993 The list of neighbor interfaces in a HELLO message can be partial 994 (e.g. due to message size limitations, imposed by the network), the 995 rule being the following: for each interface a neighbor interface is 996 heard on, its address is cited with corresponding interface id at 997 least once within a predetermined refreshing period, REFRESH_INTER- 998 VAL. To keep track of fast connectivity change a HELLO message must 999 be sent at least every HELLO_INTERVAL period, smaller than or equal 1000 to REFRESH_INTERVAL. 1002 Notice that for limiting the impact from loss of control messages, it 1003 is desirable that a message (plus the generic package header) can fit 1004 into a single MAC frame. 1006 Each HELLO message generated is broadcasted on each MANET interface 1007 of the node. 1009 2.2.4. HELLO Message Processing 1011 In this section, the terms "Originator Address", "Sender Interface", 1012 "Receiver Interface", and "Link Interface" are used. They are defined 1013 bellow and illustrated in the following figure: 1015 ______________ _____________ 1016 | J1 |= -- = |I1 | 1017 | Main -> J2 |= | = |I2 <- Main | 1018 | J3 |= -- = |I3 | 1019 -------------- | ------------- 1020 | 1021 ______________ | 1022 | K1 |= 1023 | Main -> K2 |= 1024 -------------- 1026 J1, J2 and J3 are the addresses of local interfaces on node J. Like- 1027 wise, I1, I2 and I3 are addresses of local interfaces on node I and 1028 K1 and K2 are addresses of local interfaces on node K. There are sym- 1029 metric links between J1 and I3 and between J3 and K1. 1031 The three nodes have selected, respectively, J2, I2 and K2 as their 1032 "main addresses". I.e. the Originator Address of all OLSR-messages 1033 sent by node J will have the Originator Address J2 (and likewise for 1034 node I and K). 1036 A HELLO message, sent by node J, is transmitted on all node J's 1037 interfaces. Recieved by node I, the following naming conventions 1038 apply: 1040 - The term "Originator Address" is the main address of the node, 1041 originating a message. In the example above, the Originator 1042 Address of the HELLO is J2. 1044 - The term "Sender Interface" for the HELLO message is the 1045 interface over which the HELLO was transmitted. In the example 1046 above, the Sender Interface Address is J1. 1048 - The term "Receiver Interface" will be used for the interface 1049 which received the HELLO message. In the example above, node 1050 I's "Receiver Interface" for the HELLO generated by node J is 1051 I3. 1053 - The term "Link Interface" will be used to in a HELLO message 1054 to designate on which interface (of the sender of a HELLO mes- 1055 sage) a neighbor is detected. In the example above, K1 is 1056 listed in the HELLO message of J with Link Interface J3. The 1057 "Link Interface" is calculated based on the Interface # in the 1058 HELLO message). Notice that an interface address may be listed 1059 several times with different Link Interfaces. 1061 Upon receiving a HELLO message, the node SHOULD update the neighbor 1062 information corresponding to the sender node address (a node may - 1063 e.g. for security reasons - wish to restrict updating the neighbor- 1064 table, i.e. ignoring HELLO messages from some nodes). 1066 The Neighbor Set should be updated as follows: 1068 1 Upon receiving a HELLO message, if there exists no neighbor 1069 tuple with 1071 N_if_addr == Sender Interface Address 1073 and 1075 N_if_id == identifier of the Receiver Interface, 1077 a new tuple is created with 1079 N_if_addr = Sender Interface Address 1081 N_if_id = identifier of the Receiver Interface 1083 N_SYM_time = current time - 1 (expired) 1085 N_time = current time + NEIGHB_HOLD_TIME 1087 2 The tuple is then modified as follows: 1089 2.1 N_main_addr = Originator Address. 1091 2.3 N_time = max (N_time, current time + 1092 NEIGHB_HOLD_TIME); 1094 2.4 N_ASYM_time = current time + NEIGHB_HOLD_TIME; 1096 2.5 if the node finds the Receiver Interface Address among 1097 the addresses listed in the HELLO with: 1099 Link Interface Address == Sender Interface Address, 1101 then, the tuple is modified as follows: 1103 if Link Type == LOST_LINK then 1105 N_SYM_time = current time - 1 (expired) 1107 else: 1109 N_SYM_time = current time + NEIGHB_HOLD_TIME, 1111 N_time = current time + 2 * 1112 NEIGHB_HOLD_TIME. 1114 The rule for setting N_time is the following: a link loosing its sym- 1115 metry should still be advertised at least NEIGHB_HOLD_TIME. This 1116 allows neighbors to detect the link breakage. 1118 The 2-hop Neighbor Set is updated as follows: 1120 1 for each 2-hop interface address listed in the HELLO message 1121 with Link Type SYM_LINK or MPR_LINK, a 2-hop tuple is created 1122 with: 1124 N_main_addr = Originator Address; 1126 N_if_addr = Link Interface Address corresponding to the 1127 2-hop interface address; 1129 N_2hop_addr = the interface address of the 2-hop neigh- 1130 bor; 1132 N_time = current time + 2HOP_HOLD_TIME. 1134 This tuple may replace an older similar tuple with same 1135 N_if_addr and N_2hop_addr values. 1137 2 For each 2-hop interface address listed in the HELLO message 1138 with Link Type LOST_LINK or ASYM_LINK, all the 2-hop tuples 1139 where: 1141 N_if_addr == Link Interface Address corresponding to the 1142 2-hop interface address, 1144 and 1146 N_2hop_addr == the 2-hop interface address 1148 are deleted. 1150 Based on the information obtained from the HELLO messages, each node 1151 constructs its MPR selector set. 1153 Thus, upon receiving a HELLO message, if a node finds one of its 1154 interface addresses in a list with a link type of "MPR", it MUST 1155 update the MPR selector set to contain updated information about the 1156 sender of the HELLO message: 1158 1 If there exists no MPR selector tuple with: 1160 MS_if_addr == Link Interface Address 1162 and 1164 MS_main_addr == Originator Address 1166 then MSSN is incremented to indicate that the MPR selector 1167 table is going to change. 1169 2 If there exists no MPR selector tuple with: 1171 MS_if_addr == Link Interface Address 1173 then a new tuple is created with: 1175 MS_if_addr = Link Interface Address 1177 3 The tuple is then modified as follows: 1179 MS_main_addr = Originator Address, 1181 MS_time = current time + NEIGHB_HOLD_TIME. 1183 Deletion of MPR selector tuples occurs in case of expiration of the 1184 timer or in case of link breakage as described in the neighborhood 1185 and 2-hop neighborhood changes section. 1187 2.2.5. Multipoint Relay Selection 1189 MPRs are used to flood control messages from that node into the net- 1190 work while reducing the number of retransmissions that will occur in 1191 a region. Thus, the concept of MPR is an optimization of a classical 1192 flooding mechanism. 1194 Each node in the network selects, independently, its own set of MPRs 1195 among its symmetric neighborhood. The symmetric links with MPRs are 1196 advertised with Link Type MPR_LINK instead of SYM_LINK in HELLO mes- 1197 sages. 1199 The MPR set MUST be calculated by a node in such a way that it, 1200 through the neighbors in the MPR-set, can reach all symmetric 2-hop 1201 neighbors which are not at the same time symmetric neighbors of the 1202 node. This means that the union of the symmetric neighborhoods of the 1203 MPR nodes contains the symmetric 2-hop neighborhood. MPR set recalcu- 1204 lation should occur when changes are detected in the neighborhood or 1205 in the 2-hop neighborhood. 1207 While it is not essential that the MPR set is minimal, it is essen- 1208 tial that all 2-hop neighbors can be reached through the selected MPR 1209 nodes. A node SHOULD select an MPR set such that any 2-hop neighbor 1210 is covered by at least MPR_COVERAGE MPR nodes. With MPR_COVERAGE=1 1211 the overhead of the protocol is kept at a minimum. In presence of 1212 mobility and link failure, an MPR_COVERAGE=2 could provide a more 1213 redundant connectivity, for example to support a link failure without 1214 rerouting. 1216 Notice that MPR_COVERAGE can be tuned locally without affecting the 1217 consistency of the protocol. For example, a node can set MPR_COVER- 1218 AGE=2 if it observes many changes in its neighbor information base 1219 caused by mobility, while otherwise keeping MPR_COVERAGE=1. 1221 By default, the MPR set can coincide with the entire symmetric neigh- 1222 bor set. This will be the case at network initialization (and will 1223 correspond to classic link-state routing). 1225 The following specifies a proposed heuristic for selection of MPRs 1226 [2] adapted for multiple interfaces support. It constructs an MPR-set 1227 that enables it to reach any symmetrical 2-hop interface (i.e. any 1228 interface of a 2-hop neighbor having a symmetrical link with a neigh- 1229 bor). The following terminology will be used in describing this 1230 algorithm (neighbors are identified by their main address and 2-hop 1231 interfaces by their address): 1233 N: 1234 The set of neighbors with which there exists a symmetric link. 1236 N2: 1237 The set made of the symmetric 2-hop interfaces excluding all 1238 the interfaces of members of N and the interfaces of the node 1239 performing the computation. 1241 D(y): 1242 Degree of one hop neighbor node y (where y is a member of N), 1243 defined as the number of symmetric neighbor interfaces of node 1244 y, EXCLUDING all the interfaces of members of N and the inter- 1245 faces of the node performing the computation. 1247 Poorly covered interface: 1248 A poorly covered interface is an interface in N2 which is cov- 1249 ered by less than MPR_COVERAGE nodes in N. 1251 The proposed heuristic is as follows: 1253 1 Start with an empty MPR set 1255 2 Calculate D(y), where y is a member of N, for all nodes in N. 1257 3 Select as MPRs those nodes in N which cover the poorly covered 1258 interfaces in N2. The interfaces are then removed from N2 for 1259 the rest of the computation. 1261 4 While there exist interfaces in N2 which are not covered by at 1262 least MPR_COVERAGE nodes in the MPR set: 1264 4.1 For each node in N, calculate the number of interfaces in 1265 N2 which are not yet covered by at least MPR_COVERAGE 1266 nodes in the MPR set, and which are reachable through 1267 this one hop neighbor; 1269 4.2 Select as a MPR the node from N which provides reachabil- 1270 ity to the maximum number of those interfaces in N2. In 1271 case of multiple nodes providing the same amount of 1272 reachability, select that node as MPR whose D(y) is 1273 greater. Remove from N2 the interfaces that are now cov- 1274 ered by MPR_COVERAGE node in the MPR set. 1276 5 As an optimization, process each node y in the MPR set. If 1277 all interfaces in N2 are still covered by at least 1278 MPR_COVERAGE nodes in the MPR set excluding y, node y is 1279 removed from the MPR set. 1281 When the MPR set has been computed, all the corresponding main 1282 addresses are stored in the MPR Set. 1284 2.2.5.1. Neighborhood and 2-hop Neighborhood Changes 1286 A change in the neighborhood is detected when: 1288 - The N_SYM_time field of a neighbor tuple expires. This is con- 1289 sidered as a neighbor loss if it was the last link with a 1290 neighbor node (on the contrary, a link with an interface may 1291 break while a link with another interface of the neighbor node 1292 remains intact). 1294 - The N_ASYM_time field of a neighbor tuple expires and 1295 N_SYM_time is expired. The link is then considered lost. 1297 - A new neighbor tuple is inserted in the Neighbor Set with a 1298 valid N_SYM_time or a tuple with expired N_SYM_time is modi- 1299 fied so that N_SYM_time becomes valid. This is considered as a 1300 neighbor appearance if there was previously no link with the 1301 corresponding neighbor node. 1303 A change in the 2-hop neighborhood is detected when a 2-hop neighbor 1304 tuple expires or is deleted according to the HELLO message processing 1305 section. 1307 The following processing should occur when changes in the neighbor- 1308 hood or the 2-hop neighborhood are detected: 1310 - In case of neighbor loss, all the 2-hop tuples with 1311 N_main_addr == Main Address of the neighbor are deleted. 1313 - In case of neighbor loss, all the MPR selector tuples with 1314 MS_main_addr == Main Address of the neighbor are deleted 1316 - The MPR set is re-calculated when a neighbor appearance or 1317 loss is detected, or when a change in the 2-hop neighborhood 1318 is detected. 1320 - An additional HELLO message may be sent when the MPR set 1321 changes. 1323 2.2.6. Advanced Neighbor Sensing Functioning 1325 Established links should be as reliable as possible to avoid data 1326 packet loss. To enhance the reliability of the neighbor sensing mech- 1327 anism, the following implementation recommendations should be consid- 1328 ered. 1330 Each neighbor tuple in the neighbor set SHOULD, in addition to what 1331 is described in previous sections, include a N_pending field, a 1332 N_quality field, and a N_LOST_time field. N_pending is a boolean 1333 value specifying if the link is considered pending (i.e. the link is 1334 not considered established). N_quality is a dimensionless number 1335 between 0 and 1 describing the quality of the link. N_LOST_time is a 1336 timer for declaring a link as lost when an established link becomes 1337 pending. 1339 HELLO message generation should consider those new fields as follows: 1341 1 if N_LOST_time is not expired, the link is advertised with a 1342 link type of LOST_LINK; 1344 2 otherwise, if N_LOST_time is expired and N_pending is set to 1345 "true", the link SHOULD NOT be advertised at all; 1347 3 otherwise, if N_LOST_time is expired and N_pending is set to 1348 "false", the link is advertised as described in the HELLO mes- 1349 sage generation section. 1351 A node considers that it has a symmetric link for each neighbor tuple 1352 where 1354 1 N_LOST_time is expired, AND 1356 2 N_pending is "false", AND 1358 3 N_SYM_time is not expired. 1360 This should be taken as definition for computing the symmetric neigh- 1361 borhood when computing the MPR set. 1363 Apart from the above points, what has been described previously does 1364 not interfere with these advanced neighbor sensing fields in the 1365 neighbor tuples. The N_quality, N_pending and N_LOST_time fields are 1366 exclusively updated according to the present section. Advanced neigh- 1367 bor sensing does not modify the function of any other fields in the 1368 neighbor tuples. 1370 This advanced functioning is described as separately as possible to 1371 increase readability. 1373 2.2.6.1. Link Hysteresis 1375 The link between a node and some of its neighbor interfaces might be 1376 "bad", i.e. from time to time let HELLOs pass through only to fade 1377 out immediately after. In this case, the neighbor information base 1378 would contain a bad link for at least NEIGHB_HOLD_TIME. In absence of 1379 link layer notification, such a bad link might affect routing badly. 1380 To cope with such unstable links, the following hysteresis strategy 1381 SHOULD be adopted. 1383 For each neighbor interface NI heard by interface I, the N_quality 1384 field of the corresponding Neighbor Tuple determines the establish- 1385 ment of the link. The value of N_qualityis compared to two thresholds 1386 HYST_THRESHOLD_HIGH, HYST_THRESHOLD_LOW, fixed between 0 and 1 and 1387 such that HYST_THRESHOLD_HIGH >= HYST_THRESHOLD_LOW. 1389 The N_pending field is set according to the following: 1391 1 if N_quality > HYST_THRESHOLD_HIGH: 1393 N_pending = false 1395 N_LOST_time = current time - 1 (expired) 1397 2 otherwise, if N_quality < HYST_THRESHOLD_LOW: 1399 N_pending = true 1401 N_LOST_time = min (N_time, current time + 1402 NEIGHB_HOLD_TIME) 1404 (the link is then considered as lost according to the 1405 Neighborhood and 2-hop neighborhood changes section and 1406 this may produce a neighbor loss). 1408 3 otherwise, if HYST_THRESHOLD_LOW <= N_quality <= HYST_THRESH- 1409 OLD_HIGH: 1411 N_pending and N_LOST_time remain unchanged. 1413 The condition for considering a link established is thus stricter 1414 than the condition for loosing it. 1416 As a basic implementation requirement, an estimation of the link 1417 quality must be maintained and stored in the N_quality field. If some 1418 measure of the signal/noise level on a received message is available 1419 (e.g. as a link layer notification), then it can be used as estima- 1420 tion after normalization. 1422 If no signal/noise information is available from the link layer, an 1423 algorithm such as the following can be utilized. The algorithm is 1424 parameterized by a scaling parameter HYST_SCALING which is a number 1425 fixed between 0 and 1. For each neighbor interface NI heard by inter- 1426 face I, the first time NI is heard by I, N_quality is set to 1427 HYST_SCALING (N_pending is set to true and N_LOST_time to current 1428 time - 1). 1430 A tuple is updated according to two rules. Every time an OLSR mes- 1431 sage emitted by NI is received by I, the stability rule is applied: 1433 N_quality = (1-HYST_SCALING)*N_quality + HYST_SCALING. 1435 When an OLSR message emitted by NI is lost by I, the instability 1436 rule is applied: 1438 N_quality = (1-HYST_SCALING)*N_quality. 1440 The loss of OLSR messages is detected by tracking the missing Message 1441 Sequence Numbers and by long period of silence. If no HELLO message 1442 has been received for a HELLO_INTERVAL period, a loss of HELLO mes- 1443 sage is detected. 1445 2.2.6.2. Optional Link layer notification 1447 OLSR is designed not to impose or expect any specific information 1448 from the link layer. However, if information from the link-layer is 1449 available, a node MAY use this as described in this section. 1451 If link layer information describing connectivity to neighboring 1452 nodes is available (i.e. loss of connectivity such as through absence 1453 of a link layer acknowledgment), this information is used in addition 1454 to the information from the HELLO-messages to maintain the neighbor 1455 information base and the MPR selector set. 1457 Thus, upon receiving a link-layer notification that the link between 1458 a node and a neighbor interface is broken, the following actions are 1459 taken with respect to neighbor sensing: 1461 1 if the link to a neighboring symmetric or asymmetric interface 1462 is broken, the corresponding neighbor tuple is modified: 1463 N_LOST_time and N_time are set to current time + 1464 NEIGHB_HOLD_TIME. 1466 2 this is considered as a link loss and the appropriate process- 1467 ing described in the neighborhood and 2-hop neighborhood 1468 changes section should be performed. 1470 2.3. Topology Discovery 1472 The Neighbor Sensing part of the protocol basically offers to each 1473 node a list of neighbors with which it can communicate directly and 1474 an optimized flooding mechanism through MPRs. Based on this mecha- 1475 nism, topology information is disseminated through the network. The 1476 present section describes what part of the information given by the 1477 Neighbor Sensing is disseminated and how it is used to construct 1478 routes. 1480 Routes are constructed through MPR-links and links with neighbors. A 1481 node thus basically disseminates its MPR-selector set. If a node has 1482 multiple interfaces, it must also disseminate the list of its inter- 1483 face addresses. 1485 2.3.1. TC Message Format 1487 The proposed format of a TC message is 1489 0 1 2 3 1490 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 1491 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1492 | MSSN | Reserved | 1493 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1494 | Multipoint Relay Selector Main Address | 1495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1496 | Multipoint Relay Selector Main Address | 1497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1498 | ... | 1499 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1501 This is sent as the data-portion of the general message format with 1502 the "Message Type" set to TC_MESSAGE. The time to live SHOULD be set 1503 to 255 (maximum value) to diffuse the message into the entire net- 1504 work. 1506 MPR Selector Sequence Number (MSSN) 1508 A sequence number is associated with the MPR selector set. 1509 Every time a node detects a change in its MPR selector set, it 1510 increments this sequence number. This number is sent in this 1511 MSSN field of the TC message to keep track of the most recent 1512 information. When a node receives a TC message, it can decide 1513 on the basis of this MPR Sequence Number, whether or not the 1514 received information about the MPR selectors of the originator 1515 node is more recent than what it already has. 1517 Multipoint Relay Selector Main Address 1519 This field contains the main address of a node, which has 1520 selected the Originator node (of the TC message) as a MPR. 1521 All addresses of the MPR selectors of the Originator node are 1522 put in the TC message. If the maximum allowed message size (as 1523 imposed by the network) is reached while there are still MPR 1524 selector addresses which have not been inserted into the TC- 1525 message, more TC messages will be generated until the entire 1526 MPR selector set has been sent. 1528 Reserved 1530 This field is reserved for future usage, and MUST be set to 1531 "0000000000000000" for compliance with this draft. 1533 2.3.2. Topology Information Base 1535 Each node in the network maintains topological information about the 1536 network. This information is acquired from TC-messages and is used 1537 for routing table calculations. 1539 Thus, for each destination in the network, a "Topology Tuple" 1540 (T_dest, T_last, T_seq, T_time) is recorded. T_dest is the main 1541 address of a node, which may be reached in one hop from the node with 1542 the main address T_last. Typically, T_last is a MPR of T_dest. T_seq 1543 is a sequence number, and T_time specifies the time at which this 1544 tuple expires and *MUST* be removed. 1546 In a node, the set of Topology Tuples are denoted the "Topology Set". 1548 2.3.3. TC Message Generation 1550 In order to build the topology information base needed, each node, 1551 which has been selected as MPR, broadcasts Topology Control (TC) mes- 1552 sages. TC messages are flooded to all nodes in the network and take 1553 advantage of MPRs. MPRs enable a better scalability in the distribu- 1554 tion of topology information [1]. 1556 A TC message is sent by a node in the network to declare its MPR 1557 Selector set. I.e., the TC message contains the list of neighbors 1558 which have selected the sender node as a MPR. The sequence number 1559 (MSSN) associated with this MPR selector set is also sent with the 1560 list. The list of addresses can be partial in each TC message (e.g. 1561 due to message size limitations, imposed by the network), but parsing 1562 of all TC messages describing the MPR selector set of a node MUST be 1563 complete within a certain refreshing period (TC_INTERVAL). The infor- 1564 mation diffused in the network by these TC messages will help each 1565 node calculate its routing table. 1567 A node which has an empty MPR selector set, i.e. nobody has selected 1568 it as a MPR, may not generate any TC message. Indeed, when its MPR 1569 selector set becomes empty, it SHOULD still send (empty) TC-messages 1570 during TOP_HOLD_TIME to invalidate the previous TC-messages. It MAY 1571 then stop sending TC-messages until some node is inserted in its MPR 1572 selector set. 1574 A node MAY transmit additional TC-messages to increase its reactive- 1575 ness to link failures. I.e. when a change to the MPR selector set is 1576 detected and this change can be attributed to a link failure, a TC- 1577 message SHOULD be transmitted after a shorter interval than TC_INTER- 1578 VAL. 1580 2.3.4. TC Message Processing 1582 TC messages are broadcasted and retransmitted by the MPRs in order to 1583 diffuse the messages in the entire network. 1585 In this section, the term "originator" is used to designate the node 1586 from which the message originally originated, while the term "sender" 1587 is used to designate the node from which the message was received 1588 (i.e. the "last hop" of the message). 1590 The tuples in the topology set are recorded with the topology infor- 1591 mation that is exchanged through TC messages, according to the fol- 1592 lowing algorithm: 1594 1 If the sender interface (NB: not originator) of this message 1595 is not in the symmetric neighborhood of this node, the message 1596 is discarded. 1598 2 A tuple is inserted into the duplicate table to prevent it 1599 from being processed again with: 1601 D_addr = originator address 1603 D_seq_num = Message Sequence 1605 D_time = current time + D_HOLD_TIME. 1607 3 If there exist some tuple in the topology set where: 1609 T_last == originator address AND 1611 T_seq > MSSN, 1613 then no further processing of this TC message is performed and 1614 the message is silently discarded (case: message received out 1615 of order). 1617 4 All tuples in the topology set where: 1619 T_last == originator address AND 1621 T_seq < MSSN 1623 are removed from the topology set. 1625 5 For each of the MPR selector address received in the TC mes- 1626 sage: 1628 5.1 If there exist some tuple in the topology set where: 1630 T_dest == MPR selector address, AND 1632 T_last == originator address, 1634 then the holding time of that tuple is set to: 1636 T_time = current time + TOP_HOLD_TIME. 1638 5.2 Otherwise, a new tuple is recorded in the topology set 1639 where: 1641 T_dest = MPR selector address, 1643 T_last = originator address, 1645 T_seq = MSSN, 1647 T_time = current time + TOP_HOLD_TIME. 1649 6 If the sender address is an interface address of a MPR selec- 1650 tor of this node and if the time to live of the message is 1651 greater than '1', the message MUST be forwarded according to 1652 the following: 1654 6.1 The TTL of the message is reduced by one. 1656 6.2 The hop-count of the message is increased by one 1658 6.3 The message is broadcasted on all interfaces (Notice: The 1659 remaining fields of the message header SHOULD be left 1660 unmodified.) 1662 2.3.5. Multiple Interface Association 1664 Each node in the network maintains interface information about the 1665 other nodes in the network. This information acquired from MID-mes- 1666 sages, emitted by nodes with multiple interfaces participating in the 1667 MANET, and is used for routing table calculations. 1669 2.3.5.1. Multiple Interface Association Information Base 1671 For each destination in the network, "Interface association Tuples" 1672 (I_if_addr, I_main_addr, I_time) are recorded. I_if_addr is an inter- 1673 face address of a node, I_main_addr is the main address of this node. 1674 I_time specifies the time at which this tuple expires and *MUST* be 1675 removed. 1677 In a node, the set of Interface association Tuples is denoted the 1678 "Interface association Set". 1680 2.3.5.2. MID Message Format 1682 The proposed format of a MID message is 1683 0 1 2 3 1684 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 1685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1686 | Interface Address | 1687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1688 | Interface Address | 1689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1690 | ... | 1691 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1693 This is sent as the data-portion of the general message format with 1694 the "Message Type" set to MID_MESSAGE. The time to live SHOULD be 1695 set to 255 (maximum value) to diffuse the message into the entire 1696 network. 1698 Interface Address 1700 This field contains the address of an interface of the node 1701 other than its main address (already indicated in the origina- 1702 tor address). All interface addresses other than the main 1703 address of the Originator node are put in the MID message. If 1704 the maximum allowed message size (as imposed by the network) 1705 is reached while there are still interface addresses which 1706 have not been inserted into the MID-message, more MID messages 1707 are generated until the entire interface addresses set has 1708 been sent. 1710 2.3.5.3. MID Message Generation 1712 In order to build the interface association information base, each 1713 node with multiple interfaces broadcast Multiple Interface Declara- 1714 tion (MID) messages. MID messages are flooded to all nodes in the 1715 network and take advantage of MPRs. 1717 A MID message is sent by a node in the network to declare its multi- 1718 ple interfaces (if any). I.e., the MID message contains the list of 1719 interface addresses which are associated to its main address. The 1720 list of addresses can be partial in each TC message (e.g. due to mes- 1721 sage size limitations, imposed by the network), but parsing of all 1722 MID messages describing a nodes interface set MUST be complete within 1723 a certain refreshing period (MID_INTERVAL). The information diffused 1724 in the network by these MID messages will help each node to calculate 1725 its routing table. A node which has only a single interface address 1726 participating in the MANET (i.e. running OLSR), MUST NOT generate any 1727 MID message. 1729 A node with more interfaces, where only one is participating in the 1730 MANET and running OLSR (e.g. a node is connected to a wired network 1731 as well as to a MANET) MUST NOT generate any MID messages. 1733 2.3.5.4. MID Message Processing 1735 MID messages are broadcasted and retransmitted by the MPRs in order 1736 to diffuse the messages in the entire network. 1738 In this section, the term "originator" is used to designate the node 1739 from which the message originally originated, while the term "sender" 1740 is used to designate the node from which the message was received 1741 (i.e. the "last hop" of the message). 1743 The tuples in the multiple interface association set are recorded 1744 with the information that is exchanged through MID messages, follow- 1745 ing the following algorithm: 1747 1 If the sender (NB: not originator) of this message is not in 1748 the symmetric neighborhood of this node, the message is dis- 1749 carded. 1751 2 A tuple is inserted into the duplicate table to prevent it 1752 from being processed again with: 1754 D_addr = originator address 1756 D_seq_num = Message Sequence 1758 D_time = current time + D_HOLD_TIME. 1760 3 For each of the interface address received in the MID message: 1762 3.1 If there exist some tuple in the interface association 1763 set where: 1765 I_if_addr == interface address, AND 1767 I_main_addr == originator address, 1769 then the holding time of that tuple is set to: 1771 I_time = current time + MID_HOLD_TIME. 1773 3.2 Otherwise, a new tuple is recorded in the interface asso- 1774 ciation set where: 1776 I_if_addr = interface address, 1778 I_main_addr = originator address, 1780 I_time = current time + MID_HOLD_TIME. 1782 4 If the sender address is an interface address of a MPR selec- 1783 tor of this node and if the time to live of the message is 1784 greater than '1', the message MUST be forwarded according to 1785 the following: 1787 4.1 The TTL of the message is reduced by one. 1789 4.2 The hop-count of the message is increased by one 1791 4.3 The message is broadcasted on all interfaces (Notice: The 1792 remaining fields of the message header SHOULD be left 1793 unmodified.) 1795 2.3.6. Associated Networks and Hosts 1797 A node MAY provide access to a set of associated hosts. I.e., a node 1798 may act as a "gateway" between the MANET and a number of associated 1799 hosts and/or subnets, not running OLSR and thus not participating in 1800 the MANET. Thus, a node SHOULD be able to inject routing information 1801 describing these associated hosts or networks into MANET, as SHOULD 1802 all nodes be capable of interpreting such information. 1804 Notice that this is a different case from that of "multiple inter- 1805 faces", described previously. Where, in the "Multiple Interface Asso- 1806 ciations", all the described interfaces were participating in the 1807 MANET through running the OLSR protocol, this section addresses the 1808 interfaces which do not participate. This is, e.g., the case where a 1809 node has both a wireless interface (participating in the MANET) and a 1810 wired interface, through which a number of hosts statically connect 1811 (to the nodes in the MANET). 1813 To accomplish this, a node, to which there are associated hosts 1814 and/or networks, periodically issues an Host and Network Association 1815 (HNA) message, containing sufficient information for the recipients 1816 to construct an appropriate routing table. 1818 2.3.6.1. HNA Message Format 1820 The proposed format of an HNA-message is: 1822 0 1 2 3 1823 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 1824 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1825 | Network Address | 1826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1827 | Netmask | 1828 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1829 | Network Address | 1830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1831 | Netmask | 1832 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1833 | ... | 1834 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1836 This is sent as the data part of the general packet format with the 1837 "Message Type" set to HNA and the TTL field set to 255. 1839 It should be noticed, that the HNA-message can be considered as a 1840 "generalized version" of the TC-message: the originator of both the 1841 HNA and TC messages announce "reachability" to some other host(s). In 1842 the TC-message, no netmask is required, since all reachability is 1843 announced on a per-host basis. In HNA-messages, announcing reachabil- 1844 ity to an address sequence through a network- and netmask address is 1845 typically preferred over announcing reachability to individual host 1846 addresses. 1848 Network Address 1850 The network address of the associated network 1852 Netmask 1854 The netmask, corresponding to the network address immediately 1855 above. 1857 2.3.6.2. Host and Network Association Information Base 1859 Each node maintains information concerning which nodes may act as 1860 "gateways" to associated hosts and networks by recording "association 1861 tuples" (GW_main_addr, NET_addr, NET_mask, GS_time), where 1862 GW_main_addr is the main address of the gateway, NET_addr and 1863 NET_mask specifies the network address and netmask of a network, 1864 reachable through this gateway, and GS_time specifies the time at 1865 which this tuple expires and hence *MUST* be removed. 1867 The set of all association tuples in a node is called the "associa- 1868 tion set". 1870 2.3.6.3. HNA Message Generation 1872 A node with associated hosts and/or networks SHOULD periodically gen- 1873 erate a Host and Network Association (HNA) message, containing pairs 1874 of (network address, netmask) corresponding to the connected hosts and 1875 networks. HNA-messages SHOULD be transmitted periodically every 1876 HNA_INTERVAL. 1878 A node without any associated hosts and/or networks SHOULD NOT gener- 1879 ate HNA-messages. 1881 2.3.6.4. HNA Message Processing 1883 In this section, the term "originator address" is used to designate 1884 the main address of the node which originally issued the HNA-message. 1886 Upon receiving a HNA-message, the node performs the following: 1888 1 An entry in the duplicate set is recorded for this message 1889 with: 1891 D_addr = originator address 1893 D_seq_num = Message Sequence Number 1895 D_time = current time + D_HOLD_TIME. 1897 2 For each (network address, netmask) pair in the message: 1899 2.1 if an entry in the association set already exists, where: 1901 GW_main_addr == originator address 1903 NET_addr == network address 1905 NET_mask == netmask 1907 then the holding time for that tuple is set to: 1909 GW_time = current time + GW_HOLDING_TIME 1911 2.2 otherwise, a new tuple is recorded with: 1913 GW_main_addr == originator address 1915 NET_addr == network address 1917 NET_mask == netmask 1919 GW_time = current time + GW_HOLDING_TIME 1921 3 If the sender address is an interface address of a MPR selec- 1922 tor of this node and if the time to live of the message is 1923 greater than '1', the message MUST be forwarded according to 1924 the following: 1926 3.1 The TTL of the message is reduced by one. 1928 3.2 The hop-count of the message is increased by one 1930 3.3 The message is broadcasted on all interfaces (Notice: The 1931 remaining fields of the message header SHOULD be left 1932 unmodified.) 1934 2.3.7. Routing Table Calculation 1936 Each node maintains a routing table which allows it to route data, 1937 destined for the other nodes in the network. The routing table is 1938 based on the information contained in the neighbor sensing informa- 1939 tion base, the interface association set and the topology set. There- 1940 fore, if any of these tables are changed, the routing table is re- 1941 calculated to update the route information about each destination in 1942 the network. The route entries are recorded in the routing table in 1943 the following format: 1945 1. R_dest R_next R_dist R_if_id 1946 2. R_dest R_next R_dist R_if_id 1947 3. ,, ,, ,, 1949 Each entry in the table consists of R_dest, R_next, R_dist, and 1950 R_if_id which specifies that the node identified by R_dest is esti- 1951 mated to be R_dist hops away from the local node, and that the sym- 1952 metric neighbor node with interface address R_next is the next hop 1953 node in the route to R_dest, and this one hop is reachable through 1954 the local interface 1955 R_if_id. Entries are recorded in the table for each destination in 1956 the network for which the route is known. All the destinations for 1957 which the route is broken or partially known are not entered in the 1958 table. 1960 This routing table is updated when a change is detected in the neigh- 1961 bor information base, or the topology set. More precisely, it is re- 1962 calculated in case of neighbor appearance or loss, or when a topology 1963 tuple is created or removed. The update of this routing information 1964 does not generate or trigger any messages to be transmitted, neither 1965 in the network, nor in the one-hop neighborhood. 1967 To construct the routing table of node X, a shortest path algorithm 1968 is run on the directed graph containing the arcs X -> Y where Y is 1969 any symmetric neighbor of X (with Link Type SYM_LINK or MPR_LINK) and 1970 the arcs U -> V where there exists an entry in the topology set with 1971 V as T_dest and U as T_last. 1973 The following procedure is given as an example to calculate (or re- 1974 calculate) the routing table : 1976 1 All the entries from the routing table are removed. 1978 2 The new routing entries are added starting with the symmetric 1979 neighbors (h=1) as the destination nodes. I.e. for each neigh- 1980 bor tuple in the neighbor set where: 1982 N_LOST_time < current time AND 1984 N_pending == false AND 1986 N_SYM_time >= current time 1988 (there is a symmetric link to the neighbor), a new routing 1989 entry is recorded in the routing table with: 1991 R_dest = N_main_addr of the neighbor; 1993 R_next = N_if_addr of the neighbor interface; 1995 R_dist = 1; 1996 R_if_id = N_if_id of the entry. 1998 If N_if_addr is distinct from N_main_addr, another new routing 1999 entry with is added, with: 2001 R_dest = N_main_addr; 2003 R_next = N_if_addr; 2005 R_dist = 1; 2007 R_if_id = N_if_id. 2009 3 The new route entries for the destination nodes h+1 hops away 2010 are recorded in the routing table. The following procedure is 2011 executed for each value of h, starting with h=1 and increment- 2012 ing it by 1 each time. The execution will stop if no new entry 2013 is recorded in an iteration. 2015 3.1 For each topology entry in the topology table, if its 2016 T_dest does not correspond to R_dest of any route entry 2017 in the routing table AND its T_last corresponds to R_dest 2018 of a route entry whose R_dist is equal to h, then a new 2019 route entry is recorded in the routing table (if it does 2020 not already exist) where: 2022 R_dest = T_dest; 2024 R_next = R_next of the recorded route entry whose 2025 R_dest == T_last 2027 R_dist = h+1; and 2029 R_if_id = R_if_id of the recorded route entry whose 2030 R_dest == T_last. 2032 3.2 Several topology entries may be used to select a next hop 2033 R_next for reaching the node R_dest. When h=1, ties 2034 should be broken such that MPR selectors are preferred as 2035 next hop. 2037 The routing table is further completed by using the multiple inter- 2038 face association set: 2040 1 For each entry in the multiple interface association base 2041 where there exists a routing entry such that: 2043 R_dest == I_main_addr (of the multiple interface inter- 2044 face association entry) 2046 a route entry is created in the routing table with: 2048 R_dest = I_if_addr (of the multiple interface associa- 2049 tion entry) 2051 R_next = R_next (of the recorded route entry) 2053 R_dist = R_dist (of the recorded route entry) 2055 R_if_id = R_if_id (of the recorded route entry). 2057 The routing table is finally completed by using the host and network 2058 association set: 2060 1 For each tuple in the routing set, record an entry in the 2061 routing table, with: 2063 R_dest = NET_addr/NET_mask 2065 R_next = the next hop on the path from the node to 2066 GW_main_addr 2068 R_dist = dist to GW_main_addr 2070 R_next and R_if_id are set to the same values as the 2071 tuple from the routing set with R_dest == GW_main_addr. 2073 2.3.8. Advanced Topology Discovery Functioning 2075 Due to mobility, some links of the broadcasted topology may fail. 2076 Additional messages may be sent to recover quickly. Ideally the load 2077 of control messages should increase smoothly with mobility. This sec- 2078 tion describes how this may be achieved in OLSR. 2080 2.3.8.1. Reaction to Link Failure with a MPR Selector 2082 Detection of a link failure between a node and one of its MPR selec- 2083 tors through a link-layer notification may trigger additional TC- 2084 messages to increase the protocol reactiveness to link failures. I.e. 2085 when a change to the MPR selector set is detected and this change can 2086 be attributed to a link failure, an additional TC-message MAY be 2087 transmitted. 2089 More precisely, if a link failure appears to be a neighbor loss with 2090 a neighbor, which has selected this node as MPR, the MPR selector set 2091 is updated (MSSN is thus incremented) and a TC message MAY be gener- 2092 ated. Moreover if it appears that data traffic was flowing through 2093 this link, a TC message SHOULD be generated. Notice, that a node may 2094 be aware of data traffic flowing to the lost neighbor in case of a 2095 link layer notification coming from a missing acknowledgement or when 2096 statistics about packet forwarding is given by the IP stack. 2098 2.3.8.2. Advanced Fast Re-routing Mechanism 2100 When a link breaks, information stored in the neighbor sensing infor- 2101 mation base may be used to compute an alternative route immediately 2102 if necessary. 2104 If there exists a N_2hop_address listed in the 2-hop neighbor set, 2105 and for which no route exists, a route entry is created in the rout- 2106 ing table with: 2108 R_dest = N_2hop_address 2110 R_next = R_next of the recorded route entry whose R_dest is 2111 equal to N_main_addr of the corresponding 2-hop tuple 2113 R_dist = 2 2115 R_if_id = R_if_id of the recorded route entry whose R_dest is 2116 equal to N_main_addr of the corresponding 2-hop tuple. 2118 If an entry in the multiple interface association base records a main 2119 address I_main_addr reporting an interface I_if_addr = 2120 N_2hop_address, then R_dest is set to I_main_addr instead of 2121 N_2hop_address. 2123 If the two hop neighbor allows to reach other nodes at distance 2124 greater than 2 according to the topology set then other entries may 2125 be added in the routing table with same R_next for these nodes. 2127 The routing table is finally completed using the multiple interface 2128 association set and the host and network association set as described 2129 in the routing table calculation section. 2131 To allow other nodes to benefit from the alternative route, the node 2132 MAY trigger a fast re-routing event by generating a FRR message. 2134 2.3.8.2.1. FRR Message Format 2136 The proposed format of a FRR message is 2138 0 1 2 3 2139 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 2140 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2141 | Next Hop Address | 2142 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2143 | Two Hop Address | 2144 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2145 | Two Hop Address | 2146 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2147 | ... | 2148 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2150 This is sent as the data-portion of the general message format with 2151 the "Message Type" set to FRR_MESSAGE. The time to live SHOULD be 2152 set to 1, ensuring that the message is only received by one-hop 2153 neighbors. 2155 Next Hop Address 2157 This field contains the main address of a node which is used 2158 as next hop by the Originator for reaching all the nodes iden- 2159 tified by the Two Hop Address fields. 2161 Two Hop Address 2163 This field contain the main address of a 2-hop neighbor of the 2164 Originator of the message. 2166 2.3.8.2.2. FRR Message Generation 2168 When the fast re-routing mechanism allows to reach 2-hop neighbors 2169 through a neighbor which is not recorded as MPR of them in the topol- 2170 ogy set, the node MAY inform this next hop by generating a FRR Mes- 2171 sage with Next Hop Address containing the main address of this next 2172 hop and listing the main addresses of these 2-hop neighbors. 2174 If some information allows to deduce that some data traffic flows 2175 through the node to some of these 2-hop neighbors, such a FRR Message 2176 SHOULD be generated. This can be the case if such a 2-hop neighbor 2177 was previously a neighbor and a link layer notification of a missing 2178 acknowledgement has been received or statistics about packet forward- 2179 ing are provided by the IP stack. Otherwise, an FFR-message MAY be 2180 generated. 2182 2.3.8.2.3. FRR Message Processing 2184 Upon reception of a FRR message a node performs the following: 2186 1 If the Next Hop Address field is not the main address of the 2187 node, the message is dropped. 2189 2 For each Two Hop Address listed in the FRR Message for which 2190 there exists a neighbor tuple with N_main_addr = the Two Hop 2191 Address and for which there exists no tuple in the MPR selec- 2192 tor set with MS_main_addr = the Two Hop Addres, a new tuple is 2193 inserted with: 2195 MS_main_addr = the Two Hop Addres 2197 MS_if_addr = N_if_addr of the corresponding neighbor 2198 tuple 2200 MS_time = current time + 2HOP_HOLD_TIME. 2202 If the MPR set has changed then the MSSN is incremented by 1 and a TC 2203 message containing the new MPR selector set SHOULD be generated. 2205 3. Node Configuration 2207 3.1. Address Assignment 2209 The nodes in the MANET network SHOULD be assigned addresses within a 2210 defined address sequence. I.e., the nodes in the MANET SHOULD be 2211 addressable through a network address and a netmask. 2213 Likewise, the nodes in each associated network SHOULD be assigned 2214 addresses from a defined address sequence, distinct from that being 2215 used in the MANET. 2217 3.2. Routing Configuration 2219 Any MANET node with associated networks or hosts SHOULD 2220 be configured such that it has routes set up to the interfaces with 2221 associated hosts or network. 2223 3.3. Data Packet Forwarding 2225 OLSR itself does not perform packet forwarding. Rather, it maintains 2226 the routing table in the underlying operating system, which is 2227 assumed to be forwarding packets as specified in RFC1812. 2229 4. IPv6 Considerations 2231 All the operations and parameters described in this document used by 2232 OLSR for IP version 4 are the same as those used by OLSR for IP ver- 2233 sion 6. However, to operate with IP version 6, the only required 2234 change is to replace the IPv4 addresses with Ipv6 address. 2236 5. Proposed Values for the Constants 2238 This section list the values for the constants used in the descrip- 2239 tion of the protocol. 2241 HELLO_INTERVAL = 2 seconds 2243 REFRESH_INTERVAL = 2 seconds 2245 TC_INTERVAL = 5 seconds 2247 MID_INTERVAL = TC_INTERVAL 2249 HNA_INTERVAL = TC_INTERVAL 2251 NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL 2253 2HOP_HOLD_TIME = 3 x REFRESH_INTERVAL 2255 TOP_HOLD_TIME = 3 x TC_INTERVAL 2257 D_TIME = 30 seconds 2258 I_TIME = 3 x MID_INTERVAL 2260 GW_TIME = 3 x HNA_INTERVAL 2262 HELLO_MESSAGE = 1 2264 TC_MESSAGE = 2 2266 MID_MESSAGE = 3 2268 HNA_MESSAGE = 4 2270 MID_MESSAGE = 5 2272 FRR_MESSAGE = 6 2274 ASYM_LINK = 1 2276 SYM_LINK = 2 2278 MPR_LINK = 3 2280 LOST_LINK = 4 2282 HYST_THRESHOLD_HIGH = 0.8 2284 HYST_THRESHOLD_LOW = 0.3 2286 HYST_SCALING = 0.5 2288 MPR COVERAGE = 1 2290 MAXJITTER = HELLO_INTERVAL / 4 2292 6. Sequence Numbers 2294 Sequence numbers are used in OLSR with the purpose of discarding 2295 "old" information, i.e. messages received out of order. However with 2296 a limited number of bits for representing sequence numbers, wrap- 2297 arounds (that the sequence number is incremented from the maximum 2298 possible value to zero) will occur. To prevent this from interfering 2299 with the operation of the protocol, the following MUST be observed. 2301 The term MAXVALUE designates in the following the largest possible 2302 value for a sequence number. 2304 The sequence number S1 is said to be "greater than" the sequence num- 2305 ber S2 iff: 2307 S1 > S2 AND S1 - S2 <= MAXVALUE/2 OR 2309 S2 > S1 AND S2 - S1 > MAXVALUE/2 2311 Thus when comparing two messages, it is possible - even in the pres- 2312 ence of wrap-around - to determine which message contains the most 2313 recent information. 2315 7. Acknowledgments 2316 The authors would like to thank Joseph Macker and his team 2317 for their valuable suggestions on the 2318 advanced neighbor sensing mechanism. 2320 8. Authors' Addresses 2322 Thomas Heide Clausen Project HIPERCOM INRIA Rocquencourt BP 105 78153 2323 Le Chesnay Cedex, France Phone: +33 1 3963 5133 Email: 2324 Thomas.Clausen@inria.fr 2326 Philippe Jacquet Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le 2327 Chesnay Cedex, France Phone: +33 1 3963 5263 Email: 2328 Philippe.Jacquet@inria.fr 2330 Anis Laouiti Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le 2331 Chesnay Cedex, France Phone: +33 1 3963 508832 Email: 2332 Anis.Laouiti@inria.fr 2334 Pascale Minet Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le 2335 Chesnay Cedex, France Phone: +33 1 3963 508832 Email: Pas- 2336 cale.Minet@inria.fr 2338 Paul Muhlethaler Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le 2339 Chesnay Cedex, France Phone: +33 1 3963 5278 Email: Paul.Muh- 2340 lethaler@inria.fr 2341 Amir Qayyum Avaz Networks 5-A Constitution Avenue Islamabad, Pakistan 2342 Phone: +92-51-2826160 Email: qayyum@avaznet.com 2344 Laurent Viennot Project HIPERCOM INRIA Rocquencourt BP 105 78153 Le 2345 Chesnay Cedex, France Phone: +33 1 3963 5225 Email: Laurent.Vien- 2346 not@inria.fr 2348 9. References 2350 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia- 2351 bility in cable free radio LANs: Low level forwarding in HIPERLAN. 2352 Wireless Personal Communications, 1996 2354 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient 2355 technique for flooding in mobile wireless networks. 35th Annual 2356 Hawaii International Conference on System Sciences (HICSS'2001). 2358 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 2359 1, functional specifications ETS 300-652, ETSI, June 1996 2361 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net- 2362 work Protocols, INRIA research report RR-3965, 2000 2364 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- 2365 els. Request for Comments (Best Current Practice) 2119, Internet 2366 Engineering Task Force, March 1997. 2368 6. T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The Optimized 2369 Link State Routing Protocol, Evaluation through Experiments and 2370 Simulation. IEEE Symposium on "Wireless Personal Mobile Communica- 2371 tions", september 2001. 2373 7. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum and L. 2374 Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan 2375 2001.