Common Ancestor Objective Function and Parent Set DAG Metric Container Extension

Abstract

Packet Replication and Elimination is a method in which several copies of a data packet are sent in the network in order to achieve high reliability and low jitter. This document details how to apply Packet Replication and Elimination in RPL, especially how to exchange information within RPL control packets to let a node better select the different parents that will be used to forward the multiple copies of a packet. This document also describes the Objective Function which takes advantage of this information to implement multi-path routing.¶

1. Introduction

Networks in the industrial context must provide stringent guarantees in terms of reliability and predictability, with this domain being one of main ones addressed by Deterministic Networking [RFC8557]. Packet Replication and Elimination (PRE) [I-D.papadopoulos-raw-pareo-reqs] is a technique which allows redundant paths in the network to be utilized for traffic requiring higher reliability. Allowing industrial applications to function over wireless networks requires the application of the principles and architecture of Deterministic Networking [RFC8655]. This results in designs which aim at optimizing packet delivery rate and bounding latency. Additionally, nodes operating on battery need to minimize their energy consumption.¶

As an example, to meet this goal, IEEE Std. 802.15.4 [IEEE802154] provides Time-Slotted Channel Hopping (TSCH), a mode of operation which uses a common communication schedule based on timeslots to allow deterministic medium access as well as channel hopping to work around radio interference. However, since TSCH uses retransmissions in the event of a failed transmission, end-to-end latency and jitter performance can deteriorate.¶

Furthermore, the 6TiSCH working group, focusing on IPv6 over IEEE Std. 802.15.4-TSCH, has worked on these issues and produced the "6TiSCH Architecture" [I-D.ietf-6tisch-architecture] to address that case. Building on this architecture, "Exploiting Packet Replication and Elimination in Complex Tracks in LLNs" [I-D.papadopoulos-raw-pareo-reqs] leverages PRE to improve the Packet Delivery Ratio (PDR), to provide a hard bound to the end-to-end latency, and thus to limit jitter.¶

PRE is a general method of maximizing packet delivery rate and potentially minimizing latency and jitter, not limited to 6TiSCH. More specifically, PRE achieves controlled redundancy by laying multiple forwarding paths through the network and using them in parallel for different copies of a same packet. PRE can follow the Destination-Oriented Directed Acyclic Graph (DODAG) formed by [RPL] from a node to the root. Building a multi-path DODAG can be achieved based on the RPL capability of having multiple parents for each node in a network, a subset of which is used to forward packets. In order to select parents to be part of this subset, the RPL Objective Function (OF) needs additional information regarding the multi-path nature of PRE. This document describes an OF which implements multi-path routing for PRE and specifies the transmission of this specific path information.¶

This document describes a new Objective Function (OF) called the Common Ancestor (CA) OF (see Section 4). A detailed description is given of how the path information is used within the CA OF and how the subset of parents for forwarding packets is selected. This specification defines a new Objective Code Point (OCP) for the CA OF.¶

For the path information, this specification focuses on the extensions to the DAG Metric Container [RFC6551] required for providing the PRE mechanism a part of the information it needs to operate. This information is the [RPL] parent address set of a node and it must be sent to potential children of the node. The RPL DIO Control Message is the canonical way of broadcasting this kind of information and therefore its DAG Metric Container [RFC6551] field is used to append a Node State and Attribute (NSA) object. The node's parent address set is stored as an optional TLV within the NSA object. This specification defines the type value and structure for the parent address set TLV (see Section 5).¶

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

The draft uses the following Terminology:¶

Packet Replication and Elimination (PRE):

A method which consists of transmitting multiple copies of a packet using multi-path forwarding over a multi-hop network and which consolidates multiple received packet copies to control flooding. See "Exploiting Packet Replication and Elimination in Complex Tracks in LLNs" [I-D.papadopoulos-raw-pareo-reqs] for more details.¶

Parent Set (PS):

Given a RPL node, the set of its neighbor nodes which participate in the same RPL DODAG and which can potentially take the role of the node's preferred parent.¶

Alternative Parent (AP):

A RPL parent in the parent set of a node which is used to forward a packet copy when replicating packets.¶

Alternative Parent (AP) Selection:

The mechanism for choosing the next hop node to forward a packet copy when replicating packets.¶

Preferred Grand Parent (PGP):

The preferred parent of the preferred parent of a node.¶

3. Common Ancestor AP Selection Policies

In the RPL protocol, each node maintains a list of potential parents. For PRE, the Preferred Parent (PP) node is defined to be the same as the RPL DODAG Preferred Parent node. Furthermore, to construct an alternative path toward the root, in addition to the PP node, each node in the network selects additional parent(s), called alternative parent(s), from its Parent Set (PS).¶

There are multiple possible policies of selecting the AP node. This section details three such possible policies.¶

All three policies defined perform AP selection based on common ancestors, named Common Ancestor Strict, Common Ancestor Medium, and Common Ancestor Relaxed, depending on how restrictive the selection process is. A more restrictive policy will limit flooding but might fail to select an appropriate AP, while a less restrictive one will more often find an appropriate AP but might increase flooding.¶

All three policies apply their corresponding common ancestor criterion to filter the list of candidate neighbours in the alternative parent set.¶

               (  R  ) root
                  .                      PS(S) = {A, B, C, D}
                  .                      PP(S) = C
                  .                      PP(PP(S)) = Y
                  .
                                         PS(A) = {W, X}
  ( W )    ( X )    ( Y )    ( Z )       PP(A) = X
    ^ ^   ^^ ^ ^    ^^^^ ^   ^ ^^
    |  \ //  |  \ //  ||  \ /  ||        PS(B) = {W, X, Y}
    |   //   |   //   ||   /   ||        PP(B) = Y
    |  // \  |  // \  ||  / \  ||
    | //   \ | //   \ || /   \ ||        PS(C) = {X, Y, Z}
  ( A )    ( B )    ( C )    ( D )       PP(C) = Y
      ^        ^      ^^     ^
       \        \     ||    /            PS(D) = {Y, Z}
         \       \    ||   /             PP(D) = Z
           \      \   ||  /
             \----\\  || /               || Preferred Parent
                  (   S   ) source       |  Potential Alternative Parent

6. Controlling PRE

PRE is very helpful when the aim is to increase reliability for a certain path, however its use creates additional traffic as part of the replication process. It is conceivable that not all paths have stringent reliability requirements. Therefore, a way to control whether PRE is applied to a path's packets SHOULD be implemented. For example, a traffic class label can be used to determine this behavior per flow type as described in Deterministic Networking Architecture [RFC8655].¶

7. Security Considerations

The structure of the DIO control message is extended, within the pre-defined DIO options. The additional information are the IPv6 addresses of the parent set of the node transmitting the DIO. This use of this additional information can have the following potential consequences:¶

• A malicious node that can receive and read the DIO can "see" further than it's own neighbourhood by one hop, learning the addresses of it's two hop neighbors. This is a privacy / network discovery issue.¶
• A malicious node that can send DIOs can use the parent set extension to convince neighbours to route through itself, instead of the normal preferred parent they would use. However, this is already possible with other OFs (like [OF0] and [MRHOF]) by reporting a fake rank value in the DIO, thus masquerading as the DODAG root.¶

8. IANA Considerations

This proposal requests the allocation of a new value TBD1 from the "Objective Code Point (OCP)" sub-registry of the "Routing Protocol for Low Power and Lossy Networks (RPL)" registry.¶

This proposal also requests the allocation of a new value TBD2 for the "Parent Set" TLV from the Routing Metric/Constraint TLVs sub-registry from IANA.¶

9. References

Appendix A. Implementation Status

A research-stage implementation of the PRE mechanism using the proposed extension as part of a 6TiSCH IOT use case was developed at IMT Atlantique, France by Tomas Lagos Jenschke and Remous-Aris Koutsiamanis. It was implemented on the open-source Contiki OS and tested with the Cooja simulator. The DIO DAGMC NSA extension is implemented with a configurable number of parents from the parent set of a node to be reported.¶

                 ( R )


(11)   (12)   (13)   (14)   (15)   (16)


(21)   (22)   (23)   (24)   (25)   (26)


(31)   (32)   (33)   (34)   (35)   (36)


(41)   (42)   (43)   (44)   (45)   (46)


(51)   (52)   (53)   (54)   (55)   (56)


                 ( S )

The simulation setup is:¶

Topology:

32 nodes structured in regular grid as show in Figure 4. Node S (source) is the only data packet sender, and send data to node R (root). The parent set of each node (except R) is all the nodes in the immediately higher row, the immediately above 6 nodes. For example, each node in {51, 52, 53, 54, 55, 56} is connected to all of {41, 42, 43, 44, 45, 46}. Node 11, 12, 13, 14, 15, 16 have a single upwards link to R.¶

MAC:

TSCH with 1 retransmission¶

Platform:

Cooja¶

Schedule:

Static, 2 timeslots per link from each node to each parent in its parent set, 1 broadcast EB slot, 1 sender-based shared timeslot (for DIO and DIS) per node (total of 32).¶

Simulation lifecycle:

Allow link formation for 100 seconds before starting to send data packets. Afterwards, S sends data packets to R. The simulation terminates when 1000 packets have been sent by S.¶

Radio Links:

Every 60 s, a new Packet Delivery Rate is randomly drawn for each link, with a uniform distribution spanning the 70% to 100% interval.¶

Traffic Pattern:

CBR, S sends one non-fragmented UDP packet every 5 seconds to R.¶

PS extension size:

3 parents.¶

Routing Methods:

• RPL: The default RPL non-PRE implementation in Contiki OS.¶
• 2nd ETX: PRE with a parent selection method which picks as AP the 2nd best parent in the parent set based on ETX.¶
• CA Strict: As described in Section 3.1.¶
• CA Medium: As described in Section 3.2.¶

Simulation results:¶

Links:¶

• Contiki OS DIO DAGMC NSA extension (draft-koutsiamanis-roll-nsa-extension branch)¶
• Wireshark dissectors (for the optional PS TLV) - currently merged / in master¶

Appendix B. Choosing an AP selection policy

The manner of choosing an AP selection policy is left to the implementation, for maximum flexibility.¶

For example, a different policy can be used per traffic type. The network configurator can choose the CA Relaxed policy to increase reliability (thus producing some flooding) for specific, extremely important, alert packets. On the other hand, all normal data traffic uses the CA Strict policy. Therefore, an exception is made just for the alert packets.¶

Another option would be to devise a new disjoint policy, where the paths are on purpose non-correlated, to increase path diversity and resilience against whole groups of nodes failing. The disadvantage may be increased jitter.¶

Finally, a network configurator may provide the CA policies with a preference order of Strict > Medium > Relaxed as a means of falling back to more flood-prone policies to maintain reliability.¶