A Distance Vector Protocol for Routing Over Low Power and Lossy Networks
draft-goyal-roll-dv-00

Status of this Memo

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

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts.

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

The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html.

This Internet-Draft will expire on December 28, 2009.

Copyright Notice

Copyright (c) 2009 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 in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

Abstract

This draft describes a distance vector protocol for routing over low power and lossy networks. In this protocol, each node periodically advertises its minimum hop distance and "current" end-to-end reliability of reaching a destination in the network via local broadcast of Hello messages. One Hello message may contain several such advertisements. The inter-Hello time period is determined using an adaptive scheme designed to speed up routing convergence to both good and bad news while avoiding unnecessary transmissions. A node maintains hop distance and end-to-end reliability information for a subset of its neighbors and for a subset of destinations in the network. For each such destination, the node also maintains the set of neighbors that it would use to forward packets going to that destination. These neighbors are selected such that they are closest to the destination in terms of hops among neighbors that satisfy a certain minimum reliability criterion.

Table of Contents

1.  Introduction
2.  Selection of Next Hop Neighbors for a Destination
    2.1.  Metrics Used
    2.2.  Selecting NextHops(D)
3.  Sending Hello Messages
4.  IANA Considerations
5.  Security Considerations
6.  Informative References
§  Author's Address

1.  Introduction

This draft describes a distance vector protocol for routing over low power and lossy networks (LLN). In this protocol, each node periodically advertises its minimum hop distance and "current" end-to-end reliability of reaching a destination in the network via local broadcast of Hello messages. One Hello message may contain several such advertisements. The inter-Hello time period is determined using an adaptive scheme designed to speed up routing convergence to both good and bad news while avoiding unnecessary transmissions. A node maintains hop distance and end-to-end reliability information for a subset of its neighbors and for a subset of destinations in the network. For each such destination, the node also maintains the set of neighbors that it would use to forward packets going to that destination. These neighbors are selected such that they are closest to the destination in terms of hops and satisfy a certain minimum reliability criterion.

The protocol is designed to automatically determine highly reliable routes to a destination node in face of dynamic network conditions, such as changes in network topology, traffic loads and link-level reliabilities. The protocol satisfies the routing state, loss response and control cost criteria listed in I-D.ietf-roll-protocols-survey (Tavakoli, A., Dawson-Haggerty, S., and P. Levis, “Overview of Existing Routing Protocols for Low Power and Lossy Networks,” April 2009.) [I‑D.ietf‑roll‑protocols‑survey]. In the following description, we have used link-level reliability, defined as the link-level packet success rate, as the link-level cost metric and consequently determine the path-level cost metric, which is the end-to-end reliability of the path, as a multiplicative function of link-level metric values. However, the protocol can be modified to use any other link-level cost metric as well and an additive function may be used to determine the path-level cost metric if considered more appropriate. The protocol, as described next, does not consider any node-level cost metric in making routing decisions. As described later, a node controls its level of participation in packet routing by manipulating the reliability values it advertises in its Hello messages. However, the protocol can be modified to explicitly take in account the node-level costs also while making the routing decisions.

The following discussion assumes that a node knows about its current link-level reliability to reach the neighbors that it selects as next hops on routes to destinations it serves. Such reliability values can be maintained easily if the underlying layers support MAC-level acknowledgements. Otherwise, a node may need to communicate with the neighbor node to determine the fraction of its transmitted packets successfully received by the neighbor in a given time interval and thus determine the link-level reliability of reaching the neighbor. The following discussion does not specify a mechanism for such communication. As mentioned before, the routing protocol described in this draft does not depend on the use of link-level reliability as the link-level cost metric and can be modified to use any other link-level cost metric as well.

The following sections describe various aspects of the protocol's operation.

2.  Selection of Next Hop Neighbors for a Destination

Consider a node X that is willing to route packets going to the destination node D. For this purpose, node X maintains a subset, NextHops(D), of its neighbors among the ones that are similarly willing to route packets headed towards destination D. On receiving such a packet, the node forwards it to a randomly selected neighbor belonging to subset NextHops(D). This section describes the procedure used by a node to select the subset, NextHops(D), of its neighbors among the ones willing to route packets to destination D.

2.1.  Metrics Used

A node selects the subset, NextHops(D), of its neighbors based on the values of the following metrics advertised by the neighbors in their Hello messages:

• Minimum hop distance from node D: The minimum hop distance of node A from node D is the smallest number of hops a packet would need to travel to reach node D starting from node A such that the link-level reliability of each hop is non-zero. In other words, the minimum hop distance of node A from node D is the hop-count of the minimum hop route from node A to node D as long as the end-to-end reliability along this route is non-zero.
• Current end-to-end reliability to reach node D: The current end-to-end reliability of node A to reach node D is calculated as follows.
  • If node A is node D itself, the reliability value is 1.
  • If node D is a direct neighbor of node A then the end-to-end reliability is same as node A's link-level reliability, linkR(D), of reaching node D.
  • Otherwise, suppose node B is node A's neighbor that belongs to subset NextHops(D) maintained by node A and advertises the highest reliability (to reach node D) among all neighbors in node A's NextHops(D). Let maxRel(D) denote the value of this reliability and linkR(B) denote node A's link-level reliability of reaching node B. Then, the end-to-end reliability (to reach node D) advertised by node A is maxRel(D)*linkR(B).
  • A node is allowed to advertise a smaller value as its end-to-end reliability to reach D, rather than the one calculated using above mentioned rules, in order to control its participation in routing packets going to destination D.

Note that the minimum hop distance of a node from a destination D is a relatively static value that depends on the underlying network topology. This value does not change as long as the underlying topology does not change and the minimum hop route from the node to the destination D has non-zero reliability. On the other hand, a node's current end-to-end reliability of reaching destination D is a highly dynamic parameter whose value changes with changes in the composition of NextHops(D) subset of neighbors, the maximum reliability (to reach D) advertised by these neighbors and the node's link-level reliability of reaching these neighbors.

2.2.  Selecting NextHops(D)

Based on the information contained in the Hello messages from its neighbors, a node maintains the following data structures:

• R(A,D): Node A's end-to-end reliability to reach node D as advertised in the last Hello received from A.
• Hops(A,D): The minimum hop distance of neighbor A from node D as advertised in the last Hello received from A.
• NeighborAtHops(i,D): The list of neighbors 'i' hops away from node D.

Note that a node need not maintain this information about all destinations in the network or all neighbors willing to route packets going to a particular destination. The destinations to be supported by a node may be decided as a matter of policy. Otherwise, within the constraints imposed by available memory, a node should support routing to destinations that are direct neighbors or, based on neighbor Hellos, known to be close by or reachable with high reliability. Similarly, for a supported destination, the node should maintain above information for neighbors that advertise a small hop distance from the destination or high reliability of reaching it.

The process of determining NextHops(D) consists of the following steps:

• The current NextHops(D) is invalidated. NextHops(D) is always rebuilt from scratch.
• If no neighbor has advertised reachability to D, a preconfigured number of randomly selected neighbors are included in NextHops(D) and the procedure terminates.
• The node determines the maximum among all R(A,D)*linkR(A) values where A is a neighbor node. Let this maximum value be maxRel(D).
• The node examines the lists of neighbors, NeighborAtHops(*,D), in increasing order of the hop distance from D. Starting with the list of neighbors closest to D, the node checks the R(A,D) value of each neighbor A in the list and adds the neighbor A to NextHops(D) if R(A,D)*linkR(A) value is greater than a certain fraction of maxRel(D). In other words, a node A in the list being examined is added to NextHops(D) if R(A,D)*linkR(A) >= x*maxRel(D), where x is a pre-configured value less than 1. If the node did not add any neighbor from a list in NextHops(D), it examines the next list. Otherwise, the process of determining NextHops(D) concludes.

Thus, NextHops(D) consists of neighbors that are closest to D in terms of hops among the ones that satisfy a certain minimum reliability criterion. The reliability criterion listed above can be replaced with a different criterion if desired. Note that the emphasis on selecting neighbors closest to D in terms of hops provides significant protection against routing loops.

3.  Sending Hello Messages

A node periodically sends a Hello message via local broadcast to inform its neighbors regarding its reachability to various destinations in the network. The reachability information for a particular destination consists of the node's minimum hop distance and current end-to-end reliability to reach that destination. The node may advertise the reachability to only a few destinations in a single Hello message. Additionally, a Hello message may also contain

• the remaining time interval before the node goes to sleep
• a request to one or more explicitly identified neighbors to send a Hello message advertising its reachability to an explicitly identified destination.

Before sending a Hello message advertising reachability to node D, the node recalculates NextHops(D) as described above (Selecting NextHops(D)). This is followed by the calculation of the node's end-to-end reliability to reach D (Section 2.1 (Metrics Used)) and its minimum hop distance from D, which is simply one plus the minimum hop distance advertised by a neighbor that also reports a non-zero reliability of reaching D.

When a node receives a Hello from neighbor A carrying reachability information regarding destination D, it replaces the old values of R(A,D) and Hops(A,D) with new values contained in the Hello message, updates the affected NeighborAtHops(,D) lists accordingly and recomputes NextHops(D). If the Hello message from neighbor A specifies a time interval before the neighbor goes to sleep, the node must ensure that R(A,*) values are set to zero and all affected NextHops() recalculated when this time interval expires.

Generation of Hello messages by a node is governed by the following set of rules. The destinations to be advertised in a Hello can be chosen by the node as per the local policy unless one of the rules listed below specifically requires a particular destination to be advertised.

• When a node wakes up, it schedules a pre-configured number of Hello messages to be sent. The interval between two Hello messages is selected in a random fashion from a certain range of values around a pre-configured value - helloIntervalSmall.
• When a node receives a Hello from a neighbor A advertising
  • a minimum hop distance from D that is more than one plus the node's own minimum hop distance from D, OR
  • a minimum hop distance from D that is one plus the node's own minimum hop distance from D AND an end-to-end reliability of reaching D that is less than the product of node's link-level reliability to reach A and the node's end-to-end reliability to reach D (calculated as per Section 2.1 (Metrics Used))
  it immediately schedules a Hello to be sent within the helloIntervalSmall duration. This Hello must advertise information regarding the node's reachability to destination D.
• When a node notices
  • any change in its minimum hop distance from D OR
  • a significant change in its end-to-end reliability of reaching D(calculated as per Section 2.1 (Metrics Used))
  it immediately schedules a Hello to be sent within the helloIntervalSmall duration. This Hello must advertise information regarding the node's reachability to destination D.
• When a node has forwarded a certain number of packets going to destination D without receiving a Hello from some neighbors in NextHops(D), it schedules a Hello to be sent within the helloIntervalSmall duration to request these neighbors to send their current reachability information regarding destination D. If the node does not receive a Hello from such a neighbor within helloIntervalSmall duration, it reduces the R(,D) value of that neighbor by a multiplicative factor and recomputes NextHops(D).
• When a node receives a Hello message requesting the node to send its reachability to destination D, the node immediately schedules a Hello to be sent within helloIntervalSmall duration and includes the information regarding its reachability to D in that Hello.
• Otherwise, a node sends a Hello message helloIntervalLarge, which is much larger than helloIntervalSmall, duration after sending the previous Hello. If this Hello can not advertise all reachable destinations, subsequent Hellos should be generated at randomly selected intervals less than helloIntervalSmall until reachability to all destinations has been advertised.

Note that the Hello generation follows an adaptive scheme that allows a Hello to be quickly generated (within helloIntervalSmall) when it is obvious that neighbors do not have correct reachability information for some destinations. Otherwise, the Hellos are originated relatively infrequently. It is possible that a neighbor currently being used to forward packets is no longer reliable enough but the failure to receive its Hello messages, e.g. due to connectivity problems, are preventing an update of its reliability. To allow timely reduction in the reachability reliability of such neighbors in such situations, a node is allowed to explicitly request reachability updates from their neighbors. Failure to receive such updates within helloIntervalSmall duration causes a node to reduce the reachability reliability of such neighbors by a multiplicative factor that may cause such neighbors to drop out of NextHops() sets.

4.  IANA Considerations

This memo includes no request to IANA.

5.  Security Considerations

TBD

6. Informative References

Author's Address