MPL Forwarder Select (MPLFS)
draft-vanderstok-roll-mpl-forw-select-00

roll                                                     P. van der Stok
Internet-Draft                                                consultant
Intended status: Standards Track                               AR. Sangi
Expires: January 5, 2017                             Huawei Technologies
                                                            July 4, 2016

                      MPL Forwarder Select (MPLFS)
                draft-vanderstok-roll-mpl-forw-select-00

Abstract

   This document describes a Forwarder Selection (MPLFS) protocol for
   the Multicast Protocol for Low-Power and lossy Networks (MPL) to
   reduce the density of forwarders such that the number of forwarded
   messages is reduced.  The protocol uses Trickle to distribute link-
   local information about the identity of the neighbours of the nodes
   which are enabled for MPL.  In the end-state all nodes are connected
   to a minimum number, N_DUPLICATE, of forwarders, where N_DUPLICATE is
   application dependent.

Note

   Discussion and suggestions for improvement are requested, and should
   be sent to roll@ietf.org.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on January 5, 2017.

Copyright Notice

   Copyright (c) 2016 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

van der Stok & Sangi     Expires January 5, 2017                [Page 1]

Internet-Draft                    MPLFS                        July 2016

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Terminology . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Protocol overview . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Data sets . . . . . . . . . . . . . . . . . . . . . . . . . .   4
   4.  Neighbor distribution . . . . . . . . . . . . . . . . . . . .   5
   5.  Selection Algorithm . . . . . . . . . . . . . . . . . . . . .   6
   6.  CBOR payload  . . . . . . . . . . . . . . . . . . . . . . . .   6
   7.  Default parameter values  . . . . . . . . . . . . . . . . . .   7
   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   7
   9.  Changelog . . . . . . . . . . . . . . . . . . . . . . . . . .   7
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .   7
     10.1.  Normative References . . . . . . . . . . . . . . . . . .   7
     10.2.  Informative References . . . . . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   8

1.  Introduction

   The Multicast Protocol for Low-Power and Lossy Networks (MPL)
   [RFC7731] is designed for small devices interconnected by a lossy
   wireless network such as IEEE 802.15.4.  A seed sends a multicast
   message with a realm-local scope, admin-local scope or higher
   [RFC4291].

   Forwarders forward these messages with an increasing interval size.
   When the density of forwarders is high, the message may be forwarded
   for a possibly unacceptable number of times.  With extreme forwarder
   densities and small Trickle intervals, just sending one multicast
   message may lead to an overload of the communication medium.

   The number of forwarded messages can be reduced by selecting a
   minimal set of forwarders.  However, for large networks, manually
   selecting the forwarders is much work, and changing network
   conditions and configurations make the manual selection an unwanted
   burden to the network management.

van der Stok & Sangi     Expires January 5, 2017                [Page 2]

Internet-Draft                    MPLFS                        July 2016

   This document specifies a protocol that selects the forwarders such
   that each MPL-enabled device is connected to N_DUPLICATE forwarders,
   where N_DUPLICATE > 0 can be set.  The parameter N_DUPLICATE
   determines how much path redundancy there is for each MPL message.
   The value of N_DUPLICATE should be at least 1, because a value of 0
   has as result that no forwarder exists in the network during the
   protocol execution.  Moreover, the approach is distributed and
   dynamic in nature to meet ever changing topology as well as
   rationally minimizing the selected forwarding nodes.

   The protocol is inspired by the work described for NeighbourHood
   Discovery (NHDP) [RFC6130] and Simple Multicast Forwarding (SMF)
   [RFC6621].  In contrast to the "HELLO" messages described in
   [RFC6130], this protocol uses the Trickle protocol [RFC6206] to
   multicast link-local messages, containing a CBOR payload [RFC7049].

1.1.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

   Readers of this specification should be familiar with all the terms
   and concepts discussed in [RFC7731].  The following terms are defined
   in this document:

   TODO  new terms used in this document

   The following list contains the abbreviations used in this document.

   XXXX:  TODO, and others to follow.

2.  Protocol overview

   Nodes participating in MPLFS exchange messages with a format that is
   described in Section 6.  A participating node communicates to all its
   neighbours with link-local multicast messages as described in
   Section 4.

   Failing links provide a lot of instability.  Only messages sent over
   stable links are accepted.  Section 4 describes a mechanism to refuse
   messages from unstable links.

   Each node maintains a set of 1-hop neighbours and a set of 2-hop
   neighbours.  On the basis of the contents of the set, the node can
   decide to become a Forwarder or not, as explained in Section 5.

van der Stok & Sangi     Expires January 5, 2017                [Page 3]

Internet-Draft                    MPLFS                        July 2016

   The protocol never ends, with a minimum frequency of exchanging
   maintenance messages specified by an interval size of I_MAX_SELECT.
   When the set of links is stable, the protocol stabilizes such that
   every MPL-enabled node is connected to at least N_DUPLICATE MPL
   forwarders (when existing), where N_DUPLICATE > 0.  N_DUPLICATE can
   be set dependent on the application requirements.  With N_DUPLICATE =
   2, it is expected that a message does not arrive at an intended
   recipient with very low probability.

   Nodes have a state that determines whether they are forwarder or not.
   The state of a node can only be changed by the node itself.  To avoid
   race conditions, (e.g. two nodes simultaneously decide to be no
   forwarder, while only one is intended) the node with the highest
   address of all 2-hop neighbours is the only one allowed to change
   state.  Unlike [RFC5614], that considers 3-tuple (Router Priority,
   MDR Level and Router ID) to allow self state change, this approach
   only takes into account the node address.  Consequently, only k-hop
   neighbours, with k > 2, can change state simultaneously, and the
   1-hop and 2-hop neighbours of a given node can change state one by
   one.

3.  Data sets

   Each node, n_0, maintains a state with three values: Possible
   Forwarder (PF), Fixed Forwarder (FF) and No Forwarder (NF).  Each
   node also maintains a set, S1_0, containing information about n_0's
   1-hop neighbours and a set S2_0 containing information about n_0's
   2-hop neighbours.  Each entry, n_i, in S1_0 or S2_0 has the following
   attributes:

   address of n_i:   the address can be the 64 bit IPv6 address or the
      short 16 bit address.

   average-rssi-in:   the average rssi of the messages received by n_0
      from n_i.

   average-rssi-out:   the average rssi of the messages received by n_i
      from n_0.

   nr_FF:   the number of n_i in S1_0 with state = FF.

   nr_under:   the number of neighbours of n_i in S1_0 with nr_FF <
      N_DUPLICATE.

   size:   the size of S1_i, the set of 1-hop neighbours of n_i.

   state:   the state of n_i.

van der Stok & Sangi     Expires January 5, 2017                [Page 4]

Internet-Draft                    MPLFS                        July 2016

   During the protocol execution the state of the nodes change.
   Although the protocol never ends due to changes in configuration and
   link state, in a steady state, no node has the state PF.

4.  Neighbor distribution

   A participating node multicasts link-local so-called "neighbour
   messages" with the Trickle protocol.  It uses the multicast address
   LINK_LOCAL_ALL_NODES as destination.  The message sent by n_0
   contains the contents of S1_0.  The contents of a "neighbour message"
   from n_i received by n_0 is called M_i.  The rssi value associated
   with the reception of the "neighbour message" is called new_rssi.
   The message M_i describes n_i followed by the neighbours of n_i with
   the following attributes:

   o  address, is address of n_i

   o  average-rssi-in

   o  nr_FF

   o  nr_Under

   o  size

   o  state

   On reception of M_i from n_i for the first time, the receiving node
   adds n_i to S1_0, and sets average-rssi-in to new_rssi.  For all
   following messages from n_i, the average-rssi-in for n_i is
   calculated in the following way: average-rssi-in := (average-rssi-
   in*WEIGHT_AVERAGE + new_rssi)/(WEIGHT_AVERAGE+1).

   The entries of M_i are called n_ij.  For the entry n_ij with an
   address that is equal to the address of n_0: the value of average-
   rssi-out of n_i is set equal to the value of average-rssi-in of n_ij.

   When the average-rssi-in and average-rssi-out values have been
   averaged over more than WEIGHT_AVERAGE messages, and the averaged
   RSSI values are smaller than MAXIMUM_RSSI, n_0 updates the contents
   of S1_0 and S2_0 with the contents of M_i.

   o  Add n_i to S1_0, or refresh values of n_i.

   o  For every entry n_ij in M_i that is not present in S1_0 add n_ij
      to S2_0.

   o  Set size of n_i equal to the number of entries in M_i.

van der Stok & Sangi     Expires January 5, 2017                [Page 5]

Internet-Draft                    MPLFS                        July 2016

   Set nr_FF equal to the number of n_i in S1_0 with state is equal to
   FF.  Set nr-Under equal to the the number of n_i with nr_FF <
   N_DUPLICATE.

5.  Selection Algorithm

   The protocol allocates forwarders in the densest part of the network.
   A dense network is characterized by a high number of neighbours.
   Therefore, the protocol attempts to assign status FF to the nodes
   with the highest number of neighbours that have less than N_DUPLICATE
   neighbours with state = FF.

   At the start of the selection protocol every node sets its state to
   Possible Forwarder (PF).  It sets the Trickle timer to its minimum
   interval, I_MIN_SELECT, and starts multicasting M_0 to its
   neighbours.  Every time entries are added to, or removed from, S1_0
   or S2_0, the Trickle interval timer is set to I_MIN_SELECT.

   The executing node, n_0, calculates for all entries of S1_0 and S2_0
   with state PF:

   o  max-under is the maximum of the nr_Under attribute.

   o  max_address is the maximum of the addresses of the entries with
      nr_Under =max-under.

   To calculate its new state, n_0 does the following at the next
   synchronization moment:

   When the state is not equal to FF and nr_Under = max-under and
   address = max-address: set state to FF.

   Discussion:

   The information about the state and the nr_under value of the
   neighbours comes in asynchronously.  A criterion must be defined,
   called synchronization moment, that these values can be trusted to
   represent the state of the neighbours at this moment of time.

6.  CBOR payload

   The payload format is /application/cbor [RFC7049].  The contents of
   the message is the rssi value of messages received by the neighbour,
   followed by a list of lists composed of neighbour address, rssi
   value, size of S1_i, forwarder state, nr_FF, and nr_Under.  Assuming
   two neighbours, in diagnostic JSON the payload looks like:

van der Stok & Sangi     Expires January 5, 2017                [Page 6]

Internet-Draft                    MPLFS                        July 2016

   [
   [address_1, average-rssi-in_1, size_1, state_1, nr_FF_1, nr_Under_1],
   [address_2, average-rssi-in_2, size_2, state_2, nr_FF_2, nr_Under_2]
   ]

                          Figure 1: CBOR payload

7.  Default parameter values

   The following text recommends default values for the MPLFS protocols.

   I_MIN_SELECT  = 0,2; minimum Trickle timer interval.

   I_MAX_SELECT  = 10; maximum Trickle timer interval.

   WEIGHT_AVERAGE  = 10; number of values to average rssi.

   MAXIMUM_RSSI  = 3; maximum acceptable average rssi value.

   N_DUPLICATE  = 2; requested number of MPL forwarder neighbours for
      every MPL enabled node.

8.  Acknowledgements

   We are very grateful to

9.  Changelog

   Changes from version 00 to version 01

   o  Not yet relevant

10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>.

   [RFC6206]  Levis, P., Clausen, T., Hui, J., Gnawali, O., and J. Ko,
              "The Trickle Algorithm", RFC 6206, DOI 10.17487/RFC6206,
              March 2011, <http://www.rfc-editor.org/info/rfc6206>.

   [RFC7049]  Bormann, C. and P. Hoffman, "Concise Binary Object
              Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049,
              October 2013, <http://www.rfc-editor.org/info/rfc7049>.

van der Stok & Sangi     Expires January 5, 2017                [Page 7]

Internet-Draft                    MPLFS                        July 2016

   [RFC7731]  Hui, J. and R. Kelsey, "Multicast Protocol for Low-Power
              and Lossy Networks (MPL)", RFC 7731, DOI 10.17487/RFC7731,
              February 2016, <http://www.rfc-editor.org/info/rfc7731>.

10.2.  Informative References

   [RFC4291]  Hinden, R. and S. Deering, "IP Version 6 Addressing
              Architecture", RFC 4291, DOI 10.17487/RFC4291, February
              2006, <http://www.rfc-editor.org/info/rfc4291>.

   [RFC5614]  Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET)
              Extension of OSPF Using Connected Dominating Set (CDS)
              Flooding", RFC 5614, DOI 10.17487/RFC5614, August 2009,
              <http://www.rfc-editor.org/info/rfc5614>.

   [RFC6130]  Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc
              Network (MANET) Neighborhood Discovery Protocol (NHDP)",
              RFC 6130, DOI 10.17487/RFC6130, April 2011,
              <http://www.rfc-editor.org/info/rfc6130>.

   [RFC6621]  Macker, J., Ed., "Simplified Multicast Forwarding",
              RFC 6621, DOI 10.17487/RFC6621, May 2012,
              <http://www.rfc-editor.org/info/rfc6621>.

Authors' Addresses

   Peter van der Stok
   consultant

   Phone: +31-492474673 (Netherlands), +33-966015248 (France)
   Email: consultancy@vanderstok.org
   URI:   www.vanderstok.org

   Abdur Rashid Sangi
   Huawei Technologies
   No.156 Beiqing Rd. Haidian District
   Beijing  100095
   P.R. China

   Email: rashid.sangi@huawei.com

van der Stok & Sangi     Expires January 5, 2017                [Page 8]