idnits 2.17.1 draft-ietf-roll-mpl-forw-select-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == It seems as if not all pages are separated by form feeds - found 0 form feeds but 10 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.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (December 7, 2016) is 2696 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) ** Obsolete normative reference: RFC 7049 (Obsoleted by RFC 8949) Summary: 3 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 roll P. van der Stok 3 Internet-Draft consultant 4 Intended status: Standards Track AR. Sangi 5 Expires: June 10, 2017 Huawei Technologies 6 December 7, 2016 8 MPL Forwarder Select (MPLFS) 9 draft-ietf-roll-mpl-forw-select-00 11 Abstract 13 This document describes a Forwarder Selection (MPLFS) protocol for 14 the Multicast Protocol for Low-Power and lossy Networks (MPL) to 15 reduce the density of forwarders such that the number of forwarded 16 messages is reduced. 18 The protocol uses Trickle to distribute link-local information about 19 the identity of the neighbours of the nodes that have MPL-enabled 20 interfaces. In the end-state all nodes are connected to a minimum 21 number, N_DUPLICATE, of forwarders, where N_DUPLICATE is application 22 dependent, and there is a path between any two forwarders. 24 Note 26 Discussion and suggestions for improvement are requested, and should 27 be sent to roll@ietf.org. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on June 10, 2017. 46 Copyright Notice 48 Copyright (c) 2016 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 64 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Protocol overview . . . . . . . . . . . . . . . . . . . . . . 4 66 3. Data sets . . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 4. Neighbor distribution . . . . . . . . . . . . . . . . . . . . 5 68 5. Selection Algorithm . . . . . . . . . . . . . . . . . . . . . 6 69 6. CBOR payload . . . . . . . . . . . . . . . . . . . . . . . . 7 70 7. Default parameter values . . . . . . . . . . . . . . . . . . 7 71 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 72 9. Changelog . . . . . . . . . . . . . . . . . . . . . . . . . . 8 73 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 74 10.1. Normative References . . . . . . . . . . . . . . . . . . 8 75 10.2. Informative References . . . . . . . . . . . . . . . . . 9 76 Appendix A. example forwarder allocations . . . . . . . . . . . 9 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 79 1. Introduction 81 The Multicast Protocol for Low-Power and Lossy Networks (MPL) 82 [RFC7731] is designed for small devices interconnected by a lossy 83 wireless network such as IEEE 802.15.4. A seed sends a multicast 84 message with a realm-local scope, admin-local scope or higher as 85 specified in [RFC4291]. 87 Forwarders forward these messages with an increasing interval size. 88 When the density of the forwarders is high, the DATA_MESSAGE_K (k) 89 parameter stops the retransmission of messages in a given Trickle 90 interval when more than k copies of a message have been received. 91 This mechanism prevents network saturation but leads to difficult to 92 predict end-to-end data transmission delays. For IoT short 93 predictable delays are wanted and the k parameter is set to a large 94 value. When the density of forwarders is high and k is large, the 95 message may be forwarded by a high number of forwarders that conflict 96 on the link. With extreme forwarder densities, small Trickle 97 intervals, and k is infinite, just sending one multicast message may 98 lead to an overload of the communication medium. 100 The number of forwarded messages can be reduced by selecting a 101 minimal set of forwarders. However, for large networks, manually 102 selecting the forwarders is much work, and changing network 103 conditions and configurations make the manual selection an unwanted 104 burden to the network management. 106 This document specifies a protocol that selects the forwarders such 107 that each MPL-enabled device is connected to N_DUPLICATE forwarders, 108 where N_DUPLICATE > 0 can be set. The parameter N_DUPLICATE 109 determines how much path redundancy there is for each MPL message. 110 The value of N_DUPLICATE should be at least 1, because a value of 0 111 has as result that no forwarder exists in the network during the 112 protocol execution. Moreover, the protocol is distributed and 113 dynamic in nature to face a continuously changing topology. 115 The protocol is inspired by the work described for NeighbourHood 116 Discovery (NHDP) [RFC6130] and Simple Multicast Forwarding (SMF) 117 [RFC6621]. In contrast to the "HELLO" messages described in 118 [RFC6130], this protocol uses the Trickle protocol [RFC6206] to 119 multicast link-local messages, containing a CBOR payload [RFC7049]. 121 A simulation of the protocol has been done for some example 122 topologies. The number of forwarders allocated by the protocol are 123 compared in Appendix A with the optimum (lowest) number of forwarders 124 for these topologies. 126 1.1. Terminology 128 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 129 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 130 document are to be interpreted as described in [RFC2119]. 132 Readers of this specification should be familiar with all the terms 133 and concepts discussed in [RFC7731]. The following terms are defined 134 in this document: 136 synchronization time The moment that a node can change its state at 137 messages reception. 139 The following list contains the abbreviations used in this document. 141 XXXX: TODO, and others to follow. 143 2. Protocol overview 145 Nodes participating in MPLFS exchange messages with a format that is 146 described in Section 6. A participating node communicates to all its 147 neighbours with link-local multicast messages as described in 148 Section 4. 150 Failing links provide a lot of instability. Only messages sent over 151 stable links are accepted. Section 4 describes a mechanism to refuse 152 messages from unstable links. 154 Each node maintains a set of 1-hop neighbours where each neighbour 155 contains information about its own 1-hop neighbours. On the basis of 156 the contents of the set, the node can decide to become a Forwarder or 157 not, as explained in Section 5. 159 The protocol never ends, with a minimum frequency of exchanging 160 maintenance messages specified by an interval size of I_MAX_SELECT. 161 When the set of links is stable, the protocol stabilizes such that 162 there is a path between any two forwarders, and every MPL-enabled 163 node is connected to at least N_DUPLICATE MPL forwarders (when 164 existing), where N_DUPLICATE > 0. N_DUPLICATE can be set dependent 165 on the application requirements. With N_DUPLICATE = 2, it is 166 expected that a multicast message arrives at an intended recipient 167 with very high probability. 169 Nodes have a state that determines whether they are forwarder or not. 170 The state of a node can only be changed by the node itself. To avoid 171 race conditions, (e.g. two nodes simultaneously decide to be 172 forwarder, while only one is intended) the node with the highest 173 address of all 1-hop neighbours is the only one allowed to change 174 state. Unlike [RFC5614], that considers 3-tuple (Router Priority, 175 MDR Level and Router ID) to allow self state change, this approach 176 only takes into account the node address. Consequently, only k-hop 177 neighbours, with k > 2, can change state simultaneously, and the 178 1-hop and 2-hop neighbours of a given node can change state one by 179 one. 181 3. Data sets 183 Each node, n_0, maintains a state with two values: Fixed Forwarder 184 (FF) and No Forwarder (NF). Each node also maintains a set, S1_0, 185 containing information about n_0's 1-hop neighbours and n_0 itself. 186 Each entry, n_i, in S1_0 has the following attributes: 188 address of n_i: the address can be the 64 bit IPv6 address or the 189 short 16 bit address. 191 average-rssi-in: the average rssi of the messages received by n_0 192 from n_i. 194 average-rssi-out: the average rssi of the messages received by n_i 195 from n_0. 197 nr_FF: the number of neighbours, n_ij, of n_i (including n_i) with 198 state = FF. 200 nr_Under: the number of neighbours, n_ij, of n_i with nr_FF < 201 N_DUPLICATE. 203 nr_Above: the number of neighbours, n_ij, of n_i with nr_FF > 204 N_DUPLICATE. 206 size: the size of S1_i, the set of 1-hop neighbours of n_i. 208 state: the state of n_i. 210 4. Neighbor distribution 212 A participating node multicasts link-local so-called "neighbour 213 messages" with the Trickle protocol. It uses the multicast address 214 LINK_LOCAL_ALL_NODES as destination. The message sent by n_0 215 contains the contents of S1_0. The contents of a "neighbour message" 216 from n_i received by n_0 is called M_i. The rssi value associated 217 with the reception of the "neighbour message" is called new_rssi. 218 The message M_i contains information about the set S1_i with the 219 following attributes for all nodes in S1_i: 221 o address 223 o average-rssi-in 225 o nr_FF 227 o nr_Under 229 o nr_Above 231 o size 233 o state 235 On reception of M_i from n_i for the first time, the receiving node 236 adds n_i to S1_0, and sets average-rssi-in of n_i in S1_0 to 237 new_rssi. For all following messages from n_i, the average-rssi-in 238 for n_i is calculated in the following way: average-rssi-in := 239 (average-rssi-in*WEIGHT_AVERAGE + new_rssi)/(WEIGHT_AVERAGE+1). 241 The neighbour nodes of M_i are called n_ij. For the n_ij with an 242 address that is equal to the address of n_0: the value of average- 243 rssi-out of n_0 is set equal to the value of average-rssi-in of n_ij. 245 The contents of n_0 is updated with the contents of M_i. Updating 246 includes the following actions: 248 o Add n_i to S1_0, if n_i not present in S1_0. 250 o Set size of n_i equal to the number of entries in M_i. 252 o When n_ij.address = n_j.address, copy the values of nr_Under, 253 nr_Above, nr_FF, and state of n_ij to n_j. 255 When the average-rssi-in and average-rssi-out values of n_i have been 256 averaged over more than WEIGHT_AVERAGE messages, and the averaged 257 RSSI values are smaller than MAXIMUM_RSSI, n_i is called "valid". 259 5. Selection Algorithm 261 The protocol aims at allocating forwarders in the densest part of the 262 network. A dense network is characterized by a high number of 263 neighbours. Therefore, the protocol attempts to assign status FF to 264 the nodes with the highest number of neighbours that have less than 265 N_DUPLICATE neighbours with state = FF (nr_FF < N_DUPLICATE). 267 It is required that a path exists between every two forwarders to 268 prevent network partitioning. Therefore, a node can become forwarder 269 iff one of its neighbours is a forwarder. The consequence of this 270 rule is that one so-called "source-forwarder" must be selected by the 271 network administrator. A likely choice for the "source-forwarder" is 272 the border router. 274 At the start of the selection protocol the node, n_0, sets its state 275 to No Forwarder (NF). It sets the Trickle timer to its minimum 276 interval, I_MIN_SELECT, and starts multicasting M_0 to its 277 neighbours. Every time entries are added to, or removed from, S1_0, 278 the Trickle interval timer is set to I_MIN_SELECT. 280 The executing node, n_0, calculates the following parameter values: 282 o max-under is the maximum of the nr_Under attribute of all valid 283 n_i in S1_0. 285 o max_address_u is the maximum of the addresses of valid n_i with 286 nr_Under = max-under. 288 o max_address_a is the maximum of the addresses of all valid n_i. 290 o connected is true iff nr_FF of all neighbouring forwarders is 291 equal to nr_FF of n_0. 293 The information about the state and the nr_Under value of the 294 neighbours comes in asynchronously. Time is needed before the state 295 in a node correctly reflects the state changes of the network. A 296 node can change its state when during the reception of messages of 297 all neighbours, the value of nr_Under has not changed. 299 To calculate its new state, n_0 does the following: 301 When the state is NF, a neighbour with state = FF exists, and address 302 = max-address_u: 303 set state to FF. 305 When the state is FF, nr_Above = size S1_0, connected is true, and 306 address = max_address_a: 307 set state to NF. 309 6. CBOR payload 311 The payload format is /application/cbor [RFC7049]. The contents of 312 the message is a CBOR array (Major type 4) of CBOR arrays composed of 313 neighbour address, rssi value, size of S1_i, forwarder state, nr_FF, 314 nr_Under, and nr_Above. Assuming two neighbours, in diagnostic JSON 315 the payload looks like: 317 [ 318 [address_1, average-rssi-in_1, size_1, state_1, 319 nr_FF_1, nr_Under_1, nr_Above_1], 320 [address_2, average-rssi-in_2, size_2, state_2, 321 nr_FF_2, nr_Under_2, nr_Above_2] 322 ] 324 Figure 1: CBOR payload 326 7. Default parameter values 328 The following text recommends default values for the MPLFS protocols. 330 I_MIN_SELECT = 0,2; minimum Trickle timer interval. 332 I_MAX_SELECT = 10; maximum Trickle timer interval. 334 DATA_MESSAGE_K > 10; the redundancy constant. 336 WEIGHT_AVERAGE = 10; number of values to average rssi. 338 MAXIMUM_RSSI = 3; maximum acceptable average rssi value. 340 N_DUPLICATE = 2; requested number of MPL forwarder neighbours for 341 every MPL enabled node. 343 8. Acknowledgements 345 We are very grateful to Yasuyuki Tanaka for pointing out the missing 346 discussion on k-values. 348 9. Changelog 350 Changes from vanderstok version to ietf version 00 352 o copied from vanderstok-roll-forw-select-01 354 o added discussion on DATA_MESSAGE_K 356 o compared generated forwarder set with optmal set 358 10. References 360 10.1. Normative References 362 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 363 Requirement Levels", BCP 14, RFC 2119, 364 DOI 10.17487/RFC2119, March 1997, 365 . 367 [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko, 368 "The Trickle Algorithm", RFC 6206, DOI 10.17487/RFC6206, 369 March 2011, . 371 [RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object 372 Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, 373 October 2013, . 375 [RFC7731] Hui, J. and R. Kelsey, "Multicast Protocol for Low-Power 376 and Lossy Networks (MPL)", RFC 7731, DOI 10.17487/RFC7731, 377 February 2016, . 379 10.2. Informative References 381 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 382 Architecture", RFC 4291, DOI 10.17487/RFC4291, February 383 2006, . 385 [RFC5614] Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET) 386 Extension of OSPF Using Connected Dominating Set (CDS) 387 Flooding", RFC 5614, DOI 10.17487/RFC5614, August 2009, 388 . 390 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 391 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 392 RFC 6130, DOI 10.17487/RFC6130, April 2011, 393 . 395 [RFC6621] Macker, J., Ed., "Simplified Multicast Forwarding", 396 RFC 6621, DOI 10.17487/RFC6621, May 2012, 397 . 399 Appendix A. example forwarder allocations 401 The protocol has been simulated with omnet++ on four different 402 network topologies. The value of N_DUPLICATE is set to two. Each 403 topology is a rectangular grid, where each grid point is occupied by 404 a node. The distance, D, between two horizontal and vertical direct 405 neighbours is the same. The topologies differ in number of grid 406 points and D. A topology of 9x9 grid points shows how the selection 407 criteria of the protocol affect the distribution of the forwarders 408 when the number of edge nodes is small compared to the number of 409 interior nodes. A topology of 3x20 nodes shows the distribution with 410 a majority of edge nodes. Two radio ranges of the link have been 411 selected: (1) a range of 3,5 times D, and (2) a range of 7 times D. 412 The node density of case 2 is four times higher than for case 1. The 413 two example ranges nicely show how the average distance between the 414 forwarders increases with increasing range. 416 Table 1 shows the comparison results. Column one indicates the grid 417 topology, Columns 2 indicates the radio range, column 3 indicates the 418 number of protocol forwarders as delivered by the simulation, column 419 four indicates the minimum number of forwarders needed to arrive at 420 at least N-DUPLICATE forwarders for all nodes, column five cites the 421 number of nodes. 423 +----------+--------+------------+---------+-------+ 424 | topology | range | forwarders | optimum | nodes | 425 +----------+--------+------------+---------+-------+ 426 | 9x9 | 3,5 D | 10 | 9 | 81 | 427 | | | | | | 428 | 9x9 | 7 D | 3 | 3 | 81 | 429 | | | | | | 430 | 3x20 | 3,5 D | 8 | 8 | 60 | 431 | | | | | | 432 | 3x20 | 7 D | 5 | 5 | 60 | 433 +----------+--------+------------+---------+-------+ 435 Table 1: comparison of protocol set size and optimal set 437 The table gives confidence that for many cases the size of the 438 protocol forwarder set will be close to the size of an optimal set. 440 Authors' Addresses 442 Peter van der Stok 443 consultant 445 Phone: +31-492474673 (Netherlands), +33-966015248 (France) 446 Email: consultancy@vanderstok.org 447 URI: www.vanderstok.org 449 Abdur Rashid Sangi 450 Huawei Technologies 451 No.156 Beiqing Rd. Haidian District 452 Beijing 100095 453 P.R. China 455 Email: rashid.sangi@huawei.com