Internet DRAFT - draft-ji-traffic-aware-objective-function

draft-ji-traffic-aware-objective-function







ROLL                                                          C. Ji, Ed.
Internet-Draft                                           R. Koutsiamanis
Intended status: Standards Track                         G. Papadopoulos
Expires: June 4, 2018                                     IMT Atlantique
                                                              D. Dujovne
                                              Universidad Diego Portales
                                                            N. Montavont
                                                          IMT Atlantique
                                                        December 1, 2017


                    Traffic-aware Objective Function
              draft-ji-traffic-aware-objective-function-00

Abstract

   This document proposes a packet transmission rate metric for parent
   selection.  This metric represents the amount of traffic that the
   node is transmitting to the current parent node.  This document also
   proposes an Objective Function (OF) using the packet transmission
   rate metric for parent selection in order to balance the amount of
   traffic between nodes.

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 https://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 June 4, 2018.

Copyright Notice

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

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (https://trustee.ietf.org/license-info) in effect on the date of



Ji, et al.                Expires June 4, 2018                  [Page 1]

Internet-Draft              Traffic-aware OF               December 2017


   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
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.  DODAG construction in RPL . . . . . . . . . . . . . . . . . .   3
   4.  Load distribution problem in RPL  . . . . . . . . . . . . . .   3
   5.  TAOF description  . . . . . . . . . . . . . . . . . . . . . .   5
   6.  DIO Metric Container Type extension . . . . . . . . . . . . .   6
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .   7
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   7
   9.  Informative references  . . . . . . . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   8

1.  Introduction

   RPL [RFC6550] is an IPv6 Routing protocol for LLNs.  It uses
   Objective Functions (OF) to construct the Destination Oriented
   Directed Acyclic Graph (DODAG) containing the nodes of the network.
   The existing OFs defined are OF Zero (OF0) [RFC6552] and Minimum Rank
   with Hysteresis OF (MRHOF) [RFC6719].  These OFs specify how nodes in
   a DODAG select their preferred parent using different metrics.

   The metrics can be separated into two different types, link metrics
   (e.g.  ETX) and node metrics (e.g. energy).  Experimental results
   [I-D.qasem-roll-rpl-load-balancing] conclude that using the current
   OFs leads to an unbalanced network within which some of the nodes are
   overloaded.  In this case, a node is overloaded in the sense that it
   forwards much more packets than it otherwise would if the network
   were balanced.  This problem has consequences for the lifetime of the
   network because overloaded nodes tend to drain quicker than others, a
   problem which becomes even more significant when the overloaded nodes
   are near the DODAG root [I-D.qasem-roll-rpl-load-balancing].

   This problem is still an open issue and this draft proposes a new way
   of parent selection as an attempt towards a solution.  This draft
   proposes a new OF that considers the packet transmission rate as a
   representation of traffic each node faces and use this information to
   balance the amount of traffic between nodes.

   In brief, each node tracks its packet transmission rate and appends
   this information to DIO messages it sends as a DAG Metric Container



Ji, et al.                Expires June 4, 2018                  [Page 2]

Internet-Draft              Traffic-aware OF               December 2017


   option.  When the DIO message is received by child nodes or potential
   child nodes, the packet transmission rate information is stored and
   used to influence the result when RPL parent selection is performed.

2.  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].

3.  DODAG construction in RPL

   RPL uses OFs to construct a DODAG.  OFs define the way the nodes
   select their preferred parent and how they compute the new rank.  A
   node's rank is always larger than its parent's rank because the
   calculation of rank is based on an increment to the parent's rank.
   This increment differs for each OF but all include the
   MinHopRankIncrease which is the minimum increase in rank between a
   node and a node's parent and a step.  Different OFs use different
   metrics or constraints to select the preferred parent and to define
   the step, depending on application requirements.  Nodes obtain these
   values from DODAG Information Object (DIO) control messages sent by
   their neighbor nodes.

   The construction of a DODAG starts when the root node sends DIO
   messages to its neighbors.  After receiving the DIO, these neighbor
   nodes select the root as their preferred parent if they wish to join
   the DODAG.  In order to announce that they joined the DODAG as its
   child node, they send a Destination Advertisement Object (DAO) to
   their preferred parent - the DODAG root.  After joining the DODAG,
   these nodes send their own DIO messages with the new computed rank to
   their neighbors.  This procedure repeats for every node which joins
   the DODAG.

4.  Load distribution problem in RPL

   Numerous experiments using existing OFs have been conducted and
   according to results, RPL faces a load distribution problem in large
   LLNs.  With RPL using existing OFs, such as MRHOF, an unbalanced
   network is formed with some of the nodes overloaded and other nodes
   at rest.  This problem is severe for network performance because
   overloaded nodes will use up their available energy faster than other
   nodes.  This is exacerbated for nodes near the root (within 1 hop
   distance) or nodes which are the only parent candidate for some other
   nodes.  Additionally, when the overloaded node shuts down, a big part
   of the network will become disconnected and will have to be
   transferred to another parent.  There is a high probability that the
   children nodes will also select the same new node as their parent,



Ji, et al.                Expires June 4, 2018                  [Page 3]

Internet-Draft              Traffic-aware OF               December 2017


   leading to another overloaded node.  Also, when a node has selected
   its parent, it will change only when the parent node is not reachable
   (due to battery depletion or packet losses).

   The existing OFs usually use a single metric to compare parent
   candidates, for example, as described in [RFC6719] the default metric
   used in MRHOF is ETX [RFC6551], which represents the number of
   transmissions a node expects to make to a destination in order to
   successfully deliver one packet.  The result from using a single
   metric is that nodes prefer to select the same node as their parent,
   which according to [I-D.qasem-roll-rpl-load-balancing] leads to an
   unbalanced network with overloaded nodes (node load is indicated by a
   node's child count).  But the child count does not accurately
   indicate the load because among these child nodes, some of them may
   have higher traffic load and others may have lower.

   The network traffic can be quantified by tracking the packets a node
   generates/sends/receives and the amount of energy it consumes.
   Energy consumption is strongly correlated to the amount of network
   traffic handled by a node since the energy consumption for the
   operation of the radio is the primary energy consumer in typical
   nodes.  However, directly measuring the packet transmission rate is
   both more accurate and also works when nodes have atypical energy
   consumption profiles (e.g. increased node processing or high energy
   consumption sensors).

           4pkt/s (R)                         4pkt/s (R)
                   ^                                  ^
                   |                                  |
           +-------+-------+                  +-------+-------+
           |               |                  |               |
           +               +                  +               +
   3pkt/s (A)      1pkt/s (B)         2pkt/s (A)      2pkt/s (B)
           ^               ^                  ^               ^
           |               |                  |               |
    +------+------+        |           +------+        +------+
    |      |      |        |           |      |        |      |
    +      +      +        +           +      +        +      +
    (C1)  (C2)   (C3)     (D1)         (C1)  (C2)     (C3)   (D1)
   1pkt/s 1pkt/s 1pkt/s   1pkt/s      1pkt/s 1pkt/s   1pkt/s 1pkt/s

               Unbalanced                          Balanced

        Figure 1: Packet Transmission Rates of nodes with the same
                               requirements

   As a first simple example, an unbalanced network with nodes which all
   have the same packet transmission rates is shown in Figure 1.  Its



Ji, et al.                Expires June 4, 2018                  [Page 4]

Internet-Draft              Traffic-aware OF               December 2017


   transformation into a balanced equivalent network is shown on the
   right.

            6pkt/s (R)                        6pkt/s (R)
                    ^                                 ^
                    |                                 |
            +-------+-------+                 +-------+-------+
            |               |                 |               |
            +               +                 +               +
    2pkt/s (A)      4pkt/s (B)        3pkt/s (A)      3pkt/s (B)
            ^               ^                 ^               ^
            |               |                 |               |
     +------+        +------+          +------+------+       +
     |      |        |      |          |      |      |        |
     +      +        +      +          +      +      +        +
     (C1)  (C2)     (D1)   (D2)        (C1)  (C2)   (D1)     (D2)
    1pkt/s 1pkt/s   1pkt/s 3pkt/s     1pkt/s 1pkt/s 1pkt/s   3pkt/s

                Unbalanced                         Balanced

        Figure 2: Packet Transmission Rates of nodes with different
                               requirements

   As a second simple example, an unbalanced network with nodes which
   have different packet transmission rates is shown in Figure 2.  Its
   transformation into a balanced equivalent network is shown on the
   right.

5.  TAOF description

   In this specification, a metric is proposed to be used in the parent
   selection mechanism, the Packet Transmission Rate (PTR) which
   represents the number of packets each node transmitted (sent or
   forwarded) during a certain time period.  As mentioned below, the
   number of transmitted packets can directly show the amount of traffic
   each node is facing.  This information is added in DIO messages and
   is broadcast to every neighbor.

   At first, each node MUST identify from their neighbor set which nodes
   are acceptable to be selected as a parent.  For this purpose, the
   metric ETX is used as a filter to filter out parent candidates with
   low link quality with a preference for nodes with link quality below
   a given threshold.  The ETX threshold SHOULD be different depending
   on application requirements.  The suggested value for the relevant
   threshold MAX_PATH_COST from MRHOF [RFC6719] is 32768, which means
   the specific path has expected transmission counts greater than 256.





Ji, et al.                Expires June 4, 2018                  [Page 5]

Internet-Draft              Traffic-aware OF               December 2017


   For the packet transmission rate, each node maintains in a variable a
   counter which will increment by 1 every time a data packet is
   transmitted by the node.  When the ETX value is used as a filter,
   nodes with bad link quality will not be included in the parent set.
   This ensures that undue retransmissions caused by bad link will be
   avoided.  In any case, the node chooses the parent candidate with the
   least packet transmission rate.

   This proposal is expected to increase the frequency of parent change
   because the packet transmission rate is more likely to be different
   between DIO messages, even for DIO messages from the same node.
   There are multiple ways to minimize the frequency of unnecessary
   parent changes:

   a.  Use the packet transmission rate in combination with another
       metric (e.g. child count, hop counts).

   b.  Use a threshold when comparing the packet transmission rate,
       similar to the approach in MRHOF [RFC6719].  Switch parents when
       the difference of packet transmission rate between the original
       parent and the alternative parent is above a threshold.  This
       threshold depends on different factors (e.g. network size,
       average traffic load) and SHOULD be defined differently for each
       use case.

6.  DIO Metric Container Type extension


                     0                   1
                     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     | Packet Transmission Rate (PTR)|
                     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 3: DAG metric container type format.

   A DIO message carries fields as described in RFC6550 [RFC6550] and
   the available options for the DAG metric container are described in
   RFC6551 [RFC6551].  In this specification, a metric container option
   is proposed and the detailed format is shown in Figure 3.  The
   information carried is the PTR, represented as a 2 byte unsigned
   integer.









Ji, et al.                Expires June 4, 2018                  [Page 6]

Internet-Draft              Traffic-aware OF               December 2017


    0                   1                   2                   3
    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | RPLInstanceID |Version Number |             Rank              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |G|0| MOP | Prf |     DTSN      |     Flags     |   Reserved    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   +                                                               +
   |                                                               |
   +                            DODAGID                            +
   |                                                               |
   +                                                               +
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | DAGMC Type (PC)| DAGMC Length | Packet Transmission Rate (PTR)|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


     Figure 4: Example DIO Message with a DAG Metric Container option

   An example DIO Message containing the proposed DAG Metric Container
   type is shown in Figure 4.  The explicit definition of the fields is:

   DAGMC type:  The type of the proposed DAGMC extension.  To be
         assigned by IANA.

   DAGMC Length:  The total length of the proposed DAGMC extension in
         bytes.  MUST be 2.

   Packet Transmission Rate (PTR):  The DAG Metric Container data,
         containing the packet transmission rate, represented as a 2
         byte unsigned integer.

7.  Security Considerations

   The structure of the DIO control message is extended, within the
   predefined DIO options.  Therefore, the security mechanisms defined
   in RPL [RFC6550] apply to this proposed extension.

8.  IANA Considerations

   This proposal requests the allocation of a new value for the metric
   type "PTR" in the Routing Metric/Constraint Type in the DAG MC from
   IANA.






Ji, et al.                Expires June 4, 2018                  [Page 7]

Internet-Draft              Traffic-aware OF               December 2017


9.  Informative references

   [I-D.qasem-roll-rpl-load-balancing]
              Qasem, M., Al-Dubai, A., Romdhani, I., Ghaleb, B., Hou,
              J., and R. Jadhav, "Load Balancing Objective Function in
              RPL", draft-qasem-roll-rpl-load-balancing-02 (work in
              progress), October 2017.

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

   [RFC6550]  Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J.,
              Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur,
              JP., and R. Alexander, "RPL: IPv6 Routing Protocol for
              Low-Power and Lossy Networks", RFC 6550,
              DOI 10.17487/RFC6550, March 2012,
              <https://www.rfc-editor.org/info/rfc6550>.

   [RFC6551]  Vasseur, JP., Ed., Kim, M., Ed., Pister, K., Dejean, N.,
              and D. Barthel, "Routing Metrics Used for Path Calculation
              in Low-Power and Lossy Networks", RFC 6551,
              DOI 10.17487/RFC6551, March 2012,
              <https://www.rfc-editor.org/info/rfc6551>.

   [RFC6552]  Thubert, P., Ed., "Objective Function Zero for the Routing
              Protocol for Low-Power and Lossy Networks (RPL)",
              RFC 6552, DOI 10.17487/RFC6552, March 2012,
              <https://www.rfc-editor.org/info/rfc6552>.

   [RFC6719]  Gnawali, O. and P. Levis, "The Minimum Rank with
              Hysteresis Objective Function", RFC 6719,
              DOI 10.17487/RFC6719, September 2012,
              <https://www.rfc-editor.org/info/rfc6719>.

Authors' Addresses

   Chenyang Ji (editor)
   IMT Atlantique
   Office D00 - 116A
   2 Rue de la Chataigneraie
   Cesson-Sevigne - Rennes  35510
   FRANCE

   Email: chenyang.ji@imt-atlantique.net





Ji, et al.                Expires June 4, 2018                  [Page 8]

Internet-Draft              Traffic-aware OF               December 2017


   Remous-Aris Koutsiamanis
   IMT Atlantique
   Office B00 - 126A
   2 Rue de la Chataigneraie
   Cesson-Sevigne - Rennes  35510
   FRANCE

   Phone: +33 299 12 70 49
   Email: aris@ariskou.com


   Georgios Papadopoulos
   IMT Atlantique
   Office B00 - 114A
   2 Rue de la Chataigneraie
   Cesson-Sevigne - Rennes  35510
   FRANCE

   Phone: +33 299 12 70 04
   Email: georgios.papadopoulos@imt-atlantique.fr


   Diego Dujovne
   Universidad Diego Portales
   Escuela de Informatica y Telecomunicaciones, Av. Ejercito 441
   Santiago, Region Metropolitana
   Chile

   Phone: +56 (2) 676-8121
   Email: diego.dujovne@mail.udp.cl


   Nicolas Montavont
   IMT Atlantique
   Office B00 - 106A
   2 Rue de la Chataigneraie
   Cesson-Sevigne - Rennes  35510
   FRANCE

   Phone: +33 299 12 70 23
   Email: nicolas.montavont@imt-atlantique.fr










Ji, et al.                Expires June 4, 2018                  [Page 9]