Extending the Bundle Protocol with Relative Time and Hops to Live
draft-ellard-dtnrg-reltime-htl-00

Abstract

This draft presents two extensions to the DTN bundle protocol. The first extension is the use of relative time rather than absolute time to address situations where the DTN nodes cannot achieve loosely synchronized clocks, as required by the current DTN bundle protocol. The second extension is the addition of a "hops-to-live" field to the bundle header, which specifies how many node-to-node hops each instance of a bundle is permitted to make before it expires.

These two extensions are separable; either may be used independently of the other. Used together, however, they provide a powerful way to constrain resources consumed by the handling of a DTN bundle despite the absence of synchronized clocks or the presence of incomplete knowledge of the network topology (which may lead to the presence of hazards such as routing loops).

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 August 29, 2010.

Copyright Notice

Copyright (c) 2010 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 BSD License.

Table of Contents

1.  Introduction
    1.1.  Problems Establishing a Real-time Clock
    1.2.  Requirements Notation
    1.3.  Scope of This Document
2.  Changes to the DTN Bundle Header
    2.1.  The Version
    2.2.  Bundle Processing Flags
    2.3.  Creation Timestamp Time
    2.4.  Bundle Lifetime
    2.5.  Remaining Lifetime
    2.6.  Hops to Live
    2.7.  Primary Block Diagram
3.  Discussion
    3.1.  The Granularity of the Remaining Lifetime
    3.2.  Compatibility with the Bundle Security Protocol
    3.3.  Startup Issues
    3.4.  Compatibility with DTNv6
        3.4.1.  Changing from AT to RT mode
        3.4.2.  Translation between RT mode and AT mode
        3.4.3.  Discussion
    3.5.  Bundle Status Reports
4.  Security Considerations
    4.1.  Incompatibility with the Bundle Security Protocol
    4.2.  Bundle Lifetime Limits and Incorrect Creation Times
5.  IANA Considerations
6.  Acknowledgments
7.  Informative References
§  Author's Address

1.  Introduction

1.1.  Problems Establishing a Real-time Clock

Delay/Disruption-Tolerant Networking (DTN) is an architecture and a set of protocols that enable communication in environments with intermittent connectivity and long delays. An architecture for disruption tolerant networks [RFC4838] (Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R., Scott, K., Fall, K., and H. Weiss, “Delay-Tolerant Networking Architecture,” April 2007.) has been defined. This architecture describes disruption tolerant networks in terms of DTN nodes that create, relay, and deliver units of information termed bundles. Each bundle is defined to have a finite lifetime, after which it is deemed to be expired. A full definition of the protocol for creating, interpreting, and handling bundles by DTN nodes has also been defined [RFC5050] (Scott, K. and S. Burleigh, “Bundle Protocol Specification,” November 2007.).

One issue that has been raised about the bundle protocol is that it assumes that every node in the network has access to a realtime clock, and all of these realtime clocks are synchronized to a reasonable degree (typically within a small number of seconds). This assumption, when it holds, provides the convenience that the timing of both future events (i.e., when a bundle should expire because it is no longer needed, or no longer relevant) and past events (i.e., when a bundle was created or delivered) may be represented using this common, absolute frame of reference.

Unfortunately, our experiences in deploying disruption tolerant networks have shown that the problem of establishing a common realtime clock is currently intractable in some real-world scenarios. The reason is usually a combination of several factors:

• DTN nodes may have reliable, inaccurate clocks. These clocks might not have been initialized to the correct time or may have lost power since their initialization, or may drift significantly over time.
• The links between the DTN nodes may often be disrupted. The nodes might not be able to communicate with an accurate time source to find the current time, or to run a time synchronization protocol such as NTP [RFC2030] (Mills, D., “Simple Network Time Protocol (SNTP) Version 4 for IPv4, IPv6 and OSI,” October 1996.) to negotiate a shared time reference.
• Bundle lifetimes may be short. If bundle lifetimes are comparable with the amount of clock drift that can accumulate between good clock settings, bundles may appear to have expired before they are sent.

There have been other discussions of extensions to the bundle protocol to address the problem of unsynchronized clocks in the context of DTN [I‑D.farrell‑dtnrg‑alt‑time] (Farrell, S., McMahon, A., and J. Ott, “Handling Issues with Real Time in the Bundle Protocol,” November 2009.).

1.2.  Requirements Notation

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] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).

1.3.  Scope of This Document

This document describes extensions to version six of the DTN bundle protocol (DTNv6) [RFC5050] (Scott, K. and S. Burleigh, “Bundle Protocol Specification,” November 2007.). With respect to DTNv6, this document does not:

• describe details of the DTNv6 protocol, except where needed to compare or contrast with the proposed extensions.
• modify the specification of the DTNv6 protocol.

2.  Changes to the DTN Bundle Header

The changes described in this document are relative to version 6 ("DTNv6") of the DTN bundle protocol [RFC5050] (Scott, K. and S. Burleigh, “Bundle Protocol Specification,” November 2007.). Fields of the bundle header that are not mentioned in this section should be assumed to have the identical format and meaning as described in RFC5050.

2.1.  The Version

We propose that version number 7 be assigned to represent bundles that include any of the new fields described in this proposal.

In order to differentiate bundles represented in the proposed format, it is customary to choose a different version number than that employed any past or current version of the bundle protocol. Although this is optional in our proposal (because version 6 bundles may be interpreted as a subset of version 7 bundles, with the difference being determined entirely via the Bundle Processing Flags, as described in Section 2.2 (Bundle Processing Flags)), this approach is extremely likely to lead to problems with backwards compatibility. Current implementations of DTN do not check for the new Bundle Processing Flag values, and therefore would misinterpret bundles that used any of the new functionality proposed here.

2.2.  Bundle Processing Flags

Bits 0-19

There are no changes to the lower 20 bits of the bundle processing flags.

Bit 20 (the RT bit)

If bit 20 is 1, then use relative time (RT) instead of absolute time (AT). If 0, then use absolute time, in a manner compatible with DTNv6, and the Remaining Lifetime (RL) field (described in Section 2.5 (Remaining Lifetime) MUST be omitted.

Bit 21 (the HTL bit)

If bit 21 is 1, then use the Hops to Live (HTL) field to determine whether a bundle should be discarded because it has traversed too many hops. If 0, then the Hops to Live field is ignored, and the Hops to Live field (described in Section 2.6 (Hops to Live)) MUST be omitted.

2.3.  Creation Timestamp Time

If the RT bit in the bundle processing flags is 0, then this field is initialized, interpreted, and used exactly as in DTNv6.

When the RT bit in the bundle processing flags is 1, then this field is not used to determine when a bundle expires.

Note that the Creation Timestamp SHOULD be initialized with the current local time because the Creation Timestamp is often used for additional purposes, such as creating unique bundle identifiers. If the node does not have a reliable source of local time (at minimum, a monotonically increasing counter) then this implies that the Creation Timestamp Sequence Number must be created in such a way that it alone suffices to ensure uniqueness across all bundles created on the local node. This property is not guaranteed by the method for choosing the Creation Timestamp sequence number described in DTNv6, which relies upon the existence of a good, monotonically-increasing local clock, but may be guaranteed via other methods.

2.4.  Bundle Lifetime

This field represents the number of seconds that a bundle may exist between its creation and expiration. This meaning is the same as in DTNv6, and is the same for both AT and RT modes. The only difference between AT and RT modes is how the calculation of the age of a bundle is performed.

In AT mode, the local clock is assumed to be synchronized (or nearly synchronized) with the clock of the node that created the bundle, and therefore the calculation is performed by comparing the difference between the of the local clock and the Creation Timestamp of the bundle. If this difference is greater than the Lifetime, then the bundle has expired.

In RT mode, the Creation Timestamp field is not used to perform this calculation, but is only used as a reference for the sake of backwards compatibility with AT mode. The Remaining Lifetime field (described in Section 2.5 (Remaining Lifetime) is used to determine whether or not a bundle has expired. When the Remaining Lifetime reaches zero, the bundle has expired.

2.5.  Remaining Lifetime

This is a new field that does not exist in DTNv6.

The "Remaining Lifetime" (RL) field is an SDNV field that specifies how many seconds the bundle can remain in the system before it expires.

The RL is expressed in seconds, as an SDNV. It is decremented as the bundle is processed, and the bundle expires when it reaches zero.

If the bundle is created in RT mode, then the initial value of the Remaining Lifetime field MUST be identical to the value of the Lifetime field. At each hop, the Remaining Lifetime is decremented by the length of time that has elapsed since the previous hop, rounded down to the nearest second.

There are several points in the handling of a bundle where the Remaining Lifetime may be decremented by the BPA. These include:

• When the bundle is received by a convergence layer adapter (CLA). The CLA may have knowledge about the time required for the bundle to traverse the link, given the size of the bundle, the effective bandwidth of the channel, and the latency or propagation delay of the channel (which may be the most significant factor in the case of links between DTN nodes separated by light-seconds or light-minutes of distance).
• When the bundle is retrieved from local storage.
• When the bundle is idle in the BPA for a significant period of time, for any reason, such as waiting for a router to compute a route and choose a CLA.

For some applications, such as using DTN to move small bundles within a MANET, the effective processing and transmission delay may generally be small enough so that the only time that the Remaining Lifetime field needs to be decremented is when a bundle is retrieved from local storage. For other applications, such moving large bundles between deep space nodes, the channel latency and transmission delays must also be considered.

2.6.  Hops to Live

This is a new field that does not exist in DTNv6.

The Hops to Live (HTL) field is an SDNV field that specifies the number of "hops" (transitions from one DTN node to another) that the bundle is permitted to make before the bundle expires.

If the HTL bit is not set in the Bundle Processing Flag, then this field is omitted.

2.7.  Primary Block Diagram

+----------------+----------------+----------------+----------------+
|    Version     |           Bundle Processing Flags (*)            |
+----------------+----------------+----------------+----------------+
|                          Block length (*)                         |
+----------------+----------------+---------------------------------+
|   Destination scheme offset (*) |     Destination SSP offset (*)  |
+----------------+----------------+----------------+----------------+
|      Source scheme offset (*)   |        Source SSP offset (*)    |
+----------------+----------------+----------------+----------------+
|    Report-to scheme offset (*)  |      Report-to SSP offset (*)   |
+----------------+----------------+----------------+----------------+
|    Custodian scheme offset (*)  |      Custodian SSP offset (*)   |
+----------------+----------------+----------------+----------------+
|                    Creation Timestamp time (*)                    |
+---------------------------------+---------------------------------+
|             Creation Timestamp sequence number (*)                |
+---------------------------------+---------------------------------+
|                           Lifetime (*)                            |
+----------------+----------------+----------------+----------------+
|                   [(NEW) Remaining Lifetime (*)]                  |
+----------------+----------------+----------------+----------------+
|                      [(NEW) Hops to Live (*)]                     |
+----------------+----------------+----------------+----------------+
|                        Dictionary Length (*)                      |
+----------------+----------------+----------------+----------------+
|                  Dictionary byte array (variable)                 |
+----------------+----------------+---------------------------------+
|                      [Fragment offset (*)]                        |
+----------------+----------------+---------------------------------+
|              [Total application data unit length (*)]             |
+----------------+----------------+---------------------------------+

Note that in Figure 1 all of the fields in the primary block, with the exception of the 8-bit Version field, are variable length (either SNDV, or in the case of the Dictionary, a string of bytes whose length is defined by the SDNV Dictionary Length. The alignments shown here are simply for the sake of notational convenience. See RFC 5050 [RFC5050] (Scott, K. and S. Burleigh, “Bundle Protocol Specification,” November 2007.) for more detail.

3.  Discussion

3.1.  The Granularity of the Remaining Lifetime

If a bundle is forwarded "quickly" through a node, and the transfer time is small, then its RL might not be decremented (since the elapsed time is always rounded down to the nearest second, and many bundles will require less than one second to receive and forward). Therefore a bundle may survive for many seconds longer than its RL, as long as it continues to make steady progress hops. The only time that the RL will be decremented is if the bundle is "stalled" in a node and remains there for longer than one second.

Is this what we want, or should the RL be measured in a finer unit (milliseconds? microseconds? nanoseconds?), so that it is decremented even when a bundle is forwarded without only a very small amount of delay, and bundles can still expire even if they are never stalled?

3.2.  Compatibility with the Bundle Security Protocol

We can reuse the bundle header canonical format used by the Bundle Security Protocol (BSP) [I‑D.irtf‑dtnrg‑bundle‑security] (Symington, S., Farrell, S., Weiss, H., and P. Lovell, “Bundle Security Protocol Specification,” February 2010.) of DTNv6 for this proposed format.

The only question is whether there is any need to protect the Hops to Live or Remaining Lifetime fields in a way more powerful than provided by the current hop-by-hop security.

3.3.  Startup Issues

If the BPA is shut down (or crashes, etc) or for some other reason loses track of the passage of time, it may not be able to update the RL properly for bundles that it has in its storage system. This problem is particularly difficult if there is no reliable way to determine whether the clock has changed when the BPA was down.

There are several possible approaches:

1. If the device has access to an accurate clock, or can reliably measure the passage of time even when it is shut down, the receipt time of all bundles could be recorded and used normally, as if the shutdown had not occurred.
2. Assume that no time has passed since the shut down and that the local clock has not been altered. The remaining RL of bundles stored locally is not impacted by the reboot.
3. Assume that a period of time equal to the expected time required to shut down and restart the node has elapsed. This assumes that the node was not actually halted, but simply reset.
4. Assume that an unknown and potentially large period of time has elapsed since the system was shut down. This period of time may be chosen arbitrarily (i.e., it may reduce to the previous case).
5. Assume that a period of time greater than the longest remaining lifetime of any bundle in storage has elapsed since the system was shut down, and therefore all stored bundles with an RL have expired.

3.4.  Compatibility with DTNv6

In this section, we outline how bundles may be translated between the proposed protocol and DTNv6.

We note that the reviewers of this draft feel that the utility of backward compatibility with DTNv6 is questionable and agree that it adds complexity in implementation. In Section 3.4.3 (Discussion) we discuss some of the obstacles to complete compatibility.

There is a mechanical way to rewrite bundle headers traversing from nodes that implement DTNv6 to nodes that implement the proposed protocol and vice versa, assuming that all the intermediate nodes between the trans-protocol frontiers share a common clock (which is a valid assumption in some cases). Two DTN nodes that share a common clock may correctly communicate via either DTNv6 or the proposed protocol, using either RT or AT mode, but two nodes that do not share a common clock must use the proposed protocol in RT mode (or some equivalent mechanism) in order to ensure correct communication.

3.4.1.  Changing from AT to RT mode

This section specifies an algorithm for transforming an AT mode bundle header to an RT mode bundle header.

1. Calculate the value of the Remaining Lifetime field by computing the difference between the expiration time of the bundle (the sum of the Creation Timestamp and the Lifetime fields) and the current lifetime.
2. Create a new bundle header, with the same contents as the current header, but set the RT mode bit in the Bundle Processing Flags field, and insert the Remaining Lifetime field.

3.4.2.  Translation between RT mode and AT mode

This section specifies an algorithm for transforming an RT mode bundle header to an AT mode bundle header.

If the DTN nodes have synchronized clocks, then all that is necessary is to remove the Remaining Lifetime field and clear the RT bit from the Bundle Processing Flags field. This algorithm handles the case when the clocks on the two nodes are not synchronized.

1. Compute the current age of the bundle by subtracting the Lifetime field from the Remaining Lifetime field.
2. Compute the effective creation timestamp of the bundle by subtracting the current age of the bundle from the current clock value.
3. Create a new AT-mode bundle header, using the effective creation timestamp as the value of the Creation Timestamp.

3.4.3.  Discussion

The process of conversion between RT and AT mode may break central assumptions about how bundles may be uniquely identified. For example, some DTN implementations use the Creation Timestamp as part of their check to see whether a given bundle has already been seen. If there are two versions of the bundle (one in RT mode, and the other in AT mode) then this test will not reliably detect duplicates unless additional steps are taken to normalize the bundle header fields before comparison.

An additional problem is that this rewriting is not backwards-compatible with BSP, because it changes the length of the bundle header and also modifies the value of the Creation Timestamp field, which is part of the canonical representation of the bundle header [I‑D.irtf‑dtnrg‑bundle‑security] (Symington, S., Farrell, S., Weiss, H., and P. Lovell, “Bundle Security Protocol Specification,” February 2010.).

Is it worth providing this mechanism, even though we know that it doesn't work with BSP?

To work with BSP, one practical alternative is to use Bundle-in-Bundle, with a special (to-be-defined) tag, but this has issues as well.

3.5.  Bundle Status Reports

Timestamps appear in bundle status reports (i.e., time when a bundle was deleted or delivered). In DTNv6, these are all specified in absolute time, because it is assumed that any node or app that reads the timestamps will be in the same frame of reference as the writer. If this assumption is false, then these timestamps have no useful interpretation.

One possible modification, whose interpretation makes sense in "relative time" mode, is to replace these timestamps with the value of the time-to-live field on the bundle at the moment that the status change occurred (e.g., "this bundle was delivered five seconds before it would have expired"), or the lifetime field minus the time-to-live field (e.g., "this bundle was delivered twelve seconds after it was created").

4.  Security Considerations

4.1.  Incompatibility with the Bundle Security Protocol

As mentioned in Section 3.2 (Compatibility with the Bundle Security Protocol) and Section 3.4.3 (Discussion), the changes proposed in this document may require changes to BSP as well.

4.2.  Bundle Lifetime Limits and Incorrect Creation Times

A malicious or incorrect DTN node may create bundles with excessive lifetimes. This consideration is not unique to the proposed protocol, but already exists in DTNv6. If a DTN node creates a bundle with a very long Lifetime (in RT or AT mode), or a Creation Timestamp in the future (in AT mode), then the bundle may consume DTN resources for a very long time. It is possible to imagine a denial-of-service attack on a DTN by an attacker who slowly clogs the network with many immortal bundles that consume resources until the network is unable to accept any new bundles.

Every DTN node should have a policy about how it will handle a bundle with a Creation Timestamp from the future (for AT mode), an excessive Lifetime (in AT or RT mode) or Remaining Lifetime (in RT mode). How such a policy is specified is beyond the scope of this document.

5.  IANA Considerations

If a IANA registry for bundle protocol version numbers is ever created, then it will need to be updated to assign a new number to the protocol described by this document.

6.  Acknowledgments

This document incorporates suggestions and ideas from many members of the DTN community.

This draft incorporates significant improvements suggested by John Zinky, Brenton Walker, and William Ivancic.

7. Informative References

Author's Address