idnits 2.17.1 draft-perkins-manet-smurf-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1.a on line 21. -- Found old boilerplate from RFC 3978, Section 5.5 on line 509. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 2 IPR Disclosure Acknowledgement. ** The document seems to lack an RFC 3979 Section 5, para. 3 IPR Disclosure Invitation. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: This document is an Internet-Draft and is subject to all provisions of Section 3 of RFC 3667. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. -- 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) == Unused Reference: '4' is defined on line 461, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 469, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' ** Downref: Normative reference to an Informational RFC: RFC 3753 (ref. '3') -- Possible downref: Normative reference to a draft: ref. '5' ** Downref: Normative reference to an Experimental RFC: RFC 3626 (ref. '7') Summary: 11 errors (**), 0 flaws (~~), 4 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Mobile Ad Hoc Networking Working Group Charles E. Perkins 2 INTERNET DRAFT Nokia Research Center 3 8 July 2006 Thomas Clausen, 4 Philippe Jacquet 5 INRIA Rocquencourt, France 7 Multicast With Minimal Congestion Using Connected Dominating Sets 8 draft-perkins-manet-smurf-00.txt 10 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@ietf.org mailing list. 16 This document is an Internet-Draft and is subject to all provisions 17 of section 3 of RFC 3667. By submitting this Internet-Draft, each 18 author represents that any applicable patent or other IPR claims of 19 which he or she is aware have been or will be disclosed, and any of 20 which he or she becomes aware will be disclosed, in accordance with 21 Section 6 of BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF), its areas, and its working groups. Note 25 that other groups may also distribute working documents as 26 Internet-Drafts. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at 30 any time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 The list of current Internet-Drafts can be accessed at 34 http://www.ietf.org/ietf/1id-abstracts.txt. 36 The list of Internet-Draft Shadow Directories can be accessed at 37 http://www.ietf.org/shadow.html. 39 Abstract 40 Flooding is useful for many reasons in ad hoc networks, but 41 causes congestion that can block traffic. Selecting multi-point 42 relays (MPRs) reduces congestion due to flooding, but has several 43 disadvantages. It is possible to select a subset of the MPRs to 44 do the same job more effectively. In this document, signaling is 45 specified for identifying a relatively small connected dominating set 46 that can still manage the flooding operation. 48 1. Introduction 50 Flooding is useful for many reasons in ad hoc networks, but causes 51 congestion that can block traffic within such a network. The goal 52 of this document is to specify a flooding algorithm that greatly 53 reduces the number of packet retransmissions needed to flood the 54 whole network. Since there a many fewer retransmissions, the amount 55 of congestion due to flooding will be greatly reduced. 57 In order to reduce the total number of retransmissions, we can reduce 58 the number of nodes that perform the retransmissions, as long as 59 all nodes still receive at least one transmission of the flooded 60 packet. If a particular node can determine its one-hop and two-hop 61 neighborhoods, then it can identify a subset of its neighboring nodes 62 that still be able to reach every node of the two-hop neighborhood. 63 The nodes in such a subset are called "multi-point relays" (MPRs) 64 in the OLSR specification [7]. There are various ways to pick 65 enough MPRs so that, when each MPR retransmits a packet, the two-hop 66 neighborhood will be completely covered. These neighboring MPRs will 67 themselves have selected some of their other neighbors to be MPRs. 68 When the neighboring MPRs retransmit, then some of their neighbors 69 will again retransmit, until eventually the whole network is covered. 71 Selecting multi-point relays MPRs, as specified in OLSR [7] is 72 beneficial to reduce congestion due to flooding, but has several 73 disadvantages. Another related concept is that of a "connected 74 dominating set" (CDS). There are many distributed algorithms for 75 computing a CDS, with a variety of interesting properties. The set 76 of MPRs that retransmit a packet originated from a source node within 77 an ad hoc network is also a CDS. Otherwise, the set of MPRs would not 78 be able to cover the network by retransmission hop-by-hop. 80 In this document, signaling is specified for identifying a relatively 81 small connected dominating set that can still manage the flooding 82 operation. 84 The names of the multicast groups used for flooding are given as 85 "ALL_IPv4_MANET_NODES" and "ALL_IPv6_MANET_NODES" [5]. The backbone 86 nodes selected for flooding packets can, however, be used for 87 flooding to any designated multicast address as long as the members 88 of that multicast group form a connected subgraph of the ad hoc 89 network. Specifications for future multicast groups intended for 90 flooding or very dense dissemination should specifically indicate 91 that their members should communicate across the SMURF backbone. 92 Future documents may offer improved algorithms for the purpose of 93 identifying backbone nodes, while still utilizing the protocol in 94 this document for periodic updates to the necessary neighborhood 95 information. 97 DISCUSSION: should there be a version field to handle 98 unforeseen future incompatibilities? 100 2. SMURF Terminology 102 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 103 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 104 document are to be interpreted as described in RFC 2119 [2]. 106 This section defines other terminology that is not already defined 107 in [3]. 109 MPR 111 A "multi-point relay" -- that is, a neighboring node that can 112 relay flooded packets, thus assisting with the dissemination of 113 those packets throughout the network 115 broadcast 117 Transmit to the IPv4 Limited Broadcast address, 118 255.255.255.255, or else for IPv6 to the link-local 119 AllNodesMulticast address. 121 neighborhood, one-hop neighborhood 123 The neighborhood (also called the one-hop neighborhood) of a 124 node is the set of nodes which are directly reachable by that 125 node. 127 two-hop neighborhood 129 The two-hop neighborhood of a node is the set of nodes which 130 are either directly reachable by that node, or directly 131 reachable by one of the neighbors of that node. 133 dominating set 135 A subset of a graph is a dominating set if every node in the 136 graph is eiher a member of the subset, or else a neighbor of at 137 least one node in the subset. 139 connected set 141 A set with more than one element is connected if every node in 142 the subset is a neighbor of some other node in the subset. A 143 set with fewer than two elements is connected. 145 CDS (connected dominating set) 147 A subset of a graph is a CDS if it is a dominating set, and it 148 is connected. 150 flooding backbone 152 The flooding backbone of an ad hoc network is a CDS which is 153 used for flooding packets throughout the network, considering 154 every node in the ad hoc network as a node in a graph with 155 edges defined by the (one-hop) communication links that are 156 available between the nodes in the ad hoc network. 158 backbone 160 in this document, ``backbone'' always means the flooding 161 backbone 163 3. Overview 165 Each node listens for advertisements from its neighbors. From the 166 advertisements, the node updates its stored information about its 167 one-hop neighborhood and its two-hop neighborhood. The sender of 168 the advertisement is a member of the node's one-hop neighborhood, 169 and the sender's neighbors are either members of the node's one-hop 170 neighborhood or its two-hop neighborhood. 172 There are two kinds of periodic local topology advertisements, 173 which are used to enable each node to construct a representation 174 of its two-hop neighborhood and subsequently select MPRs. The 175 first is called the "full advertisement", which has complete lists 176 of all the necessary data. The second is called the "incremental 177 advertisement", which only has information that has changed since 178 the last full advertisement. It is expected that the incremental 179 advertisement will be much smaller than the full advertisement. 181 A node's neighborhood is considered to be composed of three mutually 182 exclusive subsets: 184 - undistinguished first hop neighbors 185 - MPRs 186 - the node itself 188 Likewise, a node's two hop neighborhood is considered to be composed 189 of four mutually exclusive subsets: 191 - second hop neighbors 192 - undistinguished first hop neighbors 193 - MPRs 194 - the node itself 196 If a node is described as being in any one of these subsets, then 197 by convention and agreement it does not belong to any of the other 198 subsets. This eliminates overlap of information in the local 199 topology advertisements. 201 The following information is present in full advertisements: 203 - advertisement sequence number 204 - reluctance for offering service as a backbone node 205 - first hop neighbors 206 - MPRs 207 - flags 209 The following information is present in incremental advertisements: 211 - advertisement sequence number of the last full advertisement 212 - reluctance for offering service as a backbone node 213 - addresses of new first hop neighbors 214 - addresses of new MPRs 215 - addresses of lost nodes 216 - flags 218 Any address in the lost node list has to be deleted from the neighbor 219 list or the MPR list of the last full advertisement, and the nodes in 220 these two lists reclassified if they were classified differently in 221 the last full advertisement. 223 A neighboring node cannot be considered for selection as an MPR until 224 the link to that node has been verified as bidirectional. For each 225 neighbor, two conditions must be verified: 227 1. an advertisement has been recently heard from the neighbor 229 2. the node itself must appear as a member of the one-hop neighbors 230 reported by that neighbor. 232 Once each node has constructed its two-hop neighborhood, it uses 233 any reasonable algorithm to identify a subset of neighbors which 234 are to be designated as MPRs. One algorithm that works well is the 235 so-called "greedy algorithm": 237 1. Initialize the set of uncovered two-hop neighbors to contain all 238 known two-hop neighbors 240 2. Pick the neighbor that is within range of the largest number of 241 uncovered nodes in the two-hop neighborhood. 243 3. Mark the two-hop neighbors reachable by that neighbor's local 244 broadcasts as already covered. 246 4. If there are no more uncovered two-hop neighbors, stop. 248 5. Otherwise, iterate steps (2) -- (4). 250 Once the nodes have identified the MPRs in their neighborhoods, each 251 node must also determine whether to prune itself from the flooding 252 backbone (i.e., the connected dominating set of nodes which will take 253 responsibility for disseminating flooded data). 255 In order for a node to prune itself to the flooding backbone, it uses 256 the following algorithm [1]: 258 1. It forms a "CDS identifier" by appending its IP address to its 259 last advertised "reluctance" value. 261 2. If it is the node with a CDS identifier lower than any of its 262 neighbors, then it must continue to participate as a member of 263 the flooding backbone. 265 3. Otherwise, if it not a MPR of its neighbor with the lowest CDS 266 identifier, then it may prune itself from the flooding backbone. 268 A node advertises the status of its decision to prune itself from the 269 CDS backbone in its advertisement messages. 271 4. Full Advertisement 273 The Full Advertisement has the following format: 275 0 1 2 3 276 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 277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 278 | Type | Length | 279 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 280 | Sequence # |Rel| #1-hop | #MPRs | reserved|C| 281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 282 : List of IP addresses of 1-hop neighbors : 283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 284 : List of IP addresses of MPR neighbors : 285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 287 Type 289 Type == 1. 291 Length 293 Length of the full advertisement data, in bytes, including all 294 fields except for the Type and Length. 296 Sequence # 298 Advertisement sequence number 300 Rel 302 Reluctance (2 bits). A node selects a low value for its 303 reluctance, if it is willing to be identified as an MPR, and 304 thus potentially as a member of the connected dominating set. 306 #1-hop 308 Number of one-hop neighbors 310 #MPRs 312 Number of one-hop neighbors reclassified as MPRs 314 'C' 316 The 'C' flag is set if the advertising node has selected itself 317 as a member of the connecting dominating set for flooding 319 1-hop list 321 List of IP addresses of 1-hop neighbors (#1-hop total 322 addresses) 324 MPR list 326 List of IP addresses of MPR neighbors (#MPRs total addresses) 328 The IP header TTL for the Full Advertisement packet MUST be 1. 330 DISCUSSION: is 255 better? 332 DISCUSSION: Is the Length field needed, or should we spend 333 the bits on enlarging the other fields? 335 5. Incremental Advertisement 337 The Incremental Advertisement has the following format: 339 0 1 2 3 340 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 341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 342 | Type | Length | 343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 344 | Sequence # |Rel| #1-hop|#MPRs| #lost |reservd|C| 345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 346 : List of IP addresses of 1-hop neighbors : 347 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 348 : List of IP addresses of MPR neighbors : 349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 350 : List of IP addresses of lost neighbors : 351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 353 Type 355 Type == 2. 357 Length 359 Length of the incremental advertisement data, in bytes, 360 including 362 Sequence # 364 Advertisement sequence number 366 Rel 368 Reluctance (2 bits). A node selects a low value for its 369 reluctance, if it is willing to be identified as an MPR, and 370 thus potentially as a member of the connected dominating set. 372 #1-hop 374 Number of new one-hop neighbors 376 #MPRs 378 Number of new nodes classified as MPRs 380 #lost 382 Number of nodes no longer in the one-hop neighborhood 383 (and, thus, not possibly MPRs) as shown in the last full 384 advertisement 386 'C' 388 The 'C' flag is set if the advertising node has selected itself 389 as a member of the connecting dominating set for flooding 391 1-hop list 393 List of IP addresses of new 1-hop neighbors (#1-hop total 394 addresses) 396 MPR list 398 List of IP addresses of new MPR neighbors (#MPRs total 399 addresses) 401 lost list 403 List of IP addresses of former neighbors that have not 404 exhibited local connectivity recently (#lost total addresses) 406 The IP header TTL for the Incremental Advertisement MUST be 1. 408 DISCUSSION: is 255 better? 410 DISCUSSION: Is the Length field needed, or should we spend 411 the bits on enlarging the other fields? 413 6. Security Considerations 415 This draft specifies a general mechanism for identifying a flooding 416 backbone in an ad hoc network. It does not make any provision for 417 securing the contents of the flooded data, either to protect against 418 tampering or to protect against unauthorized inspection of the data. 419 It does not make any provision for ensuring that the nodes of the 420 flooding backbone are operating as expected. It does not make any 421 provision to guarantee the correctness of information presented 422 within the advertisement messages. The use of local broadcast for 423 the advertisement messages precludes the use of point-to-point 424 security associations such as might be used for constructing 425 Authentication Header digests. 427 In the future, if further security measures are to be undertaken, 428 one could attempt to utilize public keys for the purpose of 429 authenticating the flooded data, as long as the public keys were 430 known to be properly associated with the node in question (to avoid 431 man-in-the-middle attacks). 433 7. IANA considerations 435 New multicast addresses have to be allocated. A new UDP port number 436 has to be allocated for the neighborhood messages. ICMP is another 437 possibility. 439 8. Acknowledgments 441 Thomas Clausen and Emmanuel Baccelli were frequent contributors to 442 the conversation which inspired the production of this document. The 443 algorithm for identifying the flooding backbone was published as 444 Research Report 4597 [1] by Cedric Adjih et al. 446 References 448 [1] Cedric Adjih, Phlippe Jacquet, and Laurent Veinnot. Computing 449 Connected Dominating Sets with Multipoint Relays. Technical 450 report, Institut National de Recherche en Informatique et en 451 Automatique (INRIA). INRIA RR 4597, October 2002. 453 [2] S. Bradner. Key words for use in RFCs to Indicate Requirement 454 Levels. Request for Comments (Best Current Practice) 2119, 455 Internet Engineering Task Force, March 1997. 457 [3] Ed. J. Manner and Ed. M. Kojo. Mobility Related Terminology. 458 Request for Comments (Informational) 3753, Internet Engineering 459 Task Force, June 2004. 461 [4] C. Perkins. Minimal Encapsulation within IP. Request for 462 Comments (Proposed Standard) 2004, Internet Engineering Task 463 Force, October 1996. 465 [5] Charles E. Perkins. IP Flooding in Ad hoc Networks (Work In 466 Progress). Internet Draft, Internet Engineering Task Force. 467 draft-perkins-manet-bcast-02.txt, June 2005. 469 [6] J. Postel. Internet Protocol. Request for Comments (Standard) 470 791, Internet Engineering Task Force, September 1981. 472 [7] Ed. T. Clausen and Ed. P. Jacquet. Optimized Link State Routing 473 Protocol (OLSR). Request for Comments (Experimental Protocol) 474 3626, Internet Engineering Task Force, June 2004. 476 Author's Addresses 478 Questions about this memo can be directed to: 480 Charles E. Perkins 481 Networking Technology Laboratory / Nokia Research Center 482 313 Fairchild Drive 483 Mountain View, CA 94303 484 +1 650 625 2986 485 +1 650 625-2502 (fax) 486 Charles.Perkins@nokia.com 488 Thomas Heide Clausen 489 INRIA Rocquencourt, BP 105, 490 78153 Le Chesnay Cedex 491 France 492 +33 1 3963 5133 493 Thomas.Clausen@inria.fr 495 Full Copyright Statement 497 Full Copyright Statement 499 Copyright (C) The Internet Society (2005). This document is subject 500 to the rights, licenses and restrictions contained in BCP 78, and 501 except as set forth therein, the authors retain all their rights. 503 This document and the information contained herein are provided 504 on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 505 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE 506 INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR 507 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 508 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 509 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.