idnits 2.17.1 draft-perkins-manet-mprf-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The 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 106: '... header MUST be set to 1, and the de...' RFC 2119 keyword, line 109: '... they MAY be addressed to the "All-M...' RFC 2119 keyword, line 238: '... forwarding node MUST take action so t...' RFC 2119 keyword, line 331: '... MUST silently be dropped....' RFC 2119 keyword, line 340: '... MUST silently be ignored....' (19 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 627 has weird spacing: '...isement messa...' -- 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 (9 February 2004) is 7376 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 86 looks like a reference -- Missing reference section? '2' on line 716 looks like a reference -- Missing reference section? '5' on line 158 looks like a reference -- Missing reference section? '9' on line 216 looks like a reference -- Missing reference section? '10' on line 216 looks like a reference -- Missing reference section? '8' on line 300 looks like a reference -- Missing reference section? '0' on line 418 looks like a reference -- Missing reference section? 'MAXJITTER' on line 418 looks like a reference -- Missing reference section? 'RFC 1321' on line 435 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT Thomas Clausen 3 IETF MANET Working Group Pascale Minet 4 Expiration: 9 August 2004 INRIA Rocquencourt, France 5 Charles E. Perkins 6 Nokia Research Center 7 9 February 2004 8 Multipoint Relay Flooding for Manets 9 draft-perkins-manet-mprf-00.txt 11 Status of this Memo 12 This document is a submission by the Mobile Ad Hoc Networking Working 13 Group of the Internet Engineering Task Force (IETF). Comments should 14 be submitted to the manet@itd.nrl.navy.mil mailing list. 16 Distribution of this memo is unlimited. 18 This document is an Internet-Draft and is in full conformance with 19 all provisions of Section 10 of RFC 2026. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that other 23 groups may also distribute working documents as Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in 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 37 This document describes the MultiPoint Relay Flooding (MPRF) protocol 38 for maintenance of efficient flooding structures in mobile ad-hoc 39 networks. The protocol is an adaptation of the classical flooding 40 algorithm, with the difference that many nodes are relieved of the 41 responsibility to relay flooded messages while still ensuring that 42 all nodes receive the messages. The key concept used in the protocol 43 is that of multipoint relays (MPRs). MPRs are selected nodes which 44 are the only nodes needed to forward messages during the flooding 45 process. This technique substantially reduces the message overhead 46 as compared to the more straightforward and well-known flooding 47 mechanism, where every node retransmits each message just once, upon 48 receiving the first copy of the message. The protocol is particularly 49 suitable for dense networks. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 54 1.1. MPRF Terminology . . . . . . . . . . . . . . . . . . . . . 5 55 1.2. Applicability Section . . . . . . . . . . . . . . . . . . 6 56 1.3. Protocol Overview . . . . . . . . . . . . . . . . . . . . 7 58 2. MPRF Protocol Details . . . . . . . . . . . . . . . . . . . 8 59 2.1. Broadcast Processing and Message Flooding . . . . . . . . 9 61 2.2. MPRF Message Types . . . . . . . . . . . . . . . . . . . . 10 62 2.2.1. Message Emission and Jitter . . . . . . . . . . . . . . 10 64 2.3. Identification for Flooded Packets . . . . . . . . . . . . 11 65 2.4. Unique Identifier Destination Option . . . . . . . . . . . 12 66 2.5. Neighbor Solicitation Message Format . . . . . . . . . . . 12 67 2.5.1. Neighbor Advertisement Message Format . . . . . . . . . 13 68 2.5.2. Neighborhood Information Base . . . . . . . . . . . . . 14 69 2.5.2.1. Symmetric Neighbor Set . . . . . . . . . . . . . . . . 15 70 2.5.2.2. 2-hop Neighbor Set . . . . . . . . . . . . . . . . . . 15 71 2.5.2.3. MPR selector set . . . . . . . . . . . . . . . . . . . 15 72 2.5.3. Neighbor Advertisement Message Generation . . . . . . . 15 73 2.5.4. Neighbor Advertisement Message Processing . . . . . . . 16 75 3. Multipoint Relay Selection . . . . . . . . . . . . . . . . . 17 77 4. Proposed Values for the Constants . . . . . . . . . . . . . 20 78 5. Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 20 80 1. Introduction 82 The MultiPoint Relay Flooding protocol for Manets (MPRF) is a proto- 83 col for reducing the overhead due to flooding in MANETs. 85 MPRF operates by identifying a set of nodes called "multipoint 86 relays" (MPRs) [1][2]. A node, N, selects a subset of its neighbors 87 as MPRs. These MPRs are selected to ensure that a flooded message, 88 emitted by node N and retransmitted by its MPRs, will be received by 89 all the nodes which are two hops away from N. Every node in the net- 90 work is a neighbor of some MPR, and every node (and every MPR) has an 91 MPR among its set of neighbors. Thus, flooded messages are relayed 92 by MPRs until the whole network has been covered. 94 MPRF is developed to work independently from other protocols. MPRF 95 can take advantages of various features that might be provided by a 96 given link layer, and requires only that a node has the ability to 97 transmit a message to all of its neighbors. This can be done by way 98 of a broadcast primitive, or in the less efficient case by way of 99 iterated unicast. 101 MPRF operates by establishing state in the nodes of the ad hoc net- 102 work. The MPRs accept the responsibility for retransmitting messages 103 that are meant to be flooded. The messages themselves often may 104 require processing and possible modifications to the message payload 105 before retransmission. For such messages, the TTL value in the IP 106 header MUST be set to 1, and the destination IP address MUST be set 107 to the "All-Manet-Neighbors" multicast address. If there are mes- 108 sages which do not require any modifications outside the IP header, 109 they MAY be addressed to the "All-Manet-Nodes" multicast address, and 110 the TTL set to a value larger than 1. The set of MPRs does not 111 depend on whether or not the TTL is larger than 1. 113 Note that many flooding algorithms will attempt to limit the spread 114 of the flooded signaling by using an "expanding rings" search tech- 115 nique. For these algorithms to work well with MPRF, the ring radius 116 should be a parameter under control of the protocol algorithm, not 117 the TTL parameter in the IP header. 119 DISCUSSION: Should TTL > 1 be allowed when protocol processing would 120 modify the payload? 122 According to the algorithms presented in this document, the set of 123 neighboring MPRs selected by a particular MPR node for relaying 124 flooded packets is dependent on the particular MPR node running the 125 algorithm. So, when a neighboring node receives a flooded packet, it 126 must identify which of its neighbors transmitted the packet before 127 determining whether to relay the flooded packet. When TTL is larger 128 than one, the transmitter cannot be identified by the value of the 129 source IP address of the flooded packet. In this situation, the 130 appropriate action depends on whether the node receiving the flooded 131 packet can identify the transmitter from the MAC address of the 132 layer-2 framing for the payload. If the identification can be made, 133 then the node has to keep track of the MAC address of its neighbors 134 as well as their IP address to enable the identification. This is 135 already done for many physical media such as Ethernet or WLAN, so no 136 special arrangements are needed in these typical cases. Otherwise, 137 flooded packets can be encapsulated for reliable identification of 138 the originator of the flooded packet. 140 DISCUSSION: Should the flooding ALWAYS work by way of encapsulation? 141 IP-in-IP encapsulation? Or, is it better to attempt an MPR selection 142 algorithm that does NOT depend on the selector node? 144 The set of MPR nodes is selected based in information provided by 145 periodic neighbor advertisements. In order to be compatible with 146 network deployments in which some nodes are not MPR aware, by default 147 every node in the network is an MPR. Thus, the MPR selection algo- 148 rithm can be viewed as a "pruning" operation during which some nodes 149 are relieved of their responsibility to retransmit broadcasts from 150 some of their neighbors. 152 1.1. MPRF Terminology 154 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 155 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 156 document are to be interpreted as described in RFC2119 [5]. The MPRF 157 protocol uses the following terminology: 159 multipoint relay (MPR) 161 A node which is selected by its one-hop neighbor, node X, 162 to "re-transmit" all the flooded messages that it 163 receives from X, provided that the same message is not 164 already received, and the time to live field of the mes- 165 sage is greater than one. 167 multipoint relay selector (MPR selector) 169 A node which has selected its one-hop neighbor, node X, 170 as its multipoint relay, will be called a multipoint 171 relay selector of node X. 173 node 175 A MANET router which supports this MPRF protocol. 177 link 179 A link is a physical medium which can carry data between 180 a pair of network interfaces (from two different nodes). 181 A node is said to have a link to another node when one of 182 its network interfaces can use a link to transmit data to 183 one of the network interfaces of the other node. 185 symmetric link 187 A confirmed (through neighbor sensing or otherwise) bi- 188 directional link between two nodes. 190 symmetric neighbor 191 A node X is a symmetric neighbor of node Y if there 192 exists a symmetric link between node X and Y. 194 symmetric neighborhood 195 The symmetric neighborhood of any node X is the set of 196 nodes which have at least one symmetric link to X. 198 symmetric 2-hop neighborhood 199 The symmetric 2-hop neighborhood of X is the set of nodes 200 which don't have a symmetric link to X but have a symmet- 201 ric link to a node belonging to the symmetric neighbor- 202 hood of X. 204 1.2. Applicability Section 206 MPRF is a protocol for identifying MPRs. This optimization is well 207 suited for dense wireless networks. The larger and more dense a net- 208 work, the more optimization can be achieved as compared to the clas- 209 sic flooding algorithm. In very small networks, or in sparse net- 210 works, little or no performance improvement may be achieved by use of 211 this technique. 213 MPRF is designed to carry flooded control or data traffic. This is 214 specifically intended to include Topology Control messages in OLSR 215 [pick one 6,7,8] or TBRPF[citation needed], and Route Requests in 216 AODV [9] or DSR [10]. 218 MPRF is designed such that it can operate independantly from other 219 protocols and does not rely on specific features from the underlying 220 link layer except for the ability to transmit broadcast packets. If 221 certain functionalities (e.g. neighbor sensing) are provided by the 222 link layer or by other protocols, they may be utilized. 224 The MPRF algorithm requires the receiver of a flooded packet to iden- 225 tify of the transmitter for that flooded packet. Only in this way 226 can the receiver determine whether or not it should further dissemi- 227 nate the packet to all of the nodes in its own neighborhood. 229 For flooded packets that have TTL larger than one, there are two sub- 230 cases: 232 1. ALL of the nodes in the neighborhood of the forwarding node can 233 detect the framing address (MAC address) of the forwarding node. 235 2. One of the nodes in the neighborhood of the forwarding node CANNOT 236 detect the framing address (MAC address) of the forwarding node. 238 In the latter case, the forwarding node MUST take action so that all 239 of its neighbors can identify it as the source of the newly retrans- 240 mitted packet. 242 1.3. Protocol Overview 244 MPRF reduces the overhead from flooding by identifying selected 245 nodes, called Multipoint Relays (MPRs), to retransmit flooded pack- 246 ets. This technique significantly reduces the number of retransmis- 247 sions required to flood a message to all nodes in the network. 249 Multipoint relays minimize the overhead of flooding messages in the 250 network by reducing duplicate retransmissions. Each node in the net- 251 work selects a set of nodes in its symmetric neighborhood which may 252 retransmit its messages. This set of selected neighbor nodes is 253 called the "Multipoint Relay" (MPR) set of that node. The neighbors 254 of node N which are *NOT* in its MPR set, receive and process flooded 255 messages but do not retransmit flooded messages received from node N. 257 Each node selects its MPR set among its one hop symmetric neighbors. 258 This set is selected such that it covers (in terms of radio range) 259 all nodes that are two hops away. The MPR set of N, denoted as 260 MPR(N), is then a subset of the symmetric neighborhood of N which is 261 only constrained to satisfy the following condition: every node in 262 the symmetric 2-hop neighborhood of N must have a symmetric link to a 263 node belonging to MPR(N). In general, the smaller the MPR set is, 264 the less congestion will be created by flooding operations. For an 265 analysis and example of MPR selection algorithms, see [2]. 267 Each node maintains information about the set of neighbors that have 268 selected it as MPR. This set is called the "Multipoint Relay Selec- 269 tor set" (MPR selector set) of a node. A node obtains this informa- 270 tion from periodically transmitted Neighbor Advertisement messages 271 received from the neighbors. 273 A flooded message, intended to be disseminated across the whole net- 274 work, coming from any of the MPR selectors of node N is expected to 275 be retransmitted by node N. 277 2. Protocol Details 279 This section describes details about how MPRF functions. This 280 includes descriptions of the format and contents of the packets being 281 exchanged as well as the algorithms operating in each node in the 282 network. 284 The "Packet Forwarding" mechanism is used by MPRs to accomplish the 285 flooding of packets. For this to function, the MPRs have to be 286 selected and made aware that they have been selected to function as 287 MPRs. For this, a neighbor advertisement mechanism and an MPR selec- 288 tion algorithm are required. 290 Through the neighbor advertisement mechanism, a node advertises its 291 symmetric neighborhood as well as its MPR selection to neighboring 292 nodes. With this information, each node can build up both its sym- 293 metric neighborhood and its symmetric 2-hop neighborhood (for MPR 294 selection). Using this information, the node must its selected MPR 295 nodes and subsequently inform those MPR nodes that they have been 296 selected. 298 Neighbor advertisements provide each node with the addresses of its 299 symmetric neighbors. This list may instead be provided by a neighbor 300 sensing protocol, such as used in the proactive protocols [8], or by 301 any link-layer mechanism, or by tabulating the neighbors from which 302 Neighbor Advertisements are received with an indication that the 303 nodes can detect each others' messages. 305 The MPR selection algorithm specifies the conditions that each node 306 must satisfy. Some heuristics are also provided for selecting MPRs. 308 2.1. Broadcast Processing and Message Flooding 310 To avoid unnecessary retransmission of a message which was already 311 received, processed, and retransmitted, each node maintains a table 312 of packets which have been transmitted to "All-Manet-Neighbors". In 313 this table, called the node's "Flooding History" table, the node 314 records information about the most recently received messages. This 315 includes the source_addr, where source_addr is the originator address 316 of the message, and a value called the Flooded Packet Identifier 317 (FPI), which is a number uniquely identifying the flooded message. 318 See section QQQ1 for details about computing the FPI for broadcast 319 messages. 321 In this section, the term "Originator Address" will be used for the 322 main address of the node which sent the message. The term "Sender 323 Interface Address" will be used for the sender address (given in the 324 IP header of the packet containing the message) of the interface 325 which sent the message. For messages with TTL = 1, these addresses 326 are the same. 328 Upon receiving a flooded packet, a node performs the following tasks: 330 1. If the TTL of the message is equal to '0' (zero), the message 331 MUST silently be dropped. 333 2. If there exists an entry in the Flooding History such that 335 source_addr == Originator Address, AND 337 FPI == derived from packet data as in section QQQ1 339 then the message has already been completely processed and 340 MUST silently be ignored. 342 3. Otherwise, if the node does not implement the message type of 343 the message, and if TTL == 1, then the node MUST silently dis- 344 card the message. 346 4 Otherwise, if the sender of the message is not detected to be 347 in the symmetric neighborhood of the node, the message MUST 348 silently be dropped. 350 5 Otherwise, if the message is addressed to All-Manet-Nodes, the 351 message is processed according to the specifications for the 352 message type, and 353 5.1 an entry in the Flooding History is recorded with: 355 source_addr = originator address 357 the FPI (see section 2.3) 359 5.2 If the sender is an MPR selector of this node and if the 360 time to live of the message is greater than '1', the mes- 361 sage MUST be forwarded according to the following by 362 broadcasting it on all interfaces that have symmetric 363 neighbors other than the sender, with the TTL of the mes- 364 sage reduced by one. 366 When TTL=1 (and destination = All-Manet-Nodes) forwarding (and set- 367 ting the correct message header in the forwarded, known, message) is 368 the responsibility of the algorithm specifying how the message is to 369 be handled. This enables, e.g., a message type to be specified such 370 that the message can be modified while in transit (e.g. to reflect 371 the route the message has taken). 373 2.2. MPRF Message Types 375 The following message types are specified for MPRF. 377 - Neighbor Solicitation message, for the case when a node has 378 missed one of the Advertisement messages from one of its 379 neighbors since the last full advertisement from that neighbor 381 - Neighbor Advertisement messages, which announce symmetric 382 neighbors and MPR selection. Each symmetric neighbor of any 383 node N must be advertised by node N at least once per 384 N_ADV_INTERVAL. 386 These messages are carried over ICMP, or ICMPv6, with two new ICMP 387 type values to be allocated by IANA. 389 2.2.1. Message Emission and Jitter 391 As a basic implementation requirement, synchronization of flooded 392 messages SHOULD be avoided. As a consequence, periodic messages 393 SHOULD be emitted at slightly variable times. 395 Emission of control traffic from neighboring nodes may, for various 396 reasons (mainly timer interactions with packet processing), become 397 synchronized such that several neighbor nodes attempt to transmit 398 control traffic simultaneously. Depending on the nature of the under- 399 lying link-layer, this may or may not lead to collisions and hence 400 message loss - possibly loss of several subsequent messages of the 401 same type. 403 To avoid such synchronizations, the following simple strategy for 404 emitting control messages is proposed. A node MAY add an amount of 405 jitter to the interval at which messages are generated. The jitter 406 must be a random value for each message generated. Thus, for a node 407 utilizing jitter: 409 Actual message interval = MESSAGE_INTERVAL - rnd_jitter 411 where rnd_jitter is a value, randomly selected from the interval 412 [0,MAXJITTER] and MESSAGE_INTERVAL is the value of the message inter- 413 val specified for the message being emitted. 415 Jitter MAY also be introduced when forwarding messages. The follow- 416 ing simple strategy may be adopted: when a message is to be forwarded 417 by a node, it should be delayed by the node during a short random 418 period of time in the range [0,MAXJITTER]. 420 This specification imposes a minimal rate of control message emis- 421 sion. However, a node MAY send control messages at a higher rate 422 (e.g. in cases of high mobility). Tuning the rate of protocol con- 423 trol traffic to operational conditions is an implementation issue. 425 2.3. Identification for Flooded Packets 427 Every node maintains a list to keep track of which flooded packets 428 have already been received and retransmitted. The list contains, for 429 each distinct flooded packet received, a value called the Flooded 430 Packet Identifier (FPI). For IPv4, this FPI is composed of the source 431 IP address, the IP ident value, and the fragment offset values 432 obtained from the IP header of the flooded packet. For IPv6, the FPI 433 is calculated as specified as follows. 435 To obtain the FPI for IPv6 packets, a node uses MD5 [RFC 1321] to 436 perform the following calculation for the incoming flooded packet: 438 FPI = MD5 (IPv6 packet data). 439 The IP packet data includes all non-mutable IPv6 headers and exten- 440 sions, as well as any higher-level protocol data. The source node 441 for each flooded packet MUST ensure that this FPI is distinct from 442 the FPI from every other flooded packet which the node has 443 transmitted during the last BROADCAST_RECORD_TIME. In the unlikely 444 event that the FPI value is identical to some such recently transmit- 445 ted packet, the source node MUST add a Unique Identifier Destination 446 Option to the flooded packet (see section 2.4). 448 2.4. Unique Identifier Destination Option 450 The Unique Identifier option is encoded in type-length-value (TLV) 451 format as follows: 453 0 1 2 3 454 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 455 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 456 | Option Type | Option Length | 457 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 458 | Uniquifying Value | 459 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 461 Option Type 463 TBD 464 Option Length 466 2 467 Uniquifying Value 468 The 16-bit Uniquifying Value is chosen to make the flooded packet 469 FPI computation different than that for any other flooded packet 470 from the same source node. 472 The Unique Identifier MUST be placed in the Destination Options 473 before the Routing Header (and, thus, before the fragment header). 474 This allows proper handling by all intermediate forwarding nodes. 476 2.5. Neighbor Solicitation Message Format 478 The format of a Neighbor Solicitation is as follows: 479 0 1 2 3 480 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 481 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 482 | Reserved | 483 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 485 This is sent as the data-portion of the general packet format 486 described in the Packet Format and Forwarding section, with the "Mes- 487 sage Type" set to NEIGHBOR_SOLICITATION and the TTL field set to 1 488 (one). 490 2.5.1. Neighbor Advertisement Message Format 492 To accommodate the above requirements, as well as to accommodate for 493 future extensions, an approach similar to the overall packet format 494 is taken. Thus the proposed format of a Neighbor Advertisement mes- 495 sage is: 497 0 1 2 3 498 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 499 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 500 | # of MPRs |# of Non-MPRs|# of LostNbrs|I| Rsvd | Seq# | 501 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 502 | MPR Addresses... 503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 504 | Other Non-MPR Neighbor Addresses... 505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 506 | Lost Neighbor Addresses... 507 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 508 : : 509 : : 511 This is sent as the data-portion of the general packet format 512 described in the Packet Format and Forwarding section, with the "Mes- 513 sage Type" set to NEIGHBOR_ADVERTISEMENT and the TTL field set to 1 514 (one). 516 # of MPRs 518 The number of IP addresses in the list following that belong 519 to nodes that have been chosen as Multipoint Relays 521 # of Non-MPRs 523 The number of IP addresses in the list following that belong 524 to nodes that have not been chosen as Multipoint Relays. For 525 incremental advertisements, this includes those nodes that 526 were formerly chosen as MPRs, but during the recent reselec- 527 tion of MPRs were deselected. 529 # of LostNbrs 531 The number of IP addresses in the list following that belong 532 to nodes that were previously neighbors but have been "lost" 533 (i.e., are no longer detectable within the neighborhood). 535 Seq# 537 The Seq# for this advertisement is incremented by one for 538 every advertisement. 540 'I' 542 The 'I' flag specifies whether the advertisement is an Incre- 543 mental advertisement or a Full advertisement. If the 'I' flag 544 is zero, the number of Lost neighbors MUST be zero. 546 Rsvd 548 Ignored on reception; MUST be set to 0 on transmission. 550 The sequence number of a full Advertisement MUST be at least 5 551 greater than the sequence number of the last incremental Advertise- 552 ment which was broadcast by the node, and one greater than the last 553 full Advertisement which was broadcast. If a node receives an 554 Advertisement which contains a sequence number which is more than 5 555 greater than the sequence number in the last advertisement (modulo 556 64), then the node may have missed a full advertisement, and MUST 557 transmit a Neighbor Solicitation to the source of the Advertise- 558 ment. 560 2.5.2. Neighborhood Information Base 562 Each node maintains an information base, consisting of a symmetric 563 neighbor set, a 2-hop neighbor set and an MPR selector set. 565 The symmetric neighbor set is populated by a neighbor sensing mecha- 566 nism, which can be external to MPRF, or which can just consist of 567 keeping track of the periodic transmissions of Neighbor Advertisement 568 messages. 570 The 2-hop neighbor set and the MPR selector set are both populated as 571 a result of Neighbor Advertisement message exchange. 573 2.5.2.1. Symmetric Neighbor Set 575 A node stores, for each entry in its symmetric neighbor set, a "Sym- 576 metric Neighbor Tuple" (node_addr, exp_time) where node_addr is the 577 address of a neighbor which has been detected to be symmetric, and 578 exp_time specifies the time at which this tuple expires and *MUST* be 579 removed. In a node, the set of Symmetric Neighbor Tuples are denoted 580 the "Symmetric Neighbor Set". 582 2.5.2.2. 2-hop Neighbor Set 584 A node maintains a set of "2-hop tuples" (node_addr, N_2hop_addr, 585 exp_time), describing symmetric links between nodes in its symmetric 586 neighbor set and the symmetric 2-hop neighborhood. 'node_addr' is 587 the address address of a symmetric neighbor, N_2hop_addr is an 588 address of a 2-hop neighbor with a symmetric link to the neighbor 589 with address node_addr, and exp_time specifies the time at which the 590 tuple expires and *MUST* be removed. 592 This information is gathered from the Neighbor Advertisement messages 593 received by a node from its neighbor nodes. 595 In a node, the set of 2-hop tuples are denoted the "2-hop Neighbor 596 Set". 598 2.5.2.3. MPR selector set 600 A node, N, stores, for each neighbor which has selected node N as 601 MPR, a "MPR selector tuple" (MPR_addr, MPR_time) where MPR_addr is 602 the address of a neighbor which has selected node N as MPR and 603 MPR_time specifies the time at which this tuple expires and *MUST* be 604 removed. 606 This information is used when deciding if an incoming message is to 607 be forwarded or not. 609 2.5.3. Neighbor Advertisement Message Generation 611 The list of nodes contained in an Neighbor Advertisement message can 612 be partial (e.g. due to message size limitations, imposed by the net- 613 work). However, every MPR selected by a node must be advertised at 614 least once during N_ADV_INTERVAL. 616 Notice that for limiting the impact from loss of control messages, it 617 is desirable that a message (plus the generic package header) can fit 618 into a single layer-2 frame. The use of incremental advertisements 619 in networks of moderate mobilty is expected to substantially reduce 620 the need for large-sized Advertisement messages. 622 Each Neighbor Advertisement message generated is broadcasted on each 623 MANET interface of the node. 625 2.5.4. Neighbor Advertisement Message Processing 627 Upon receiving a Neighbor Advertisement message, the node SHOULD 628 update its symmetric 2-hop neighbor set and MPR selector set. If the 629 advertisement is an incremental Advertisement, the content of the 630 last full Advertisement is revised according to the information pro- 631 vided in the incremental Advertisement. 633 The symmetric 2-hop neighbor set should be updated as follows: 635 For each neighbor, listed in the Neighbor Advertisement message 636 with a status of MPR or SYM_LINK a 2-hop tuple is created or 637 updated with: 639 node_addr = Originator Address; 641 N_2hop_addr = the interface address of the 2-hop neigh- 642 bor; 644 exp_time = current time + 2HOP_HOLD_TIME. 646 For each 2-hop node, listed in an incremental Advertisement message 647 with a status of LOST_LINK, the 2-hop tuple with 649 node_addr == Sender Address 651 N_2hop_addr == the 2-hop node address 653 is deleted. 655 If a node finds itself in the Neighbor Advertisement message, listed 656 with a link type of "MPR", it MUST update the MPR selector set as 657 follows: 659 If there exists no MPR selector tuple with 661 MPR_addr == Sender Address 663 a new tuple is created with: 665 MPR_addr = Sender Address 667 MPR_time = current time + MPR_HOLD_TIME 669 otherwise, if a tuple exists where M_addr == Sender Address, 670 it is updated as follows: 672 MPR_time = current time + MPR_HOLD_TIME 674 3. Multipoint Relay Selection 676 MPRs are used to flood control messages from a node into the network 677 while reducing the number of retransmissions that will occur in a 678 region. Thus, the concept of MPR is an optimization of a classical 679 flooding mechanism. 681 Each node in the network selects, independently, its own set of MPRs 682 among its symmetric neighborhood. The neighbor nodes, selected as 683 MPR, are announced to the neighborhood using Neighbor Advertisement 684 messages as described in the previous section. 686 The MPR set MUST be calculated by a node in such a way that it, 687 through the neighbors in the MPR-set, can reach all symmetric 2-hop 688 neighbors which are not at the same time symmetric neighbors of the 689 node. This means that the union of the symmetric neighborhoods of the 690 MPR nodes contains the symmetric 2-hop neighborhood. 692 While it is not essential that the MPR set is minimal, it is essen- 693 tial that all 2-hop neighbors can be reached through the selected MPR 694 nodes. A node SHOULD select an MPR set such that any 2-hop neighbor 695 is covered by at least MPR_COVERAGE MPR nodes. With MPR_COVERAGE=1 696 the overhead of the protocol is kept at a minimum. In presence of 697 mobility and link failure, an MPR_COVERAGE=2 could provide a more 698 redundant connectivity, for example to support a link failure without 699 rerouting. 701 Notice that MPR_COVERAGE can be tuned locally without affecting the 702 consistency of the protocol. For example, a node can set MPR_COVER- 703 AGE=2 if it observes many changes in its neighbor information base 704 caused by mobility, while otherwise keeping MPR_COVERAGE=1. The 705 fractional part of MPR_COVERAGE, if nonzero, specifies the likelihood 706 for transmitting another broadcast. For instance, when MPR_COVERAGE 707 = 1.4, there is a 40% chance that the node will transmit the broad- 708 cast twice, and a 60% chance that the node will transmit the broad- 709 cast only once. 711 By default, the MPR set can coincide with the entire symmetric neigh- 712 bor set. This will be the case at network initialization (and will 713 correspond to classic flooding). 715 The following specifies a proposed heuristic for selection of MPRs 716 [2]. The following terminology will be used in describing this algo- 717 rithm (neighbors are identified by their main address and 2-hop 718 interfaces by their address): 720 N: 721 The set of neighbors with which there exists a symmetric link. 723 N2: 724 The set made of the symmetric 2-hop neighbors excluding (i) 725 the node performing the computation, (ii) all the members of 726 N, 728 D(y): 729 Degree of node y (where y is a member of N), defined as the 730 number of symmetric neighbors of node y, EXCLUDING all the 731 nodes which are of members of N and the node performing the 732 computation. 734 Poorly covered node: 735 A poorly covered node is a node in N2 which is covered by 736 (strictly) less than Floor(MPR_COVERAGE) nodes in N, where 737 Floor(X) is the integer part of X. 739 The proposed heuristic is as follows: 741 1 Start with an MPR set made of all members of N 743 2 Calculate D(y), where y is a member of N, for all nodes in N. 745 3 Select as MPRs those nodes in N which cover the poorly covered 746 nodes in N2. The nodes are then removed from N2 for the rest 747 of the computation. 749 4 While there exist nodes in N2 which are not covered by at 750 least MPR_COVERAGE nodes in the MPR set: 752 4.1 For each node in N, calculate the reachability, i.e. the 753 number of nodes in N2 which are not yet covered by at 754 least Floor(MPR_COVERAGE) nodes in the MPR set, and which 755 are reachable through this one hop neighbor; 757 4.2 Select as a MPR a node with non zero reachability. In 758 case of multiple choice take the node which which pro- 759 vides reachability to the maximum number of those nodes 760 in N2. In case of multiple nodes providing the same 761 amount of reachability and reachability, select that node 762 as MPR whose D(y) is greater. Remove from N2 the nodes 763 that are now covered by Floor(MPR_COVERAGE) node in the 764 MPR set. 766 5 As an optimization, process each node y in the MPR set; if all 767 nodes in N2 are still covered by at least MPR_COVERAGE nodes 768 in the MPR set excluding y, then remove node y from the MPR 769 set. 771 When the MPR set has been computed, all the corresponding main 772 addresses are stored in the MPR Set. 774 The outcome of the MPR calculation is a list of the neighbor nodes 775 which have been selected as MPR. These are advertised through the 776 Neighbor Advertisement messages, as previously described in section 777 2.5.1. 779 MPR set recalculation should occur when changes are detected in the 780 neighborhood or in the 2-hop neighborhood. A change in the neighbor- 781 hood is detected when: 783 - The exp_time field of a neighbor tuple expires. This is con- 784 sidered as a neighbor loss. 786 - A neighbor tuple is deleted according to the Neighbor Adver- 787 tisement message processing section. This is also considered 788 as a neighbor loss. 790 - A new neighbor tuple is inserted in the Neighbor Set with a 791 valid exp_time. 793 A change in the 2-hop neighborhood is detected when a 2-hop neighbor 794 tuple is inserted, or expires or is deleted according to the Neighbor 795 Advertisement message processing section. 797 The following processing should occur when changes in the neighbor- 798 hood or the 2-hop neighborhood are detected: 800 - In case of neighbor loss, all the 2-hop tuples with N_addr == 801 main address of the lost neighbor are deleted. 803 - In case of neighbor loss, all the MPR selector tuples with 804 MPR_addr == main address of the neighbor are deleted 806 - The MPR set is re-calculated when a neighbor appearance or 807 loss is detected, or when a change in the 2-hop neighborhood 808 is detected. 810 - An additional Neighbor Advertisement message may be sent when 811 the MPR set changes. 813 4. Proposed Values for the Constants 815 This section list the values for the constants used in the descrip- 816 tion of the protocol. 818 MPR COVERAGE = 1 820 MAXJITTER = 0.5 seconds 822 N_ADV_INTERVAL = 3 seconds 824 2HOP_HOLD_TIME = 2 seconds 826 5. Authors' Addresses 828 Thomas Heide Clausen, Project HIPERCOM, INRIA Rocquencourt, BP 105, 829 78153 Le Chesnay Cedex, France, Phone: +33 1 3963 5133, Email: 830 Thomas.Clausen@inria.fr 832 Pascale Minet, Project HIPERCOM, INRIA Rocquencourt, BP 105, 78153 Le 833 Chesnay Cedex, France, Phone: +33 1 3963 508832, Email: Pas- 834 cale.Minet@inria.fr 836 Charles E. Perkins, Communications Systems Laboratory, Nokia Research 837 Center, 313 Fairchild Drive, Mountain View, CA 94303, USA, Phone: +1 838 650 625 2986, Email: charliep@iprg.nokia.com 840 6. References 842 1. P. Jacquet, P. Minet, P. Muhlethaler, N. Rivierre. Increasing relia- 843 bility in cable free radio LANs: Low level forwarding in HIPERLAN. 844 Wireless Personal Communications, 1996 846 2. A. Qayyum, L. Viennot, A. Laouiti. Multipoint relaying: An efficient 847 technique for flooding in mobile wireless networks. 35th Annual 848 Hawaii International Conference on System Sciences (HICSS'2001). 850 3. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 851 1, functional specifications ETS 300-652, ETSI, June 1996 853 4. Philippe Jacquet and Laurent Viennot, Overhead in Mobile Ad-hoc Net- 854 work Protocols, INRIA research report RR-3965, 2000 856 5. S. Bradner. Key words for use in RFCs to Indicate Requirement Lev- 857 els. Request for Comments (Best Current Practice) 2119, Internet 858 Engineering Task Force, March 1997. 860 6. T. Clausen, G. Hansen, L. Christensen and G. Behrmann. The Optimized 861 Link State Routing Protocol, Evaluation through Experiments and 862 Simulation. IEEE Symposium on "Wireless Personal Mobile Communica- 863 tions", september 2001. 865 7. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum and L. 866 Viennot. Optimized Link State Routing Protocol. IEEE INMIC Pakistan 867 2001. 869 8. T. Clausen, P. Jacquet, A. Laouiti, P. Minet, P. Muhlethaler, A. 870 Qayyum and L. Viennot. Optimized Link State Routing Protocol, 871 draft-ietf-manet-olsr-06.txt, work in progress, march 2002. 873 9. C. Perkins, E. Belding-Royer, S. Das. Ad hoc On-Demand Distance Vec- 874 tor (AODV) Routing, draft-ietf-manet-aodv-09.txt, work in progress, 875 november 2001 877 10. D. Johnson, D. Maltz, Y. Hu, J. Jetcheva. The Dynamic Source Routing 878 Protocol for Mobile Ad Hoc Networks, draft-ietf-manet-dsr-06.txt, 879 work in progress, november 2001