Networking Working Group J. Ko
Internet-Draft J. Jeong
Intended status: Standards Track J. Park
Expires: February 18, 2013 J. Jun
N. Kim
Electronics and
Telecommunications Research
Institute
O. Gnawali
University of Houston
August 17, 2012
RPL Routing Pathology In a Network With a Mix of Nodes Operating in
Storing and Non-Storing Modes
draft-ko-roll-mix-network-pathology-00
Abstract
Nodes can run RPL in storing or non-storing modes for downward
routing. When a downward-bound packet traverses a node running in
storing to a node running in non-storing mode, there is a routing
pathology that makes the packet bounce between the two nodes. Due to
this pathology, the packet never reaches the destination if it lies
beyond these nodes in the multi-hop path. The solution is to mandate
that all the nodes parse and interpret source routing headers and
storing nodes to sometimes act like non-storing mode root.
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 February 18, 2013.
Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the
Ko, et al. Expires February 18, 2013 [Page 1]
Internet-Draft draft-ko-roll-mix-network-pathology August 2012
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 . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Storing and Non-storing modes . . . . . . . . . . . . . . . . . 3
4. Routing Pathology . . . . . . . . . . . . . . . . . . . . . . . 4
5. Fixing the Pathology . . . . . . . . . . . . . . . . . . . . . 5
6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 6
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 6
8. Security Considerations . . . . . . . . . . . . . . . . . . . . 6
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 6
9.1. Normative References . . . . . . . . . . . . . . . . . . . 6
9.2. Informative References . . . . . . . . . . . . . . . . . . 6
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 6
Ko, et al. Expires February 18, 2013 [Page 2]
Internet-Draft draft-ko-roll-mix-network-pathology August 2012
1. Introduction
RPL [RFC6550] can use storing and non-storing mode operation to
compute paths for downward routing. Downward routing is used when a
node needs to send a packet to an arbitrary node in the network: the
packet might go from a node upward towards the root and downwards to
the destination.
The only discussion about what would happen if a single network had a
mix of nodes running in storing and non-storing modes that the
specification of RPL introduces is that node that operate with a
different Mode of Operation (MOP) than the DODAG root will act as a
leaf node in the network. The consensus it is unknown if the network
would work properly because no one had required or built such a
network and left to be explored in the future. In this draft, we
document a case in which we allow a mix of nodes running in storing
and non-storing modes to form a single network (e.g, despite having
different MOPs) and introduce that RPL's two downwards routing modes,
as it is, can cause a routing pathology that results in packets
bouncing between the two nodes on the path and never reaching the
destination.
We also propose one approach to modifying RPL to prevent this routing
pathology. The methodology, introducing a new mode of operation, 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 arise due to the
existence of a mix of nodes running in storing and non-storing nodes,
we review storing and non-storing modes of RPL.
In Storing mode, a node keeps a (not necessarily) complete list of
Ko, et al. Expires February 18, 2013 [Page 3]
Internet-Draft draft-ko-roll-mix-network-pathology August 2012
(nodid, 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
Lets imagine a network of five nodes as shown below:
A -> B -> N -> S -> Root
In this network, N is operating in non-storing and S is operating in
storing mode. N wants to send a packet to A. N sends this packet to
S because S is the preferred parent. S is operating in storing mode
so it looks up node A in its forwarding table and finds that the next
hop to reach A is using node N. With the assumption that node N will
also know how to reach node A it will forward the packet back to node
N. N is operating in non-storing mode so without a source routing
header, it will forward the packet back to S. Thus the packet bounces
between N and S.
RPL indicates that, since storing mode nodes and non-storing mode
nodes use a different mode of operation (MOP) field, 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. Notice that
when following RPL as it is, there is no routing pathology since
nodes with different MOPs will not be forwarding downwards packets
interchangeably. In such cases a path of storing mode nodes can
forward packets to a non-storing leaf node and vice versa. However,
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.
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
Ko, et al. Expires February 18, 2013 [Page 4]
Internet-Draft draft-ko-roll-mix-network-pathology August 2012
downwards packets to be dropped before reaching the destination.
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.
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 capability.
3. Non-storing nodes send hop-by-hop DAO.
4. 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.
5. Change the forwarding mechanism in the storing mode node when it
receives a downward bound packet:
6.
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
Ko, et al. Expires February 18, 2013 [Page 5]
Internet-Draft draft-ko-roll-mix-network-pathology August 2012
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. Acknowledgements
7. IANA Considerations
8. Security Considerations
Future work.
9. References
9.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC6550] Winter, T., Thubert, P., 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, March 2012.
[RFC6551] Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D.
Barthel, "Routing Metrics Used for Path Calculation in
Low-Power and Lossy Networks", RFC 6551, March 2012.
[RFC6554] Hui, J., Vasseur, JP., Culler, D., and V. Manral, "An IPv6
Routing Header for Source Routes with the Routing Protocol
for Low-Power and Lossy Networks (RPL)", RFC 6554,
March 2012.
9.2. Informative References
[I-D.ietf-roll-terminology]
Vasseur, J., "Terminology in Low power And Lossy
Networks", draft-ietf-roll-terminology-05 (work in
progress), March 2011.
Ko, et al. Expires February 18, 2013 [Page 6]
Internet-Draft draft-ko-roll-mix-network-pathology August 2012
Authors' Addresses
JeongGil Ko
Electronics and Telecommunications Research Institute
218 Gajeong-Ro
Yuseong-Gu, Daejeon 305-700
Korea
Phone: +82-42-860-5824
Email: jeonggil.ko@etri.re.kr
Jongsoo Jeong
Electronics and Telecommunications Research Institute
218 Gajeong-Ro
Yuseong-Gu, Daejeon 305-700
Korea
Phone: +82-42-860-1806
Email: jsjeong@etri.re.kr
Jongjun Park
Electronics and Telecommunications Research Institute
218 Gajeong-Ro
Yuseong-Gu, Daejeon 305-700
Korea
Phone: +82-42-860-5413
Email: juny@etri.re.kr
Jong Arm Jun
Electronics and Telecommunications Research Institute
218 Gajeong-Ro
Yuseong-Gu, Daejeon 305-700
Korea
Phone: +82-42-860-4835
Email: jajun@etri.re.kr
Ko, et al. Expires February 18, 2013 [Page 7]
Internet-Draft draft-ko-roll-mix-network-pathology August 2012
Naesoo Kim
Electronics and Telecommunications Research Institute
218 Gajeong-Ro
Yuseong-Gu, Daejeon 305-700
Korea
Phone: +82-42-860-5214
Email: nskim@etri.re.kr
Omprakash Gnawali
University of Houston
PGH 577, University of Houston
Houston, TX 77204
USA
Phone: +1-713-743-3356
Email: gnawali@cs.uh.edu
Ko, et al. Expires February 18, 2013 [Page 8]