DTN IP Neighbor Discovery (IPND)
draft-irtf-dtnrg-ipnd-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 February 10, 2010.

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

Disruption Tolerant Networking (DTN) IP Neighbor Discovery (IPND), is a method for otherwise oblivious nodes to learn of the existence, availability, and addresses of other DTN participants. IPND both sends and listens for small IP UDP announcement "beacons." Beacon messages are addressed to an IP unicast, multicast, or broadcast destination to discover specified remote neighbors, or unspecified local neighbors in the topology, e.g. within wireless range. IPND beacons advertise neighbor availability by including the DTN node's canonical endpoint identifier. IPND beacons optionally include service availability and parameters. In this way, neighbor discovery and service discovery may be coupled or decoupled as required. Once discovered, new neighbor pairs use advertised availabilities to connect, exchange routing information, etc. This document describes DTN IPND.

Table of Contents

1.  Introduction
    1.1.  Terminology
2.  Protocol Description
    2.1.  Unknown Neighbors
    2.2.  Enumerated Neighbors
    2.3.  Beacon Message Format
        2.3.1.  Services
        2.3.2.  Zero-length EID Beacons
    2.4.  Connection Establishment
    2.5.  Disconnection
3.  Relation to Other Discovery Protocols
4.  Implementation Experience
5.  Security Considerations
6.  IANA Considerations
7.  References
    7.1.  Normative References
    7.2.  Informative References
§  Authors' Addresses

1.  Introduction

Delay and Disruption Tolerant Networks (DTNs) [RFC4838] (Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R., Scott, K., Fall, K., and H. Weiss, “Delay-Tolerant Networking Architecture,” April 2007.) make no presumptions about network topology, routing, or availability. DTNs therefore attempt to provide communication in challenged environments where, for instance, contemporaneous end-to-end paths do not exist. Examples of such DTNs arise is a variety of contexts including mobile social networks, space communications, rural message delivery, military networks, etc.

In many DTN scenarios, the identity and meeting schedule of other participating nodes is not known in advance. Therefore, an important primitive is Neighbor Discovery (ND), or the ability to dynamically locate other DTN nodes. This document specifies Internet Protocol Neighbor Discovery (IPND). In contrast to link or physical layer discovery, IPND enables a general form of neighbor discovery across a heterogeneous range of links, as are often found in DTN networks. IPND is particularly useful in mobile, ad-hoc DTN environments where meeting opportunities are not known a priori and connections may appear or disappear without warning. For example, two mobile nodes might come into radio distance of each other, discover the new connection, and move data along that connection before physically disconnecting.

In addition to discovering neighbors, it is often valuable to simultaneously discover services available from that neighbor. Examples of DTN services include a neighbor's available Convergence Layer Adapters (CLAs) and their parameters (e.g. [TCPCLA] (Demmer, M. and J. Ott, “Delay Tolerant Networking TCP Convergence Layer Protocol,” Nov 2008.)), available routers (e.g. [PROPHET] (Lindgren, A. and A. Doria, “Probabilistic Routing Protocol for Intermittently Connected Networks,” Mar 2006.)), tunnels, etc. Newly discovered nodes will then typically participate in bundle [RFC5050] (Scott, K. and S. Burleigh, “Bundle Protocol Specification,” November 2007.) routing and delivery.

In other situations it is useful to decouple service discovery from neighbor discovery for efficiency and generality. For example, upon discovering a neighbor, a DTN node might initiate a separate negotiation process to establish 1-hop connectivity via a particular convergence layer, perform routing setup, exchange availability information, etc.

IPND beacons thus optionally advertise a node's available services while maintaining the ability to decouple node and service discovery as necessary. This flexibility is important to various DTN use scenarios where connection opportunities may be limited (thus necessitating an atomic message for all availability information), bandwidth might be scarce (thus implying that service discovery should be an independent negotiation to lower beacon overhead), or connections have very large round-trip-times (service negotiation is therefore too costly with respect to time).

DTN IPND is designed to be simple, efficient, and general.

Although this document describes a neighbor discovery protocol in terms of IP, the principles and basic mechanisms used in this protocol may also be expressed in terms of other datagram protocols.

The remainder of this document describes DTN IPND.

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

The following terminology is used for describing DTN IPND.

Bundle: A PDU as defined in [RFC5050] (Scott, K. and S. Burleigh, “Bundle Protocol Specification,” November 2007.).

Node: A DTN entity in the network that receives and processes bundles.

Beacon message: An IPND-specific message, defined in this document, used to announce the presence of a DTN node and parameters with which to connect to that node.

Convergence layer adapter: A convergence layer adapter (CLA) sends and receives bundles on behalf of a node by providing the conversion between bundles and a transport protocol such as TCP or UDP.

2.  Protocol Description

Nodes use DTN IPND beacons, small UDP messages in the IP underlay, to advertise presence. Similarly, IPND beacons received from other nodes serve to detect the availability of DTN neighbors. Nodes SHOULD both send and receive beacons. These beacon messages, detailed in Section 2.3 (Beacon Message Format), may be sent either as IP unicast, multicast, or broadcast UDP packets. The beacon message content is agnostic to the underlying transport mode.

Broadcast beacons are designed to reach unknown neighbors in neighborhoods within the local network broadcast domain. Multicast [RFC1112] (Deering, S., “Host extensions for IP multicasting,” August 1989.) beacons extend the scope of beacon dissemination to potentially include multiple networks across routed boundaries. On broadcast media such as Ethernet or wireless, multicast and broadcast beacons are sent as link-layer broadcast messages.

Broadcast and multicast discovery are described in Section 2.1 (Unknown Neighbors). In contrast, unicast beacons are sent only to explicitly known and enumerated neighbors as described in Section 2.2 (Enumerated Neighbors).

Upon discovering a neighbor, IPND can establish a connection to the new neighbor via an IP-based Convergence Layer Adapter (CLA), for example the TCP [TCPCLA] (Demmer, M. and J. Ott, “Delay Tolerant Networking TCP Convergence Layer Protocol,” Nov 2008.) or UDP [UDPCLA] (Kruse, H. and S. Ostermann, “UDP Convergence Layers for the DTN Bundle and LTP Protocols,” Nov 2008.) CLA. The CLA then negotiates the connection per its individual specification and installs the appropriate next-hop routing information in the BPA.

2.1.  Unknown Neighbors

In the general case, the IP addresses of potential neighbors are not known in advance. To discover unknown neighbors, IPND beacon messages are sent as IP packets with either multicast or broadcast destination addresses. IPND MUST support multicast IP destination addresses [RFC1112] (Deering, S., “Host extensions for IP multicasting,” August 1989.) and multicast IGMP group membership [RFC3376] (Cain, B., Deering, S., Kouvelas, I., Fenner, B., and A. Thyagarajan, “Internet Group Management Protocol, Version 3,” October 2002.). IPND MAY support IP broadcast destinations. IPND multicast addresses SHOULD be from the IANA assigned local network control block 224.0.0/24 [RFC3171] (Albanna, Z., Almeroth, K., Meyer, D., and M. Schipper, “IANA Guidelines for IPv4 Multicast Address Assignments,” August 2001.). This block of multicast addresses is intentionally scoped to the local network to prevent dissemination to the wider Internet.

IPND MAY also use other multicast addresses as required, such as multicast addresses from the IANA assigned Internetwork Control Block [RFC3171] (Albanna, Z., Almeroth, K., Meyer, D., and M. Schipper, “IANA Guidelines for IPv4 Multicast Address Assignments,” August 2001.).

In all cases, IPND MUST support a configurable IP time-to-live value for all beacon messages.

2.2.  Enumerated Neighbors

IPND SHOULD support unicast beacons. IPND is primarily designed for discovery of nodes in the current broadcast or multicast domain. However, some situations mandate discovery across multiple Internet IP overlay hops. Across the wide-area Internet, multicast or broadcast discovery is not feasible. In such instances, the IP addresses of potential neighbors must be explicitly enumerated. While the neighbor's address is therefore known, the availability of that neighbor is not known. IPND thus permits DTN nodes to discover available remote neighbors across multiple IP overlay hops simply by enumerating their addresses.

Note that unicast discovery scales with the square of the number of enumerated nodes, i.e. one beacon packet per enumerated destination. Therefore, unicast discovery is intended for relatively small numbers of neighbors.

2.3.  Beacon Message Format

Figure 1 (Beacon Message Format) depicts the format of beacon messages. Note that IPND follows the DTN convention of using Self-Delimiting Numeric Values (SDNVs) [SDNV] (Eddy, W., “Using Self-Delimiting Numeric Values in Protocols,” Jan 2009.) to represent variable length integers (denoted by *). IPND MUST use UDP checksums to ensure correctness.

0                   1                   2                   3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    Version    |     Flags     |         Beacon Len (*)        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          EID Len  (*)         |   Canonical EID (variable)    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
/                   Service Blocks (optional)                   /
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The beacon message is comprised of the following fields:

• Version: A 1-byte field indicating the version of IPND that constructed this beacon. The present document describes version 0x01 of IPND.
• Flags: A 1-byte field indicating IPND processing flags. Two flags are currently defined. 0x00 indicates that no special processing should be performed on the beacon. 0x01 indicates that no length or local EID fields follow and allows for very short, efficient beacons; see Section 2.3.2 (Zero-length EID Beacons) for details.
• Beacon Length: The byte length of the beacon inclusive of the entire beacon message, but exclusive of IP or UDP headers. The length field is an SDNV and is therefore variable length. A two-octet length is shown for convenience of representation.
• EID Length: The byte length of the canonical EID contained in the beacon. The EID length field is an SDNV and is therefore variable length. A two-octet length is shown for convenience of representation.
• Canonical EID: The canonical end node identifier of the neighbor advertised by the beacon message. The canonical EID is variable length and represented as a Uniform Resource Identifier [RFC3986] (Berners-Lee, T., Fielding, R., and L. Masinter, “Uniform Resource Identifier (URI): Generic Syntax,” January 2005.).
• Service Blocks: Optional announced services in the beacon, described in Section 2.3.1 (Services).

2.3.1.  Services

As described previously, beacon messages may optionally include service availability information. The services are intended to represent available CLAs, routers, etc., but are sufficiently general to accommodate unanticipated services provided by the advertising node.

For example, the source IP address of a received beacon suffices to identify the remote node at the IP level. However, the IP address alone does not inform other processes via which transport mechanism (e.g. TCP or UDP) or via which transport port the remote node is offering a connection. Similarly, nodes do not know which routers (e.g. [PROPHET] (Lindgren, A. and A. Doria, “Probabilistic Routing Protocol for Intermittently Connected Networks,” Mar 2006.)) are running on a remote node in order to inform bundle exchange.

Therefore, beacons may contain service blocks. An end-node determines the length of the announced service blocks as follows.

A node parses the beacon length and EID length SDNV fields. Let v(b) represent the value of the beacon length and v(e) represent the value of the EID length. The SDNV representation of beacon and EID length is itself variable length. Let l(b) represent the on-wire length of the beacon length SDNV and l(e) represent the on-wire length of the EID length SDNV. The total byte length of any option service blocks is then:

            service block length = v(b) - 2 - l(b) - l(e) - v(e)

The format of a service block is given in Figure 2 (Service Block Format).

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     Service Name Len (*)      | Service Name (variable)       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|     Service Param Len (*)     | Service Parameters (variable) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

A service block is comprised of the following fields:

• Service Name Length: The length of the advertised service name or description. The service name length is an SDNV and is therefore variable length. The service name MUST have non-zero length.
• Service Name: An identifying name for the service, e.g. "UDPCLA."
• Service Parameters Length: The length of service-specific parameters that accompany this announcement. The service parameters length is an SDNV and is therefore variable length.
• Service Parameters: Service-specific parameters required to use the service, e.g. "port=4453."

2.3.2.  Zero-length EID Beacons

A beacon with a 0x01 flag has special meaning and indicates a "zero-length EID." IPND MUST support zero-length EID beacons. Neither the beacon length, canonical EID, nor any service block fields are present in these beacons, and the total length of the beacon is therefore only two octets. Nodes SHALL assume that the canonical EID of a zero-length EID is the dotted-quad URI representation of the beacon's source IP address.

Zero-length beacons imply that any remote node receiving the beacon may connect via the source IP address of the beacon, using the UDP CLA on UDP port 4556. This optimization is made for efficiency and ease of implementation reasons, for instance in constrained scenarios where devices are unwilling or unable to implement SDNV and a default connection procedure suffices.

2.4.  Connection Establishment

Once IPND discovers a new node and the connection parameters, it may initiate the connection. The exact means by which IPND communicates with the CLAs is implementation dependent. The specified CLA should establish the connection using the methods and conventions defined for that CLA.

Note that two nodes may discover each other simultaneously and attempt to initiate connections simultaneously. In instances of uni-directional CLAs, IPND must provide uni-directional discovery. However, in general, bi-direction CLAs such as TCP should attempt to form a single connection rather than two separate connections. IPND does not discern between uni and bi-directional connections or address potential race conditions in bilateral connection establishment.

2.5.  Disconnection

Note that IPND SHOULD maintain state over all existing neighbors in order to prevent CLAs from needlessly attempting to establish connections between nodes that are already connected. To maintain the current neighbor set, IPND removes stale neighbors after the defined neighbor receive timeout period elapses without receiving any beacon messages from a particular neighbor.

Upon detecting a neighbor that is no longer available, IPND MAY provide hints to the CLA that the neighbor is gone. Note that some CLAs themselves provide keepalive-type functionality and therefore IPND is not necessarily required to detect down neighbors. However, placing both discovery and availability information in IPND provides a single, coherent point in the system design to maintain neighbor information.

3.  Relation to Other Discovery Protocols

A variety of discovery protocols exist in other contexts and domains. These discovery protocols include the ability to discover available neighbors and services. For example, the IETF zero configuration working group [RFC3927] (Cheshire, S., Aboba, B., and E. Guttman, “Dynamic Configuration of IPv4 Link-Local Addresses,” May 2005.), the bonjour protocol [BONJOUR] (Cheshire, S., “Bonjour,” Apr 2005.), and the OLSR discovery protocol [NHDP] (Clausen, T., Dearlove, C., and J. Dean, “MANET Neighborhood Discovery Protocol (NHDP),” Mar 2009.) all provide similar functionality.

Other rendezvous mechanisms are possible that allow a node to find a neighbor of a particular type or with particular properties. For example, the Domain Name System (DNS) or Distributed Hash Tables (DHTs) could be used to find a neighbor that provides an inter-planetary gateway. Such advanced rendezvous schemes are beyond the scope of this document.

In contrast, DTN-IPND is designed to be DTN-specific, efficient, and extremely lightweight. For instance, DTN-IPND is capable of supporting arbitrary length DTN EIDs, and includes CLA information in order to maximize the utility of each beacon message without requiring multiple round-trip times in order to perform complex protocol negotiation.

While DTN-IPND MAY be used in non-DTN environments, its use is RECOMMENDED only in DTNs.

4.  Implementation Experience

BBN Technologies has implemented and deployed DTN IPND as part of the SPINDLE [SPINDLE] (Krishnan, R., “Survivable Policy-Influenced Networking: Disruption-tolerance through Learning and Evolution,” Oct 2006.) project.

5.  Security Considerations

Neighbor discovery may be perceived as an impediment to security because it advertises a potential target for attacks. Discovering the existence of a particular node is orthogonal to securing the services of that node. Nodes that desire or require higher-levels of security SHOULD disable the broadcast IPND beacons and rely instead on static neighbor configuration.

Further, neighbor discovery represents a potential source of network congestion and contention. Therefore, careful consideration should be made to the frequency and TTL scope of beacons when setting implementation-specific parameters, particularly when a setting affects larger regions of the network.

6.  IANA Considerations

None at this time.

7.  References

7.1. Normative References

7.2. Informative References

Authors' Addresses