Delay Tolerant Networking

 

Introduction

 

w        The US Defense Advanced Research Projects Agency (DARPA), as part of its "Next Generation Internet" initiative, has recently been supporting a small group at the Jet Propulsion Laboratory (JPL) in Pasadena, California to study the technical architecture of an "Interplanetary Internet".

 

w        The idea was to blend ongoing work in standardized space communications capabilities with state of the art techniques being developed within the terrestrial Internet community, with a goal of facilitating a transition as the Earth's Internet moves off-planet between the applications and the locally optimized stacks

 

w        The "Interplanetary Internet" name was deliberately coined to suggest a far-future integration of space and terrestrial communications infrastructure to support the migration of human intelligence throughout the Solar System

w        An architecture based on a "least common denominator " protocol that can operate successfully and reliably in multiple disparate environments would simplify the development and deployment of Interplanetary Internet.

 

w        It is this analysis that lead to the proposal of Delay-Tolerant Network (DTN) architecture, an architecture that can support deep space applications, centered on a new end-to-end overlay network protocol called 'Bundling'.

 

w        The architecture and protocols developed for the project could also be useful in terrestrial environments where the dependence on real time interactive communication is not possible.

w        The Internet protocols are ill suited for this purpose, while the overlay

 

w        DTN is an architecture based on Internet-independent middleware: use exactly those protocols at all layers that are best suited to operation within each environment, but insert a new overlay network protocol between the applications

 

Why a Delay-Tolerant Network

 

w        Intermittent Connectivity

w        Lone or Variable Delay

w        Asymmetric Data Rates

w        High Error Rates

ConcepT

 

w        A delay-tolerant network (DTN) is a network of regional networks.

w         It is an over-lay on top of regional networks, including the Internet. DTNs support interoperability of regional networks by accommodating long de-lays between and within regional networks, and by translating between regional network communication characteristics.

w        In providing these functions, DTNs accommodate the mobility and limited power of evolving wireless communication devices.

w        The wireless DTN technologies may be diverse, including not only radio frequency (RF) but also ultra-wide band (UWB), free-space optical, and acoustic (sonar or ultrasonic) technologies

 Store-and-Forward Message Switching

 

w        DTNs overcome the problems associated with intermittent connectivity, long or variable delay, asymmetric data rates, and high error rates by using store-and-forward message switching.

 

w         This is an old method, used by pony-express and postal systems since ancient times.

 

w        Whole messages (entire blocks of application program user data)—or pieces (fragments) of such messages—are moved (forwarded) from a storage place on one node (switch intersection) to a storage place on another node, along a path that eventually reaches the destination

 

w        Store-and-forwarding methods are also used in today's voicemail and email systems, although these systems are not one-way relays (as shown above) but rather star relays; both the source and destination independently contact a central storage device at the center of the links

  

The Bundle Layer

 

w        The DTN architecture implements store-and-forward message switching by overlaying a new protocol layer—called the bundle layer—on top of heterogeneous region-specific lower layers.

w         The bundle layer ties together the region-specific lower layers so that application programs can communicate across multiple regions

w        Bundles are also called messages (as in message-switched). The bundle layer stores and forwards entire bundles (or bundle fragments) between nodes.

w        A single bundle-layer protocol is used across all networks (regions) that make up a DTN.

w        By contrast, the layers below the bundle layer (the transport layer and be-low) are chosen for their appropriateness to the communication environment of each region

 

A Non-Conversational Protocol

 

w        On intermittently connected links with long delays, conversational protocols such at TCP that involve many end-to-end round-trips may take impractical amounts of time or fail completely.

w         For this reason, DTN bundle layers communicate between themselves using simple sessions with minimal or no round-trips.

w        Any acknowledgement from the receiving node is optional, depending on the class of service selected .

w        The lower-layer protocols that support bundle-layer exchanges may, of course, be conversational like TCP.

w        But on intermittently connected links with long de-lays, non-conversational or minimally-conversational lower-layer protocols can be implemented

  

DTN Nodes

 

w        In a DTN, a node is an entity with a bundle layer. A node may be a host, router, or gateway (or some combination) acting as a source, destination, or forwarder of bundles

w        Host—Sends and/or receives bundles, but does not forward them. A host can be a source or destination of a bundle transfer

w        Gateway—Forwards bundles between two or more DTN regions and may optionally be a host.

w        The bundle layers of gateways must have persistent storage and support custody transfers.

w        Gateways provide conversions between the lower-layer protocols of the regions they span.

 

Custody Transfers

 

w        A delay tolerant network consists of a directed graph G = (E; V ) where the set of directed edges E are derived from a list of contacts.

w         A contact describes a link's tail and head vertex, existence interval (from the tail's point of view), plus its (constant) capacity and latency during the interval. 1

w        An edge e = (t; h) is placed in the set E if t and h ever appear in a contact.

w        The set of vertices V consist of store-and-forward message routers which may optionally provide custody transfer.

w         Accepting a message with custody transfer amounts to promising not to delete it until it can be reliably delivered to another node providing custody transfer (or to the message's destination), to the best of the ability of the forwarder.

  

Internet vs. DTN Routing

 

w        TCP operates at the end points of a path, where it manages reliable end-to-end delivery of message segments.

w        IP operates at all nodes on the path, where it routes message data grams.

w         Internet routers do not require a transport layer for routing, but they implement transport and application layers (not shown) for routing-table maintenance and other management purposes

w        In a DTN, the protocol stacks of all nodes include both bundle and transport layers.

w        DTN gateways have the same double-stack layers as DTN routers, but gateways can run different lower-layer protocols (below the bundle layer) on each side of their double stack.

w        This allows gateways to span two reg ions that use different lower-layer protocols ions that use different lower-layer protocols

  

DTN Routing

 

 

w        The routing problem in a DTN may at first appear as the standard problem of dynamic routing but with extended link failure times. This is not the case.

 

w         For the standard dynamic routing problem, the topology is assumed to be connected (or partitioned for very short intervals), and the objective of the routing algorithm is to find the best currently-available path to move trace end-to-end.

 

w        In a DTN, however, an end-to-end path may be unavailable at all times; routing is performed over time to achieve eventual delivery by employing long-term storage at the intermediate nodes.

 

w        The DTN routing problem amounts to a constrained optimization problem where edges may be unavailable for extended periods of time and a storage constraint exists at each node

 

  

Routing With Zero Knowledge

 

w        A message is forwarded along an edge chosen randomly among all the current contacts.

 

w        If all edges are currently unavailable, the message waits for an edge to become available and is as- signed to the first available contact.

 

w        Properties FC performs poorly in nontrivial topologies because the chosen next-hop is essentially random and forwarding along the selected edge may not make any progress toward the destination.

 

w        A message may also oscillate forever among a set of nodes (especially when frequent contacts are present among a small set of nodes) or be delivered to a dead end. It has no provision to route around congestion.

 

w         Clearly, FC requires only local knowledge about the network and is trivial to implement improvements. The basic approach can be enhanced in many ways

 

w        One is to incorporate a sense of trajectory between the source and the destinations so that the message is routed in a direction closer to the destination.To prevent loops, a path vector type of approach can be used

 


Routing With Partial Knowledge

 

  • The algorithms in this category compute paths using one or more of the following oracles: contacts summary, contacts, and queuing.
  • Further, each message is routed independently of the future demand because the trace oracle is not used.
  •  These algorithms are all based upon assigning costs to edges and computing a form of minimum-cost (\shortest") path.
  •  Costs are assigned to edges (by consulting the available oracles) to reject the estimated delay of the message in taking that edge.
  • The challenge and sophistication lies in assigning costs such that the assigned costs are close to the delay that will actually be encountered when a message is forwarded across the DTN

 

Routing With Complete Knowledge

 

  • A Linear Programming formulation that uses all the oracles to determine the optimal routing for minimizing average delay in the network can be built.
  • The LP formulation is an adaptation of the dynamic version of the classical multi-commodity flow problem.
  • The dynamic version involves balancing flow during a set of disjoint time intervals.
  • Thus, the first step in employing an LP approach is to determine the time intervals over which the balance equations must hold.
  • The second step is to construct the other LP constraints for the DTN routing problem in which edges and nodes are capacitated in a time- varying fashion.
  • These constraints may cause messages to split

 

Other Algorithmic Variations

 

w        Active route re-computation

 

w        Global queuing estimation

 

w        Splitting revisited

 

Classes of Bundle Service

 

 

w        Custody Transfer

 

w        Return Receipt

 

w        Custody-Transfer Notification

 

w        Bundle-Forwarding Notification

 

w        Priority of Delivery


Security

 

w        Most network security methods attempt to mutually authenticate user identities and the integrity of messages, but they do not attempt to authenticate the routers that forward information.

 

w         In DTNs, forwarding nodes (routers and gateways) are also authenticated, and sender information is authenticated by forwarding nodes, so that network resources can be conserved by preventing the carriage of prohibited traffic at the earliest opportunity

 

An Interplanetary (IPN) Internet Example


Conclusion

 

w        Delay-tolerant applications would still need to be engineered with DTN architectural principles borne in mind, but at least the interface to the DTN technology would be one that has been used to implement any number of Internet applications over the past few decades

 

w        Work on the architecture for the Interplanetary Internet, which has since been generalized to DTN architecture, began in early 1998.

 

w         A new Research Group for Delay Tolerant Networking was chartered within the Internet Research Task Force in October 2002

 

w        Man has never stopped at the limitations of distances. Thanks to internet, the world has already become a global village.

 

w         Thanks to Inter Planetary Internet, the solar village is in the making. Delay Tolerant Networks will make IPN a reality. All this may take time, but it certainly will

 

Comments

Popular posts from this blog

Chemical test for Tragacanth

Chemical test for Benzoin

Chemical test for Agar/Agar-Agar / Japaneese Isinglass