idnits 2.17.1 draft-ietf-manet-olsr-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == It seems as if not all pages are separated by form feeds - found 0 form feeds but 27 pages 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 1 character in excess of 72. ** There is 1 instance 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. 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 (7 February 2000) is 8816 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 664 looks like a reference -- Missing reference section? '2' on line 612 looks like a reference -- Missing reference section? '3' on line 62 looks like a reference -- Missing reference section? '4' on line 251 looks like a reference -- Missing reference section? '5' on line 92 looks like a reference -- Missing reference section? '6' on line 135 looks like a reference -- Missing reference section? 'Neighbor' on line 553 looks like a reference -- Missing reference section? 'Status' on line 553 looks like a reference Summary: 8 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: 7 August 2000 Amir Qayyum 4 INRIA Rocquencourt, France 5 7 February 2000 7 Optimized Link State Routing Protocol 8 draft-ietf-manet-olsr-01.txt 10 Status of this Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC 2026 except that the right to 14 produce derivative works is not granted. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as 19 Internet-Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six 22 months and may be updated, replaced, or obsoleted by other 23 documents at any time. It is inappropriate to use Internet-Drafts 24 as reference material or to cite them other than as "work in 25 progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 Abstract 35 This document describes the Optimized Link State Routing (OLSR) 36 protocol for mobile ad hoc networks. The protocol is an 37 optimization of the pure link state algorithm tailored to the 38 requirements of a mobile wireless LAN. The key concept used in the 39 protocol is that of multipoint relays (MPRs) [1] & [2]. MPRs are 40 the selected nodes which forward the broadcast packets during the 41 flooding process. This technique substantially reduces the packet 42 overhead as compared to pure flooding mechanism where every node 43 retransmits the packet when it receives the first copy of the 44 packet. In OLSR protocol, the information flooded in the network 45 "through" these multipoint relays is also "about" the multipoint 46 relays. Hence, a second optimization is achieved here by minimizing 47 the "contents" of the control packet flooded in the network. Hence, 48 as contrary to the classic link state algorithm, only a small 49 subset of links with the neighbor nodes are declared instead of all 50 the links. This information is then used by OLSR protocol for route 51 calculation, and therefore the routes contain only the MPRs as the 52 intermediate nodes from Source to Destination. It results in 53 providing the optimal routes (in terms of number of hops), and 54 hence another optimization. The protocol is particularly suitable 55 for the large dense networks as the technique of multipoint relays 56 works well in this context. 58 1. Introduction 60 This Optimized Link State Routing protocol inherits the concept of 61 forwarding and relaying from HIPERLAN (a MAC layer protocol) which 62 is standardized by ETSI [3]. OLSR protocol is developed in the 63 IPANEMA project (part of Euclid program) and in the PRIMA project 64 (part of RNRT program). 66 This protocol is developed for the mobile adhoc networks. It 67 functions as a table driven or proactive protocol and exchanges 68 topology information with other nodes of the network at regular 69 intervals. The nodes which are selected as a multipoint relay by 70 some neighbor nodes announce this information periodically in their 71 control messages. The protocol uses the multipoint relays to do 72 efficient flooding of its control messages in the network. In route 73 calculation, these are the multipoint relays which are used to form 74 the route towards any destination in the network. 76 Multipoint relays are selected among the one hop neighbors with 77 "symmetric" i.e. bi-directional link. Therefore, selecting the 78 route through multipoint relays automatically avoids the problems 79 associated with data packet transfer on uni-directional links; like 80 the problem of getting the acknowledgement for the data packets at 81 each hop, which cannot be received if there is a uni-directional 82 link in the selected route. 84 OLSR protocol is developed to work independently. But it can be 85 modified to work with a protocol (like IMEP protocol [4]) which 86 could provide common functionalities such as neighbor sensing, 87 multipoint relaying, security authentication, etc. 89 2. OLSR terminology 91 OLSR protocol uses the following terminology, in addition to the 92 terms defined in [5]. 94 connection 96 A communication channel or medium *on the same physical 97 interface*, over which the nodes can communicate with each 98 other. 100 holding time 102 The lifetime associated to an entry in any table. That entry is 103 kept in the table for a period equal to its holding time. If the 104 entry is not refreshed during this period, it is removed from 105 the table when its holding time expires. 107 multipoint relay (MPR) 109 A node which is selected by its one-hop neighbor node X to 110 "re-transmit" all the broadcast packets that it will receive 111 from X, provided that the same packet is not already received, 112 and the hop count field of the packet is greater than zero. 114 multipoint relay selector (MPR-S) 116 A node which has selected its one-hop neighbor node X as its 117 multipoint relay will be called the multipoint relay selector of 118 node X. 120 node 122 A MANET router that implements this Optimized Link State Routing 123 protocol. 125 symmetric link 127 A bi-directional *link* (not connection) between two neighbor 128 nodes, i.e. node X and node Y, both can hear each other. This 129 bi-directional link can be a union of two oppositely-directed 130 uni-directional connections using different interfaces. 132 3. Applicability Section 134 This section dictates the characteristics of the OLSR protocol, as 135 specified in the Applicability Statement draft [6]. 137 3.1. Networking Context 139 The protocol is best suited to the large dense networks, as the 140 optimization done using the multipoint relays works well in this 141 context. More the network is dense and large, more optimization is 142 achieved as compared to the normal link state algorithm. OLSR uses 143 the hop-by-hop routing, i.e. each node uses its most recent 144 information to route the packet. So when a node is moving, its 145 speed should be such that its movement could be followed in *at 146 least* its neighborhood, to correctly route the packets to the 147 destination. 149 This protocol is best suited for the networks where the traffic is 150 random and sporadic between "several" nodes instead of being 151 between a small specific set of nodes of the network. The 152 comparative performance of the protocol with a reactive protocol is 153 still better if these [source, destination] pairs change with 154 time. These changes may initiate substantial traffic (Query flooding) 155 in case of reactive protocol, but nothing in OLSR, as the routes 156 are maintained for each known destination all the time. 158 3.2. Protocol Characteristics and Mechanisms 160 * Does the protocol provide support for unidirectional links? (if so, 161 how?) 163 No. It uses only bi-directional links (like in 802.11), but 164 these links may be composed of oppositely directed 165 uni-directional "connections". 167 * Does the protocol require the use of tunneling? (if so, how?) 169 No. 171 * Does the protocol require using some form of source routing? (if 172 so, how?) 174 No. The protocol uses hop-by-hop routing. 176 * Does the protocol require the use of periodic messaging? (if so, 177 how?) 179 Yes. Periodically, each node in the network send a message 180 containing the addresses of its neighbors who has selected that 181 node as a multipoint relay. This information helps other nodes 182 to build routes to that node through these multipoint relay 183 selectors. 185 * Does the protocol require the use of reliable or sequenced packet 186 delivery? (if so, how?) 188 No. As the packets are sent periodically, they need not be sent 189 reliably. Each packet not only contains a unique Packet Sequence 190 Number, but it also contains the sequence number for the most 191 recent information (for example "MPR Sequence Number" in the TC 192 packet), so un-sequenced delivery of packets will also not 193 create any problem. 195 * Does the protocol provide support for routing through a multi- 196 technology routing fabric? (if so, how?) 198 Yes. Each network interface is assigned a unique IP address. 200 * Does the protocol provide support for multiple hosts per router? 201 (if so, how?) 203 Yes. The concept of RID [4] may be used to associate to a single 204 RID (which can also be a unique IP address) more than one IP 205 addresses which represent different hosts associated to the 206 router. 208 * Does the protocol support the IP addressing architecture? (if so, 209 how?) 211 Yes. 213 * Does the protocol require link or neighbor status sensing (if so, 214 how?) 216 Yes. The protocol requires the link status sensing. This service 217 is provided by sending/receiving periodic HELLO messages to/from 218 one hop neighbors. 220 * Does the protocol have dependence on a central entity? (if so, 221 how?) 223 No. All the routers in the network have their own routing tables 224 and does not depend on any specific node. 226 * Does the protocol function reactively? (if so, how?) 228 No. But it decreases and increases the interval (within certain 229 limits) of sending the TC packet periodically, depending upon 230 the rate of link changes in its neighborhood. 232 * Does the protocol function proactively? (if so, how?) 234 Yes. It periodically sends the information about its multipoint 235 relay selectors, which helps other nodes to build routes to it. 237 * Does the protocol provide loop-free routing? (if so, how?) 239 As the protocol uses link state algorithm, so the routing is 240 loop-free in a stable state. 242 * Does the protocol provide for sleep period operation? (if so, how?) 244 Yes, it can provide support for sleep period operation. To 245 enable this feature, the protocol should select its multipoint 246 relays from only among the nodes which can (or agree to) store 247 its packets while it is in sleep mode. 249 * Does the protocol provide some form of security? (if so, how?) 251 No, not itself. It can use other protocols (like IMEP [4]) which 252 provide authentication and security. 254 * Does the protocol provide support for utilizing multi-channel, 255 link-layer technologies? (if so, how?) 257 Yes. Each interface has a unique IP address. 259 4. Protocol Overview 261 OLSR is a proactive routing protocol for mobile adhoc networks. 262 The protocol inherits the stability of a link state algorithm and 263 has the advantage of having the routes immediately available when 264 needed due to its proactive nature. OLSR protocol is an 265 optimization of the pure link state protocol, tailored for the 266 mobile adhoc networks. First, it reduces the size of the control 267 packets: instead of all links, it declares only a subset of links 268 with its neighbors who are its multipoint relay selectors (see 269 section 5 on Multipoint Relays). Secondly, it minimizes flooding of 270 its control traffic by using only the selected nodes, called 271 multipoint relays, to diffuse its messages. This technique 272 significantly reduces the number of retransmissions in a flooding 273 or broadcast procedure. 275 Apart from its normal periodic control messages, the protocol does 276 not generate extra control traffic in response to link failures and 277 additions. Thus it is suitable for networks with a high rate of 278 topological changes. As OLSR protocol keeps the routes for all the 279 destinations in the network so the protocol is beneficial for the 280 traffic patterns where a large subset of network nodes are 281 communicating with another large subset of nodes, and the 282 [source,destination] pairs are also changing with time. The 283 protocol is particularly suited to large and dense networks, as the 284 optimization done using the multipoint relays works well in this 285 context. More dense and large a network is, more optimization is 286 achieved as compared to the normal link state algorithm. 288 The protocol is designed to work in a completely distributed manner 289 and thus does not depend upon any central entity. The protocol does 290 not require a reliable transmission for its control messages: each 291 node sends its control messages periodically, and can therefore 292 sustain a loss of some packets from time to time, which arrives 293 very often in the radio networks due to collisions or other 294 transmission errors and problems. The protocol also does not need a 295 sequenced delivery of its messages, as each control message 296 contains a sequence number of the most recent information. So the 297 re-ordering at the receiving end can not affect the functioning of 298 the protocol. Furthermore, it provides support for the sleep mode 299 operation, which is quite advantageous for the battery operated 300 small terminals. 302 OLSR protocol does not do the source routing. Instead it performs 303 hop by hop routing, i.e. each node uses its most recent information 304 to route the packet. Hence, when a node is moving, its speed should 305 be such that its movement could be followed in at least its 306 neighborhood, to correctly route the packets to the 307 destination. 309 The protocol does not require any change in the IP format of 310 packets and classical IP stack can be used as it is, since the 311 protocol only impacts the routing table management. 313 5. Multipoint relays 315 The idea of multipoint relays is to minimize the flooding of 316 broadcast messages in the network by reducing duplicate 317 retransmissions in the same region. Each node in the network 318 selects a set of nodes in its neighborhood, which retransmit its 319 packets. This set of selected neighbor nodes is called the 320 multipoint relay (MPR) set of that node. The neighbors of node N 321 which are *NOT* in its MPR set, read and process the packet but do 322 not retransmit the broadcast message received from node N. 324 Each node selects its multipoint relay set among its one hop 325 neighbors in such a manner that it covers (in terms of radio range) 326 all the nodes that are two hops away. We define the neighborhood of 327 any node N as the set of nodes which have a symmetric link to N. We 328 define the two hop neighborhood of N as the set of nodes which 329 don't have a symmetric link to N but have a symmetric link to the 330 neighborhood of N. The multipoint relay set of N (we can call as 331 MPR(N) ) is an arbitrary subset of the neighborhood of N which 332 satisfies the following condition: every node in the two hop 333 neighborhood of N must have a symmetric link toward MPR(N). The 334 smaller the multipoint relay set is, the more optimal is the 335 routing protocol. [2] gives an analysis and example about 336 multipoint relay selection algorithms. 338 Each node has a set of its neighbors which are called the 339 "Multipoint Relay Selectors" of the node. A node obtain this 340 information from the periodic HELLO messages of its neighbors. A 341 broadcast message intended to be diffused in the whole network 342 coming from these MPR Selector neighbor nodes is assumed to be 343 retransmitted by the node. This set can change over time, which is 344 indicated by the selector nodes in their HELLO messages. Each node 345 has a specific Multipoint relay Selector Sequence Number (MSSN) 346 associated with this set. Whenever its MPR selector set is updated, 347 the node also increments its MSSN. 349 OLSR protocol relies on the selection of multipoint relays, and 350 calculates the routes to a destination through these nodes, i.e. 351 MPR nodes are selected as intermediate nodes. To implement this, 352 each node in the network periodically broadcast the information 353 describing which neighbors have selected it as a multipoint relay. 354 Upon receipt of this "MPR Selectors" information, each node 355 calculates or updates the route to each known destination. So 356 principally, the route is a sequence of hops through the multipoint 357 relays from source to the destination. 359 Multipoint relays are selected among the one hop neighbors with 360 "symmetric" i.e. bi-directional link. Therefore, selecting the 361 route through multipoint relays automatically avoids the problems 362 associated with data packet transfer on uni-directional links such 363 as the problem of getting an acknowledgement for the data packets 364 at each hop which cannot be received if there is a uni-directional 365 link in the selected route. 367 6. Protocol functioning 369 OLSR protocol carry out different functions which are required to 370 perform the task of routing. Here we discuss these functionalities 371 of the protocol. 373 6.1. Neighbor sensing 375 6.1.1. HELLO message broadcast 377 Each node must detect the neighbor nodes with which it has a direct 378 and symmetric link. The uncertainties over radio propagation may 379 make some links asymmetric. Consequently, all links must be checked 380 in both directions in order to be considered valid. 382 To accomplish this, each node periodically broadcasts its HELLO 383 messages, containing the information about its neighbors and their 384 link status. These control packets are transmitted in the broadcast 385 mode. These are received by all one-hop neighbors, but they are 386 *not relayed* to further nodes. A HELLO message contain: 388 - list of addresses of the neighbors to which there exists a 389 valid symmetric link; 390 - list of addresses corresponding to heard nodes, i.e., the 391 nodes which are heard by this node (a HELLO has been received) 392 but the link is not yet validated as symmetric 394 The list of neighbors in the HELLO packet can be partial, the rule 395 being that all neighbor nodes are cited at least once within a 396 predetermined refreshing period (HELLO_INTERVAL). 398 The proposed format of a HELLO packet is 400 0 1 2 3 401 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 402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 403 | Destination Address | 404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 405 | Source Address | 406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 407 | Packet Length | Packet Sequence Number | 408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 409 | Packet Type | Unused | MPR Sequence number | 410 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 411 | Neighbor Address | 412 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 413 | Neighbor Status | Neighbor 414 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 415 Address | Neighbor Status | 416 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 417 | ... | 418 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 420 6.1.1.1. Description of the fields 422 Destination address 424 For all the HELLO packets, this 4-bytes address field is always 425 set to the broadcast address of the network, so that when this 426 packet is transmitted, each neighbor node get this information 427 and hence update its neighbor table. 429 Source address 431 It is set to the address of the node transmitting this HELLO 432 packet. 434 Packet Length 436 This field contains the length of the HELLO packet in bytes, 437 starting from the Packet Type field, i.e., length of rest of the 438 packet. 440 Packet Sequence Number 442 While generating the HELLO packet, the node will assign a unique 443 identification number to this packet, and will put this number 444 in the Sequence Number field. This sequence number will be 445 different for all the packets originated by that node. 447 Packet Type 449 The Packet Type field is set to the HELLO_PACKET value. 451 Unused 453 This unused one byte field is reserved for the future use. 455 MPR Sequence Number 457 This field indicates the sequence number with which the most 458 recent multipoint relay set is calculated by the sender node. 460 [Neighbor Address, Neighbor Status] 462 These pairs of fields contain, one by one, all the addresses of 463 the neighbor nodes present in the neighbor table, along with 464 their link status. 466 6.1.2. HELLO message processing 468 The HELLO messages permit each node to learn the knowledge of its 469 neighborhood up to two hops. A node maintains a Neighbor table in 470 which it records the information obtained from the HELLO messages, 471 about its one hop neighbors, the status of the link with these 472 neighbors, and a list of two hop neighbors that these one hop 473 neighbors give access to. The information is recorded in the 474 Neighbor table as a neighbor entry, which may have the following 475 format to record these entries: 477 N_MPR_seq 478 1. N_addr N_status N_2hop_list N_time 479 2. N_addr N_status N_2hop_list N_time 480 3. ,, ,, ,, ,, 482 Each entry in the table consists of N_addr, N_status, N_2hop_list, 483 and N_time, which specifies that the node with address N_addr is a 484 one-hop neighbor to this node, the status of the link between them 485 is N_status, and this neighbor provides access to the two hop 486 neighbors listed in N_2hop_list. The N_status can be ASYM_LINK, 487 SYM_LINK or MPR_LINK. The link status as MPR_LINK implies that the 488 link with the neighbor node N_addr is symmetric *AND* the node 489 N_addr is selected as a multipoint relay by this node. Each 490 neighbor entry has an associated holding time N_time, upon expiry 491 of which it is no longer valid and hence removed. 493 The neighbor table also contains a sequence number N_MPR_seq which 494 specifies that the node keeping this neighbor table has selected 495 its most recent MPR set with the sequence number N_MPR_seq. Every 496 time a node selects or updates its multipoint relay set, this 497 N_MPR_seq is incremented to a higher value. 499 On reception of a HELLO message, the node updates the neighbor 500 entry corresponding to the sender node address: 502 1. If the entry already exists: 504 1.1 the holding time of the entry is refreshed to 505 NEIGHB_HOLD_TIME 506 1.2 if the node finds its own address in one of the 507 [Neighbor, Status] pairs in the HELLO message, it updates 508 the status of the link to the sender node as SYM_LINK if 509 it was ASYM_LINK before. 511 2. Otherwise a new entry is recorded in the Neighbor table with: 513 2.1 N_addr is set to the sender node address 514 2.2 N_status is set to the value of ASYM_LINK (asymmetric 515 link) 516 2.3 N_2hop_list is filled with the list of addresses 517 contained in the HELLO message in the [Neighbor, Status] 518 pairs for which the Status is *NOT* asymmetric and which 519 are not already present in the Neighbor table (i.e., they 520 are not one-hop neighbors). If a node finds its own 521 address in the [Neighbor, Status] pair, it does not 522 register itself in the N_2hop_list, and it changes the 523 link status to the sender node from ASYM_LINK to 524 SYM_LINK. 525 2.4 N_time is set to the value of NEIGHB_HOLD_TIME 527 With information obtained from the HELLO messages, each node also 528 construct its MPR Selector table, in which it puts the addresses of 529 its one hop neighbor nodes which has selected it as a multipoint 530 relay. The MPR Selector table may have the following format to 531 record the entries: 533 MSSN 534 1. MS_addr MS_seq_num MS_time 535 2. MS_addr MS_seq_num MS_time 536 3. ,, ,, ,, 538 Each entry in the table consists of MS_addr, MS_seq_num and 539 MS_time, which specifies that the node with address MS_addr has 540 selected this node as its multipoint relay with the MPR sequence 541 number equal to MS_seq_num. Each entry has an associated holding 542 time MS_time, upon expiry of which it is no longer valid and hence 543 removed. 545 A sequence number MSSN is associated to this table which specifies 546 that the multipoint relay selector set of the node keeping 547 this MPR Selector table is most recently modified with the sequence 548 number MSSN. The node modifies its MPR Selector set according to 549 the information it receives in the HELLO messages, and increment 550 this sequence number on each modification. 552 On the reception of a HELLO message, if a node finds its own 553 address in the [Neighbor, Status] pair with the Status field equal 554 to "MPR", then it updates the entry corresponding to the sender 555 node's address in the MPR Selector table: 557 1. If the entry exists already: 559 1.1 if the MPR Sequence Number field of the HELLO message is 560 greater than or equal to the MS_seq_num field of that 561 entry, then the MS_time is refreshed to NEIGHB_HOLD_TIME. 562 1.2 if the MPR Sequence Number field of the HELLO message is 563 greater than the MS_seq_num field of that entry, the 564 MS_seq_num field is updated to the value of MPR Sequence 565 Number field of the HELLO message. 567 2. Otherwise, a new entry is recorded in the MPR Selector table, 568 with: 570 2.1 MS_addr is set to the address of sender of the HELLO 571 message 572 2.2 MS_seq_num is set to the MPR Sequence Number field of the 573 HELLO message 574 2.3 MS_time is set to the value of NEIGHB_HOLD_TIME 576 6.2. Multipoint relay selection 578 Each node of the network selects independently its own set of 579 multipoint relays. Multipoint relays are used to flood the control 580 messages of that node. The MPR set is calculated in a manner to 581 contain a subset of one hop neighbors which covers all the two hop 582 neighbors. By this we mean that the union of the neighbor sets of 583 all MPRs contains the entire two hop neighbor set. In order to 584 build the list of the two hop nodes from a given node, it suffices 585 to track the list of symmetric link nodes found in the HELLO 586 packets received by this node (this two-hop neighbor information is 587 recorded in the neighbor table as N_2hop_list). Multipoint relays 588 of a given node are declared in the subsequent HELLOs transmitted 589 by this node, so that the information reaches the multipoint relays 590 themselves. These selected multipoint relays are indicated in the 591 HELLO messages with the link status as "MPR". The multipoint relay 592 set is re-calculated when: 594 - a change in the neighborhood is detected when either a 595 symmetric link with a neighbor is failed, or a new neighbor 596 with a symmetric link is added; or 597 - a change in the two-hop neighbor set with symmetric link is 598 detected. 600 The MPR set need not be optimal, however it should be small enough 601 to achieve the benefit of the multipoint relays. Multipoint relays 602 is an optimization of the pure flooding mechanism; it is not 603 essential that the multipoint relay set be minimal or optimal. But 604 it is essential that it covers the two hop nodes. By default, the 605 multipoint relay set can coincide with the whole neighbor set. This 606 will be the case at network initialization. Each node will manage a 607 dedicated sequence number in order to track the changes in its 608 multipoint relay set. This sequence number will also appear, along 609 with the MPR list, in the HELLO messages. 611 We propose here a heuristic for the selection of multipoint relays 612 [2]. We use the following terminology in describing this algorithm: 614 MPR(x): Multipoint relay set of node x which is running this 615 algorithm 616 N(x): One hop neighbor set of node x (containing only symmetric 617 neighbors) 618 N2(x): Two hop neighbor set of node x (containing only symmetric 619 neighbors of nodes in N(x) ). The two hop neighbor set 620 N2(x) of node x does not contain any one hop neighbor of 621 node x 623 D(x,y): Degree of one hop neighbor node y (where y is a member 624 of N(x) ), is defined as the number of symmetric one hop 625 neighbors of node y EXCLUDING the node x and all the 626 symmetric one hop neighbors of node x which exit also 627 in N(y), i.e., 628 D(x,y) = N(y) - x - N(x) 630 The proposed heuristic is as follows: 632 1. Start with an empty MPR(x) 633 2. Calculate D(x,y), where y is a member of N(x), for all nodes 634 in N(x) 635 3. First select as MPRs those nodes in N(x) which provide the 636 "only path" to reach some nodes in N2(x) 637 4. While there still exist some nodes in N2(x) that are not 638 covered by MPR(x): 640 4.1 For each node in N(x), calculate the number of nodes in 641 N2(x) which are not yet covered by MPR(x) and are 642 reachable through this one hop neighbor; 643 4.2 Select as a MPR that node of N(x) which reaches the 644 maximum number of uncovered nodes in N2(x). In case of a 645 tie, select that node as MPR whose D(x,y) is greater. 647 5. To optimize, remove each node in MPR(x), one at a time, and 648 check if MPR(x) still covers all nodes in N2(x) 650 After selecting the multipoint relays from among the neighbors, the 651 link status of the corresponding one hop neighbors is changed from 652 SYM_LINK to MPR_LINK in the neighbor table. MPR_Seq_Num value in 653 the Neighbor table is also incremented by one. 655 6.3. Multipoint relay information declaration 657 6.3.1. TC Packet Broadcast 659 In order to build the topology information database needed for 660 routing packets, each relay node broadcasts specific service 661 packets called Topology Control (TC) packets. TC packets are 662 forwarded like usual broadcast packets to all nodes in the network 663 and take advantage of multipoint relays. Multipoint relays enable a 664 better scalability of topology information [1]. 666 A TC message is sent by a node in the network at regular intervals 667 to declare its MPR Selector set, i.e., the message contains the 668 list of neighbors who have selected the sender node as a multipoint 669 relay. The sequence number (MSSN) associated to this multipoint 670 relay selector set is also sent with the list. The list of 671 addresses can be partial in each TC packet due to maximum size 672 limitation, but parsing must be complete within a certain 673 refreshing period (TC_INTERVAL). The information diffused in the 674 network by these TC packets will help each node to calculate its 675 routing table. A node which has an empty MPR Selector set, i.e., 676 nobody has selected it as a multipoint relay, does NOT generate the 677 TC packet. 679 The interval between the transmission of two TC packets depends 680 upon whether the MPR Selector set is changed or not, since the last 681 TC packet transmitted. If no change occur in the MPR Selector set, 682 the TC packet is sent after its normal interval (TC_INTERVAL). When 683 a change occur in the MPR Selector set, the next TC packet is sent 684 after a pre-specified minimum interval (TC_MIN_INTERVAL), 685 starting from the time the last TC packet was sent. If this much 686 time has already elapsed, the next TC packet is transmitted 687 immediately. After sending a TC packet with that minimum interval, 688 the default value for the interval again becomes the normal 689 interval (TC_INTERVAL) for sending TC packets, until the MPR 690 Selector set is changed again. 692 The proposed format of a TC packet is 694 0 1 2 3 695 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 696 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 697 | Destination Address | 698 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 699 | Source Address | 700 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 701 | Packet Length | Packet Sequence Number | 702 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 703 | Packet Type | Hop Count | MSSN | 704 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 705 | Originator Address | 706 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 707 | Multipoint Relay Selector Address | 708 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 709 | Multipoint Relay Selector Address | 710 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 711 | ... | 712 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 714 6.3.1.1. Description of the fields 716 Destination address 718 For all the TC packets, this 4-bytes address field is always 719 set to the broadcast address of the network, so that when this 720 packet is diffused in the network, every node get this 721 information and hence update its topology table. 723 Source address 725 It is set to the address of the node *transmitting* 726 this TC packet. This field should not be confused with the 727 Originator Address of the TC packet. Whenever a node 728 "re-transmit" the TC packet, this field is updated to that 729 transmitter node's address. 731 Packet Length 733 This field contains the length of the TC packet in bytes, 734 starting from the Packet Type field, i.e., the length of rest of 735 the packet. 737 Packet Sequence Number 739 While generating the TC packet, the "originator" node will 740 assign a unique identification number to this packet, and will 741 put this number in the Sequence Number field. This sequence 742 number will be different for all the packets originated by that 743 node, which will help to recognize the duplicate reception of 744 the packets. 746 Packet Type 748 The Packet Type field is set to the TC_PACKET value. 750 Hop Count 752 This field will contain the maximum number of hops a TC packet 753 can attain. Every time a TC packet is re-transmitted, this field 754 is decremented by 1. When this field reaches zero, the TC packet 755 is no more re-transmitted and is discarded. 757 MPR Selector Sequence Number (MSSN) 759 A sequence number is associated with the multipoint relay 760 selector set and every time a node detects a change in its 761 multipoint relay selector set, it increments this sequence 762 number. This number is sent in this MSSN field of the TC packet 763 to keep track of the most recent information. When a node 764 receives a TC packet, it can decide on the basis of this MPR 765 Sequence Number, whether the information about the multipoint 766 relay selectors of the originator node is more recent than that 767 it already has, or not. 769 Originator Address 771 This field contains the address of the node which has originally 772 generated this TC packet to declare its multipoint relay selector's 773 information. This field should not be confused with the Source 774 Address field, which is changed each time to the address of the 775 intermediate node which is "re-transmitting" this TC packet, 776 while the Originator Address field in never changed in the 777 retransmissions. 779 Multipoint Relay Selector Address (MPR-S) 781 This field contains the address of the node which has selected 782 the Originator node (of the TC packet) as a multipoint relay. 783 All the node addresses of the multipoint relay selectors of the 784 Originator node are put in the TC packet, one after another. If 785 the maximum allowed packet size (of IP protocol) is attained and 786 there are still some multipoint relay selector addresses which 787 remain in the MPR Selector set, then more TC packets will be 788 generated, until all addresses in the multipoint relay selector 789 set are transmitted. 791 6.3.2. TC Packet Processing 793 In OLSR protocol, TC packets are sent in broadcast and are 794 retransmitted by the selected nodes to diffuse the packet in the 795 whole network. In this process, a node may receive more than once 796 the same TC packet. To avoid the re-processing of the TC packet 797 which was already received and processed, each node maintains a 798 Duplicate table in which it records the information about the most 799 recently received TC packets. The information is recorded in the 800 Duplicate table as a Duplicate entry. The table may have 801 the following format to record these entries: 803 1. D_addr D_seq_num D_time 804 2. D_addr D_seq_num D_time 805 3. ,, ,, ,, 807 Each entry in the table consists of D_addr, D_seq_num and D_time, 808 which specifies that a TC packet was received from the node with 809 address D_addr, having the packet sequence number as D-seq_num. 810 Each Duplicate entry has an associated holding time D_time, upon 811 expiry of which it is no longer valid and hence removed. 813 On reception of a TC packet, a node checks in its Duplicate table 814 if it has already received the same packet or not. If it finds a 815 corresponding entry, the packet is discarded. Otherwise, a new 816 entry is recorded in the Duplicate table for this newly received TC 817 packet, and the packet is then processed further. When a node 818 receives a TC packet from its neighbor node with an asymmetric (or 819 uni-directional) link, it does not register the packet in the 820 Duplicate table neither it processes the packet. 822 Each node of the network maintains a topology table, in which it 823 records the information about the topology of the network obtained 824 from the TC packets. Based on this information, the routing table 825 is calculated. A node records information about the multipoint 826 relays of other nodes in the network in its topology table as a 827 topology entry, which may have the following format: 829 1. T_dest T_last T_seq T_time 830 2. T_dest T_last T_seq T_time 831 3. ,, ,, ,, ,, 833 Each entry in the table consists of T_dest, T_last, T_seq, and 834 T_time which specifies that the node T_dest has selected the node 835 T_last as a multipoint relay and that the node T_last has announced 836 this information of its multipoint relay selector set with the 837 sequence number T_seq. Therefore, the node T_dest can be reached in 838 the last hop through the node T_last. Each topology entry has an 839 associated holding time T_time, upon expiry of which it is no 840 longer valid and hence removed. 842 The entries in the topology table are recorded with the topology 843 information that is exchanged among the network nodes through TC 844 packets. Upon receipt of a TC packet, the following procedure is 845 executed to record the information in the topology table: 847 1. If there exist some entry in the topology table whose T_last 848 corresponds to the originator address of the TC packet and 849 whose T_seq is greater in value than the MSSN in the received 850 packet, then no further processing of this TC packet is done 851 and it is silently discarded (case: packet received out of 852 order). 854 2. If there exist some entry in the topology table whose T_last 855 corresponds to the originator address of the TC packet and 856 whose T_seq is lesser in value than the MSSN in the received 857 packet, then that topology entry is removed. 859 3. For each of the MPR Selector address received in the TC 860 packet: 862 3.1 If there exist some entry in the topology table whose 863 T_dest corresponds to the MPR Selector address and the 864 T_last corresponds to the originator address of the TC 865 packet, then the holding time T_time of that topology 866 entry is refreshed to TOP_HOLD_TIME. 868 3.2 Otherwise, a new topology entry is recorded in the 869 topology table whereas: 871 - T_dest is set to the MPR Selector address, 872 - T_last is set to the originator address of the TC 873 packet, 874 - T_seq is set to the value of MSSN received in the TC 875 packet, 876 - T_time is set to the value of TOP_HOLD_TIME. 878 6.4. Routing table calculation 880 Each node maintains a routing table which allows it to route the 881 packets for the other destinations in the network. The nodes which 882 receive the TC packet parse and store some of the connected pairs 883 of form [node, source] where "nodes" are identified with the 884 addresses found in the TC packet list. The routing table is built 885 from this database by tracking the connected pairs in a descending 886 order. To find a path from a given origin to a remote node R, one 887 has to find a connected pair (R,X), then a connected pair (X,Y), 888 and so forth until one finds a node Y in the neighbor set of the 889 origin. In order to restrict to optimal paths, the relay nodes will 890 consider only the connected pairs on the minimal path. This 891 selection can be done dynamically and with minimal storage 892 facilities. The sequence numbers are used to detect connected pairs 893 which have been invalidated by further topology changes. The 894 information contained in the topology database, which has not been 895 refreshed is discarded. 897 The routing table is based on the information contained in the 898 neighbor table and the topology table. Therefore, if any of these 899 tables is changed, the routing table is re-calculated to update the 900 route information about each destination in the network. The route 901 entries are recorded in the routing table in the following format: 903 1. R_dest R_next R_dist 904 2. R_dest R_next R_dist 905 3. ,, ,, ,, 907 Each entry in the table consists of R_dest, R_next and R_dist, 908 which specifies that the node identified by R_dest is estimated to 909 be R_dist hops away from the local node, and that the one hop 910 neighbor node with address R_next is the next hop node in the route 911 to R_dest. Entries are recorded in the table for each destination 912 in the network for which the route is known. All the destinations 913 for which the route is broken or partially known are not entered in 914 the table. 916 This routing table information is updated when 918 - a change in the neighborhood is detected concerning a 919 symmetric link; 920 - a route to any destination is expired (because the 921 corresponding topology entry is expired) or 922 - a better (e.g. shorter) route is found for a destination. 924 Therefore, the routing table is re-calculated locally each time the 925 neighbor table or the topology table or both are changed. The 926 update of this routing table does not generate or trigger any 927 packets to be transmitted, neither in the network, nor in the 928 one-hop neighborhood. 930 The following procedure is executed to calculate (or re-calculate) 931 the routing table : 933 1. All the entries of the routing table are removed. 935 2. The new entries are recorded in the table starting with the one 936 hop neighbors (h=1) as the destination nodes. For each neighbor 937 entry in the neighbor table, whose link status is not 938 asymmetric, a new route entry is recorded in the routing table 939 where R_dest and R_next are both set to the address of the 940 neighbor and R_dist is set to 1. 942 3. Then the new route entries for the destination nodes h+1 hops 943 away are recorded in the routing table. The following procedure 944 is executed for each value of h, starting with h=1 and 945 incrementing it by 1 each time. The execution will stop if no 946 new entry is recorded in an iteration. 948 3.1 For each topology entry in the topology table, if its 949 T_dest does not correspond to R_dest of any route entry 950 in the routing table AND its T_last corresponds to R_dest 951 of a route entry whose R_dist is equal to h, then a new 952 route entry is recorded in the routing table where : 954 - R_dest is set to T_dest; 955 - R_next is set to R_next of the route entry whose 956 R_dest is equal to T_last; and 957 - R_dist is set to h+1. 959 4. After calculating the routing table, the topology table entries 960 which are not used in calculating the routes may be removed, if 961 there is a need to save memory space. Otherwise, these entries 962 may provide multiple routes. 964 7. Packet forwarding 966 7.1. Data packet forwarding 968 Data packets are relayed on a hop by hop basis. In the source 969 router and in any intermediate router, the next hop router is 970 identified by the entry of the destination in the host routing 971 table. 973 Whenever a data packet is received to route to a destination and 974 its TTL field (in IP header) is greater than zero, the node must 975 look at the final destination field in the packet. If the route is 976 known, i.e. an entry is found in the routing table in which R_dest 977 corresponds to the final destination, then the packet is 978 transmitted to the next hop node. While forwarding a unicast 979 packet, the originator address, and the final destination address 980 of the packets are not changed. The packet traverses the 981 intermediate source and destination pair, hop by hop, until it 982 reaches its final destination. 984 7.2. Topology Control (TC) packet forwarding 986 TC packets are relayed by the multipoint relays via the 987 following rule: 989 A node retransmits a TC packet only when it receives its first 990 copy from a node which is its multipoint relay selector. 992 When a TC packet is received and its hop count is greater than 993 zero, then it is retransmitted by the multipoint relays of the 994 sender node. Before retransmitting, the hop count is decremented by 995 one. 997 8. Power Conservation or Sleep mode operation 999 Power conservation mode is very desirable for the low capacity, 1000 battery operated small terminals. With the constraint on the power 1001 consumption, nodes may wish to conserve their battery power by 1002 going into "sleep mode". The sleep mode may simply be a pause in 1003 the operation of a node, or it may be some intermittent sleep and 1004 wake periods of a node to economically use its battery resources. 1006 8.1. Sleep mode initiation 1008 When a node plans to go in sleep mode, it has to stop sending its 1009 periodic control messages: 1011 - HELLO messages: so that it is no more selected as a multipoint 1012 relay by its neighbor nodes, and 1013 - TC messages: so that it is no more used as an intermediate 1014 node while calculating a route. 1016 Then it looks its MPR Selector set. If this set is not empty, it 1017 means that some of its neighbors are using it as a multipoint 1018 relay, and secondly, other nodes of the network may calculate the 1019 route to some destinations using this node as an intermediate 1020 node. In this case, the node can not go into sleep mode immediately 1021 because it is assumed to function as a multipoint relay of some 1022 node. The node must wait until its MPR Selector set becomes 1023 empty. As the node is sending no more HELLOs, so it will not be 1024 selected as a multipoint relay further more, and hence the entries 1025 in the MPR Selector set will be expired. 1027 After terminating the transmission of its periodic messages, the 1028 node has to negotiate with its multipoint relays to keep its data 1029 packets while it is in sleep mode. The node has to keep only those 1030 MPRs in its MPR set which agree to keep its packets. 1032 To initiate the negotiation for the power conservation mode, the 1033 node has to transmit a power conservation (PC) message. This PC 1034 message is broadcast to one hop neighbors only with packet type 1035 equal to PC_PACKET. It contains the list of the MPRs of the sender 1036 node, along with the intended duration of the sleep period (in 1037 milliseconds). The Request/Reply field is set to 1 by the sender 1038 node who is requesting to keep its packets while it is in sleep 1039 mode. 1041 The proposed format of a PC packet is 1043 0 1 2 3 1044 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 1045 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1046 | Destination Address | 1047 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1048 | Source Address | 1049 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1050 | Packet Length | Packet Sequence Number | 1051 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1052 | Packet Type | Request/Reply | Sleep period (in msec) | 1053 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1054 | MPR Address | 1055 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1056 | MPR Address | 1057 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1058 | ... | 1059 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1061 When a node receives a PC message with Request/Reply field equal to 1062 1, then: 1064 1. if its MPR set contains the sender node's address, this 1065 address must be removed from the MPR set and the receiver 1066 must re-calculate its MPR set; 1067 2. if the receiver is listed as an MPR address in the PC 1068 message, it will decide if it can keep the packets for the 1069 sender node during the sleep period mentioned in the PC 1070 message: 1072 2.1 if it does not agree to keep sender node's packets, 1073 then no further processing of PC message is done; 1074 2.2 otherwise, if it agrees to keep the packets of the 1075 sender node for the intended sleep mode duration, 1076 then: 1078 2.2.1 it will add the intended sleep period time to 1079 the holding time of the entry in the MPR 1080 Selector table corresponding to the sender 1081 node's address 1082 2.2.2 it will reply to the sender node with a PC 1083 message in unicast, with the Request/Reply 1084 field set to 2. The sleep period field will 1085 be equal to that in the received PC message 1086 and there will be no list of MPR Addresses. 1088 When the node who intends to go in sleep mode receives a reply of 1089 its PC message from one or more of its MPRs, it should keep only 1090 these addresses (of the MPRs) in its neighbor table and remove all 1091 others. It can now go in sleep mode. 1093 If the node does not receive a reply after one HELLO_INTERVAL, it 1094 can re-send its PC message and wait for the reply. If still no 1095 reply is received, the node can not go in sleep mode, OR, it can go 1096 in sleep mode with a risk to loose its own packets. A "sleeping" 1097 node does not affect the routing of packets which are not destined 1098 to it. In OLSR, packets are routed hop-by-hop. So the neighbor 1099 nodes of the sleeping node will not send the packets to it, and 1100 will route the packet towards its destination according to their 1101 own most recent information. 1103 8.2. Wake up procedure 1105 8.2.1. Wake up to resume activities after sleep mode 1107 The sleeping node must wake up before the sleep period (mentioned 1108 in its PC message) expires. It should start its normal operation, 1109 i.e. sending periodic HELLO and TC messages. At the same time, it 1110 should look in its neighbor table the addresses of its MPR nodes 1111 who agreed to keep its packets. Then it should request those 1112 neighbors to send these kept packets, by sending a PC message to 1113 all of them, one after another. This PC message will have the 1114 Request/Reply field equal to zero and the sleep period equal to 1115 zero. A node who receives a PC message containing Request/Reply 1116 field equal to zero the sleep period equal to zero, should send all 1117 the packets, which it has kept for the sender node. 1119 This method of requesting its kept packets to its MPRs one by one, 1120 when a node wakes up, may avoid the high packet flow towards a node 1121 who wakes up. 1123 If a node A is keeping packets for any node B, and the intended 1124 sleep period arrives at its expiration, node A should see if the 1125 route to node B is known, i.e. if node B is alive or not. If the 1126 route is known, all the packets are send to the node B, otherwise, 1127 node A will discard all packets of node B. 1129 8.2.2. Wake up in the intermittent wake-and-sleep periods 1131 The sleeping node must wake up before the sleep period (mentioned 1132 in its PC message) expires. As the node intends to re-go into sleep 1133 mode after a small wake up period, it does not resume sending HELLO 1134 and TC packets. To collect its packets from its MPR neighbors, it 1135 will send a PC message with the Destination address set to the 1136 broadcast address, the Request/Reply field set to zero and the 1137 Sleep period field set to zero. There will be no list of MPR 1138 addresses attached to the PC packet. A node who receives this PC 1139 message will send all the packets it has kept for the sender node 1140 of the PC message. 1142 To go again into sleep mode after processing (and replying to, if 1143 necessary) the packets it receives, the node has to re-negotiate 1144 with its MPRs as mentioned in section 8.1. (Future versions of the 1145 draft may explain if sending an intermittent wake-and-sleep pattern 1146 in the first negotiation could avoid the repetitive negotiations). 1148 To end the intermittent wake-and-sleep operation, the node should 1149 follow the procedure of section 8.2.1 when it wakes up. 1151 9. Proposed values for the constants 1153 This section list the values for the constants used in the 1154 description of the protocol. 1156 HELLO_INTERVAL = 2 seconds 1157 TC_INTERVAL = 5 seconds 1158 TC_MIN_INTERVAL = 2 seconds 1160 NEIGHB_HOLD_TIME = 6 seconds 1161 TOP_HOLD_TIME = 15 seconds 1163 HELLO_PACKET = 1 1164 TC_PACKET = 2 1165 PC_PACKET = 3 1167 ASYM_LINK = 1 1168 SYM_LINK = 2 1169 MPR_LINK = 3 1171 10. References 1173 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing 1174 reliability in cable free radio LANs: Low level forwarding in 1175 HIPERLAN. Wireless Personal Communications, 1996 1177 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An 1178 efficient technique for flooding in mobile wireless networks. 1179 INRIA research report, 2000 1181 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN 1182 type 1, functional specifications ETS 300-652, ETSI, June 1996 1184 4. Corson et al. Internet MANET Encapsulation Protocol. Internet 1185 draft, draft-ietf-manet-imep-spec-01.txt, Work in progress. 1187 5. Perkins, C.E., Mobile Ad Hoc Networking Terminology, Internet 1188 draft, draft-ietf-manet-term-00.txt, work in progress. 1190 6. Corson, S., MANET Routing Protocol Applicability Statement, 1191 Internet draft, draft-ietf-manet-appl-00.txt, Work in progress. 1193 11. Authors' Addresses 1195 Amir Qayyum 1196 Project HIPERCOM 1197 INRIA Rocquencourt 1198 BP 105 1199 78153 Le Chesnay Cedex, France 1200 Phone: +33 1 3963 5273 1201 Email: Amir.Qayyum@inria.fr 1203 Philippe Jacquet 1204 Project HIPERCOM 1205 INRIA Rocquencourt 1206 BP 105 1207 78153 Le Chesnay Cedex, France 1208 Phone: +33 1 3963 5263 1209 Email: Philippe.Jacquet@inria.fr 1211 Paul Muhlethaler 1212 Project HIPERCOM 1213 INRIA Rocquencourt 1214 BP 105 1215 78153 Le Chesnay Cedex, France 1216 Phone: +33 1 3963 5278 1217 Email: Paul.Muhlethaler@inria.fr