Network Working Group S. Burleigh Internet-Draft Jet Propulsion Laboratory, Intended status: Experimental California Institute of Expires: July 4, 2010 Technology December 31, 2009 Contact Graph Routing draft-burleigh-dtnrg-cgr-00 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 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 July 4, 2010. Copyright Notice Burleigh Expires July 4, 2010 [Page 1] Internet-Draft CGR December 2009 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 (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 . . . . . . . . . . . . . . . . . . . . . . . . . 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. Excluded Neighbors . . . . . . . . . . . . . . . . . . 10 2.4.12. 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 July 4, 2010 [Page 2] Internet-Draft CGR December 2009 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 July 4, 2010 [Page 3] Internet-Draft CGR December 2009 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 July 4, 2010 [Page 4] Internet-Draft CGR December 2009 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 July 4, 2010 [Page 5] Internet-Draft CGR December 2009 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 July 4, 2010 [Page 6] Internet-Draft CGR December 2009 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 start 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 July 4, 2010 [Page 7] Internet-Draft CGR December 2009 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 July 4, 2010 [Page 8] Internet-Draft CGR December 2009 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 July 4, 2010 [Page 9] Internet-Draft CGR December 2009 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. 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.12. 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 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 Burleigh Expires July 4, 2010 [Page 10] Internet-Draft CGR December 2009 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 best-case delivery time 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 ascending order of transmission start time): A. If m's start time is after the last moment T for deadline X, then skip this xmit. B. Otherwise: 1. 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. Burleigh Expires July 4, 2010 [Page 11] Internet-Draft CGR December 2009 C. Otherwise, if D is already in the list of Proximate Nodes to send this bundle to, then skip this xmit. D. 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. 2. If m's start time is greater than the best-case delivery time computed so far on this path: A. Set the best-case delivery time to m's start time. 3. Add D to the list of Proximate Nodes. 4. Note the computed forfeit time and best-case delivery time in the event that the bundle is queued for transmission to D. 2. 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. 2. If m's start time is greater than the best-case delivery time computed so far on this path: A. Set the best-case delivery time to m's start time. 3. 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.) Burleigh Expires July 4, 2010 [Page 12] Internet-Draft CGR December 2009 4. Invoke the Contact Review Procedure again, recursively, but with destination variable D now set to S 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 best-case delivery times 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: o For communications through Earth-orbiting satellites, the "best" route may be the one that minimizes bundle delivery latency (much as in Internet routing). For this purpose we might judge the route that has the earliest best-case delivery time to be best. o For deep space mission communications, the waste of expensive communication opportunities may be judged a higher cost than a few minutes or hours of delay in delivery of a bundle to the final destination, so long as the bundle arrives before expiration of Burleigh Expires July 4, 2010 [Page 13] Internet-Draft CGR December 2009 its TTL. In this case we might judge the route that has the earliest associated forfeit time to be best, to maximize contact utilization. o Routes that traverse specific nodes may have associated network- specific cost functions. In this case, we might 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 is 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 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 Burleigh Expires July 4, 2010 [Page 14] Internet-Draft CGR December 2009 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 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. Burleigh Expires July 4, 2010 [Page 15] Internet-Draft CGR December 2009 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 information. o Bundle Authentication Blocks will be required, to minimize the effectiveness of denial-of-service attacks that might compromise contact plan information delivery. Burleigh Expires July 4, 2010 [Page 16] Internet-Draft CGR December 2009 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 July 4, 2010 [Page 17]