Network Working Group S. Burleigh
Internet-Draft Jet Propulsion Laboratory,
Intended status: Experimental California Institute of
Expires: January 9, 2011 Technology
July 8, 2010
Contact Graph Routing
draft-burleigh-dtnrg-cgr-01
Abstract
This document describes Contact Graph Routing (CGR), a procedure for
computing efficient Delay-Tolerant Networking (DTN) bundle forwarding
routes between source and destination endpoints when connectivity
between pairs of neighboring bundle protocol agents in the network is
scheduled and episodic rather than continuous.
Requirements Language
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 RFC 2119 [RFC2119].
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
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."
This Internet-Draft will expire on January 9, 2011.
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
Burleigh Expires January 9, 2011 [Page 1]
Internet-Draft CGR July 2010
(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 Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Specification . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1. Architectural Considerations . . . . . . . . . . . . . . . 5
2.2. The Contact Plan . . . . . . . . . . . . . . . . . . . . . 6
2.3. The Contact Graph . . . . . . . . . . . . . . . . . . . . 6
2.4. Terminology . . . . . . . . . . . . . . . . . . . . . . . 7
2.4.1. Well-Formed Routes . . . . . . . . . . . . . . . . . . 7
2.4.2. Expiration time . . . . . . . . . . . . . . . . . . . 7
2.4.3. OWLT Margin . . . . . . . . . . . . . . . . . . . . . 7
2.4.4. Last Moment . . . . . . . . . . . . . . . . . . . . . 8
2.4.5. Capacity . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.6. Estimated Capacity Consumption . . . . . . . . . . . . 8
2.4.7. Residual Capacity . . . . . . . . . . . . . . . . . . 9
2.4.8. Plausible Opportunity . . . . . . . . . . . . . . . . 9
2.4.9. Plausible Routes . . . . . . . . . . . . . . . . . . . 9
2.4.10. Forfeit Time . . . . . . . . . . . . . . . . . . . . . 9
2.4.11. Network distance . . . . . . . . . . . . . . . . . . . 10
2.4.12. Excluded Neighbors . . . . . . . . . . . . . . . . . . 10
2.4.13. Critical Bundles . . . . . . . . . . . . . . . . . . . 10
2.5. Dynamic Route Computation Algorithm . . . . . . . . . . . 11
2.5.1. Initialization . . . . . . . . . . . . . . . . . . . . 11
2.5.2. Contact Review Procedure . . . . . . . . . . . . . . . 11
2.5.3. Forwarding Decision . . . . . . . . . . . . . . . . . 13
2.6. Exception Handling . . . . . . . . . . . . . . . . . . . . 14
3. Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
5. Security Considerations . . . . . . . . . . . . . . . . . . . 16
6. Normative References . . . . . . . . . . . . . . . . . . . . . 17
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 17
Burleigh Expires January 9, 2011 [Page 2]
Internet-Draft CGR July 2010
1. Introduction
This document describes Contact Graph Routing (CGR), a set of
procedures for computing efficient routes by which Delay-Tolerant
Networking (DTN) Bundle Protocol (BP) [RFC5050] "bundles" may be
forwarded between source and destination BP endpoints when
connectivity between pairs of neighboring bundle protocol agents
(BPAs) in the network is scheduled and episodic rather than
continuous.
BP is designed to enable end-to-end forwarding of a unit of user
data, encapsulated in a bundle, from one BP endpoint to another,
possibly indirectly through the agency of intermediate BPAs that
relay the bundle among themselves toward the destination endpoint.
The forwarding of bundles through a DTN-based network differs in
several ways from the forwarding of packets through an IP-based
network. In an IP-based network:
o Connectivity -- the ability of topologically adjacent
("neighboring") network nodes to exchange packets -- is typically
continuous throughout the network. Lapses in connectivity are
anomalous and may be interpreted as changes in topology.
o Signal propagation latencies are very small. This fact, coupled
with continuous connectivity, ensures that the rate at which
information on changes in connectivity may be propagated through
the network far exceeds the rate at which those changes occur.
A network based on DTN is different:
o There is no expectation of continous connectivity throughout the
network. Lapses in connectivity may be routine, lengthy, and
recurring; they should not be interpreted as changes in topology.
o Signal propagation latencies may be large. This fact, coupled
with routinely punctuated connectivity, means that the rate at
which information on changes in connectivity may be propagated
through the network may be far lower than the rate at which those
changes occur.
These differences imply that the constraints within which forwarding
routes are computed in a DTN-based network are different from those
within which IP routes are computed, so route computation procedures
must be different.
In particular, IP routing at each router can be based on a local
understanding of current connectivity in the network that may be
Burleigh Expires January 9, 2011 [Page 3]
Internet-Draft CGR July 2010
assumed to be generally accurate and generally stable over time. The
route to a given destination host, once computed, may be stored in a
routing table for future reference and will only need to be changed
upon the arrival of new connectivity information -- conveyed by
routing protocol messages generated immediately in response to
detected changes in connectivity -- that invalidates that route.
DTN routing enjoys no such advantages. The potential delay in the
arrival of information regarding connectivity changes makes all such
information potentially obsolete; a BPA that relied solely on this
flow of information might never have a fully accurate understanding
of current connectivity in the network.
Yet BPAs that must compute routes in a DTN-based network have no
alternative but to rely on that understanding, imperfect as it may
be. Each BPA must therefore augment its model of connectivity in the
network by other means. Some elements of the model may simply be
asserted by network management, i.e., as static routes. Some changes
in proximate DTN network connectivity may be discovered in real time.
Other connectivity changes may be predicted on a probabilistic basis.
Contact Graph Routing is designed for use in networks where changes
in connectivity are planned and scheduled, rather than predicted,
discovered, or contemporaneously asserted.
Scheduled changes in connectivity characterize a number of potential
DTN application environments:
o Episodes of communication between robotic spacecraft in
interplanetary space and ground tracking stations on Earth are
typically scheduled weeks or months before they occur.
o The beginning and end of each communication opportunity between an
orbiting spacecraft and a communication asset on a planetary
surface -- either Earth or another planet -- can readily be
computed from known orbital elements.
o Power-conserving motes of sensor webs may communicate on
infrequent, fixed intervals established by network configuration.
Where changes in connectivity are scheduled, a global "contact plan"
of all such events may be distributed in advance to all BPAs,
enabling each BPA to have a theoretically accurate understanding of
connectivity in the network at any specified moment. The Contact
Graph Routing procedures compute bundle forwarding decisions from
this time-varying model of network connectivity.
Burleigh Expires January 9, 2011 [Page 4]
Internet-Draft CGR July 2010
2. Specification
2.1. Architectural Considerations
As discussed in the Bundle Protocol (BP) specification [RFC5050], the
source and destination of each bundle are BP endpoints, identified by
BP endpoint ID (EID) strings that are URIs.
However, the actual agents of bundle origination, forwarding, and
delivery are instances of Bundle Protocol procedures implementation
(bundle protocol agents) that are installed at physical computational
entities termed "nodes".
For bundle forwarding purposes, a BP endpoint only exists so long as
at least one node is "registered" in that endpoint: only the
operation of the BPA at a node can cause a bundle to be delivered to
an endpoint, and a BPA can only deliver a bundle to an endpoint
within which that BPA's host node is registered. That is, the
existence of a node is a precondition for the existence of an
endpoint, and arrival of a bundle at a node's BPA is a precondition
for the delivery of that bundle to an endpoint.
Moreover, it is not unusual for a single node to be registered in
multiple endpoints, each serving the needs of a different DTN
application operating at that node. When this is the case, the
arrival of a bundle at some single BPA is a precondition for the
delivery of that bundle to any of a potentially large number of
endpoints.
For these reasons, the design of CGR is based on the concept of
forwarding each bundle to the node in which the bundle's destination
endpoint is registered (rather than directly to the destination
endpoint), leaving to the node's BPA the task of final delivery.
Execution of this concept requires that nodes be recognized as first-
class BP architectural elements, which must be uniquely identified in
order to ensure accurate bundle delivery to the correct destination
endpoints. CGR assumes that all nodes in the network are identified
by unique "node numbers" as discussed in the specification for
Compressed Bundle Header Encoding (CBHE). When CGR is used to
forward a bundle to an endpoint identified by a CBHE-conformant EID,
the destination node number can simply be extracted from the EID.
CGR can also be used to forward bundles to an endpoint identified by
a non-CBHE-conformant EID, but only if that EID can somehow be mapped
to the appropriate destination node number; mechanisms for
accomplishing this mapping are beyond the scope of this
specification.
Burleigh Expires January 9, 2011 [Page 5]
Internet-Draft CGR July 2010
Note that the design of CGR precludes its use for routing a bundle to
a "multicast" endpoint: by definition, a multicast endpoint ID cannot
be mapped to the number identifying a single node. CGR can only be
used for forwarding bundles to "singleton" endpoints.
2.2. The Contact Plan
CGR relies on accurate contact plan information, provided in the form
of contact plan messages. The details of a protocol for distributing
contact plan information to the BPAs that require it have yet to be
defined; that protocol is beyond the scope of this document.
However, a working notion of contact plan message contents will help
to clarify the CGR procedures.
Contact plan messages are of two types: contact messages and range
messages. Each contact message has the following content::
o The starting UTC time of the interval to which the message
pertains.
o The stop time of this interval, again in UTC.
o The Transmitting (A) node number.
o The Receiving (B) node number.
o The planned rate of transmission from node A to node B over this
interval, in bytes per second.
Each range message has the following content:
o The starting UTC time of the interval to which the message
pertains.
o The stop time of this interval, again in UTC.
o Node number A.
o Node number B.
o The anticipated distance between A and B over this interval, in
light seconds.
2.3. The Contact Graph
Given a complete contact plan, the BPA at a node can construct a
"contact graph" data structure. The contact graph constructed
locally at a given node contains, for _every other_ node D in the
Burleigh Expires January 9, 2011 [Page 6]
Internet-Draft CGR July 2010
network:
o A list of "xmit" objects encapsulating contact start time, stop
time, transmitting node number, and data transmission rate,
derived from all contact messages whose receiving node is node D.
This list is ordered by stop time.
o A list of "origin" objects encapsulating transmitting node number
S and that node's presumed current distance from node D, based on
the information in range messages.
This information must be updated as time passes: stored range
messages must be used to add new origin objects to the contact graph
as their start times are reached, and xmit and origin objects whose
stop times have been reached must be purged from the contact graph.
2.4. Terminology
2.4.1. Well-Formed Routes
A well-formed route for given bundle is defined as a sequence of
contacts such that the first contact is from the bundle's source node
to some other node, every subsequent contact in the sequence is from
the receiving node of the prior contact to some other node, the last
contact in the sequence is from some node to the bundle's final
destination node, and the route contains no loops - i.e., no two
contacts in the sequence involve transmission from the same node and
no two contacts in the sequence involve transmission to the same
node.
2.4.2. Expiration time
Every bundle transmitted via DTN has a time-to-live (TTL), the length
of time after which the bundle is subject to destruction if it has
not yet been delivered to its destination. The expiration time of a
bundle is computed as its creation time plus its TTL. When computing
the next-hop destination for a bundle that the local bundle agent is
required to forward, there is no point in selecting a route that
can't get the bundle to its final destination prior to the bundle's
expiration time.
2.4.3. OWLT Margin
One-way light time (OWLT) - that is, distance - is obviously a factor
in delivering a bundle to a node prior to a given time. OWLT can
actually change during the time a bundle is en route, but route
computation becomes intractably complex if we can't assume an OWLT
"safety margin" - a maximum delta by which OWLT between any pair of
Burleigh Expires January 9, 2011 [Page 7]
Internet-Draft CGR July 2010
nodes can change during the time a bundle is in transit between them.
We assume that the maximum rate of change in distance between any two
nodes in the network is about 150000 miles per hour, which is about
40 miles per second. (This was the speed of the Helios spacecraft,
the fastest man-made object launched to date.) At this speed, the
distance between any two nodes that are initially separated by a
distance of N light seconds will increase by a maximum of 40 miles
per second of transit. This will result in data arrival no later
than roughly (N + Q) seconds after transmission, where the "OWLT
margin" value Q is (40 * N) divided by 186000, rather than just N
seconds after transmission as would be the case if the two nodes were
stationary relative to each other. When computing the expected time
of arrival of a transmitted bundle we simply use N + Q, the most
pessimistic case, as the anticipated total in-transit time.
2.4.4. Last Moment
The last moment for sending a bundle during a given contact such that
it will arrive at the receiving node prior to some deadline is
computed as the deadline minus the sum of (a) the current one-way
light time N between the contact's transmitting and receiving nodes
(which can be obtained from the origin object for the transmitting
node, in the receiving node's list of origins) and (b) the applicable
OWLT margin for N, as defined above. If the contact's start time is
after the last moment for the deadline, then clearly no transmission
whatsoever that is initiated during that contact can be assured of
getting the bundle to the contact's receiving node prior to the
deadline.
2.4.5. Capacity
The capacity of a contact is the product of its data transmission
rate (in bytes per second) and its duration (stop time minus start
time, in seconds).
2.4.6. Estimated Capacity Consumption
The size of a bundle is the sum of the sizes of all blocks of the
bundle including the payload block, but bundle size is not the only
lien on the capacity of a contact. The total estimated capacity
consumption (or "ECC") for a bundle that is queued for transmission
over some convergence-layer (CL) protocol channel is a more lengthy
computation. For each recognized CLprotocol, we can estimate the
number of bytes of "overhead" (that is, data that serves the purposes
of the CL protocol itself rather than the user application that is
using it) for each frame of CL protocol transmission. If the CL
protocol stack were UDP/IP over the Internet, for example, we might
estimate the CL overhead per frame to be 100 bytes, allowing for the
Burleigh Expires January 9, 2011 [Page 8]
Internet-Draft CGR July 2010
nominal sizes of the UDP, IP, and Ethernet or SONET overhead for each
IP packet. We can estimate the number of bundle bytes per CL
protocol frame as the total size of each frame less the per-frame CL
overhead. Continuing the example begun above, we might estimate the
number of bundle bytes per frame to be 1400, which is the standard
MTU size on the Internet (1500 bytes) less the estimated CL overhead
per frame. We can then estimate the total number of frames required
for transmission of a bundle of a given size: this number is the
bundle size divided by the estimated number of bundle bytes per CL
protocol frame, rounded up. The estimated total CL overhead for a
given bundle is, then, the per-frame CL overhead multiplied by the
total number of frames required for transmission of a bundle of that
size. Finally, the ECC for that bundle can be computed as the sum of
the bundle's size and its estimated total CL overhead.
2.4.7. Residual Capacity
The residual capacity of a given contact between the local node and
one of its neighbors, as computed for a given bundle, is the sum of
the capacities of that contact and all prior scheduled contacts
between the local node and that neighbor, less the sum of the ECCs of
all bundles with priority equal to or higher than the priority of the
subject bundle that are currently queued for transmission to that
neighbor.
2.4.8. Plausible Opportunity
A plausible opportunity for transmitting a given bundle to some
neighboring node is defined as a contact whose residual capacity is
at least equal to the bundle's ECC. That is, if the capacity of a
given contact is already fully subscribed, when computing routes for
the next bundle there is no purpose served by assuming transmission
during that contact.
2.4.9. Plausible Routes
A plausible route for a given bundle is a well-formed route whose
constituent contacts are all plausible transmission opportunities
such that transmission of the bundle during each contact can occur
before the last moment for that contact's applicable deadline. The
applicable deadline for the last contact in the route is the bundle's
expiration time; the applicable deadline for each preceding contact
is the end of that contact.
2.4.10. Forfeit Time
The forfeit time for a plausible route is the time by which the
subject bundle must be transmitted from the local node to a
Burleigh Expires January 9, 2011 [Page 9]
Internet-Draft CGR July 2010
neighboring node in order to have any chance of taking that route.
Typically it is the stop time of the first contact in the route (the
contact between the local node and its neighbor). However, it is
possible for the first contact in a route to be a continuous contact,
in which case the actual forfeit time may be the stop time of a
downstream contact that starts after the start of the first contact
but ends before the first contact stops. So, more generally, the
forfeit time for a route is the earliest stop time among all contacts
in the route.
2.4.11. Network distance
The network distance for a plausible route is the number of
intermediate forwarding nodes that will be utilized in conveying the
bundle to the destination node from the node at which route
computation is being performed.
2.4.12. Excluded Neighbors
A neighboring node C that refuses custody of a bundle destined for
some remote node D is termed an excluded neighbor for (that is, with
respect to computing routes to) D. So long as C remains an excluded
neighbor for D, no bundles destined for D will be forwarded to C -
except that occasionally (once per lapse of the RTT between the local
node and C) a custodial bundle destined for D will be forwarded to C
as a "probe bundle". C ceases to be an excluded neighbor for D as
soon as it accepts custody of a bundle destined for D.
2.4.13. Critical Bundles
A Critical bundle is one that absolutely has got to reach its
destination and, moreover, has got to reach that destination as soon
as is physically possible.
For ordinary non-Critical bundles, the CGR dynamic route computation
algorithm uses the contact graph to calculate which of the plausible
routes to the bundle's final destination is determined to be "best"
(as defined below). It then inserts the bundle into the outbound
transmission queue for transmission to the neighboring node that is
the first step along that route. It is possible, though, that due to
some unforeseen delay the selected route will turn out to be less
successful than another route that was not selected: the bundle might
arrive later than it would have if another route had been selected,
or it might not even arrive at all.
For Critical bundles, the CGR dynamic route computation algorithm
causes the bundle to be inserted into the outbound transmission
queues for transmission to all neighboring nodes that are on
Burleigh Expires January 9, 2011 [Page 10]
Internet-Draft CGR July 2010
plausible routes to the bundle's final destination. The bundle is
therefore guaranteed to travel over the most successful route, as
well as over all other plausible routes. Note that this may result
in multiple copies of a Critical bundle arriving at the final
destination.
Note also that designation of a bundle as Critical is not addressed
in the base Bundle Protocol specification, but it is supported by the
Extended Class of Service (ECOS) extension block specification.
2.5. Dynamic Route Computation Algorithm
2.5.1. Initialization
We start the route computation algorithm by setting destination
variable D to the bundle's final destination node number, setting
"deadline" variable X to the bundle's expiration time, creating an
empty list of Proximate Nodes to send to, initializing forfeit time
to infinity, initializing network distance to zero, and creating a
list of Excluded Nodes, i.e., nodes through which we will *not*
compute a route for this bundle. The list of Excluded Nodes is
initially populated with:
o the node from which the bundle was directly received (so that we
avoid cycling the bundle between that node and the local node) -
unless the Dynamic Route Computation Algorithm is being re-applied
due to custody refusal as discussed later;
o all excluded neighbors for the bundle's final destination node.
Then we invoke the Contact Review Procedure as described below.
2.5.2. Contact Review Procedure
1. First append node D to the list of Excluded Nodes, to prevent
routing loops. (We don't want to re-compute routes through D in
the course of computing routes for the intermediate nodes on any
path to D.)
2. Then, for each xmit m in node D's list of xmits (in descending
order of transmission stop time):
A. If either the current time or m's start time is after the
last moment T (a function of m) for deadline X, then skip
this xmit.
B. Otherwise:
Burleigh Expires January 9, 2011 [Page 11]
Internet-Draft CGR July 2010
1. If D is the final destination node:
A. Set projected delivery time on this path to m's stop
time.
2. If m's transmitting node S is the local node (that is, D
is a neighbor of the local node):
A. Compute the ECC of the bundle, assuming transmission
via the local node's outduct to D.
B. If m's residual capacity is less than the computed
ECC, then skip this xmit.
C. Otherwise, if D is already in the list of Proximate
Nodes to send this bundle to:
a. If the path's projected delivery time is less
than the projected delivery time currently noted
for D, change to the new projected delivery time.
b. If the path's projected delivery time is the same
as the one that's currently noted for D but its
network distance is less than the network
distance currently noted for D, change to the new
network distance.
D. Otherwise:
1. Add D to the list of Proximate Nodes.
2. Note the path's projected delivery time and
network distance in the event that the bundle is
queued for transmission to D.
3. Otherwise:
A. If S is already in the list of Excluded Nodes, then
skip this xmit.
B. Otherwise:
1. If m's stop time is less than the forfeit time
computed so far for this path:
A. Set the forfeit time to m's stop time.
Burleigh Expires January 9, 2011 [Page 12]
Internet-Draft CGR July 2010
2. Compute estimated forwarding latency L as twice
the size of the bundle, divided by the data
transmission rate for xmit m. (This value is
used to allow for the time needed by node S
simply to receive the bundle from its origin,
queue it for transmission, and re-radiate it.)
3. Invoke the Contact Review Procedure again,
recursively, but with destination variable D now
set to S, with network distance increased by 1,
and with deadline variable X set to either T or
the time that is L seconds before the stop time
of xmit m, whichever is earlier.
3. Finally, remove D from the list of Excluded Nodes and let the
forfeit time and network distance revert to their previous values
(unraveling the recursion stack).
2.5.3. Forwarding Decision
At this point, each member of the Proximate Nodes list is a
neighboring node to which we can forward the bundle in the
expectation that one of that node's planned contacts will enable
conveyance of the bundle on a plausible route toward its final
destination.
If the list of Proximate Nodes is empty, then CGR has been unable to
compute a route that can convey this bundle to its final destination
node prior to expiration of the bundle.
If the list of Proximate Nodes is non-empty:
1. If the bundle is Critical, then we now insert the bundle into the
appropriate outbound transmission queue (depending on priority)
for every Proximate Node in the list.
2. Otherwise (the bundle is non-critical, so we must select only a
single Proximate Node for transmission):
1. We insert the bundle into the appropriate outbound
transmission queue (depending on priority) of the Proximate
Node that is the receiving node for the first contact on the
"best" plausible route.
Selection of the "best" plausible route is a network configuration
matter. A variety of criteria might be considered:
Burleigh Expires January 9, 2011 [Page 13]
Internet-Draft CGR July 2010
o Nominally, we select the route starting with the Proximate Node
that has the earliest associated projected delivery time. In the
event of a tie among multiple Proximate Nodes, we select whichever
one of those nodes has the smallest associated network distance.
In the event that multiple Proximate Nodes are still tied for
"best", we arbitrarily choose the one with smallest node number,
just to assure consistency in route computation through the
network (e.g., to avoid routing loops).
o Routes that traverse specific nodes may have associated network-
specific cost functions. In this case, we might alternatively
judge the route that has the lowest associated net cost to be
best.
2.6. Exception Handling
Conveyance of a bundle from source to destination through a DTN-based
network can fail in a number of ways, many of which are best
addressed by means of reliability mechanisms such as BP's custodial
retransmission and LTP. Failures in Contact Graph Routing,
specifically, occur when the expectations on which routing decisions
are based prove to be false. These failures of information fall into
two general categories: contact failure and custody refusal.
Contact Failure: A scheduled contact between some node and its
neighbor on the end-to-end route may be initiated later than the
originally scheduled start time, or be terminated earlier than the
originally scheduled stop time, or be canceled altogether.
Alternatively, the available capacity for a contact might be
overestimated due to, for example, diminished link quality
resulting in unexpectedly heavy retransmission at the convergence
layer. In each of these cases, the anticipated transmission of a
given bundle during the affected contact may not occur as planned:
the bundle might expire before the contact's start time, or the
contact's stop time might be reached before the bundle has been
transmitted. For a non-Critical bundle, we may handle this sort
of failure by means of a timeout: if the bundle is not transmitted
prior to the forfeit time for the selected Proximate Node, then
the bundle MAY be removed from its outbound transmission queue and
the Dynamic Route Computation Algorithm re-applied to the bundle
so that an alternate route can be computed.
Contact Refusal: A node that receives a bundle may find it
impossible to forward it, for any of several reasons: it may not
have enough storage capacity to hold the bundle, it may be unable
to compute a forward route for the bundle, etc. Such bundles are
simply discarded, but discarding any such bundle that is marked
for custody transfer will cause a custody refusal signal to be
Burleigh Expires January 9, 2011 [Page 14]
Internet-Draft CGR July 2010
returned to the bundle's current custodian. When the affected
bundle is non-Critical, the node that receives the custody refusal
MAY re-apply the Dynamic Route Computation Algorithm to the bundle
so that an alternate route can be computed - except that in this
event the node from which the bundle was originally directly
received is omitted from the initial list of Excluded Nodes. This
enables a bundle that has reached a dead end in the routing tree
to be sent back to a point at which an altogether different branch
may be selected.
For a Critical bundle no mitigation of either sort of failure is
required or indeed possible: the bundle has already been queued for
transmission on all plausible routes, so no mechanism that entails
re-application of CGR's Dynamic Route Computation Algorithm could
improve its prospects for successful delivery to the final
destination. However, in some environments it MAY be advisable to
re-apply the Dynamic Route Computation Algorithm to all Critical
bundles that are still in local custody whenever a new Contact is
added to the contact graph: the new contact may open an additional
forwarding opportunity for one or more of those bundles.
3. Remarks
The CGR routing procedures respond dynamically and automatically to
the changes in network topology that the nodes are able know about,
i.e., those changes that are subject to managed network configuration
and are known in advance rather than discovered in real time. This
dynamic responsiveness in route computation should be significantly
more effective and less expensive than static routing.
Note that the non-Critical forwarding load across multiple parallel
paths should be balanced automatically:
o Initially all traffic will be forwarded to the node(s) on what is
computed to be the best path from source to destination.
o At some point, however, a node on that preferred path may have so
much outbound traffic queued up that no contacts scheduled within
bundles' lifetimes have any residual capacity. This can cause
forwarding to fail, resulting in custody refusal.
o Custody refusal causes the refusing node to be temporarily added
to the current custodian's excluded neighbors list for the
affected final destination node. If the refusing node is the only
one on the path to the destination, then the custodian may end up
sending the bundle back to its upstream neighbor. Moreover, that
custodian node too may begin refusing custody of bundles
Burleigh Expires January 9, 2011 [Page 15]
Internet-Draft CGR July 2010
subsequently sent to it, since it can no longer compute a
forwarding path.
o The upstream propagation of custody refusals directs bundles over
alternate paths that would otherwise be considered suboptimal,
balancing the queuing load across the parallel paths.
o Eventually, transmission and/or bundle expiration at the
oversubscribed node relieves queue pressure at that node and
enables acceptance of custody of a "probe" bundle from the
upstream node. This eventually returns the routing fabric to its
original configuration.
Note that there are no "routing tables" in Contact Graph Routing.
The best route for a bundle destined for a given node may routinely
be different from the best route for a different bundle destined for
the same node, depending on bundle priority, bundle expiration time,
and changes in the current lengths of transmission queues for
neighboring nodes; routes must be computed individually for each
bundle, from the BPA's current network connectivity model for the
bundle's destination node (the contact graph). Clearly this places a
premium on optimizing the implementation of the route computation
algorithm. The scalability of CGR to very large networks remains a
research topic.
4. IANA Considerations
This document has no IANA considerations.
5. Security Considerations
CGR in itself introduces no new security considerations. However,
the accuracy of CGR forwarding decisions depends heavily on the
validity of the contact plan information on which they are based;
attacks that would prevent the delivery of that information, corrupt
it, or introduce bogus information would degrade forwarding in a
network that relies on contact graph routing.
When a protocol for distributing contact plan information is
developed, it is likely to be an application-layer protocol that
utilizes underlying Bundle Protocol capabilities. It will be
important to apply Bundle Security Protocol measures to protect that
protocol:
o Payload Integrity Blocks will be required, to assure the
authenticity and validity of the distributed contact plan
Burleigh Expires January 9, 2011 [Page 16]
Internet-Draft CGR July 2010
information.
o Bundle Authentication Blocks will be required, to minimize the
effectiveness of denial-of-service attacks that might compromise
contact plan information delivery.
6. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC3986] Berners-Lee, T., Fielding, R., and L. Masinter, "Uniform
Resource Identifier (URI): Generic Syntax", STD 66,
RFC 3986, January 2005.
[RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol
Specification", RFC 5050, November 2007.
Author's Address
Scott Burleigh
Jet Propulsion Laboratory, California Institute of Technology
4800 Oak Grove Drive, m/s 301-490
Pasadena, CA 91109
USA
Phone: +1 818 393 3353
Email: Scott.C.Burleigh@jpl.nasa.gov
Burleigh Expires January 9, 2011 [Page 17]