idnits 2.17.1 draft-ietf-manet-olsr-02.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 are 55 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 331: '... The protocol MAY optimize the react...' RFC 2119 keyword, line 389: '...eighborhood of N MUST have a symmetric...' RFC 2119 keyword, line 486: '... case, the message itself MUST contain...' RFC 2119 keyword, line 496: '... MUST be set to '0000000000000000...' RFC 2119 keyword, line 534: '...he "Broadcast" field MUST be examined....' (22 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: This field contains the address of the node, which has originally generated this TC message. This field MUST not be confused with the Source Address field, which is changed each time to the address of the intermediate node which is "re-transmitting" this TC message. The Originator Address field is *never* changed in the retransmissions. -- 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 (18 July 2000) is 8682 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 899 looks like a reference -- Missing reference section? '2' on line 845 looks like a reference -- Missing reference section? '3' on line 98 looks like a reference -- Missing reference section? '4' on line 306 looks like a reference -- Missing reference section? '9' on line 147 looks like a reference -- Missing reference section? '5' on line 147 looks like a reference -- Missing reference section? '6' on line 190 looks like a reference -- Missing reference section? '8' on line 209 looks like a reference Summary: 7 errors (**), 0 flaws (~~), 2 warnings (==), 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: 18 January 2001 Amir Qayyum 4 Anis Laouiti 5 Laurent Viennot 6 Thomas Clausen 7 INRIA Rocquencourt, France 8 18 July 2000 10 Optimized Link State Routing Protocol 11 draft-ietf-manet-olsr-02.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 packets during the flooding 44 process. This technique substantially reduces the packet overhead 45 as compared to pure flooding mechanism where every node retransmits 46 the packet when it receives the first copy of the packet. In OLSR 47 protocol, the information flooded in the network "through" these 48 multipoint relays is also "about" the multipoint relays. Thus a 49 second optimization is achieved by minimizing the "contents" of the 50 control packets flooded in the network. Hence, as contrary to the 51 classic link state algorithm, only a small subset of links with the 52 neighbor nodes are declared instead of all the links. This 53 information is then used by the OLSR protocol for route 54 calculation. As a consequence hereof, the routes contain only the 55 MPRs as intermediate nodes from a Source to a Destination. OLSR 56 provides optimal routes (in terms of number of hops). The protocol 57 is particularly suitable for large and dense networks as the 58 technique of multipoint relays works well in this context. 60 Contents 62 Status of This Memo 1 64 Abstract 1 66 1. Introduction 2 67 2. Changes 3 68 3. OLSR terminology 4 69 4. Applicability Section 5 70 4.1 Networking Context 5 71 4.2 Protocol Characteristics and Mechanisms 5 72 5. Protocol Overview 7 73 6. Multipoint relays 9 74 7. Protocol functioning 10 75 7.1 Packet format 10 76 7.1.1 Packet Header 11 77 7.1.2 Extension Header 12 78 7.1.3 Packet Processing 12 79 7.2 Neighbor sensing 13 80 7.2.1 HELLO message broadcast 13 81 7.2.2 HELLO message processing 16 82 7.2.3 Link Notification 18 83 7.3 Multipoint relay selection 19 84 7.4 Multipoint relay information declaration 20 85 7.4.1 TC message broadcast 20 86 7.4.2 TC message processing 23 87 7.5 Routing table calculation 25 88 8. Packet Forwarding 27 89 8.1 Data packet forwarding 27 90 8.2 Topology Control (TC) packet forwarding 27 91 9. Proposed values for constants 27 92 10. References 28 93 11. Authors' addresses 29 94 1. Introduction 96 This Optimized Link State Routing protocol inherits the concept of 97 forwarding and relaying from HIPERLAN (a MAC layer protocol) which 98 is standardized by ETSI [3]. The OLSR protocol is developed in the 99 IPANEMA project (part of Euclid program) and in the PRIMA project 100 (part of RNRT program). 102 This protocol is developed for mobile ad hoc networks. It operates 103 as a table driven or proactive protocol and exchanges topology 104 information with other nodes of the network at regular intervals. 105 The nodes which are selected as a multipoint relay by some neighbor 106 nodes announce this information periodically in their control 107 messages. The protocol uses the multipoint relays to facilitate 108 efficient flooding of control messages in the network. In route 109 calculation, the multipoint relays are used to form the route from 110 a given node to any destination in the network. 112 Multipoint relays are selected by a node among its one hop 113 neighbors with "symmetric", i.e. bi-directional, link. Therefore, 114 selecting the route through multipoint relays automatically avoids 115 the problems associated with data packet transfer on 116 uni-directional links (such as the problem of getting the 117 acknowledgement for the data packets at each hop) 119 The OLSR protocol is developed to work independently from other 120 protocols. But it can be adapted to operate with a protocol (like 121 IMEP [4]) which could provide common functionalities such as 122 neighbor sensing, multipoint relaying, security authentication, 123 etc. 125 2. Changes 127 Major changes from version 01 to version 02 129 - Introduction of a unified packet format for encapsulation of 130 all messages being exchanged between nodes. This also serves 131 to facilitate extensions in future versions of the protocol 132 (i.e. introduction of new protocol messages) without breaking 133 backwards compatibility. 135 - Removal of "Power Conservation" from this draft. Power 136 Conservation may be considered as an extension to the basic 137 routing capabilities, and the information is therefore moved 138 to draft-ietf-manet-olsr-extensions-00.txt. 140 3. OLSR Terminology 142 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 143 "SHOULD", "SHOULD NOT", "RECCOMENDED", "MAY", and "OPTIONAL" in 144 this document are to be interpreted as described in RFC2119 [9]. 145 The OLSR protocol uses the following terminology, in addition to 146 the terms defined in [5]. 148 connection 150 A communication channel or medium *on the same physical 151 interface*, over which the nodes can communicate with each 152 other. 154 holding time 156 The lifetime associated with an entry in any table. An entry is 157 kept in the table for a period of time, equal to its holding 158 time. If the entry is not refreshed during this period, it is 159 removed from the table when the holding time expires. 161 multipoint relay (MPR) 163 A node which is selected by its one-hop neighbor, node X, to 164 "re-transmit" all the broadcast packets that it receive from X, 165 provided that the same packet is not already received, and the 166 hop count field of the packet is greater than zero. 168 multipoint relay selector (MPR-S) 170 A node which has selected its one-hop neighbor, node X, as its 171 multipoint relay, will be called the multipoint relay selector 172 of node X. 174 node 176 A MANET router which implements this Optimized Link State 177 Routing protocol. 179 symmetric link 181 A bi-directional *link* (not connection) between two neighbor 182 nodes, i.e. node X and node Y where both can hear each 183 other. This bi-directional link can be a union of two 184 oppositely-directed uni-directional connections using different 185 interfaces. 187 4. Applicability Section 189 This section dictates the characteristics of the OLSR protocol as 190 specified in the Applicability Statement draft [6]. 192 4.1. Networking Context 194 The protocol is best suited to large and dense networks, as the 195 optimization achieved using the multipoint relays works well in 196 this context. The larger and more dense a network, the more 197 optimization can be achieved as compared to the normal link state 198 algorithm. OLSR uses hop-by-hop routing, i.e. each node uses its 199 most recent information to route packets. Thus when a node is 200 moving, its speed should be such that its movement could be 201 followed in *at least* its neighborhood, in order to correctly 202 route packets to the destination. 204 This protocol is best suited for networks where the traffic is 205 random and sporadic between "several" nodes rather than being 206 almost exclusively between a small specific set of nodes in the 207 network. The performance of the protocol when comparing to a 208 reactive protocol is even better if these [source, destination] 209 pairs change with time [8]. Such changes may initiate substantial 210 traffic (Query flooding) in case of reactive protocol, but nothing 211 in OLSR, as the routes are maintained for each known destination 212 all the time. 214 4.2. Protocol Characteristics and Mechanisms 216 * Does the protocol provide support for unidirectional links? (if 217 so, how?) 219 No. It uses only bi-directional links (like in 802.11), but 220 these links may be composed of oppositely directed 221 uni-directional "connections". 223 * Does the protocol require the use of tunneling? (if so, how?) 225 No. 227 * Does the protocol require using some form of source routing? (if 228 so, how?) 230 No. The protocol uses hop-by-hop routing. 232 * Does the protocol require the use of periodic messaging? (if so, 233 how?) 235 Yes. Periodically, each node in the network send a message 236 containing the addresses of the neighbors which have selected 237 that node as a multipoint relay. This information enables other 238 nodes to build routes to that node through the multipoint 239 relays. 241 * Does the protocol require the use of reliable or sequenced packet 242 delivery? (if so, how?) 244 No. As the packets are sent periodically, they need not be sent 245 reliably. Each packet not only contains a unique Packet Sequence 246 Number, but it also contains the sequence number for the most 247 recent information (for example "MPR Sequence Number" in the TC 248 packet), so un-sequenced delivery of packets will also not 249 create any problem. 251 * Does the protocol provide support for routing through a multi- 252 technology routing fabric? (if so, how?) 254 Yes. Each network interface is assigned a unique IP address. 256 * Does the protocol provide support for multiple hosts per router? 257 (if so, how?) 259 Yes. The concept of RID [4] may be used to associate to a single 260 RID (which can also be a unique IP address) more than one IP 261 addresses which represent different hosts associated to the 262 router. 264 * Does the protocol support the IP addressing architecture? (if so, 265 how?) 267 Yes. 269 * Does the protocol require link or neighbor status sensing (if so, 270 how?) 272 Yes. The protocol requires the link status sensing. This service 273 is provided by sending/receiving periodic HELLO messages to/from 274 one hop neighbors. 276 * Does the protocol depend on a central entity? (if so, how?) 278 No. All the routers in the network have their own routing tables 279 and do not depend on any specific node. 281 * Does the protocol function reactively? (if so, how?) 283 No. But it decreases and increases the interval (within certain 284 limits) of sending the TC packet periodically, depending upon 285 the rate of link changes in its neighborhood. 287 * Does the protocol function proactively? (if so, how?) 289 Yes. It periodically sends the information about its multipoint 290 relay selectors, which helps other nodes to build routes to it. 292 * Does the protocol provide loop-free routing? (if so, how?) 294 As the protocol uses a link state algorithm, the routing is 295 loop-free when in a stable state. 297 * Does the protocol provide for sleep period operation? (if so, how?) 299 Yes, OLSR can provide support for sleep period operation. To 300 enable this feature, a node should select its multipoint relays 301 from among those neighbors which can (or agree to) store its 302 packets while it is in sleep mode. 304 * Does the protocol provide some form of security? (if so, how?) 306 No, not itself. It can use other protocols (like IMEP [4]) which 307 provide authentication and security. 309 * Does the protocol provide support for utilizing multi-channel, 310 link-layer technologies? (if so, how?) 312 Yes. Each interface has a unique IP address. 314 5. Protocol Overview 316 OLSR is a proactive routing protocol for mobile ad hoc networks. 317 The protocol inherits the stability of a link state algorithm and 318 has the advantage of having the routes immediately available when 319 needed due to its proactive nature. OLSR is an optimization over 320 the pure link state protocol, tailored for mobile ad hoc networks. 322 Firstly, it reduces the size of the control packets: rather than 323 declaring all links, a node declares only a subset of links with 324 its neighbors, namely the links to those nodes which are its 325 multipoint relay selectors (see section 6 on Multipoint Relays). 326 Secondly, OLSR minimizes flooding of control traffic by using only 327 selected nodes, called multipoint relays, to diffuse its messages. 328 This technique significantly reduces the number of retransmissions 329 in a flooding or broadcast procedure. 331 The protocol MAY optimize the reactivity to topological changes by 332 reducing the time interval for periodic control message 333 transmission. Furthermore, as OLSR protocol keeps the routes for 334 all destinations in the network, the protocol is beneficial for 335 traffic patterns where a large subset of nodes are communicating 336 with another large subset of nodes, and where the 337 [source,destination] pairs are changing over time. The protocol is 338 particularly suited for large and dense networks, as the 339 optimization done using the multipoint relays works well in this 340 context. The larger and more dense a network, the more optimization 341 can be achieved as compared to the normal link state algorithm. 343 The protocol is designed to work in a completely distributed manner 344 and thus does not depend on any central entity. The protocol does 345 NOT REQUIRE reliable transmission for control messages: each node 346 sends control messages periodically, and can therefore sustain an 347 occasional loss of some packets. Such losses occur very often in 348 the radio networks due to collisions or other transmission 349 problems. Also, the protocol does NOT REQUIRE sequenced delivery of 350 messages. Each control message contains a sequence number which is 351 incremented for each message. Thus the recipient of a control 352 packet can easily identify which information is newer - even if 353 messages have been re-ordered while in transmission. 355 Furthermore, OLSR provides support for protocol extensions such as 356 sleep mode operation, multicast-routing etc. Such extensions may be 357 introduced as additions to the protocol without breaking backwards 358 compatibility with earlier versions. 360 OLSR performs hop by hop routing, i.e. each node uses its most 361 recent information to route the packet. Hence for OLSR to be able 362 to route packets, the speed of mobile nodes should be limited such 363 that their movements can be tracked, at least by their neighborhood. 365 OLSR does NOT REQUIRE any changes to the format of IP packets. Thus 366 any existing IP stack can be used as it is: the protocol only 367 interacts with routing table management. 369 6. Multipoint Relays 371 The idea of multipoint relays is to minimize flooding of broadcast 372 messages in the network by reducing duplicate retransmissions in 373 the same region. Each node in the network selects a set of nodes in 374 its neighborhood which may retransmit its packets. This set of 375 selected neighbor nodes is called the multipoint relay (MPR) set of 376 that node. The neighbors of node N which are *NOT* in its MPR set, 377 receive and process broadcast messages but do not retransmit 378 broadcast messages received from node N. 380 Each node selects its MPR set among its one hop neighbors. This set 381 is selected such that it covers (in terms of radio range) all the 382 nodes that are two hops away. The neighborhood of any node N can be 383 defined as the set of nodes which have a symmetric link to N. The 384 two hop neighborhood of N can be defined as the set of nodes which 385 don't have a symmetric link to N but have a symmetric link to the 386 neighborhood of N. The multipoint relay set of N, denoted as MPR(N), 387 is then an arbitrary subset of the neighborhood of N which 388 satisfies the following condition: every node in the two hop 389 neighborhood of N MUST have a symmetric link toward MPR(N). The 390 smaller the multipoint relay set is, the more optimal is the 391 routing protocol. [2] gives an analysis and example about 392 multipoint relay selection algorithms. 394 Each node maintains information about a set of its neighbors. This 395 is the set of neighbors, called the "Multipoint Relay Selectors", 396 which have selected the node as a MPR. A node obtain this 397 information from the periodic HELLO messages received from the 398 neighbors. A broadcast message, intended to be diffused in the 399 whole network, coming from these MPR Selector neighbor nodes is 400 assumed to be retransmitted by the node. This set can change over 401 time (i.e. when a node selects another MPR-set) and is indicated by 402 the selector nodes in their HELLO messages. Each node has a 403 specific Multipoint relay Selector Sequence Number (MSSN) 404 associated with this set. Whenever its MPR selector set is updated, 405 the node also increments its MSSN. 407 OLSR relies on selection of multipoint relays, and calculates the 408 routes to a destination through these nodes. I.e. MPR nodes are 409 selected as intermediate nodes in the path between a source and a 410 destination. To implement this, each node in the network 411 periodically broadcast the information describing which neighbors 412 have selected it as a multipoint relay. Upon receipt of this "MPR 413 Selectors" information, each node calculates or updates the route 414 to each known destination. So principally, the route is a sequence 415 of hops through the multipoint relays from source to the 416 destination. 418 Multipoint relays are selected among the one hop neighbors with 419 "symmetric" i.e. bi-directional link. Therefore, selecting the 420 route through multipoint relays automatically avoids the problems 421 associated with data packet transfer on uni-directional links such 422 as the problem of getting an acknowledgement for the data packets 423 at each hop. 425 7. Protocol Functioning 427 In this section we describe the details of the protocol 428 functioning. This includes descriptions of the format and contents 429 of the packets being exchanged by routers, the algorithms (e.g. for 430 packet handling and routing table calculation) and suggested data 431 structures internally in each router. 433 7.1. Packet Format 435 OLSR communicates using an unified packet format for all data 436 related to the protocol. Inspired by the concept of "extension 437 headers" from IPv6, the purpose of this is to facilitate 438 extensibility of the protocol without breaking backwards 439 compatibility as well as to provide an easy way of piggybacking 440 different "types" of information into a single transmission. These 441 packets are embedded in UDP datagrams for transmission over the 442 network. 444 The basic layout of any packet in OLSR will be as follows: 446 0 1 2 3 447 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 448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 449 | Destination Address | 450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 451 | Source Address | 452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 453 | Packet Length | Reserved for future use | 454 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 455 | Message Type | Broadcast | Next Message | 456 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 457 | | 458 : : 459 : MESSAGE : 460 : : 461 | | 462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 463 | Message Type | Broadcast | Next Message | 464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 465 | | 466 : : 467 : MESSAGE : 468 : : 469 | | 470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 471 : : 472 (etc) 474 7.1.1. Packet Header 476 Destination Address 478 The address of the node(s) to receive this packet. This will 479 often be the broadcast address (i.e. all nodes in the 480 neighborhood) but may also be the unicast-address of a node. 482 Source Address 484 The address of the node which is transmitting this packet. A 485 packet may contain messages, which originate from other nodes 486 (see section 7.4). In that case, the message itself MUST contain 487 an originator address, since the source address of the packet 488 will be the address of the node retransmitting the message. 490 Packet Length 492 The length (in bytes) of the packet 494 Reserved for future use 496 MUST be set to '0000000000000000' to be in compliance with this 497 version of the draft. 499 The information in the header of this packet is equivalent to the 500 information obtainable from the UDP header. 502 7.1.2. Extension Header 504 Message Type 506 This field indicates which type of message are to be found in 507 the "MESSAGE" partition. Message types in the range of 0-127 are 508 reserved for messages in this draft and in 509 draft-ietf-manet-olsr-extensions-00.txt. 511 Broadcast 513 This field indicates to a node whether the message is meant for 514 diffusion into the entire network. This enables a node to 515 forward messages correctly, even if it doesn't recognize the 516 "Message Type". 518 Next Message 520 This field gives the offset where the next "extension header" 521 can be found, allowing a node to skip through the messages. 523 7.1.3. Packet Processing 525 Upon receiving such a basic packet, the protocol parser examines 526 each of the "extension headers". Based on the value of the "Message 527 Type" field, the parser can determine the faith of the data portion 528 of the message: 530 1. If the data are of a type which the receiving node can 531 process, then this data is processed. 533 2. Otherwise, if the "Message Type" indicates a type, unknown to 534 the node, the "Broadcast" field MUST be examined. 536 2.1 If the "Broadcast" field indicates that the message is 537 to be retransmitted (i.e. is set to 'BROADCAST'), and if 538 the recipient is a MPR of the sender, then the message 539 MUST be retransmitted by the node. 541 2.2 Otherwise, the message SHOULD silently be dropped. 543 By defining a set of message types, which MUST be recognized by all 544 implementations of OLSR, it will be possible to extend the protocol 545 through introduction of additional message types, while still be 546 able to maintain compatibility with older implementations. The two 547 REQUIRED message types for OLSR are: 549 - HELLO-messages, performing the task of neighbor sensing. 550 - TC-messages, performing the task of multipoint relay 551 information declaration. 553 Extensions may e.g. be PC-messages for enabling power conservation 554 / sleep mode, multicast routing, gateway announcements etc. 556 7.2. Neighbor sensing 558 7.2.1. HELLO message broadcast 560 Each node MUST detect the neighbor nodes with which it has a direct 561 and symmetric link. The uncertainties over radio propagation may 562 make some links asymmetric. Consequently, all links MUST be checked 563 in both directions in order to be considered valid. 565 To accomplish this, each node broadcasts HELLO messages, containing 566 information about neighbors and their link status. The link status 567 may either be "symmetric", "heard" (asymmetric) or "MPR". 568 "Symmetric" indicates, that the link has been verified to be 569 bi-directional, i.e. it is possible to transmit data in both 570 directions. "Heard" indicates that the node is hearing from a 571 neighbor, but it is not confirmed that this neighbor is also 572 hearing from the node. "MPR" indicates, that a node is selected by 573 the sender as multipoint relay. MPR status implies that the link is 574 symmetric too. 576 These control messages are broadcast to all one-hop neighbors, but 577 are *not relayed* to further nodes. A HELLO-message contains at a 578 minimum: 580 - a list of addresses of neighbors, to which there exists a 581 symmetric link; 583 - a list of addresses of neighbors, which have been "heard"; 585 - a list of neighbors, which have been selected as multipoint 586 relays. 588 The list of neighbors in a HELLO message can be partial (e.g. due 589 to message size limitations, imposed by the network), the rule 590 being that all neighbor nodes are cited at least once within a 591 predetermined refreshing period (HELLO_INTERVAL). 593 To accommodate for the above constraints, as well as to accommodate 594 for future extensions, an approach similar to the overall packet 595 format (see section 6.1) is taken. Thus the proposed format of a 596 HELLO message is: 598 0 1 2 3 599 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 600 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 601 | Message Sequence Number | MPR Sequence number | 602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 603 | Link Type | Reserved | Next Link Type | 604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 605 | Neighbor Address | 606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 607 | Neighbor Address | 608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 609 : . . . : 610 : : 611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 | Link Type | Reserved | Next Link Type | 613 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 614 | Neighbor Address | 615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 616 | Neighbor Address | 617 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 618 : : 619 : : 620 (etc) 622 This is sent as the data-portion of the general packet format 623 described in 6.1, with the "Message Type" set to HELLO_MESSAGE and 624 the broadcast field set to NO_BROADCAST. 626 7.2.1.1. Description of the fields 628 Message Sequence Number 630 While generating a HELLO message, the node will assign a unique 631 identification number to this message. This number is put into 632 the Sequence Number field. This sequence number will be 633 different for all the messages originated by that node. 635 MPR Sequence Number 637 This field indicates the sequence number corresponding to the 638 most recent multipoint relay set, calculated by the sender node. 640 Reserved 642 This field is reserved for future usage, and MUST be set to 643 00000000 for compliance with this draft. 645 Link Type 647 This field specifies the type of link the sending node has to 648 the following list of neighbors. As a minimum, the following 649 three link types are REQUIRED by OLSR: 651 - ASYM_LINK - indicating that the links between the sender 652 and the neighbors in the following list are asymmetric 653 (i.e. the neighbor is "heard"). 655 - SYM_LINK - indicating that the links between the sender 656 and the neighbors in the following list are symmetric. 658 - MPR_LINK - indicating, that the nodes in the following 659 list have been selected by the sender as multipoint 660 relays. 661 (Notice: this implies, that the links from the sender 662 of the HELLO and to the nodes in the list are symmetric). 664 It is possible to provide additional information by specifying 665 additional link-types, e.g. LOST_LINK - indicating that the link 666 between the sender and the neighbors in the following list has 667 been lost. 669 Neighbor Address 671 The address of a neighbor. 673 7.2.2. HELLO message processing 675 The HELLO messages permit each node to acquire information about 676 its neighborhood up to two hops. A node maintains a Neighbor table 677 in which it records the information (obtained from the HELLO 678 messages) about its one hop neighbors, the status of the link with 679 these neighbors, and a list of two hop neighbors that these one hop 680 neighbors give access to. The information is recorded in the 681 Neighbor table as a neighbor entry, which may have the following 682 format: 684 N_MPR_seq 686 1. N_addr N_status N_2hop_list N_time 687 2. N_addr N_status N_2hop_list N_time 688 3. ,, ,, ,, ,, 690 Each entry in the table consists of N_addr, N_status, N_2hop_list, 691 and N_time. This specifies that the node with address N_addr is a 692 one-hop neighbor to this node, the status of the link between them 693 is N_status, and this neighbor provides access to the two hop 694 neighbors listed in N_2hop_list. The N_status can be ASYM_LINK, 695 SYM_LINK or MPR_LINK. A link status of MPR_LINK implies that the 696 link with the neighbor node N_addr is symmetric *AND* the node 697 N_addr is selected as a multipoint relay by this node. Each 698 neighbor entry has an associated holding time N_time, upon 699 expiration of which it is no longer valid and hence MUST be 700 removed. 702 The neighbor table also contains a sequence number N_MPR_seq. This 703 specifies that the node keeping this neighbor table has selected 704 its most recent MPR set with the sequence number N_MPR_seq. Every 705 time a node selects or updates its multipoint relay set, N_MPR_seq 706 is incremented to a higher value. This number is put into the HELLO 707 messages as described in 6.2.1. 709 Upon receiving a HELLO message, the node updates the neighbor entry 710 corresponding to the sender node address: 712 1. If the entry already exists: 714 1.1 the holding time of the entry is refreshed to 715 NEIGHB_HOLD_TIME 717 1.2 if the node finds its own address among the addresses 718 listed in the HELLO message, it updates the status of the 719 link to the sender node as SYM_LINK if it was ASYM_LINK 720 before. 722 1.3 the N_2hop_list of the entry is updated to reflect the 723 contents of the HELLO-message. 725 2. Otherwise, a new entry is recorded in the Neighbor table with: 727 2.1 N_addr is set to the address of the sender node 729 2.2 N_status is set to the value of ASYM_LINK (asymmetric 730 link) 732 2.3 N_2hop_list is filled with the list of addresses 733 contained in the HELLO message which have a link type of 734 SYM_LINK or MPR_LINK, and which are not already present 735 in the Neighbor table (i.e., they are not one-hop 736 neighbors). 738 If a node finds its own address in a HELLO message with a 739 link type of ASYM_LINK, SYM_LINK or MPR_LINK, it does not 740 register itself in the N_2hop_list. Rather, it changes 741 the link status to the sender of the HELLO from ASYM_LINK 742 to SYM_LINK. 744 2.4 N_time is set to the value of NEIGHB_HOLD_TIME 746 Based on the information obtained from the HELLO messages, each 747 node construct its MPR Selector table. In this table, the node 748 registers the addresses of those one hop neighbor nodes which have 749 selected the node as a multipoint relay. The MPR Selector table may 750 have the following format: 752 MSSN 753 1. MS_addr MS_seq_num MS_time 754 2. MS_addr MS_seq_num MS_time 755 3. ,, ,, ,, 757 Each entry in the table consists of MS_addr, MS_seq_num and 758 MS_time, which specifies that the node with address MS_addr has 759 selected this node as its multipoint relay with the MPR sequence 760 number equal to MS_seq_num. Each entry has an associated holding 761 time MS_time, upon expiation of which it is no longer valid and 762 hence removed. 764 A sequence number, MSSN, is associated with this table. This number 765 specifies that the multipoint relay selector set of the node 766 keeping this MPR Selector table is most recently modified with the 767 sequence number MSSN. The node modifies its MPR Selector set 768 according to the information it receives in the HELLO messages, and 769 increment this sequence number upon each modification. 771 Upon receiving a HELLO message, if a node finds its own address in 772 the the address list with a link type of "MPR", it MUST update the 773 entry corresponding to the sender node's address in the MPR 774 Selector table: 776 1. If the entry already exists: 778 1.1 if the MPR Sequence Number field of the HELLO message is 779 greater than or equal to the MS_seq_num field of the 780 entry in the table, then the MS_time is refreshed to 781 NEIGHB_HOLD_TIME. 783 1.2 if the MPR Sequence Number field of the HELLO message is 784 greater than the MS_seq_num field of that entry, the 785 MS_seq_num field is updated to the value of MPR Sequence 786 Number field of the HELLO message. 788 2. Otherwise, a new entry is recorded in the MPR Selector table, 789 with: 791 2.1 MS_addr is set to the address of sender of the HELLO 792 message 794 2.2 MS_seq_num is set to the MPR Sequence Number field of the 795 HELLO message 797 2.3 MS_time is set to the value of NEIGHB_HOLD_TIME 799 7.2.3. Link Notification 801 If link layer information describing connectivity to neighboring 802 nodes is available (i.e. loss of connectivity such as through 803 absence of an acknowledgment), this SHOULD be used in addition to 804 the information from the HELLO-messages to maintain the neighbor 805 table and the MPR selector table. 807 7.3. Multipoint relay selection 809 Each node in the network selects independently its own set of 810 multipoint relays. Multipoint relays are used to flood the control 811 messages of that node into the network. The MPR set is calculated 812 in a way such that it contains a subset of one hop neighbors which 813 covers all the two hop neighbors. This means, that the union of the 814 neighbor sets of all MPRs contains the entire two hop neighbor 815 set. In order to build the list of the two hop nodes from a given 816 node, it suffices to track the list of symmetric link nodes found 817 in the HELLO messages received by this node (this two-hop neighbor 818 information is recorded in the neighbor table as 819 N_2hop_list). Multipoint relays of a given node are declared in the 820 subsequent HELLOs transmitted by this node, so that the information 821 reaches the multipoint relays themselves. These selected multipoint 822 relays are indicated in the HELLO messages with a link status of 823 "MPR". The multipoint relay set is re-calculated when: 825 - a change in the neighborhood is detected, i.e. either a 826 symmetric link with a neighbor is failed, or a new neighbor 827 with a symmetric link is added; or 828 - a change is detected in the two-hop neighborhood such that 829 a symmetric link is either detected or broken between a 830 two-hop neighbor and a neighbor. 832 The MPR set needs not be optimal. However it SHOULD be small enough 833 to achieve the benefit of the multipoint relays. The concept of 834 multipoint relays is an optimization of a pure flooding mechanism. 835 It is not essential that the multipoint relay set be minimal or 836 optimal. But it is essential that all two-hop neighbors can be 837 reached through the selected MPR's. By default, the multipoint 838 relay set can coincide with the entire neighbor set. This will be 839 the case at network initialization. Each node will manage a 840 dedicated sequence number in order to track the changes in its 841 multipoint relay set. This sequence number will also appear, along 842 with the MPR list, in the HELLO messages. 844 We propose a heuristic for the selection of multipoint relays 845 [2]. We use the following terminology in describing this algorithm: 847 MPR(x): Multipoint relay set of node x which is running this 848 algorithm 849 N(x): One hop neighbor set of node x (containing only symmetric 850 neighbors) 852 N2(x): Two hop neighbor set of node x (containing only symmetric 853 neighbors of nodes in N(x) ). The two hop neighbor set 854 N2(x) of node x does not contain any one hop neighbor of 855 node x 857 D(x,y): Degree of one hop neighbor node y (where y is a member 858 of N(x) ), is defined as the number of symmetric one hop 859 neighbors of node y EXCLUDING the node x and all the 860 symmetric one hop neighbors of node x which exit also 861 in N(y), i.e., 862 D(x,y) = N(y) - x - N(x) 864 The proposed heuristic is as follows: 866 1. Start with an empty MPR(x) 867 2. Calculate D(x,y), where y is a member of N(x), for all nodes 868 in N(x) 869 3. First select as MPRs those nodes in N(x) which provide the 870 "only path" to reach some nodes in N2(x) 871 4. While there still exist some nodes in N2(x) that are not 872 covered by MPR(x): 874 4.1 For each node in N(x), calculate the number of nodes in 875 N2(x) which are not yet covered by MPR(x) and are 876 reachable through this one hop neighbor; 877 4.2 Select as a MPR that node of N(x) which reaches the 878 maximum number of uncovered nodes in N2(x). In case of a 879 tie, select that node as MPR whose D(x,y) is greater. 881 5. To optimize, remove each node in MPR(x), one at a time, and 882 check if MPR(x) still covers all nodes in N2(x) 884 After selecting the multipoint relays among the neighbors, the link 885 status of the corresponding one hop neighbors is changed from 886 SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in 887 the Neighbor table is also incremented by one. 889 7.4. Multipoint relay information declaration 891 7.4.1. TC Message Broadcast 893 In order to build the topology information database needed for 894 routing the packets, each relay node broadcasts specific service 895 messages called Topology Control (TC) messages. TC messages are 896 forwarded, like usual broadcast messages, to all nodes in the 897 network and take advantage of multipoint relays. Multipoint relays 898 enable a better scalability in the distribution of topology 899 information [1]. 901 A TC message is sent by a node in the network to declare its MPR 902 Selector set. I.e., the TC message contains the list of neighbors 903 which have selected the sender node as a multipoint relay. The 904 sequence number (MSSN) associated with this multipoint relay 905 selector set is also sent with the list. The list of addresses can 906 be partial in each TC message (e.g. due to message size 907 limitations, imposed by the network), but parsing of all TC 908 messages describing a nodes MPR selector set MUST be complete 909 within a certain refreshing period (TC_INTERVAL). The information 910 diffused in the network by these TC messages will help each node to 911 calculate its routing table. A node which has an empty MPR Selector 912 set, i.e. nobody has selected it as a multipoint relay, MUST NOT 913 generate any TC message. 915 A node MAY transmit additional TC-messages to increase its 916 reactiveness to link failures. I.e. when a change to the MPR 917 selector set is detected and this change can be attributed to a 918 link failure, a TC-message MAY be transmitted after a shorter 919 interval than TC_INTERVAL. 921 The proposed format of a TC message is 923 0 1 2 3 924 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 925 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 926 | Message Sequence Number | MSSN | 927 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 928 | Hop Count | Unused | 929 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 930 | Originator Address | 931 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 932 | Multipoint Relay Selector Address | 933 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 934 | Multipoint Relay Selector Address | 935 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 936 | ... | 937 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 939 This is sent as the data-portion of the general message format 940 described in 6.1, with the "Message Type" set to TC_MESSAGE and 941 the broadcast field set to BROADCAST. 943 7.4.1.1. Description of the fields 945 Message Sequence Number 947 While generating the TC message, the "originator" node will 948 assign a unique identification number to this message, and will 949 put this number in the Sequence Number field. This sequence 950 number will be different for all messages originated by that 951 node, and will be used to recognize duplicate reception of 952 messages. 954 MPR Selector Sequence Number (MSSN) 956 A sequence number is associated with the multipoint relay 957 selector set. Every time a node detects a change in its 958 multipoint relay selector set, it increments this sequence 959 number. This number is sent in this MSSN field of the TC message 960 to keep track of the most recent information. When a node 961 receives a TC message, it can decide on the basis of this MPR 962 Sequence Number, whether or not the received information about 963 the multipoint relay selectors of the originator node is more 964 recent than what it already has. 966 Hop Count 968 This field will contain the maximum number of hops a TC message 969 can attain. Every time a TC message is re-transmitted, this 970 field is decremented by 1. When this field reaches zero, the TC 971 message is no more re-transmitted and is discarded. 973 Originator Address 975 This field contains the address of the node, which has 976 originally generated this TC message. This field MUST not be 977 confused with the Source Address field, which is changed each 978 time to the address of the intermediate node which is 979 "re-transmitting" this TC message. The Originator Address field 980 is *never* changed in the retransmissions. 982 Multipoint Relay Selector Address (MPR-S) 984 This field contains the address of a node, which has selected 985 the Originator node (of the TC message) as a multipoint relay. 986 All addresses of the multipoint relay selectors of the 987 Originator node are put in the TC message. If the maximum 988 allowed message size (as imposed by the network) is reached 989 while there are still multipoint relay selector addresses which 990 which have not been inserted into the TC-message, more TC 991 messages will be generated until the entire MPR selector set has 992 been sent. 994 7.4.2. TC Message Processing 996 In the OLSR protocol, TC messages are broadcasted and are 997 retransmitted by the multipoint relays in order to diffuse the 998 messages in the entire network. In this process, a node MAY receive 999 the same TC message more than once. To avoid re-processing of a TC 1000 message which was already received and processed, each node 1001 maintains a Duplicate table. In this table, the node records 1002 information about the most recently received TC messages. The 1003 information is recorded in the Duplicate table as Duplicate 1004 entries. 1006 The table may have the following format: 1008 1. D_addr D_seq_num D_time 1009 2. D_addr D_seq_num D_time 1010 3. ,, ,, ,, 1012 Each entry in the table consists of D_addr, D_seq_num and D_time, 1013 which specifies that a TC message was received from the node with 1014 address D_addr, having the message sequence number as D-seq_num. 1015 Each Duplicate entry also has an associated holding time D_time, 1016 upon expiration of which it is no longer valid and hence MUST be 1017 removed. 1019 Upon receiving a TC message, a node checks in its Duplicate table 1020 to see if it has already received the same message. If it finds a 1021 corresponding entry, the message is discarded. Otherwise, a new 1022 entry is recorded in the Duplicate table for this newly received TC 1023 message, and the message is processed. When a node receives a TC 1024 message from a neighbor node with which it has an asymmetric (or 1025 uni-directional) link, it neither registers the message in the 1026 Duplicate table nor it processes the message. 1028 Each node in the network maintains a topology table, in which it 1029 records the information about the topology of the network as 1030 obtained from the TC messages. Based on this information, the 1031 routing table is calculated. A node records information about the 1032 multipoint relays of other nodes in the network in its topology 1033 table as a topology entry, which may have the following format: 1035 1. T_dest T_last T_seq T_time 1036 2. T_dest T_last T_seq T_time 1037 3. ,, ,, ,, ,, 1039 Each entry in the table consists of T_dest, T_last, T_seq, and 1040 T_time, which specifies that the node T_dest has selected the node 1041 T_last as a multipoint relay and that the node T_last has announced 1042 this information of its multipoint relay selector set with the 1043 sequence number T_seq. Therefore, the node T_dest can be reached in 1044 the last hop through the node T_last. Each topology entry has an 1045 associated holding time T_time, upon expiration of which it is no 1046 longer valid and hence MUST be removed. 1048 The entries in the topology table are recorded with the topology 1049 information that is exchanged through TC messages. 1051 Upon receiving 1052 a TC message, the following procedure is executed to record the 1053 information in the topology table: 1055 1. If there exist some entry in the topology table whose T_last 1056 corresponds to the originator address of the TC message and 1057 whose T_seq is greater in value than the MSSN in the received 1058 message, then no further processing of this TC message is 1059 performed and it is silently discarded (case: message 1060 received out of order). 1062 2. If there exist some entry in the topology table whose T_last 1063 corresponds to the originator address of the TC message and 1064 whose T_seq is lesser in value than the MSSN in the received 1065 message, then that topology entry is removed. 1067 3. For each of the MPR Selector address received in the TC 1068 message: 1070 3.1 If there exist some entry in the topology table whose 1071 T_dest corresponds to the MPR Selector address and the 1072 T_last corresponds to the originator address of the TC 1073 message, then the holding time T_time of that topology 1074 entry is refreshed to TOP_HOLD_TIME. 1076 3.2 Otherwise, a new topology entry is recorded in the 1077 topology table whereas: 1079 - T_dest is set to the MPR Selector address, 1080 - T_last is set to the originator address of the TC 1081 message, 1082 - T_seq is set to the value of MSSN received in the TC 1083 message, 1084 - T_time is set to the value of TOP_HOLD_TIME. 1086 7.5. Routing table calculation 1088 Each node maintains a routing table which allows it to route the 1089 messages for the other destinations in the network. The nodes which 1090 receive TC messages parse and store some of the connected pairs of 1091 form [node, source] where "nodes" are identified with the addresses 1092 found in the TC message. The routing table is built from this 1093 database by tracking the connected pairs in a descending order. To 1094 find a path from a given origin to a remote node R, one has to find 1095 a connected pair (R,X), then a connected pair (X,Y), and so forth 1096 until one finds a node Y in the neighbor set of the origin. In 1097 order to restrict to optimal paths, the relay nodes will consider 1098 only the connected pairs on the minimal path. This selection can be 1099 done dynamically and with minimal storage facilities. The sequence 1100 numbers are used to detect connected pairs which have been 1101 invalidated by further topology changes. The information contained 1102 in the topology database, which has not been refreshed is 1103 discarded. 1105 The routing table is based on the information contained in the 1106 neighbor table and the topology table. Therefore, if any of these 1107 tables is changed, the routing table is re-calculated to update the 1108 route information about each destination in the network. The route 1109 entries are recorded in the routing table in the following format: 1111 1. R_dest R_next R_dist 1112 2. R_dest R_next R_dist 1113 3. ,, ,, ,, 1115 Each entry in the table consists of R_dest, R_next and R_dist, 1116 which specifies that the node identified by R_dest is estimated to 1117 be R_dist hops away from the local node, and that the one hop 1118 neighbor node with address R_next is the next hop node in the route 1119 to R_dest. Entries are recorded in the table for each destination 1120 in the network for which the route is known. All the destinations 1121 for which the route is broken or partially known are not entered in 1122 the table. 1124 This routing table information is updated when 1125 - a change in the neighborhood is detected concerning a 1126 symmetric link; 1127 - a route to any destination is expired (because the 1128 corresponding topology entry is expired) or 1129 - a better (e.g. shorter) route is found for a destination. 1131 Therefore, the routing table is re-calculated locally each time the 1132 neighbor table or the topology table (or both) are changed. The 1133 update of this routing table does not generate or trigger any 1134 messages to be transmitted, neither in the network, nor in the 1135 one-hop neighborhood. 1137 The following procedure is executed to calculate (or re-calculate) 1138 the routing table : 1140 1. All the entries of the routing table are removed. 1142 2. The new entries are recorded in the table starting with the one 1143 hop neighbors (h=1) as the destination nodes. For each neighbor 1144 entry in the neighbor table, whose link status is not 1145 asymmetric, a new route entry is recorded in the routing table 1146 where R_dest and R_next are both set to the address of the 1147 neighbor and R_dist is set to 1. 1149 3. Then the new route entries for the destination nodes h+1 hops 1150 away are recorded in the routing table. The following procedure 1151 is executed for each value of h, starting with h=1 and 1152 incrementing it by 1 each time. The execution will stop if no 1153 new entry is recorded in an iteration. 1155 3.1 For each topology entry in the topology table, if its 1156 T_dest does not correspond to R_dest of any route entry 1157 in the routing table AND its T_last corresponds to R_dest 1158 of a route entry whose R_dist is equal to h, then a new 1159 route entry is recorded in the routing table where : 1161 - R_dest is set to T_dest; 1162 - R_next is set to R_next of the route entry whose 1163 R_dest is equal to T_last; and 1164 - R_dist is set to h+1. 1166 4. After calculating the routing table, the topology table entries 1167 which are not used in calculating the routes MUST be removed, if 1168 there is a need to save memory space. Otherwise, these entries 1169 may provide multiple routes. 1171 8. Packet forwarding 1173 8.1. Data packet forwarding 1175 Data packets are relayed on a hop by hop basis. In the source 1176 router and in any intermediate router, the next hop router is 1177 identified by the entry of the destination in the host routing 1178 table. 1180 Whenever a data packet is received to route to a destination and 1181 its TTL field (in IP header) is greater than zero, the node MUST 1182 examine the final destination field in the packet. If the route is 1183 known, i.e. an entry is found in the routing table in which R_dest 1184 corresponds to the final destination, then the packet is 1185 transmitted to the next hop node. While forwarding a unicast 1186 packet, the originator address, and the final destination address 1187 of the packets are not changed. The packet traverses the 1188 intermediate source and destination pairs, hop by hop, until it 1189 reaches its final destination. 1191 8.2. Topology Control (TC) packet forwarding 1193 TC packets are relayed by the multipoint relays via the following 1194 rule: 1196 A node retransmits a TC packet only when it receives its first 1197 copy from a node which is its multipoint relay selector. 1199 When a TC packet is received with a hop count is greater than zero, 1200 then it is retransmitted by the multipoint relays of the sender 1201 node. Before retransmitting, the hop count is decremented by one. 1203 9. Proposed values for the constants 1205 This section list the values for the constants used in the 1206 description of the protocol. 1208 HELLO_INTERVAL = 2 seconds 1209 TC_INTERVAL = 5 seconds 1210 TC_MIN_INTERVAL = 2 seconds 1212 NEIGHB_HOLD_TIME = 6 seconds 1213 TOP_HOLD_TIME = 15 seconds 1214 HELLO_PACKET = 1 1215 TC_PACKET = 2 1217 ASYM_LINK = 1 1218 SYM_LINK = 2 1219 MPR_LINK = 3 1221 10. References 1223 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing 1224 reliability in cable free radio LANs: Low level forwarding in 1225 HIPERLAN. Wireless Personal Communications, 1996 1227 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An 1228 efficient technique for flooding in mobile wireless networks. 1229 INRIA research report RR-3898, 2000 1231 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN 1232 type 1, functional specifications ETS 300-652, ETSI, June 1996 1234 4. Corson et al. Internet MANET Encapsulation Protocol. Internet 1235 draft, draft-ietf-manet-imep-spec-01.txt, Work in progress. 1237 5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet 1238 draft, draft-ietf-manet-term-00.txt, work in progress. 1240 6. Corson, S., MANET Routing Protocol Applicability Statement, 1241 Internet draft, draft-ietf-manet-appl-00.txt, Work in progress. 1243 7. S. Bradner. Key words for use in RFCs to Indicate Requirement 1244 Levels. Request for Comments (Best Current Practice) 2119, 1245 Internet Engineering Task Force, March 1997. 1247 8. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc 1248 Network Protocols, INRIA research report RR-3965, 2000 1250 12. Authors' Addresses 1252 Amir Qayyum 1253 Project HIPERCOM 1254 INRIA Rocquencourt 1255 BP 105 1256 78153 Le Chesnay Cedex, France 1257 Phone: +33 1 3963 5273 1258 Email: Amir.Qayyum@inria.fr 1260 Philippe Jacquet 1261 Project HIPERCOM 1262 INRIA Rocquencourt 1263 BP 105 1264 78153 Le Chesnay Cedex, France 1265 Phone: +33 1 3963 5263 1266 Email: Philippe.Jacquet@inria.fr 1268 Anis Laouiti 1269 Project HIPERCOM 1270 INRIA Rocquencourt 1271 BP 105 1272 78153 Le Chesnay Cedex, France 1273 Phone: +33 1 3963 5278 1274 Email: Anis.Laouiti@inria.fr 1276 Laurent Viennot 1277 Project HIPERCOM 1278 INRIA Rocquencourt 1279 BP 105 1280 78153 Le Chesnay Cedex, France 1281 Phone: +33 1 3963 5278 1282 Email: Laurent.Viennot@inria.fr 1284 Thomas Clausen 1285 Project HIPERCOM 1286 INRIA Rocquencourt 1287 BP 105 1288 78153 Le Chesnay Cedex, France 1289 Phone: +33 1 3963 5278 1290 Email: Thomas.Clausen@inria.fr