idnits 2.17.1 draft-vanderstok-roll-mpl-forw-select-01.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 9 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 (October 14, 2016) is 2750 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: April 17, 2017 Huawei Technologies 6 October 14, 2016 8 MPL Forwarder Select (MPLFS) 9 draft-vanderstok-roll-mpl-forw-select-01 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. The protocol uses Trickle to distribute link- 17 local information about the identity of the neighbours of the nodes 18 that have MPL-enabled interfaces. In the end-state all nodes are 19 connected to a minimum number, N_DUPLICATE, of forwarders, where 20 N_DUPLICATE is application dependent, and there is a path between any 21 two forwarders. 23 Note 25 Discussion and suggestions for improvement are requested, and should 26 be sent to roll@ietf.org. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on April 17, 2017. 45 Copyright Notice 47 Copyright (c) 2016 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 63 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 64 2. Protocol overview . . . . . . . . . . . . . . . . . . . . . . 3 65 3. Data sets . . . . . . . . . . . . . . . . . . . . . . . . . . 4 66 4. Neighbor distribution . . . . . . . . . . . . . . . . . . . . 5 67 5. Selection Algorithm . . . . . . . . . . . . . . . . . . . . . 6 68 6. CBOR payload . . . . . . . . . . . . . . . . . . . . . . . . 7 69 7. Default parameter values . . . . . . . . . . . . . . . . . . 7 70 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7 71 9. Changelog . . . . . . . . . . . . . . . . . . . . . . . . . . 8 72 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 73 10.1. Normative References . . . . . . . . . . . . . . . . . . 8 74 10.2. Informative References . . . . . . . . . . . . . . . . . 8 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 77 1. Introduction 79 The Multicast Protocol for Low-Power and Lossy Networks (MPL) 80 [RFC7731] is designed for small devices interconnected by a lossy 81 wireless network such as IEEE 802.15.4. A seed sends a multicast 82 message with a realm-local scope, admin-local scope or higher as 83 specified in [RFC4291]. 85 Forwarders forward these messages with an increasing interval size. 86 When the density of forwarders is high, the message may be forwarded 87 by a high number of forwarders that conflict on the link. With 88 extreme forwarder densities and small Trickle intervals, just sending 89 one multicast message may lead to an overload of the communication 90 medium. 92 The number of forwarded messages can be reduced by selecting a 93 minimal set of forwarders. However, for large networks, manually 94 selecting the forwarders is much work, and changing network 95 conditions and configurations make the manual selection an unwanted 96 burden to the network management. 98 This document specifies a protocol that selects the forwarders such 99 that each MPL-enabled device is connected to N_DUPLICATE forwarders, 100 where N_DUPLICATE > 0 can be set. The parameter N_DUPLICATE 101 determines how much path redundancy there is for each MPL message. 102 The value of N_DUPLICATE should be at least 1, because a value of 0 103 has as result that no forwarder exists in the network during the 104 protocol execution. Moreover, the protocol is distributed and 105 dynamic in nature to face a continuously changing topology. 107 The protocol is inspired by the work described for NeighbourHood 108 Discovery (NHDP) [RFC6130] and Simple Multicast Forwarding (SMF) 109 [RFC6621]. In contrast to the "HELLO" messages described in 110 [RFC6130], this protocol uses the Trickle protocol [RFC6206] to 111 multicast link-local messages, containing a CBOR payload [RFC7049]. 113 1.1. Terminology 115 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 116 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 117 document are to be interpreted as described in [RFC2119]. 119 Readers of this specification should be familiar with all the terms 120 and concepts discussed in [RFC7731]. The following terms are defined 121 in this document: 123 synchronization time The moment that a node can change its state at 124 messages reception. 126 The following list contains the abbreviations used in this document. 128 XXXX: TODO, and others to follow. 130 2. Protocol overview 132 Nodes participating in MPLFS exchange messages with a format that is 133 described in Section 6. A participating node communicates to all its 134 neighbours with link-local multicast messages as described in 135 Section 4. 137 Failing links provide a lot of instability. Only messages sent over 138 stable links are accepted. Section 4 describes a mechanism to refuse 139 messages from unstable links. 141 Each node maintains a set of 1-hop neighbours where each neighbour 142 contains information about its own 1-hop neighbours. On the basis of 143 the contents of the set, the node can decide to become a Forwarder or 144 not, as explained in Section 5. 146 The protocol never ends, with a minimum frequency of exchanging 147 maintenance messages specified by an interval size of I_MAX_SELECT. 148 When the set of links is stable, the protocol stabilizes such that 149 there is a path between any two forwarders, and every MPL-enabled 150 node is connected to at least N_DUPLICATE MPL forwarders (when 151 existing), where N_DUPLICATE > 0. N_DUPLICATE can be set dependent 152 on the application requirements. With N_DUPLICATE = 2, it is 153 expected that a multicast message arrives at an intended recipient 154 with very high probability. 156 Nodes have a state that determines whether they are forwarder or not. 157 The state of a node can only be changed by the node itself. To avoid 158 race conditions, (e.g. two nodes simultaneously decide to be no 159 forwarder, while only one is intended) the node with the highest 160 address of all 1-hop neighbours is the only one allowed to change 161 state. Unlike [RFC5614], that considers 3-tuple (Router Priority, 162 MDR Level and Router ID) to allow self state change, this approach 163 only takes into account the node address. Consequently, only k-hop 164 neighbours, with k > 2, can change state simultaneously, and the 165 1-hop and 2-hop neighbours of a given node can change state one by 166 one. 168 3. Data sets 170 Each node, n_0, maintains a state with two values: Fixed Forwarder 171 (FF) and No Forwarder (NF). Each node also maintains a set, S1_0, 172 containing information about n_0's 1-hop neighbours and n_0 itself. 173 Each entry, n_i, in S1_0 has the following attributes: 175 address of n_i: the address can be the 64 bit IPv6 address or the 176 short 16 bit address. 178 average-rssi-in: the average rssi of the messages received by n_0 179 from n_i. 181 average-rssi-out: the average rssi of the messages received by n_i 182 from n_0. 184 nr_FF: the number of neighbours, n_ij, of n_i (including n_i) with 185 state = FF. 187 nr_Under: the number of neighbours, n_ij, of n_i with nr_FF < 188 N_DUPLICATE. 190 nr_Above: the number of neighbours, n_ij, of n_i with nr_FF > 191 N_DUPLICATE. 193 size: the size of S1_i, the set of 1-hop neighbours of n_i. 195 state: the state of n_i. 197 4. Neighbor distribution 199 A participating node multicasts link-local so-called "neighbour 200 messages" with the Trickle protocol. It uses the multicast address 201 LINK_LOCAL_ALL_NODES as destination. The message sent by n_0 202 contains the contents of S1_0. The contents of a "neighbour message" 203 from n_i received by n_0 is called M_i. The rssi value associated 204 with the reception of the "neighbour message" is called new_rssi. 205 The message M_i contains information about the set S1_i with the 206 following attributes for all nodes in S1_i: 208 o address 210 o average-rssi-in 212 o nr_FF 214 o nr_Under 216 o nr_Above 218 o size 220 o state 222 On reception of M_i from n_i for the first time, the receiving node 223 adds n_i to S1_0, and sets average-rssi-in of n_i in S1_0 to 224 new_rssi. For all following messages from n_i, the average-rssi-in 225 for n_i is calculated in the following way: average-rssi-in := 226 (average-rssi-in*WEIGHT_AVERAGE + new_rssi)/(WEIGHT_AVERAGE+1). 228 The neighbour nodes of M_i are called n_ij. For the n_ij with an 229 address that is equal to the address of n_0: the value of average- 230 rssi-out of n_0 is set equal to the value of average-rssi-in of n_ij. 232 The contents of n_0 is updated with the contents of M_i. Updating 233 includes the following actions: 235 o Add n_i to S1_0, if n_i not present in S1_0. 237 o Set size of n_i equal to the number of entries in M_i. 239 o When n_ij.address = n_j.address, copy the values of nr_Under, 240 nr_Above, nr_FF, and state of n_ij to n_j. 242 When the average-rssi-in and average-rssi-out values of n_i have been 243 averaged over more than WEIGHT_AVERAGE messages, and the averaged 244 RSSI values are smaller than MAXIMUM_RSSI, n_i is called "valid". 246 5. Selection Algorithm 248 The protocol aims at allocating forwarders in the densest part of the 249 network. A dense network is characterized by a high number of 250 neighbours. Therefore, the protocol attempts to assign status FF to 251 the nodes with the highest number of neighbours that have less than 252 N_DUPLICATE neighbours with state = FF (nr_FF < N_DUPLICATE). 254 It is required that a path exists between every two forwarders to 255 prevent network partitioning. Therefore, a node can become forwarder 256 iff one of its neighbours is a forwarder. The consequence of this 257 rule is that one so-called "source-forwarder" must be selected by the 258 network administrator. A likely choice for the "source-forwarder" is 259 the border router. 261 At the start of the selection protocol the node, n_0, sets its state 262 to No Forwarder (NF). It sets the Trickle timer to its minimum 263 interval, I_MIN_SELECT, and starts multicasting M_0 to its 264 neighbours. Every time entries are added to, or removed from, S1_0, 265 the Trickle interval timer is set to I_MIN_SELECT. 267 The executing node, n_0, calculates the following parameter values: 269 o max-under is the maximum of the nr_Under attribute of all valid 270 n_i in S1_0. 272 o max_address_u is the maximum of the addresses of valid n_i with 273 nr_Under = max-under. 275 o max_address_a is the maximum of the addresses of all valid n_i. 277 o connected is true iff nr_FF of all neighbouring forwarders is 278 equal to nr_FF of n_0. 280 The information about the state and the nr_Under value of the 281 neighbours comes in asynchronously. Time is needed before the state 282 in a node correctly reflects the state changes of the network. A 283 node can change its state when during the reception of messages of 284 all neighbours, the value of nr_Under has not changed. 286 To calculate its new state, n_0 does the following: 288 When the state is NF, a neighbour with state = FF exists, and address 289 = max-address_u: 290 set state to FF. 292 When the state is FF, nr_Above = size S1_0, connected is true, and 293 address = max_address_a: 294 set state to NF. 296 6. CBOR payload 298 The payload format is /application/cbor [RFC7049]. The contents of 299 the message is a CBOR array (Major type 4) of CBOR arrays composed of 300 neighbour address, rssi value, size of S1_i, forwarder state, nr_FF, 301 nr_Under, and nr_Above. Assuming two neighbours, in diagnostic JSON 302 the payload looks like: 304 [ 305 [address_1, average-rssi-in_1, size_1, state_1, 306 nr_FF_1, nr_Under_1, nr_Above_1], 307 [address_2, average-rssi-in_2, size_2, state_2, 308 nr_FF_2, nr_Under_2, nr_Above_2] 309 ] 311 Figure 1: CBOR payload 313 7. Default parameter values 315 The following text recommends default values for the MPLFS protocols. 317 I_MIN_SELECT = 0,2; minimum Trickle timer interval. 319 I_MAX_SELECT = 10; maximum Trickle timer interval. 321 WEIGHT_AVERAGE = 10; number of values to average rssi. 323 MAXIMUM_RSSI = 3; maximum acceptable average rssi value. 325 N_DUPLICATE = 2; requested number of MPL forwarder neighbours for 326 every MPL enabled node. 328 8. Acknowledgements 330 We are very grateful to 332 9. Changelog 334 Changes from version 00 to version 01 336 o Definition of S1_0 improved 338 o Algorithm changed and simulated 340 o Moment of state change specified 342 10. References 344 10.1. Normative References 346 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 347 Requirement Levels", BCP 14, RFC 2119, 348 DOI 10.17487/RFC2119, March 1997, 349 . 351 [RFC6206] Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko, 352 "The Trickle Algorithm", RFC 6206, DOI 10.17487/RFC6206, 353 March 2011, . 355 [RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object 356 Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, 357 October 2013, . 359 [RFC7731] Hui, J. and R. Kelsey, "Multicast Protocol for Low-Power 360 and Lossy Networks (MPL)", RFC 7731, DOI 10.17487/RFC7731, 361 February 2016, . 363 10.2. Informative References 365 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 366 Architecture", RFC 4291, DOI 10.17487/RFC4291, February 367 2006, . 369 [RFC5614] Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET) 370 Extension of OSPF Using Connected Dominating Set (CDS) 371 Flooding", RFC 5614, DOI 10.17487/RFC5614, August 2009, 372 . 374 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 375 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 376 RFC 6130, DOI 10.17487/RFC6130, April 2011, 377 . 379 [RFC6621] Macker, J., Ed., "Simplified Multicast Forwarding", 380 RFC 6621, DOI 10.17487/RFC6621, May 2012, 381 . 383 Authors' Addresses 385 Peter van der Stok 386 consultant 388 Phone: +31-492474673 (Netherlands), +33-966015248 (France) 389 Email: consultancy@vanderstok.org 390 URI: www.vanderstok.org 392 Abdur Rashid Sangi 393 Huawei Technologies 394 No.156 Beiqing Rd. Haidian District 395 Beijing 100095 396 P.R. China 398 Email: rashid.sangi@huawei.com