Delay-Tolerant Networking Research Group E. Birrane Internet-Draft Johns Hopkins University Applied Physics Laboratory Intended status: Experimental October 01, 2013 Expires: April 04, 2014 Contact Graph Routing Extension Block draft-irtf-dtnrg-cgreb-00 Abstract This draft describes an extension block used to convey path information in networks using Contact Graph Routing (CGR). The CGR Extension Block (CGR-EB) captures the set of contacts comprising the message path calculated by a CGR agent prior to forwarding a message. 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 April 04, 2014. Copyright Notice Copyright (c) 2013 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 Simplified BSD License. Birrane Expires April 04, 2014 [Page 1] Internet-Draft CGR-EB October 2013 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1. Hybrid Source-Path Routing . . . . . . . . . . . . . 3 1.1.2. Graph Synchronization . . . . . . . . . . . . . . . . 3 1.1.3. Congestion Modeling . . . . . . . . . . . . . . . . . 4 1.2. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3. Requirements Language . . . . . . . . . . . . . . . . . . 4 2. CGR Extension Block Format . . . . . . . . . . . . . . . . . 4 3. CGR Block Processing . . . . . . . . . . . . . . . . . . . . 7 4. Processing Procedures . . . . . . . . . . . . . . . . . . . . 8 4.1. Block Validation . . . . . . . . . . . . . . . . . . . . 8 4.2. Local Graph Update . . . . . . . . . . . . . . . . . . . 9 5. Policy Considerations . . . . . . . . . . . . . . . . . . . . 10 5.1. Validation Threshold . . . . . . . . . . . . . . . . . . 11 5.2. Validation Lookahead . . . . . . . . . . . . . . . . . . 11 5.3. Block Replacement . . . . . . . . . . . . . . . . . . . . 11 5.4. Block Trimming . . . . . . . . . . . . . . . . . . . . . 12 5.5. Local Contact Replacement . . . . . . . . . . . . . . . . 12 5.6. ECC Modification . . . . . . . . . . . . . . . . . . . . 12 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 7. Security Considerations . . . . . . . . . . . . . . . . . . . 12 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 8.1. Normative References . . . . . . . . . . . . . . . . . . 13 8.2. Informative References . . . . . . . . . . . . . . . . . 13 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 13 1. Introduction This document describes an extension to the Delay-Tolerant Networking (DTN) Bundle Protocol (BP) [RFC5050] that marks bundles with routing information from an instance of the Contact Graph Routing [CGR] algorithm. This information establishes a both a nominal path calculated for this bundle through the DTN as well as a snapshot of the graph information available to the route-originating node at the time the bundle routing information was generated [Acta]. 1.1. Goals Bundle agents may use the information in this block in one of three ways: (1) to implement a source-path routing system in DTNs whose dynamicism would otherwise confuse opportunistic forwarding decisions, (2) to synchronize pieces of contact graph information across portions of a network, and (3) to infer congestion metrics across heavily used paths in a DTN. Birrane Expires April 04, 2014 [Page 2] Internet-Draft CGR-EB October 2013 1.1.1. Hybrid Source-Path Routing The standard CGR routing algorithm is a hop-by-hop forwarding algorithm which produces a set of plausible next-hops for a bundle in a DTN given a source and destination node. By only persisting the next hop, CGR must be re-run on a bundle at every hop in the network. This is advantageous behavior in networks whose topology changes faster than new contact graphs can be synchronized in the network. However, this is also expensive behavior as the CGR calculations are computationally intensive [PAPER REF], as they involve calculating multiple paths through the network to derive plausible next hops. Further, the opportunistic nature of CGR as a per-hop forwarding algorithm place restrictions on the types of cost functions that may be used to route bundles. Namely, since there is no mechanism for carrying path information with a bundle as it moves through the DTN, the cost function must provide some over-arching, out-of-band information to keep the distributed algorithm from falling into routing loops. Alternatively, source path routing refers to the practice of encoding the nominal message delivery path with the bundle. Since the path computation is atomic and not spread across multiple nodes in the network, any cost function may be selected by the network for message routing. The path, once discovered, will be followed even if the network topology changes at a later time, eliminating the danger of falling into a routing loop. Source-path routing, however, fails to capture the case when the original, nominal path is invalidated by the dynamics of the network, either because a link in the DTN has been lost, or is congested with other traffic. When this occurs, a hybrid mechanism is preferred: the nominal path is used whenever the nominal path is feasible. If, and only if, the nominal path is unfeasible is a new path generated. This new path replaces the old path and the bundle continues as before. 1.1.2. Graph Synchronization The hyrbid source-path approach requires that a downstream node not only be able to understand the nominal path, but to evaluate it in the context of its local contact graph. This requires that the path information not only identify the links comprising the path, but also critical characteristics and assumptions that held when the path was created. This information is required to determine whether the links still exist at the evaluating node and, if they do, that they still have the necessary characteristics (data rate, available capacity, end time, etc...). Birrane Expires April 04, 2014 [Page 3] Internet-Draft CGR-EB October 2013 This information is determined from the contact graph of the node that populated the extension block. Downstream nodes that inspect the extension block, beyond validation, may choose to use the information in the extension block to update their own, local contact graph if the link information in the extension block represents a more recent set of information about the state of the network. This provides the potential for a path-based synchronization mechanism. 1.1.3. Congestion Modeling Nominal paths represent the anticipated path of a bundle through the DTN. Since this path is only abandoned when it loses feasibility (as opposed to more simply losing optimality) the path is expected to be honored in all cases where the network remains relatively stable. This provides every node in the network with a set of anticipated hops, and associated times, for each bundle it sees. Together this information provides a lower bound estimate on future traffic going over downstream links. Each node may use this path information to inform the Estimated Capacity Consumption (ECC) of links in its own local contact graph. This significantly provides a congestion model that is both automatic and predicted, eliminating the need to perform congestion management as an out-of-band management function. 1.2. Scope 1.3. 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]. 2. CGR Extension Block Format The CGR block conforms to sections 4.5.2 and 4.6 of [RFC5050], contrained as follows: o Block type code is 0xED. o The following block processing control flag MUST be set to 1: * Bit 0 - block must be replicated in every fragment. The setting of other block processing control flags, where not mandated by the Bundle Protocol specification, is an implementation matter. Birrane Expires April 04, 2014 [Page 4] Internet-Draft CGR-EB October 2013 The extension block content is illustrated in Figure 1. CGR Extension Block Format +------+------+-----------+ +------------+ |Flags | ND | Contact 1 | | Contact ND | | | | Parms | ... | Parms | |(Byte)|(SDNV)| (var) | | (var) | +------+------+-----------+-----+------------+ Figure 1 Flags The CGR block flags identify the amount of contact parameter information available for each of the following contact parameters. The format of the byte is as follows. +------+-------+----------+ | Res. | Time- | Reserved | | Cap. | Stamp | | +------+-------+----------+ Bit: 0 1 2 - 7 Res. Cap. Whether the residual capacity associated with each contact is provided (1) or not (0). Timestamp Whether the last update timestamp associated with each contact is provided (1) or not (0). ND The network distance of the encoded path. This specifies the number of contacts remaining in the block. Contact The information about the nth contact. Contacts are listed in order from close-to-source to close-to-destination. Contact parameters contain the information necessary to determine if the contact exists in the same manner at the local node and, if not, to update the contact in the local contact graph. The parameters are illustrated in Figure 2. Contact Parameters Birrane Expires April 04, 2014 [Page 5] Internet-Draft CGR-EB October 2013 +-------+------+------+------+------+------+ | Start | End | *Res.| Data | Rx | *Def.| | Time | Time | Cap. | Rate | Node | Time | |(SDNV) |(SDNV)|(SDNV)|(SDNV)|(EID) |(SDNV)| +-------+------+------+------+------+------+ Figure 2 Start Time The UTC time of when the contact will be available, encoded in an SDNV. End Time The UTC time of when the contact will stop being available, encoded in an SDNV. (Optional) Residual Capacity The estimated capacity of the link, without accounting for the bundle traveling over the link. This is measured in bytes. The current bundle is not factored into this value, as the contact may update the local contact graph as part of graph synchronization but still not use the contact if an alternate path is calculated as part of the hybrid path verification algorithm. Data Rate The data rate associated with this contact, measured in bps and encoded in an SDNV. RX Node The EID of the DTN node receiving transmission over this contact. The transmitting node is inferred based on the position of the contact parms in the block: the transmitting node for contact N is the receiving node for contact (N-1). (Optional) Definition Time The UTC time when the contact was authoritatively defined by the node populating this extension block. This value is used to determine whether the information associated with a particular contact in the extension block is more or less recent than the information on the same contact in the node local contact graph. Birrane Expires April 04, 2014 [Page 6] Internet-Draft CGR-EB October 2013 3. CGR Block Processing The steps taken by a bundle agent when handling the CGR Extension Block, is illustrated in Figure 3. Extension Block Lifecycle +----------+ +---------+ +-->| Block |------------------------->| Block | | | Received | | Created | | +----+-----+ +----+----+ | | | | | | | | | | v v | +-----------+ +-----------+ +---------+ | | Block |----->| Block |----->| Block | | | Validated | | Optimized | | Sent | | +-----------+ +-----------+ +----+----+ | | +----------------------------------------------+ Figure 3 Block Created A Bundle Protocol Agent will create a CGR-EB and insert it into a bundle in one of two circumstances: based on policy when a bundle is sources at the agent, or based on policy when a received bundle fails to validate an existing CGR-EB. When creating a new block, the path is always specified as from the current node onward to the bundle destination. Block Received Upon receiving a bundle with a CGR-EB, a BPA must validate the contents of the block to ensure that the contacts encoded within remain feasible. Before the block may move to the "validated" state, it must survive the block validation procedure. If the block fails to validate, then it must be discarded and a new block created from the local node onward. The validation procedure may validate all contacts along the specified path, or smaller number of contacts looking into the future. Block Validated When the block has been validated, it indicates that at least the next N hops have been validated, based on the look-ahead Birrane Expires April 04, 2014 [Page 7] Internet-Draft CGR-EB October 2013 associated with the validation procedure. All contacts in the block that represent the portion of the path prior to the current BPA are assumed correct since they always represent the path taken to the current BPA. Based on the validated contacts, the local graph may be updated using the Local Graph Update procedure. Block Optimized Once the path in the block has been validated, a local optimization may be made to determine whether there is a faster way to get to the next hop. Since this optimization only considers ways to get to the next hop in the path, this does not risk falling into a routing loop. Block Sent The local BPA may add the CGR-EB to any outgoing bundle in accordance will associated processing flags. There is no requirement for positioning of the block within the bundle. The only constraint on the bundle is that only a single CGR- EB may exist in a bundle at any time. 4. Processing Procedures This section identifies the pseudo-code associated with the core processing procedures. 4.1. Block Validation The validate block procedure examines a subset of contacts in the block, looks up their associated information from the local contact graph, and matches them within some tolerance. There is no need to check contacts that were traversed prior to reaching the current BPA. The core variables and functions that comprise this procedure as listed as follows. LOOKAHEAD The policy associated with a BPA may choose to evaluate only the next hop in the path, the entire path, or some number of hops in-between. C[i] The variable C[i] represents the ith set of contact parameters encoded in the block. FIND_CONTACT Birrane Expires April 04, 2014 [Page 8] Internet-Draft CGR-EB October 2013 The BPA must specify a look-up function that accepts a set of contact parameters from a block and must produce the contact in the local contact graph that matches these parameters, within some specified tolerance. The pseudo-code listing is as follows. PROC VALIDATE_BLOCK() MAX = MIN[ND,LOOKAHEAD] MIN = Index of contact terminating in local node FOR I = MIN..MAX IF I > 0 THEN CUR_TX = C[I-1].rxNode ELSE CUR_TX = Previous hop for this bundle. END IF LC = FIND_CONTACT(C[I].start, C[I].end, CUR_TX, C[I].rxNode) IF LC = NIL RETURN FALSE END IF IF LC does not have capacity for the bundle RETURN FALSE END IF END FOR RETURN TRUE END PROC 4.2. Local Graph Update The local graph update procedure examines those validated contacts in the extension block and compares them to the contents of the local contact graph. Two levels of update are performed by this function: (1) newer contacts parameters from the block update contacts in the graph and (2) the estimated capacity associated with transmitting the bundle is propagated through the local contact graph. The key functions and variables used by this procedure are as follows: Birrane Expires April 04, 2014 [Page 9] Internet-Draft CGR-EB October 2013 NC The number of contacts from the extension block, starting with the first in the block, that have been validated. Note that all contacts in the block representing hops prior to the current node are considered valid. B The bundle being sent. MAX The number of contacts inthe extension block. COPY_PARAMS This helper function copies contact parameters from the extension block into the local contact. UPDATE_ECC This helper function reduces the contact's estimated capacity consumption value by the anticipated capacity necessary to transmit the bundle. This function is optional to implement and may simply return an unupdated ECC value. The pseudo-code listing is as follows. PROC UPDATE_LOCAL_GRAPH(NC, B) FOR I = 0..MAX IF I > 0 THEN CUR_TX = C[I-1].rxNode ELSE CUR_TX = Previous hop for this bundle. END IF LC = FIND_CONTACT(C[I].start, C[I].end, CUR_TX, C[I].rxNode) IF I <= NC THEN IF LC.Timestamp < C[I].Timestamp THEN COPY_PARAMS(LC, C[I]) END IF END IF UPDATE_ECC(LC, B) END FOR END PROC 5. Policy Considerations This section identifies policy decisions available to BPAs processing CGR blocks and provides non-normative guidance on the impact of these decisions. Birrane Expires April 04, 2014 [Page 10] Internet-Draft CGR-EB October 2013 5.1. Validation Threshold When attempting to match contact parameters in the CGR block with a contact in the local contact graph there may be minor differences between the paramater values. Differences in transmit and receive node should not be tolerated, but minor differences in start and end times and residual capacites may not be significant enough to claim that a contact match was not made. The definition of matching thresholds, and how they are applied when matching contacts is an implementation matter left to a particular implementing bundle agent. However, some thresholds shoudl be set for start times, end times, and residual capacity. 5.2. Validation Lookahead The block validation procedure has the option of validating every future contact encoded in the block path or looking at some subset of future contacts. Validating the entire encoded path has the benefit of learning, very early, whether or not a problem exists with routing the bundle as originally planned at the bundle source. This is desirable is relatively stable network topologies where even far-down-stream path problems can be worked through by the local node's CGR algorithm. For example, stable networks that evaluate a path based on congestion forcasting may prefer vlaidating the entire remaining bundle path at each hop in the network. Validating only the immediate next hop, or some subset of hops, will only ensure that the bundle can achieve incremental progress along its path. This is desirable behavior in networks where local nodes have more current information relating to their immediate N-hop neighbors, where N is the coded lookahead value. In this configuration problems with the bundle path are dealt with when they present an immediate routing problem under the assumption that the nodes closest to the path problem will have th emost up-to-date information on how to best route around the problem. 5.3. Block Replacement When a CGR block fails to validate, the local BPA must make the decision to either abandon path encoding altogether or generate a new block. It is recommended that the block be replaced in networks whose routing cost functions are otherwise prone to routing loops. However, networks that have periods of high topological change may wish to abandon path routing until such time as the network stabilizes. The detection of topological change and related stabilization are implementation matters of the network. Birrane Expires April 04, 2014 [Page 11] Internet-Draft CGR-EB October 2013 5.4. Block Trimming The validated CGR block may be sent to the next hop intact, or trimmed. The value of sending the CGR block intact to the next hop is that the previously-used contacts may be used to inform the local graph update procedure for downstream nodes. However, if the local contact graph update procedure is not to be used in the network, or only used for to-be-traversed contacts, then the block size may be reduced by trimming old contacts. There is no change to the CGR block format when choosing to trim contacts, as long as the remaining network diamater variable is updated to reflect the new contact value. 5.5. Local Contact Replacement Local BPAs must decide whether to use the information in the CGR block to update contacts in the local contact graph. This requires the ability to timestamp contacts in the block and in the local contact graph. If the timestamp and residual capacity fields of the contacts are not included in the block there is no additional information outside of contact definition to update in the local graph. 5.6. ECC Modification The decision to update the local contact graph with the ECC associated with the path of the bundle should reflect the confidence that the bundle will actually follow the prescribed path. Much like the lookahead decision when validating paths, network characteristics must be considered when applying this update. Very stable topologies may wish to update ECCs in the local contact graph for the entire path. More dynamic topologies may wish to only update the ECC for the next N hops. 6. IANA Considerations This memo includes no request to IANA. 7. Security Considerations Transport security is handled by the transport layer, for example the Bundle Security Protocol [RFC6257] when using the Bundle Protocol [RFC5050]. 8. References Birrane Expires April 04, 2014 [Page 12] Internet-Draft CGR-EB October 2013 8.1. Normative References [CGR] Burleigh, S., "Contact Graph Routing ", draft-burleigh- dtnrg-cgr-01, July 2010. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol Specification", RFC 5050, November 2007. [RFC6257] Symington, S., Farrell, S., Weiss, H., and P. Lovell, "Bundle Security Protocol Specification", RFC 6257, May 2011. 8.2. Informative References [Acta] Birrane, E., Burleigh, S., and N. Kasch, "Analysis of the contact graph routing algorithm: Bounding interplanetary paths ", Acta Astronautica, Volume 75, Pages 108-119, ISSN 0094-5765, June-July 2012. [IJAHUC] Birrane, E., "Building Routing Overlays in Disrupted Networks: Inferring Contacts in Challenged Sensor Internetworks ", International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC) Special Issue on Algorithms and Protocols for Opportunistic and Delay Tolerant Networks, Volume 11, No. 2/3, Pages 139-156, 2012. [WD] Birrane, E., "Improving Graph-Based Overlay Routing in Delay Tolerant Networks. ", IFIP Wireless Days (WD 2011), October 2011. Author's Address Edward J. Birrane Johns Hopkins University Applied Physics Laboratory 11100 Johns Hopkins Road Laurel , Maryland 20723 USA Phone: +1 410 778 7423 Email: Edward.Birrane@jhuapl.edu Birrane Expires April 04, 2014 [Page 13]