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
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
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
Post a Comment