idnits 2.17.1 draft-ietf-manet-olsr-04.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. ** There is 1 instance of too long lines in the document, the longest one being 2 characters in excess of 72. ** There are 116 instances of lines with control characters in the document. ** 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 337: '... OLSR MAY optimize the reactivity to...' RFC 2119 keyword, line 514: '... MUST be set to '0000000000000000...' RFC 2119 keyword, line 525: '...this message. This field SHOULD NOT be...' RFC 2119 keyword, line 529: '... MUST *NEVER* be changed in the r...' RFC 2119 keyword, line 558: '... Live MUST be decremented by 1. W...' (30 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 (2 March 2001) is 8449 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 1026 looks like a reference -- Missing reference section? '2' on line 956 looks like a reference -- Missing reference section? '3' on line 100 looks like a reference -- Missing reference section? '4' on line 123 looks like a reference -- Missing reference section? '9' on line 167 looks like a reference -- Missing reference section? '5' on line 167 looks like a reference -- Missing reference section? '6' on line 207 looks like a reference -- Missing reference section? '8' on line 222 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 1 warning (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET-DRAFT Philippe Jacquet 2 IETF MANET Working Group Paul Muhlethaler 3 Expiration: 02 September 2001 Amir Qayyum 4 Anis Laouiti 5 Laurent Viennot 6 Thomas Clausen 7 INRIA Rocquencourt, France 8 2 March 2001 10 Optimized Link State Routing Protocol 11 draft-ietf-manet-olsr-04.txt 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC 2026 except that the right to 17 produce derivative works is not granted. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as 22 Internet-Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six 25 months and may be updated, replaced, or obsoleted by other 26 documents at any time. It is inappropriate to use Internet-Drafts 27 as reference material or to cite them other than as "work in 28 progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 Abstract 38 This document describes the Optimized Link State Routing (OLSR) 39 protocol for mobile ad hoc networks. The protocol is an 40 optimization of the pure link state algorithm tailored to the 41 requirements of a mobile wireless LAN. The key concept used in the 42 protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are 43 selected nodes which forward broadcast messages during the 44 flooding process. This technique substantially reduces the message 45 overhead as compared to pure flooding mechanism where every node 46 retransmits each message when it receives the first copy of the 47 packet. In OLSR, information flooded in the network "through" 48 these MPRs is also "about" the MPRs. Thus a 49 second optimization is achieved by minimizing the "contents" of 50 the control messages flooded in the network. Hence, as contrary to 51 the classic link state algorithm, only a small subset of links 52 with the neighbor nodes are declared instead of all the 53 links. This information is then used by the OLSR protocol for 54 route calculation. As a consequence hereof, the routes contain 55 only the MPRs as intermediate nodes from a Source to a 56 Destination. OLSR provides optimal routes (in terms of number of 57 hops). The protocol is particularly suitable for large and dense 58 networks as the technique of MPRs works well in this context. 60 Contents 62 Status of This Memo 1 63 Abstract 1 64 1. Introduction 3 65 2. Changes 3 66 3. OLSR terminology 4 67 4. Applicability Section 5 68 4.1 Networking Context 5 69 4.2 Protocol Characteristics and Mechanisms 6 70 5. Protocol Overview 8 71 6. Multipoint relays 9 72 7. Protocol functioning 10 73 7.1 Protocol and port number 10 74 7.2 Packet format 10 75 7.2.1 Packet Header 12 76 7.2.2 Message Header 12 77 7.2.3 Packet Processing 13 78 7.3 Neighbor sensing 15 79 7.3.1 Neighbor sensing information base 15 80 7.3.2 HELLO message broadcast 16 81 7.3.3 HELLO message processing 19 82 7.4 Multipoint relay selection 21 83 7.5 Multipoint relay information declaration 22 84 7.5.1 Topology information base 22 85 7.5.2 TC message broadcast 23 86 7.5.3 TC message processing 24 87 7.6 Routing table calculation 26 88 7.7.Link layer notification 27 89 8. Packet Forwarding 28 90 8.1 Data packet forwarding 28 91 8.2 Control message forwarding 28 92 9. Proposed values for constants 29 93 10. Sequence numbers 29 94 11. References 30 95 12. Authors' addresses 31 96 1. Introduction 98 This Optimized Link State Routing protocol inherits the concept of 99 forwarding and relaying from HIPERLAN (a MAC layer protocol) which 100 is standardized by ETSI [3]. The OLSR protocol is developed in the 101 IPANEMA project (part of Euclid program) and in the PRIMA project 102 (part of RNRT program). 104 This protocol is developed for mobile ad hoc networks. It operates 105 as a table driven and proactive protocol and exchanges topology 106 information with other nodes of the network at regular intervals. 107 The nodes which are selected as a multipoint relay by some 108 neighbor nodes announce this information periodically in their 109 control messages. The protocol uses the MPRs to facilitate 110 efficient flooding of control messages in the network. In route 111 calculation, the MPRs are used to form the route from a given node 112 to any destination in the network. 114 MPRs are selected by a node among its one hop neighbors with 115 "symmetric", i.e. bi-directional, link. Therefore, selecting the 116 route through MPRs automatically avoids the problems associated 117 with data packet transfer on uni-directional links (such as the 118 problem of not getting link-layer acknowledgments for the data 119 packets at each hop) 121 The OLSR protocol is developed to work independently from other 122 protocols. But it can be adapted to operate with a protocol (like 123 IMEP [4]) which could provide common functionalities such as 124 neighbor sensing, multipoint relaying, security authentication, 125 etc. 127 2. Changes 129 Major changes from version 03 to version 04 131 - Finalized the generic packet/message format to 132 include features for scope-limited (diameter-bound) 133 flooding of messages and to handle duplicate messages. 135 - Editorial changes towards language consistency. 137 Major changes from version 02 to version 03 139 - Introduction of assigned port number for use with OLSR. 141 - The packet format now uses "message length" rather than an 142 offset to the next message. 144 - Optional section describing how link-layer notifications 145 can be utilized included. 147 Major changes from version 01 to version 02 149 - Introduction of a unified packet format for encapsulation of 150 all messages being exchanged between nodes. This also serves 151 to facilitate extensions in future versions of the protocol 152 (i.e. introduction of new protocol messages) without breaking 153 backwards compatibility. 155 - Removal of "Power Conservation" from this draft. Power 156 Conservation may be considered as an extension to the basic 157 routing capabilities, and the information is therefore moved 158 to draft-ietf-manet-olsr-extensions-00.txt. 160 3. OLSR Terminology 162 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 163 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 164 this document are to be interpreted as described in RFC2119 [9]. 165 The OLSR protocol uses the following terminology, in addition to 166 the terms defined in [5]. 168 connection 170 A communication channel or medium *on the same physical 171 interface*, over which the nodes can communicate with each 172 other. 174 holding time 176 The lifetime associated with an entry in any table. An entry is 177 kept in the table for a period of time, equal to its holding 178 time. If the entry is not refreshed during this period, it is 179 removed from the table when the holding time expires. 181 multipoint relay (MPR) 183 A node which is selected by its one-hop neighbor, node X, to 184 "re-transmit" all the broadcast messages that it receives from 185 X, provided that the same message is not already received, and 186 the time to live field of the message is greater than zero. 188 multipoint relay selector (MPR selector, MS) 190 A node which has selected its one-hop neighbor, node X, as its 191 multipoint relay, will be called a multipoint relay selector 192 of node X. 194 node 196 A MANET router which implements this Optimized Link State 197 Routing protocol. 199 symmetric link 201 A bi-directional *link* between two neighbor nodes, i.e. node X 202 and node Y where both can hear each other. 204 4. Applicability Section 206 This section dictates the characteristics of the OLSR protocol as 207 specified in the Applicability Statement draft [6]. 209 4.1. Networking Context 211 OLSR is well suited to large and dense mobile networks, as the 212 optimi- zation achieved using the MPRs works well in this 213 context. The larger and more dense a network, the more 214 optimization can be achieved as compared to the normal link state 215 algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its 216 local information to route packets. 218 OLSR is well suited for networks, where the traffic is random and 219 sporadic between "several" nodes rather than being almost 220 exclusively between a small specific set of nodes. The performance 221 of the protocol, compared to a reactive protocol, is even better 222 if these [source, destination] pairs change with time [8]. Such 223 changes may initiate substantial traffic (Query flooding) in case 224 of reactive protocol, but nothing in OLSR, as the routes are 225 maintained for each known destination all the time. 227 4.2. Protocol Characteristics and Mechanisms 229 * Does the protocol provide shortest path routes ? 231 Yes. 233 * Does the protocol provide support for unidirectional links? (if 234 so, how?) 236 No. However, the use of uni-directional links may easily be 237 enabled through optional extensions to the protocol. 239 * Does the protocol require the use of tunneling? (if so, how?) 241 No. 243 * Does the protocol require using some form of source routing? (if 244 so, how?) 246 No. 248 * Does the protocol require the use of periodic messaging? (if so, 249 how?) 251 Yes. Periodically, each node in the network sends a message 252 containing the addresses of the neighbors which have selected 253 that node as a MPR. This information enables other nodes to 254 build routes to that node through the MPRs. 256 * Does the protocol require the use of reliable or sequenced packet 257 delivery? (if so, how?) 259 No. 261 * Does the protocol provide support for routing through a multi- 262 technology routing fabric? (if so, how?) 264 No. However, provisions for multiple interfaces may easily be 265 enabled through extensions to the protocol. 267 * Does the protocol provide support for multiple hosts per router? 268 (if so, how?) 270 Yes. The hosts are added to the MPR selector set of the node 271 (router), which will then announce that the hosts can be 272 reached through that node. 274 * Does the protocol support the IP addressing architecture? (if so, 275 how?) 277 Yes. Nodes are assigned and addressed by regular IP-addresses. 279 * Does the protocol require link or neighbor status sensing (if so, 280 how?) 282 Yes. The protocol requires link status sensing. This service is 283 provided by sending/receiving periodic HELLO messages to/from 284 one hop neighbors. 286 * Does the protocol depend on a central entity? (if so, how?) 288 No. 290 * Does the protocol function reactively? (if so, how?) 292 No. 294 * Does the protocol function proactively? (if so, how?) 296 Yes. Each node periodically sends information about its MPR 297 selectors, which enables the nodes to construct routes to these 298 MPR selectors through the node. 300 * Does the protocol provide loop-free routing? (if so, how?) 302 Yes. As the protocol uses a link state algorithm, routing is 303 loop-free when in a stable state. 305 * Does the protocol provide for sleep period operation? (if so, how?) 307 No. However, provisions for sleep-operation may easily be 308 enabled through extensions to the protocol. 310 * Does the protocol provide some form of security? (if so, how?) 312 No. 314 * Does the protocol provide support for utilizing multi-channel, 315 link-layer technologies? (if so, how?) 317 Yes. OLSR makes no assumptions on the underlying link-layer 318 other, than that local broadcast must be available. 320 5. Protocol Overview 322 OLSR is a proactive routing protocol for mobile ad hoc networks. 323 The protocol inherits the stability of a link state algorithm and 324 has the advantage of having routes immediately available when 325 needed due to its proactive nature. OLSR is an optimization over 326 the pure link state protocol, tailored for mobile ad hoc networks. 328 Firstly, it reduces the size of the control messages: rather than 329 declaring all links, a node declares only a subset of links with 330 its neighbors, namely the links to those nodes which are its MPR 331 selectors (see section 6 on MPRs). Secondly, OLSR minimizes 332 flooding of control traffic by using only selected nodes, called 333 MPRs, to diffuse its messages. This technique significantly 334 reduces the number of retransmissions in a flooding or broadcast 335 procedure. 337 OLSR MAY optimize the reactivity to topological changes by 338 reducing the time interval for periodic control message 339 transmission. Furthermore, as OLSR keeps the routes for all 340 destinations in the network, the protocol is beneficial for 341 traffic patterns where a large subset of nodes are communicating 342 with another large subset of nodes, and where the 343 [source,destination] pairs are changing over time. The protocol is 344 particularly suited for large and dense networks, as the 345 optimization done using the MPRs works well in this context. The 346 larger and more dense a network, the more optimization can be 347 achieved as compared to the normal link state algorithm. 349 OLSR is designed to work in a completely distributed manner and 350 does thus not depend on any central entity. The protocol does NOT 351 REQUIRE reliable transmission for control messages: each node 352 sends control messages periodically, and can therefore sustain an 353 occasional loss of some such messages. Such losses occur frequent 354 in radio networks due to collisions or other transmission problems. 356 Also, OLSR does NOT REQUIRE sequenced delivery of messages. Each 357 control message contains a sequence number which is incremented 358 for each message. Thus the recipient of a control message can 359 easily identify which information is newer - even if messages have 360 been re-ordered while in transmission. 362 Furthermore, OLSR provides support for protocol extensions such as 363 sleep mode operation, multicast-routing etc. Such extensions may be 364 introduced as additions to the protocol without breaking backwards 365 compatibility with earlier versions. 367 OLSR performs hop by hop routing, i.e. each node uses its most 368 recent local information to route a packet. Hence for OLSR to be 369 able to route packets, the frequency of control messages should be 370 tuned to the speed of the mobile nodes such that their movements 371 can be tracked by their neighborhood. 373 OLSR does NOT REQUIRE any changes to the format of IP packets. Thus 374 any existing IP stack can be used as it is: the protocol only 375 interacts with routing table management. 377 6. Multipoint Relays 379 The idea of multipoint relays is to minimize the overhead of 380 flooding messages in the network by reducing duplicate 381 retransmissions in the same region. Each node in the network 382 selects a set of nodes in its neighborhood which may retransmit 383 its messages. This set of selected neighbor nodes is called the 384 "Multipoint Relay" (MPR) set of that node. The neighbors of node N 385 which are *NOT* in its MPR set, receive and process broadcast 386 messages but do not retransmit broadcast messages received from 387 node N. 389 Each node selects its MPR set among its one hop neighbors. This 390 set is selected such that it covers (in terms of radio range) all 391 nodes that are two hops away. The neighborhood of any node N can 392 be defined as the set of nodes which have a symmetric link to 393 N. The 2-hop neighborhood of N can be defined as the set of nodes 394 which don't have a symmetric link to N but have a symmetric link 395 to the neighborhood of N. The MPR set of N, denoted as MPR(N), is 396 then an arbitrary subset of the neighborhood of N which satisfies 397 the following condition: every node in the 2-hop neighborhood of N 398 must have a symmetric link toward MPR(N). The smaller the MPR set 399 is, the more optimal is the routing protocol. [2] gives an 400 analysis and example about MPR selection algorithms. 402 Each node maintains information about a set of its neighbors. This 403 is the set of neighbors, called the "Multipoint Relay Selector 404 set" (MPR selector set), which have selected the node as a MPR. A 405 node obtains this information from the periodic HELLO messages 406 received from the neighbors. A broadcast message, intended to be 407 diffused in the whole network, coming from these MPR selector 408 neighbor nodes is assumed to be retransmitted by the node. This 409 set can change over time (i.e. when a node selects another 410 MPR-set) and is indicated by the selector nodes in their HELLO 411 messages. Each node has a specific "Multipoint relay Selector 412 Sequence Number" (MSSN) associated with this set. Whenever its MPR 413 selector set is updated, the node also increments its MSSN. 415 OLSR relies on selection of MPRs, and calculates routes through 416 these nodes. I.e. MPR nodes are selected as intermediate nodes in 417 the path between a source and a destination. To enable this, each 418 node in the network periodically broadcast the information 419 describing which neighbors have selected it as a MPR. Upon 420 receipt of this "MPR Selector" information, each node calculates 421 or updates the route to each known destination. So principally, 422 the route is a sequence of hops through the MPRs from source to 423 the destination. 425 MPRs are selected among the one hop neighbors with "symmetric" 426 i.e. bi-directional link. Therefore, selecting the route through 427 MPRs automatically avoids the problems associated with data packet 428 transfer on uni-directional links such as the problem of not 429 getting an acknowledgment for the data packets at each hop. 431 7. Protocol Functioning 433 This section describes the details of the protocol functioning. 434 This includes descriptions of the format and contents of the 435 packets being exchanged by routers, the algorithms (e.g. for 436 packet handling and routing table calculation) and suggested data 437 structures internally in each router. 439 7.1. Protocol and Port Number 441 Packages in OLSR are communicated using UDP. Port 698 has been 442 assigned by IANA for exclusive usage by the OLSR protocol. 444 7.2. Packet Format 446 OLSR communicates using an unified packet format for all data 447 related to the protocol. The purpose of this is to facilitate 448 extensibility of the protocol without breaking backwards 449 compatibility as well as to provide an easy way of piggybacking 450 different "types" of information into a single transmission. These 451 packets are embedded in UDP datagrams for transmission over the 452 network. The present draft uses IPv4 addresses. Support for IPv6 453 will be included in a future draft. 455 Each package encapsulates one or more messages. The messages share 456 a common header format, which enables nodes to correctly accept 457 and (if applicable) retransmit messages of an unknown type. 459 Messages can be flooded onto the entire network, or flooding can 460 be limited to nodes within a diameter (in terms of number of hops) 461 from the originator of the message. Thus, broadcasting a message 462 to a nodes neighborhood is just a special case of flooding. When 463 flooding any control message, duplicate retransmissions will be 464 eliminated locally (i.e. each node maintains a duplicate table to 465 prevent transmitting the same message twice) and minimized in the 466 entire network through the usage of MPRs as described in section 5 467 and 6. 469 Furthermore, a node can examine the header of a message to obtain 470 information on the distance (in terms of number of hops) to the 471 originator of the message. This feature may be useful in 472 situations where, e.g., the time information from a recieved 473 control messages is stored in a node depends on the distance to 474 the originator. 476 The basic layout of any packet in OLSR will be as follows: 478 0 1 2 3 479 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 480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 481 | Packet Length | Reserved for future use | 482 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 483 | Originator Address | 484 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 485 | Message Size | Time To Live | Hop Count | 486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 487 | Message Type | Message Sequence Number | 488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 489 | | 490 : MESSAGE : 491 | | 492 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 493 | Originator Address | 494 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 495 | Message Size | Time To Live | Hop Count | 496 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 497 | Message Type | Message Sequence Number | 498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 499 | | 500 : MESSAGE : 501 | | 502 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 503 : : 504 (etc) 506 7.2.1. Packet Header 508 Packet Length 510 The length (in bytes) of the packet 512 Reserved for future use 514 MUST be set to '0000000000000000' to be in compliance with this 515 version of the draft. 517 The sender information for a packet is obtainable from the UDP 518 header. 520 7.2.2. Message Header 522 Originator Address 524 This field contains the address of the node, which has 525 originally generated this message. This field SHOULD NOT be 526 confused with the source address from the UDP header, which is 527 changed each time to the address of the intermediate node which 528 is "re-transmitting" this message. The Originator Address field 529 MUST *NEVER* be changed in the retransmissions. 531 Message Sequence Number 533 While generating the TC message, the "originator" node will 534 assign a unique identification number to each message. This 535 number is inserted into the Sequence Number field of the 536 message. The sequence number is increased by 1 (one) for each 537 message originating from the node - "wrap-arounds" are handled 538 as described in section 10. 540 Message Size 542 This field gives the size of this message, measured from the 543 beginning of the "Message Type" field and until the beginning 544 of the next "Message Type" field (or - if there are no 545 following messages - the end of the packet). 547 Message Type 549 This field indicates which type of message are to be found in 550 the "MESSAGE" partition. Message types in the range of 0-127 are 551 reserved for messages in this draft and in 552 draft-ietf-manet-olsr-extensions-00.txt. 554 Time To Live 556 This field contains the maximum number of hops a message will 557 be retransmitted. Before a message is transmitted, the Time To 558 Live MUST be decremented by 1. When a node receives a message 559 with a Time To Live equal to 0, the message MUST NOT be 560 retransmitted under any circumstances. 562 Thus, by setting this field, the originator of a message can 563 limit the flooding radius. 565 Hop Count 567 This field will contain the number of hops a message has 568 attained. Before a message is (re-) transmitted, the Hop Count 569 MUST be incremented by 1. 571 Initially, this is set to '0' by the originator of the message. 573 Reserved 575 This field is reserved for future usage, and MUST be set to 576 '00000000' for compliance with this draft. 578 7.2.3. Packet Processing 580 Upon receiving a basic packet, the protocol parser examines each 581 of the "message headers". Based on the value of the "Message Type" 582 field, the parser can determine the faith of the message. A node 583 may receive the same message in several packets. This can happen 584 only if the message is retransmitted by two nodes in the receivers 585 neighborhood, i.e. the "Time To Live" and the "Hop Count" fields 586 in the message satisfies the following condition: 588 Time To Live + Hop Count > 1 590 Thus, to avoid re-processing of a message which was already 591 received and processed, each node maintains a Duplicate table. In 592 this table, the node records information about the most recently 593 received messages where the above condition holds. For each 594 message, satisfying the above condition, a node records a 595 "Duplicate Tuple" (D_addr, D_seq_num, D_time), where D_addr is the 596 originator address of the message, D_seq_num is the message 597 sequence number of the message and D_time specifies the time at 598 which a tuple expires and *MUST* be removed. 600 In a node, the set of Duplicate Tuples are denoted the "Duplicate 601 set". 603 Thus, upon receiving a basic packet, a node performs the following 604 tasks for each encapsulated message: 606 1. If there exists a tuple in the duplicate set, where: 608 D_addr == Originator Address, AND 610 D_seq_num == Message Sequence Number 612 then the message has already been completely processed 613 and MUST silently be ignored. 615 2. Otherwise, if the Message Type of the message is known to 616 the node, the message MUST be processed according to the 617 specifications of such message type. 619 3. Otherwise, If the Message Type of the message is not known 620 to the node, the message MUST be processed according to the 621 following algorithm: 623 3.1 If the sender of the message is not in the MPR selector 624 set of the node, the message MUST silently be dropped. 626 3.2 If the time to live of the message is less than or equal 627 to '0' (zero), the message MUST silently be dropped. 629 3.3 Otherwise, if the sender of the message is an MPR 630 selector of this node and if the time to live of the 631 message is greater than '0' (zero), the message MUST be 632 forwarded according to the following algorithm: 634 3.3.1 The time to live of the message is reduced by one. 636 3.3.2 The hop-count of the message is increased by one 638 3.3.3 An entry in the duplicate set is recorded with: 640 D_addr = originator address 642 D_seq_num = Message Sequence Number 644 D_time = current time + D_HOLD_TIME. 646 3.3.4 The message is retransmitted (Notice: The 647 remaining fields of the message header SHOULD 648 be left unmodified.) 650 Notice: known message types are *not* forwarded "blindly" by this 651 algorithm. Forwarding (and setting the correct message header in 652 the forwarded, known, message) is the responsibility of the 653 algorithm specifying how the message is to be handled. This 654 enables, e.g., a message type to be specified such that the 655 message can be modified while in transit (e.g. to reflect the 656 route the message has taken). Further, it enables that the 657 optimization through the MPRs can be bypassed: if for some reason 658 pure flooding of a message type is required (e.g. to transmit 659 control information over unidirectional links), the algorithm 660 specifying handling of these messages will simply rebroadcast 661 the message, regardless of MPR selectors. 663 Finally, notice that a message, which is to be broadcast in the 664 neighborhood, but not flooded into the entire network, (e.g. a 665 HELLO-message) is simply specified by setting the time to live to 666 '0' (zero), and that no duplicate entries are recorded for such 667 messages. 669 By defining a set of message types, which MUST be recognized by all 670 implementations of OLSR, it will be possible to extend the protocol 671 through introduction of additional message types, while still be 672 able to maintain compatibility with older implementations. The two 673 REQUIRED message types for OLSR are: 675 - HELLO-messages, performing the task of neighbor sensing. 676 - TC-messages, performing the task of MPR information declaration. 678 Extensions may e.g. be PC-messages for enabling power conservation 679 / sleep mode, multicast routing, gateway announcements, 680 auto-configuration/address assignment etc. 682 7.3. Neighbor sensing 684 7.3.1. Neighbor sensing information base 686 7.3.1.1 Neighbor information 688 A node maintains information (obtained from the HELLO messages) 689 about its one hop neighbors, the status of the link with these 690 neighbors, a list of 2-hop neighbors that these one hop neighbors 691 give access to, and an associated holding time. 693 Thus, for each neighbor, a node records a "Neighbor Tuple" 694 (N_addr, N_status, N_time) where N_addr is the address of the 695 neighbor, N_status designates the status of the link with that 696 neighbor (MPR, symmetric, heard) and N_time specifies the time at 697 which this record expires and *MUST* be removed. 699 Likewise, a node records a set of "2-hop tuples" (N_addr, 700 N_2hop_addr, N_time), describing symmetric or MPR links between 701 its neighbors and the 2-hop neighborhood. N_addr is the address of 702 a neighbor, N_2hop_addr is the address of a 2-hop neighbor and 703 N_time specifies the time at which a tuple expires and *MUST* 704 be removed. 706 In a node, the set of Neighbor Tuples are denoted the "Neighbor 707 Set" and the set of 2-hop tuples are denoted the "2-hop neighbor 708 set". 710 7.3.1.2 MPR Selector information 712 A node maintains information (obtained from the HELLO messages) 713 about the neighbors which have selected the node as a MPR. 715 Thus, a node records a MPR-selector tuple (MS_addr, MS_time), for 716 each neighbor which has selected the node as MPR. MS_addr is the 717 address of a node which has selected the node as MPR, and MS_time 718 specifies the time at which a tuple expires and *MUST* be 719 removed. 721 In a node, the set of MPR-tuples are denoted the "MPR selector 722 set" A sequence number, MSSN, is associated with this 723 set. Whenever a tuple is added or removed to this set, the MSSN is 724 incremented by 1. 726 7.3.2. HELLO message broadcast 728 Each node should detect the neighbor nodes with which it has a direct 729 and symmetric link. The uncertainties over radio propagation may 730 make some links asymmetric. Consequently, all links MUST be checked 731 in both directions in order to be considered valid. 733 To accomplish this, each node broadcasts HELLO messages, 734 containing information about neighbors and their link status. The 735 link status may either be "symmetric", "heard" (asymmetric) or 736 "MPR". "Symmetric" indicates, that the link has been verified to 737 be bi-directional, i.e. it is possible to transmit data in both 738 directions. "Heard" indicates that the node can hear HELLO 739 messages from a neighbor, but it is not confirmed that this 740 neighbor is also able to receive messages from the node. "MPR" 741 indicates, that a node is selected by the sender as a MPR. A 742 status of MPR further implies that the link is symmetric. 744 These control messages are broadcast to all one-hop neighbors, but 745 are *not relayed* to further nodes. A HELLO-message contains: 747 - a list of addresses of neighbors, to which there exists a 748 symmetric link; 750 - a list of addresses of neighbors, which have been "heard"; 752 - a list of neighbors, which have been selected as MPRs. 754 The list of neighbors in a HELLO message can be partial (e.g. due 755 to message size limitations, imposed by the network), the rule 756 being that all neighbor nodes are cited at least once within a 757 predetermined refreshing period (HELLO_INTERVAL). 759 To accommodate for the above constraints, as well as to accommodate 760 for future extensions, an approach similar to the overall packet 761 format (see section 6.1) is taken. Thus the proposed format of a 762 HELLO message is: 764 0 1 2 3 765 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 766 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 767 | Link Type | Reserved | Link Message Size | 768 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 769 | Neighbor Address | 770 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 771 | Neighbor Address | 772 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 773 : . . . : 774 : : 775 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 776 | Link Type | Reserved | Link Message Size | 777 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 778 | Neighbor Address | 779 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 780 | Neighbor Address | 781 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 782 : : 783 : : 784 (etc) 785 This is sent as the data-portion of the general packet format 786 described in 6.1, with the "Message Type" set to HELLO_MESSAGE and 787 the TTL field set to 0. 789 7.3.2.1. Description of the fields 791 MPR Sequence Number 793 This field indicates the sequence number corresponding to the 794 most recent MPR set, calculated by the sender node. 796 Link Message Size 798 The size of the link message, measured from the beginning of 799 the "Link Type" field and until the next "Link Type" field (or 800 - if there are no more link types - the end of the message). 802 Link Type 804 This field specifies the type of link the sending node has to 805 the following list of neighbors. As a minimum, the following 806 three link types are REQUIRED by OLSR: 808 - ASYM_LINK - indicating that the links between the sender 809 and the neighbors in the following list are asymmetric 810 (i.e. the neighbor is "heard"). 812 - SYM_LINK - indicating that the links between the sender 813 and the neighbors in the following list are symmetric. 815 - MPR_LINK - indicating, that the nodes in the following 816 list have been selected by the sender as MPR. 817 (Notice: this implies, that the links from the sender 818 of the HELLO and to the nodes in the list are symmetric). 820 It is possible to provide additional information by specifying 821 additional link-types, e.g. LOST_LINK - indicating that the link 822 between the sender and the neighbors in the following list has 823 been lost. Upon processing a HELLO message, a node silently 824 ignores link-types, which are unknown. 826 Reserved 828 This field is reserved for future usage, and MUST be set to 829 000000000000000000000000 for compliance with this draft. 831 Neighbor Address 833 The address of a neighbor. 835 7.3.3. HELLO message processing 837 Upon receiving a HELLO message, the node SHOULD update the 838 neighbor information corresponding to the sender node address (a 839 node may - e.g. for security reasons - wish to restrict updating 840 the neighbor-table, i.e. ignoring HELLO messages from some nodes). 842 In this section, the term "Originator Address" will be used for 843 the address of the node which sent the HELLO-message. 845 1. If there exists a neighbor tuple with N_addr = Originator 846 Address: 848 1.1 if for that tuple N_status == ASYM_LINK: 850 1.1.1 if the node finds its own address among the 851 addresses listed in the HELLO message (with Link 852 Type ASYM_LINK, SYM_LINK or MPR_LINK), it updates 853 the N_status of the tuple to SYM_LINK and sets 854 N_time = current time + NEIGHB_HOLDING_TIME. 856 1.1.2 otherwise, if the node does not find its own 857 address among the addresses listed in the HELLO 858 message, it sets N_time = current time + 859 NEIGHB_HOLDING_TIME. 861 1.2 otherwise, if for that tuple: 863 N_status == SYM_LINK OR 864 N_status == MPR_LINK 866 then: 868 1.2.1 if the node finds its own address among the addresses 869 listed in the HELLO message (with Link Type 870 ASYM_LINK, SYM_LINK or MPR_LINK), it sets N_time = 871 current time NEIGHB_HOLDING_TIME. 873 2. Otherwise, a new neighbor tuple is created with: 875 N_addr = Originator Address 877 N_status with the value of SYM_LINK if the node 878 finds its own address (with Link Type ASYM_LINK, SYM_LINK 879 or MPR_LINK) among the addresses listed in the HELLO 880 message, and to the value of ASYM_LINK otherwise 882 N_time = current time + NEIGHB_HOLD_TIME 884 The 2-hop neighbor set is updated as follows: for each 2-hop 885 neighbor address listed in the HELLO message with Link Type 886 SYM_LINK or MPR_LINK: 888 1. if a 2-hop tuple exists with: 890 N_addr == Originator Address AND 891 N_2hop_address == the address of the 2-hop neighbor, 893 then the N_time of that tuple is set to: 895 N_time = current time + NEIGHB_HOLD_TIME 897 2. otherwise a new 2-hop tuple is created with: 899 N_addr = Originator Address, 901 N_2hop_address = the address of the 2-hop neighbor, 903 N_time = current time + NEIGHB_HOLD_TIME. 905 Based on the information obtained from the HELLO messages, each 906 node construct its MPR selector set. 908 Thus, upon receiving a HELLO message, if a node finds its own 909 address in the address list with a link type of "MPR", it MUST 910 update the MPR selector set to contain updated information about 911 the sender of the HELLO message: 913 1. If a MPR selector tuple exists with: 915 MS_addr == Originator Address 917 then the expiration time of that tuple is set to: 919 MS_time = current time + NEIGHB_HOLD_TIME. 921 2. Otherwise, a new MPR selector tuple is created with: 923 MS_addr = Originator Address 925 MS_time = current time + NEIGHB_HOLD_TIME 927 2.1 MSSN is incremented by one to indicate that the MPR 928 selector table has been changed. 930 If link layer information describing connectivity to neighboring 931 nodes is available (i.e. loss of connectivity such as through 932 absence of an acknowledgment), this MAY be used in addition to 933 the information from the HELLO-messages to maintain the neighbor 934 table and the MPR selector table as described in section 7.7. 936 7.4. Multipoint relay selection 938 Each node in the network selects independently its own set of 939 MPRs. MPRs are used to flood control messages from that node into 940 the network while reducing the number of retransmissions that will 941 occur in a region. Thus, the concept of MPRs is an optimization 942 of a pure flooding mechanism. 944 The MPR set must be calculated by a node in a way such that it, 945 through the neighbors in the MPR-set, can reach all 2-hop 946 neighbors. This means that the union of the neighbor sets the MPR 947 nodes contains the entire 2-hop neighbor set. While it is not 948 essential that the MPR set is minimal, it is essential that all 949 2-hop neighbors can be reached through the selected MPR nodes. The 950 smaller a MPR-set, however, the more optimizations are achieved. 952 By default, the MPR set can coincide with the entire neighbor 953 set. This will be the case at network initialization. 955 The following specifies a proposed heuristic for selection of MPRs 956 [2]. The following terminology will be used in describing this 957 algorithm: 959 N: The net of neighbors with which there exists a 960 symmetric link. 962 N2: The set of 2-hop neighbors. This set does not contain 963 any one hop neighbors. 965 D(y): Degree of one hop neighbor node y (where y is a member 966 of N), is defined as the number of symmetric one hop 967 neighbors of node y, EXCLUDING the node performing the 968 computation and all its direct neighbors. 970 The proposed heuristic is as follows: 972 1. Start with an empty MPR set 973 2. Calculate D(y), where y is a member of N, for all nodes 974 in N. 975 3. Select as MPRs those nodes in N which provide the 976 "only path" to some nodes in N2 977 4. While there exist nodes in N2 which are not covered by MPR: 979 4.1 For each node in N, calculate the number of nodes in 980 N2 which are not yet covered by MPR and are 981 reachable through this one hop neighbor; 982 4.2 Select as a MPR that node of N which reaches the 983 maximum number of uncovered nodes in N2. In case of a 984 tie, select that node as MPR whose D(y) is greater. 986 5. As an optimization, process each node y in MPR. 987 If MPR\{y} still covers all nodes in N2, Y SHOULD be 988 removed from the MPR set. 990 After selecting the MPRs among the neighbors, the link status of 991 the corresponding one hop neighbors is changed from SYM_LINK to 992 MPR_LINK in the neighbor table. MPR_Seq_Num value in the Neighbor 993 table is also incremented by one. 994 The MPR set is re-calculated when: 996 - a change in the neighborhood is detected, i.e. either a 997 symmetric link with a neighbor is failed, or a new neighbor 998 with a symmetric link is added; or 999 - a change is detected in the 2-hop neighborhood such that 1000 a symmetric link is either detected or broken between a 1001 2-hop neighbor and a neighbor. 1003 7.5. Multipoint relay information declaration 1005 7.5.1 Topology information base 1007 Each node in the network maintains topological information about 1008 the network. This information is acquired from TC-messages and 1009 used for routing table calculations. 1011 Thus, for each destination in the network, a "Topology Tuple" 1012 (T_dest, T_last, T_seq, T_time) is recorded. T_dest is the address 1013 of a node, which may be reached in one hop from the node with the 1014 address T_last. T_seq is a sequence number, and T_time specifies 1015 the time at which this tuple expires and *MUST* be removed. 1017 In a node, the set of Topology Tuples are denoted the "Topology 1018 Set". 1020 7.5.2. TC Message Broadcast 1022 In order to build the topology information base needed, each node, 1023 which has been selected as MPR, broadcasts Topology Control (TC) 1024 messages. TC messages are flooded to all nodes in the network and 1025 take advantage of MPRs. MPRs enable a better scalability in the 1026 distribution of topology information [1]. 1028 A TC message is sent by a node in the network to declare its MPR 1029 Selector set. I.e., the TC message contains the list of neighbors 1030 which have selected the sender node as a MPR. The sequence number 1031 (MSSN) associated with this MPR selector set is also sent with the 1032 list. The list of addresses can be partial in each TC message 1033 (e.g. due to message size limitations, imposed by the network), 1034 but parsing of all TC messages describing a nodes MPR selector set 1035 MUST be complete within a certain refreshing period 1036 (TC_INTERVAL). The information diffused in the network by these TC 1037 messages will help each node to calculate its routing table. A 1038 node which has an empty MPR selector set, i.e. nobody has selected 1039 it as a MPR, MUST NOT generate any TC message. 1041 A node MAY transmit additional TC-messages to increase its 1042 reactiveness to link failures. I.e. when a change to the MPR 1043 selector set is detected and this change can be attributed to a 1044 link failure, a TC-message SHOULD be transmitted after a shorter 1045 interval than TC_INTERVAL. 1047 The proposed format of a TC message is 1049 0 1 2 3 1050 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 1051 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1052 | MSSN | Reserved | 1053 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1054 | Multipoint Relay Selector Address | 1055 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1056 | Multipoint Relay Selector Address | 1057 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1058 | ... | 1059 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1061 This is sent as the data-portion of the general message format 1062 described in 6.1, with the "Message Type" set to TC_MESSAGE. The 1063 time to live SHOULD be set to 255 (maximum value) to diffuse the 1064 message into the entire network. 1066 7.5.2.1. Description of the fields 1068 MPR Selector Sequence Number (MSSN) 1070 A sequence number is associated with the MPR selector 1071 set. Every time a node detects a change in its MPR selector 1072 set, it increments this sequence number. This number is sent in 1073 this MSSN field of the TC message to keep track of the most 1074 recent information. When a node receives a TC message, it can 1075 decide on the basis of this MPR Sequence Number, whether or not 1076 the received information about the MPR selectors of the 1077 originator node is more recent than what it already has. 1079 Multipoint Relay Selector Address (MPR-S) 1081 This field contains the address of a node, which has selected 1082 the Originator node (of the TC message) as a MPR. All 1083 addresses of the MPR selectors of the Originator node are put 1084 in the TC message. If the maximum allowed message size (as 1085 imposed by the network) is reached while there are still MPR 1086 selector addresses which which have not been inserted into the 1087 TC-message, more TC messages will be generated until the entire 1088 MPR selector set has been sent. 1090 Reserved 1092 This field is reserved for future usage, and MUST be set to 1093 '0000000000000000' for compliance with this draft. 1095 7.5.3. TC Message Processing 1097 TC messages are broadcasted and retransmitted by the MPRs in order 1098 to diffuse the messages in the entire network. 1100 In this section, the term "originator" is used to designate the 1101 node from which the message originally originated, while the term 1102 "sender" is used to designate the node from which the message was 1103 received (i.e. the "last hop" of the message). 1105 The tuples in the topology set are recorded with the topology 1106 information that is exchanged through TC messages, following the 1107 following algorithm: 1109 1. If the sender (NB: not originator) of this message is not in 1110 the neighbor set of this node, the message is discarded. 1112 2. A tuple is inserted into the duplicate table to prevent 1113 being processed again with: 1115 D_addr = originator address 1117 D_seq_num = Message Sequence 1119 D_time = current time + D_HOLD_TIME. 1121 3. If there exist some tuple in the topology set where: 1123 T_last == originator address AND 1124 T_seq > MSSN, 1126 then no further processing of this TC message is performed 1127 and the message is silently discarded (case: message 1128 received out of order). 1130 4. All tuples in the topology set where: 1132 T_last == originator address AND 1133 T_seq < MSSN 1135 are removed from the topology set. 1137 5. For each of the MPR selector address received in the TC 1138 message: 1140 5.1 If there exist some tuple in the topology set where: 1142 T_dest == MPR selector address, AND 1143 T_last == originator address, 1145 then the holding time of that tuple is set to: 1147 T_time = current time + TOP_HOLD_TIME. 1149 5.2 Otherwise, a new tuple is recorded in the topology set 1150 where: 1152 T_dest = MPR selector address, 1154 T_last = originator address, 1156 T_seq = MSSN, 1158 T_time = current time + TOP_HOLD_TIME. 1160 7.6. Routing table calculation 1162 Each node maintains a routing table which allows it to route the 1163 messages for the other destinations in the network. The routing 1164 table is based on the information contained in the neighbor set 1165 and the topology set. Therefore, if any of these tables is 1166 changed, the routing table is re-calculated to update the route 1167 information about each destination in the network. The route 1168 entries are recorded in the routing table in the following format: 1170 1. R_dest R_next R_dist 1171 2. R_dest R_next R_dist 1172 3. ,, ,, ,, 1174 Each entry in the table consists of R_dest, R_next and R_dist, 1175 which specifies that the node identified by R_dest is estimated to 1176 be R_dist hops away from the local node, and that the one hop 1177 neighbor node with address R_next is the next hop node in the route 1178 to R_dest. Entries are recorded in the table for each destination 1179 in the network for which the route is known. All the destinations 1180 for which the route is broken or partially known are not entered in 1181 the table. 1183 This routing table is updated when a change is detected in 1184 the neighbor set, or the topology set. The update of this routing 1185 information does not generate or trigger any messages to be 1186 transmitted, neither in the network, nor in the one-hop 1187 neighborhood. 1189 To construct the routing table of node X, a shortest path 1190 algorithm is run on the directed graph containing the arcs X -> Y 1191 where Y is any one hop neighbor of X (with Link Type SYM_LINK or 1192 MPR_LINK) and the arcs U -> V where there exists an entry in the 1193 topology set with V as T_dest and U as T_last. 1195 The following procedure is given as an example to calculate (or 1196 re-calculate) the routing table : 1198 1. All the entries from the routing table are removed. 1200 2. The new routing entries are added starting with the one 1201 hop neighbors (h=1) as the destination nodes. For each neighbor 1202 entry in the neighbor table, whose Link Type is SYM_LINK or 1203 MPR_LINK, a new routing entry is recorded in the routing table 1204 where R_dest and R_next are both set to the address of the 1205 neighbor and R_dist is set to 1. 1207 3. The new route entries for the destination nodes h+1 hops 1208 away are recorded in the routing table. The following procedure 1209 is executed for each value of h, starting with h=1 and 1210 incrementing it by 1 each time. The execution will stop if no 1211 new entry is recorded in an iteration. 1213 3.1 For each topology entry in the topology table, if its 1214 T_dest does not correspond to R_dest of any route entry 1215 in the routing table AND its T_last corresponds to R_dest 1216 of a route entry whose R_dist is equal to h, then a new 1217 route entry is recorded in the routing table where : 1219 - R_dest is set to T_dest; 1220 - R_next is set to R_next of the route entry whose 1221 R_dest is equal to T_last; and 1222 - R_dist is set to h+1. 1224 7.7 Link layer notification 1226 OLSR is designed not to impose or expect any specific information 1227 from the link layer. However, if information from the link-layer 1228 is available, a node MAY use this as described in this section. 1230 If link layer information describing connectivity to neighboring 1231 nodes is available (i.e. loss of connectivity such as through 1232 absence of a link layer acknowledgment), this information is 1233 used in addition to the information from the HELLO-messages to 1234 maintain the neighbor set and the MPR selector set. 1236 Subsequently, detection of a link failure through a link-layer 1237 notification may trigger additional TC-messages to increase the 1238 protocols reactiveness to link failures. I.e. when a change to the 1239 MPR selector set is detected and this change can be attributed to 1240 a link failure, a TC-message SHOULD be transmitted. 1242 Thus, upon receiving a link-layer notification that the link 1243 between a node and any neighbor is broken, the following actions 1244 are taken: 1246 1. if the link is broken to either a symmetric or asymmetric 1247 neighbor, the tuple for that neighbor is removed from the 1248 neighbor set, 1250 2. if the link is broken to a neighbor, which is selected as MPR, 1251 the tuple for that neighbor is removed from the neighbor 1252 set and the MPR set is recalculated, 1254 3. if the link is broken to a neighbor, which has selected this 1255 node as MPR, the MPR selector set is updated and a 1256 TC message SHOULD be generated. 1258 8. Packet forwarding 1260 8.1. Data packet forwarding 1262 OLSR itself does not perform packet forwarding. Rather, it 1263 maintains the routing table in the underlying operating system, 1264 which is assumed to be forwarding packets as specified in RFC1812. 1266 8.2. Control message forwarding 1268 Control messages, destined for flooding into the entire network, 1269 SHOULD be relayed by the MPR via the following rule: 1271 A node retransmits a message only when it is received from one 1272 of its MPR selector AND it is not before registered in the 1273 duplicate table AND the time to live is greater than zero. 1275 Before retransmitting, the hop count is incremented by one and the 1276 time to live is decremented by one. 1278 9. Proposed values for the constants 1280 This section list the values for the constants used in the 1281 description of the protocol. 1283 HELLO_INTERVAL = 2 seconds 1284 TC_INTERVAL = 5 seconds 1286 NEIGHB_HOLD_TIME = 3 x HELLO_INTERVAL 1287 TOP_HOLD_TIME = 3 x TC_INTERVAL 1288 D_TIME = 30 seconds 1290 HELLO_MESSAGE = 1 1291 TC_MESSAGE = 2 1293 ASYM_LINK = 1 1294 SYM_LINK = 2 1295 MPR_LINK = 3 1297 10. Sequence Numbers 1299 Sequence numbers are used in OLSR with the purpose of discarding 1300 "old" information, i.e. messages received out of order. However 1301 with a limited number of bits for representing sequence numbers, 1302 wrap-arounds (that the sequence number is incremented from the 1303 maximum possible value to zero) will occur. To prevent this from 1304 interfering with the operation of the protocol, the following 1305 MUST be observed. 1307 The term MAXVALUE designates in the following the largest possible 1308 value for a sequence number. 1310 The sequence number S1 is said to be "greater than" the sequence 1311 number S2 iff: 1313 S1-S2 < MAXVALUE/2 OR 1314 S1 < MAXVALUE/2 AND S2 > S1 + MAXVALUE/2 1316 Thus when comparing two messages, it is possible - even in the 1317 presence of wrap-around - to determine which message contains the 1318 most recent information. 1320 11. References 1322 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing 1323 reliability in cable free radio LANs: Low level forwarding in 1324 HIPERLAN. Wireless Personal Communications, 1996 1326 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An 1327 efficient technique for flooding in mobile wireless networks. 1328 INRIA research report RR-3898, 2000 1330 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN 1331 type 1, functional specifications ETS 300-652, ETSI, June 1996 1333 4. Corson et al. Internet MANET Encapsulation Protocol. Internet 1334 draft, draft-ietf-manet-imep-spec-01.txt, Work in progress. 1336 5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet 1337 draft, draft-ietf-manet-term-00.txt, work in progress. 1339 6. Corson, S., MANET Routing Protocol Applicability Statement, 1340 Internet draft, draft-ietf-manet-appl-00.txt, Work in progress. 1342 7. S. Bradner. Key words for use in RFCs to Indicate Requirement 1343 Levels. Request for Comments (Best Current Practice) 2119, 1344 Internet Engineering Task Force, March 1997. 1346 8. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc 1347 Network Protocols, INRIA research report RR-3965, 2000 1349 12. Authors' Addresses 1351 Amir Qayyum 1352 Project HIPERCOM 1353 INRIA Rocquencourt 1354 BP 105 1355 78153 Le Chesnay Cedex, France 1356 Phone: +33 1 3963 5273 1357 Email: Amir.Qayyum@inria.fr 1359 Philippe Jacquet 1360 Project HIPERCOM 1361 INRIA Rocquencourt 1362 BP 105 1363 78153 Le Chesnay Cedex, France 1364 Phone: +33 1 3963 5263 1365 Email: Philippe.Jacquet@inria.fr 1367 Anis Laouiti 1368 Project HIPERCOM 1369 INRIA Rocquencourt 1370 BP 105 1371 78153 Le Chesnay Cedex, France 1372 Phone: +33 1 3963 508832 1373 Email: Anis.Laouiti@inria.fr 1375 Laurent Viennot 1376 Project HIPERCOM 1377 INRIA Rocquencourt 1378 BP 105 1379 78153 Le Chesnay Cedex, France 1380 Phone: +33 1 3963 5225 1381 Email: Laurent.Viennot@inria.fr 1383 Paul Muhlethaler 1384 Project HIPERCOM 1385 INRIA Rocquencourt 1386 BP 105 1387 78153 Le Chesnay Cedex, France 1388 Phone: +33 1 3963 5278 1389 Email: Thomas.Clausen@inria.fr 1391 Thomas Clausen 1392 Project HIPERCOM 1393 INRIA Rocquencourt 1394 BP 105 1395 78153 Le Chesnay Cedex, France 1396 Phone: +33 1 3963 5133 1397 Email: Thomas.Clausen@inria.fr