RPL Routing Pathology In a Network With a Mix of Nodes Operating in Storing and Non-Storing Modes
draft-ko-roll-mix-network-pathology-02

Abstract

The RPL specification allows nodes running with storing or non-storing modes to operate in the same network. We describe how such a mix can result in network partitioning even when there are plenty of physical links available in the network. The partitioning affects both upwards (nodes to root) and downwards (root to leaf) traffic. This routing pathology stems from a recommendation made in the RPL specification forcing nodes with different modes of operation to join the RPL network as leaf nodes only. We propose a solution that modifies RPL by mandating that all the nodes parse and interpret source routing headers and storing mode nodes to sometimes act like a non-storing mode root by attaching source routing headers.

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."

Copyright Notice

Copyright (c) 2013 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 (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. Terminology
• 3. Storing and Non-storing modes
• 4. Routing Pathology
• 5. Fixing the Pathology
• 6. Considerations for Route Management
• 7. Acknowledgements
• 8. IANA Considerations
• 9. Security Considerations
• 10. References
• 10.1. Normative References
• 10.2. Informative References
• Authors' Addresses

1. Introduction

RPL [RFC6550] can operate in storing and non-storing modes. These modes introduce two different ways to perform downward routing. Downward routing is used when a node needs to send a packet to an arbitrary node (e.g., non-DODAG root node) in the network: the packet can go from a node "upward" towards the root and "downwards" to the final destination.

The RPL specification allows operating a network with a mix of storing and non-storing modes. RFC 6550 describes special rules to operate such a network: a node that operates with a different Mode of Operation (MOP) than the DODAG root will act as a leaf node in the network. The consensus was that it is unknown if the network would work properly because no one had designed such a network and was left to be explored in the future.

In this draft, we document a case in which we allow a mix of nodes operating in storing and non-storing modes to form a single network (e.g, despite having different MOPs) and show that RPL's two downwards routing modes, as it is, can cause a routing pathology. This pathology can partition the network, i.e., it can result in scenarios where nodes cannot send packets to the root and the root cannot send packets to the nodes even though these nodes have plenty of multi-hop physical connectivity in the network.

We propose one approach of modifying RPL to prevent this routing pathology. The methodology, introducing a new mode of operation (MOP), has been implemented and tested on an LLN testbed and in process of publication. It is possible there are more elegant approaches to prevent the pathology described.

2. Terminology

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

The terminologies used in this document are consistent with the terminologies described in [I-D.ietf-roll-terminology], [RFC6551], and [RFC6550].

3. Storing and Non-storing modes

Before we describe the routing pathology that arises due to the existence of a mix of nodes operating in storing and non-storing modes, we review the storing and non-storing downwards routing modes that RPL introduces.

In Storing mode, a node keeps a (not necessarily) complete list of (nodeid, nexthop) for nodes in its subtree. When a node receives a packet, it forwards the packet to the nexthop if the node finds the destination in the list. If it does not find the destination in the list, it forwards the packet to the preferred parent.

In Non-storing mode, if a packet does not have routing path in the header, it forwards the packet to the preferred parent. The root in this mode collects and maintains topology information of the network. If the packet makes it to the root, the root computes the path to the destination based on this topology information. The root puts this path in the header and sends it to the next hop. The nodes, upon receiving a packet with a path in the header, forward the packet to the next hop as indicated in the path in the header.

4. Routing Pathology

We first examine the effect of this routing pathology for routing collection traffic packets. Lets consider the following network topology.

A -> B -> N -> S -> Root (Storing)

Note that RPL indicates that, storing mode nodes and non-storing mode nodes use a different mode of operation (MOP) field. Furthermore, if the MOP supported from a DODAG root is not supported at a RPL node, the node can only participate in the RPL network as a leaf node. Say that the Root of the topology is a storing mode node. In this case, S (e.g., a storing mode node) can connect to the Root (a storing mode root) properly as a RPL router node. On the other hand, using the DIOs initiated at the Root, N (e.g., a non-storing mode node) will notice that the Root's MOP and its MOP is different; therefore, will only connect join the RPL network as a leaf node. As a result, A and B, which physically have connections to the root will not be able to join the RPL network. On a functional perspective, this means that both upwards (e.g., collection traffic) and downwards traffic to or from nodes A and B cannot reach the root or any other node in the RPL network. Thus, there is needless network partitioning. While this is an extreme case, other cases where using routes that non-storing mode nodes provide can help optimize the collection and downwards routes that RPL nodes form.

With the increasing diversity of applications we can envision a network where a part of the network consists of computationally powerful nodes with route storing capabilities and the other part of the network with low-resource nodes that use a non-storing mode and operate together in a single RPL network. Also, as the size of LLN deployments increase, using a homogeneous non-storing mode RPL network will introduce a high level of communication overhead, and a homogeneous network of strong mode nodes will require too much memory resources. Allowing storing and non-storing mode nodes to cooperate in a single network will resolve such system design issues. Furthermore, on a practical perspective, it is meaningful to use nodes that can contribute in constructing a more efficient DODAG that optimizes the data collection process rather than ignoring a node just because it supports a different MOP. Unfortunately, in such cases, the pathology that we discuss above can arise and cause downwards packets to be dropped and even more, restrict the formation of efficient collection routes.

5. Fixing the Pathology

We describe one way to fix RPL to prevent the pathology described above, while acknowledging that there might be more elegant solutions. In this approach, we acknowledge the fact that non-storing mode nodes are more likely to have strict resource limitations compared to nodes implementing the storing mode. Therefore, we make sure that the most of the required additional capabilities occur at the storing mode nodes rather than the non-storing mode nodes.

1. A new mode of operation (MOP) that allows a node to choose either to implement the storing or non-storing features, or both. The changes below are made compared to the original storing and non-storing modes.
2. Require storing and non-storing nodes to implement source routing header parsing capabilities.
3. RPL DODAG Root nodes supporting this MOP should have the capability to store routes (similar to the non-storing mode option) and also identify storing mode node children nodes.
4. Non-storing nodes send hop-by-hop DAO.
5. Storing nodes keep a table of all the DAO senders and a flag indicating if each of those sender is operating in storing or non-storing mode. This requires allocating one of the bits in the DAO message for a node to indicate if it is operating in storing or non-storing mode.
6. Change the forwarding mechanism in the storing mode node when it receives a downward bound packet:
7. 1. If packet does not have source routing header and the next hop is a storing-mode node, forward as in [RFC6550]. If the next hop is a non-storing node, insert the source routing header [RFC6554] into the packet and forward, i.e., act like a non-storing root.
   2. Using the flag indicating the storing status of nodes in its sub-DODAG, a node constructing a source routing header MAY choose to construct a source routing header only up to the next storing mode node.
   3. If the incoming packet has a source routing header, a storing mode node SHOULD obey the route specified in the source routing header to comply with the strict source routing requirements in [RFC6554].

If there is a mix of storing and non-storing nodes, we should also be more aggressive about loop detection. More aggressive loop detection will quickly remove the looping packets from the network. Even with the implementation of this suggestion, nodes beyond storing / non-storing nodes will still remain unreachable.

6. Considerations for Route Management

Given the lossy nature of the links and the variability in link quality on a temporal scale, the DAO parent(s) that were originally selected can change over time. In such cases, nodes take the following steps.

1. Upon realizing a change in the DAO parent set, a RPL node SHOULD send a DAO with an increased Path Sequence Number to its ``new" DAO parent set.
2. Next, the node experiencing the change in its DAO parents, SHOULD send a No-Path DAO message with an increased Path Sequence Number to the set of DAO parents that have been deleted.
3. When nodes receive a DAO that contains a modified Transit Information option for a specific Target option, they SHOULD propagate this information to its DAO parents while respecting the Path Control field in the Transit Information option.
4. When a node without the route storing capability fails in forwarding a packet using the information provided by a source routing header, the node initiates an ICMPv6 error message to the node that constructed the source routing header.

This process alerts nodes keeping the routing state of the DAO initiating nodes with the up-to-date DAO parent information. Nodes with route storing capabilities will process the information and nodes without this capability will pass the information up the DODAG. When using the flag indicating the storing status, the propagation of the updated DAO and ICMPv6 error message MAY stop at the first node with route storing capability since this node takes the role of managing the routing state for the target node.

7. Acknowledgements

8. IANA Considerations

9. Security Considerations

Future work.

10. References

10.1. Normative References

10.2. Informative References

Authors' Addresses