DTN IP Neighbor Discovery (IPND)
draft-irtf-dtnrg-ipnd-01

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.

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 September 9, 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.  Terminology
2.  Protocol Description
    2.1.  Beacon Period
    2.2.  Unknown Neighbors
    2.3.  Enumerated Neighbors
    2.4.  Allowing Data to Substitute for Beacons
    2.5.  Discovering Bidirectional Links
    2.6.  Beacon Message Format
        2.6.1.  Services
        2.6.2.  Neighborhood Bloom Filter
    2.7.  IPND and CLAs
    2.8.  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 in 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 participating nodes is not known in advance. Therefore, an important primitive is Neighbor Discovery (ND), or the ability to dynamically discover 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.6 (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.2 (Unknown Neighbors). In contrast, unicast beacons are sent only to explicitly known and enumerated neighbors as described in Section 2.3 (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 local node.

2.1.  Beacon Period

An IPND implementation SHOULD send beacons periodically. The time interval between beacons SHOULD be appropriate for the conditions of the network and MAY be configurable.

A receiving node SHOULD know the expected beacon interval and use this parameter, along with the existence and time of received beacons to determine whether state of the sender's ability to transmit to the receiver, i.e., the up or down state of the sender to receiver link. The exact algorithm for determining the link status based on received beacons is implementation-defined.

2.2.  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.3.  Enumerated Neighbors

IPND MUST support multicast or broadcast beacons and SHOULD support both. IPND SHOULD support unicast beacons. Since multicast or broadcast discovery is not feasible over internetworks, the IP addresses of potential neighbors reachable only across multiple underlay hops must be explicitly enumerated for discovery. 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 underlay hops when provided with the addresses of those neighbors. In this way, IPND can be used to bridge IP-based DTNs while detecting disconnections among and between the DTNs.

2.4.  Allowing Data to Substitute for Beacons

Sending data to an IP address matching a configured beacon destination SHOULD suppress the generation of beacon messages to that destination for a period of time up to but no longer than the beacon sending interval. This suppression SHOULD NOT occur if the parameters of a new beacon message would differ from the preceding beacon including the advertised services (Services) or Neighborhood Bloom Filter (NBF) (Neighborhood Bloom Filter).

Upon receiving a data packet from a neighbor where the packets do not represent a beacon, a node SHOULD behave as if a beacon had been received from that neighbor, as follows. If the data packet is addressed to this node via a unicast address, then the behavior SHOULD be as if the implied received beacon contains a Neighborhood Bloom Filter which indicates the membership of the receiving node in the sender's 1-hop neighborhood. Otherwise, if the destination address is multicast or broadcast, then the receiving node should presume that the link is bidirectional if and only if its state was bidirectional prior to receiving the data packet. See Section 2.5 (Discovering Bidirectional Links). The sender's advertised services are presumed to be unchanged since the sender's last received beacon. If no beacons have previously been received from such a neighbor, then it is presumed that there are no services associated with the sender.

2.5.  Discovering Bidirectional Links

Many routing protocols work correctly only when links are bidirectional. In wired IP networks, link bidirectionality can often be presumed. For other types of networks, such as Mobile Ad-Hoc Networks (MANETs) this assumption often does not hold. If a link to a neighbor is said to be "up" only because one or more beacon messages have been received from that neighbor over a wireless medium, it is not generally safe to assume that the link is bidirectional. In practice, MANET networks often have links that are only unidirectional due to differences in antennae, transmit power, hardware variability, multi-path effects, etc.

To discover the bidirectionality of links, an IPND Neighborhood Bloom Filter (NBF) (Neighborhood Bloom Filter) facility MAY be employed in which each node advertises a Bloom filter representation of the set of neighbors from whom it has received enough recent beacons to be considered "up". Upon receiving a beacon from an "up" neighbor that advertises an NBF which represents a set containing the receiving node's ID, then the link SHOULD be considered bidirectional.

2.6.  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 Sequence Number    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          EID Len  (*)         |   Canonical EID (variable)    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
/                    Service Block (optional)                   /
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  NBF Length (*) (optional)    |    NBF Bloom Filter Bits      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The beacon message is comprised of the following fields:

• Version: An 8-bit field indicating the version of IPND that constructed this beacon. The present document describes version 0x02 of IPND. This version field is incremented for IPND if either the IPND protocol is modified or the Bundle Protocol version is incremented. In this way the field can also be used to determine the BP version supported by a potential DTN neighbor.
• Flags: An 8-bit field indicating IPND processing flags. Two flags are currently defined. 0x00 indicates that no special processing should be performed on the beacon. Semantics of bits are described here from least significant (LSb) to most significant (MSb).

  Bit 0

  Source EID present: iff set, indicates that the source node's EID is present in the beacon. If the EID is present, it is preceded by an SDNV indicating its length.

  Bit 1

  Service Block present: iff set, indicates that a service block is present.

  Bit 2

  Neighborhood Bloom Filter present: iff set, indicates that a Neighbor Bloom Filter is present.

• Beacon sequence number: A two-octet unsigned integer value incremented once for each beacon transmitted to a particular IP address.
• 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: (Services) Optional announced services in the beacon.
• Neighborhood Bloom Filter: (Neighborhood Bloom Filter) Optional length-prefixed bitfield representing the source node's 1-hop neighborhood.

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

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

+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Number of services (*) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Service Name Len (*)  | Service Name (variable)       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Service 1
|   Service Param Len (*) | Service Parameters (variable) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   Service Name Len (*)  | Service Name (variable)       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Service 2
|   Service Param Len (*) | Service Parameters (variable) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    ...

A service block is comprised of the following fields:

• Number of services: The number of services described in the block.
• 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.6.2.  Neighborhood Bloom Filter

In order to efficiently determine link bidirectionality, a node represents the set of its 1-hop neighbors using a Bloom filter referred to as the Neighborhood Bloom Filter (NBF). Upon receiving a beacon from a neighbor that contains an NBF, a node can quickly determine whether it is in the neighbor's NBF set, and thereby determine whether the link is bidirectional.

Every node that might operate in an environment where discovered links may not be bidirectional SHOULD include a Bloom filter in some of its beacons which describes the membership of its 1-hop neighbor set. The bits to set in the Bloom filter MUST be computed by computing hash(es) on the canonical EID of each 1-hop neighbor considered to be "up".

Different networks naturally have distinct requirements, tolerance for overhead, and node computing resources, so the parameters of the Bloom filter such as length, number and types of hash algorithms, etc., are not mandated by IPND. However, all nodes participating in such a DTN MUST use the same Bloom filter representation and parameters if they send Bloom filters.

Bloom filter data, if present, MAY be ignored by a node if its implementation does not provide for it, or if the parameters of the Bloom filter cannot be determined with certainty.

Nodes in DTNs with a likelihood of unidirectional links SHOULD provide Bloom filter data in some broadcast or multicast beacons if the routing protocol in use presumes that links are bidirectional.

A neighborhood Bloom filter need not be included on every beacon, but one SHOULD be present on at least one broadcast or multicast beacon following a change in the 1-hop neighborhood of the node. A neighborhood Bloom filter MAY be present on every broadcast or multicast beacon beacon.

A Bloom filter, if included in a beacon message, MUST be represented by an SDNV, and MUST follow Service Blocks field, if present, or the Canonical EID field if the Service Blocks field is not present.

2.7.  IPND and CLAs

IP-based CLAs are generally expected to depend on an IPND implementation module for their discovery service. A CLA MAY opt not to use IPND, either because that CLA does not require discovery or provides its own.

Once IPND discovers a new neighbor it MUST inform all CLAs which depend on IPND of the neighbor's existence and the discovered parameters. The exact means by which IPND communicates with the CLAs is implementation dependent.

Similarly, once IPND determines that a link has gone down, it MUST inform all dependent CLAs of the link down event.

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