idnits 2.17.00 (12 Aug 2021) /tmp/idnits46695/draft-irtf-dtnrg-cgreb-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 01, 2013) is 3147 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'PAPER REF' is mentioned on line 106, but not defined == Missing Reference: 'ND' is mentioned on line 379, but not defined == Missing Reference: 'LOOKAHEAD' is mentioned on line 379, but not defined == Missing Reference: 'I-1' is mentioned on line 441, but not defined == Missing Reference: 'I' is mentioned on line 450, but not defined == Unused Reference: 'IJAHUC' is defined on line 581, but no explicit reference was found in the text == Unused Reference: 'WD' is defined on line 588, but no explicit reference was found in the text Summary: 0 errors (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Delay-Tolerant Networking Research Group E. Birrane 3 Internet-Draft Johns Hopkins University Applied Physics Laboratory 4 Intended status: Experimental October 01, 2013 5 Expires: April 04, 2014 7 Contact Graph Routing Extension Block 8 draft-irtf-dtnrg-cgreb-00 10 Abstract 12 This draft describes an extension block used to convey path 13 information in networks using Contact Graph Routing (CGR). The CGR 14 Extension Block (CGR-EB) captures the set of contacts comprising the 15 message path calculated by a CGR agent prior to forwarding a message. 17 Status of This Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at http://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on April 04, 2014. 34 Copyright Notice 36 Copyright (c) 2013 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 52 1.1. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 2 53 1.1.1. Hybrid Source-Path Routing . . . . . . . . . . . . . 3 54 1.1.2. Graph Synchronization . . . . . . . . . . . . . . . . 3 55 1.1.3. Congestion Modeling . . . . . . . . . . . . . . . . . 4 56 1.2. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 4 57 1.3. Requirements Language . . . . . . . . . . . . . . . . . . 4 58 2. CGR Extension Block Format . . . . . . . . . . . . . . . . . 4 59 3. CGR Block Processing . . . . . . . . . . . . . . . . . . . . 7 60 4. Processing Procedures . . . . . . . . . . . . . . . . . . . . 8 61 4.1. Block Validation . . . . . . . . . . . . . . . . . . . . 8 62 4.2. Local Graph Update . . . . . . . . . . . . . . . . . . . 9 63 5. Policy Considerations . . . . . . . . . . . . . . . . . . . . 10 64 5.1. Validation Threshold . . . . . . . . . . . . . . . . . . 11 65 5.2. Validation Lookahead . . . . . . . . . . . . . . . . . . 11 66 5.3. Block Replacement . . . . . . . . . . . . . . . . . . . . 11 67 5.4. Block Trimming . . . . . . . . . . . . . . . . . . . . . 12 68 5.5. Local Contact Replacement . . . . . . . . . . . . . . . . 12 69 5.6. ECC Modification . . . . . . . . . . . . . . . . . . . . 12 70 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12 71 7. Security Considerations . . . . . . . . . . . . . . . . . . . 12 72 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 73 8.1. Normative References . . . . . . . . . . . . . . . . . . 13 74 8.2. Informative References . . . . . . . . . . . . . . . . . 13 75 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 13 77 1. Introduction 79 This document describes an extension to the Delay-Tolerant Networking 80 (DTN) Bundle Protocol (BP) [RFC5050] that marks bundles with routing 81 information from an instance of the Contact Graph Routing [CGR] 82 algorithm. This information establishes a both a nominal path 83 calculated for this bundle through the DTN as well as a snapshot of 84 the graph information available to the route-originating node at the 85 time the bundle routing information was generated [Acta]. 87 1.1. Goals 89 Bundle agents may use the information in this block in one of three 90 ways: (1) to implement a source-path routing system in DTNs whose 91 dynamicism would otherwise confuse opportunistic forwarding 92 decisions, (2) to synchronize pieces of contact graph information 93 across portions of a network, and (3) to infer congestion metrics 94 across heavily used paths in a DTN. 96 1.1.1. Hybrid Source-Path Routing 98 The standard CGR routing algorithm is a hop-by-hop forwarding 99 algorithm which produces a set of plausible next-hops for a bundle in 100 a DTN given a source and destination node. By only persisting the 101 next hop, CGR must be re-run on a bundle at every hop in the network. 102 This is advantageous behavior in networks whose topology changes 103 faster than new contact graphs can be synchronized in the network. 105 However, this is also expensive behavior as the CGR calculations are 106 computationally intensive [PAPER REF], as they involve calculating 107 multiple paths through the network to derive plausible next hops. 108 Further, the opportunistic nature of CGR as a per-hop forwarding 109 algorithm place restrictions on the types of cost functions that may 110 be used to route bundles. Namely, since there is no mechanism for 111 carrying path information with a bundle as it moves through the DTN, 112 the cost function must provide some over-arching, out-of-band 113 information to keep the distributed algorithm from falling into 114 routing loops. 116 Alternatively, source path routing refers to the practice of encoding 117 the nominal message delivery path with the bundle. Since the path 118 computation is atomic and not spread across multiple nodes in the 119 network, any cost function may be selected by the network for message 120 routing. The path, once discovered, will be followed even if the 121 network topology changes at a later time, eliminating the danger of 122 falling into a routing loop. 124 Source-path routing, however, fails to capture the case when the 125 original, nominal path is invalidated by the dynamics of the network, 126 either because a link in the DTN has been lost, or is congested with 127 other traffic. When this occurs, a hybrid mechanism is preferred: 128 the nominal path is used whenever the nominal path is feasible. If, 129 and only if, the nominal path is unfeasible is a new path generated. 130 This new path replaces the old path and the bundle continues as 131 before. 133 1.1.2. Graph Synchronization 135 The hyrbid source-path approach requires that a downstream node not 136 only be able to understand the nominal path, but to evaluate it in 137 the context of its local contact graph. This requires that the path 138 information not only identify the links comprising the path, but also 139 critical characteristics and assumptions that held when the path was 140 created. This information is required to determine whether the links 141 still exist at the evaluating node and, if they do, that they still 142 have the necessary characteristics (data rate, available capacity, 143 end time, etc...). 145 This information is determined from the contact graph of the node 146 that populated the extension block. Downstream nodes that inspect 147 the extension block, beyond validation, may choose to use the 148 information in the extension block to update their own, local contact 149 graph if the link information in the extension block represents a 150 more recent set of information about the state of the network. This 151 provides the potential for a path-based synchronization mechanism. 153 1.1.3. Congestion Modeling 155 Nominal paths represent the anticipated path of a bundle through the 156 DTN. Since this path is only abandoned when it loses feasibility (as 157 opposed to more simply losing optimality) the path is expected to be 158 honored in all cases where the network remains relatively stable. 159 This provides every node in the network with a set of anticipated 160 hops, and associated times, for each bundle it sees. Together this 161 information provides a lower bound estimate on future traffic going 162 over downstream links. 164 Each node may use this path information to inform the Estimated 165 Capacity Consumption (ECC) of links in its own local contact graph. 166 This significantly provides a congestion model that is both automatic 167 and predicted, eliminating the need to perform congestion management 168 as an out-of-band management function. 170 1.2. Scope 172 1.3. Requirements Language 174 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 175 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 176 document are to be interpreted as described in RFC 2119 [RFC2119]. 178 2. CGR Extension Block Format 180 The CGR block conforms to sections 4.5.2 and 4.6 of [RFC5050], 181 contrained as follows: 183 o Block type code is 0xED. 185 o The following block processing control flag MUST be set to 1: 187 * Bit 0 - block must be replicated in every fragment. 189 The setting of other block processing control flags, where not 190 mandated by the Bundle Protocol specification, is an 191 implementation matter. 193 The extension block content is illustrated in Figure 1. 195 CGR Extension Block Format 197 +------+------+-----------+ +------------+ 198 |Flags | ND | Contact 1 | | Contact ND | 199 | | | Parms | ... | Parms | 200 |(Byte)|(SDNV)| (var) | | (var) | 201 +------+------+-----------+-----+------------+ 203 Figure 1 205 Flags 206 The CGR block flags identify the amount of contact parameter 207 information available for each of the following contact 208 parameters. The format of the byte is as follows. 210 +------+-------+----------+ 211 | Res. | Time- | Reserved | 212 | Cap. | Stamp | | 213 +------+-------+----------+ 214 Bit: 0 1 2 - 7 216 Res. Cap. Whether the residual capacity associated with each 217 contact is provided (1) or not (0). 219 Timestamp Whether the last update timestamp associated with 220 each contact is provided (1) or not (0). 222 ND 223 The network distance of the encoded path. This specifies the 224 number of contacts remaining in the block. 226 Contact The information about the nth contact. Contacts are listed 227 in order from close-to-source to close-to-destination. 229 Contact parameters contain the information necessary to determine if 230 the contact exists in the same manner at the local node and, if not, 231 to update the contact in the local contact graph. The parameters are 232 illustrated in Figure 2. 234 Contact Parameters 236 +-------+------+------+------+------+------+ 237 | Start | End | *Res.| Data | Rx | *Def.| 238 | Time | Time | Cap. | Rate | Node | Time | 239 |(SDNV) |(SDNV)|(SDNV)|(SDNV)|(EID) |(SDNV)| 240 +-------+------+------+------+------+------+ 242 Figure 2 244 Start Time 245 The UTC time of when the contact will be available, encoded 246 in an SDNV. 248 End Time 249 The UTC time of when the contact will stop being available, 250 encoded in an SDNV. 252 (Optional) Residual Capacity 253 The estimated capacity of the link, without accounting for 254 the bundle traveling over the link. This is measured in 255 bytes. The current bundle is not factored into this value, 256 as the contact may update the local contact graph as part of 257 graph synchronization but still not use the contact if an 258 alternate path is calculated as part of the hybrid path 259 verification algorithm. 261 Data Rate 262 The data rate associated with this contact, measured in bps 263 and encoded in an SDNV. 265 RX Node 266 The EID of the DTN node receiving transmission over this 267 contact. The transmitting node is inferred based on the 268 position of the contact parms in the block: the transmitting 269 node for contact N is the receiving node for contact (N-1). 271 (Optional) Definition Time 272 The UTC time when the contact was authoritatively defined by 273 the node populating this extension block. This value is used 274 to determine whether the information associated with a 275 particular contact in the extension block is more or less 276 recent than the information on the same contact in the node 277 local contact graph. 279 3. CGR Block Processing 281 The steps taken by a bundle agent when handling the CGR Extension 282 Block, is illustrated in Figure 3. 284 Extension Block Lifecycle 286 +----------+ +---------+ 287 +-->| Block |------------------------->| Block | 288 | | Received | | Created | 289 | +----+-----+ +----+----+ 290 | | | 291 | | | 292 | | | 293 | v v 294 | +-----------+ +-----------+ +---------+ 295 | | Block |----->| Block |----->| Block | 296 | | Validated | | Optimized | | Sent | 297 | +-----------+ +-----------+ +----+----+ 298 | | 299 +----------------------------------------------+ 301 Figure 3 303 Block Created 304 A Bundle Protocol Agent will create a CGR-EB and insert it 305 into a bundle in one of two circumstances: based on policy 306 when a bundle is sources at the agent, or based on policy 307 when a received bundle fails to validate an existing CGR-EB. 308 When creating a new block, the path is always specified as 309 from the current node onward to the bundle destination. 311 Block Received 312 Upon receiving a bundle with a CGR-EB, a BPA must validate 313 the contents of the block to ensure that the contacts encoded 314 within remain feasible. Before the block may move to the 315 "validated" state, it must survive the block validation 316 procedure. If the block fails to validate, then it must be 317 discarded and a new block created from the local node onward. 318 The validation procedure may validate all contacts along the 319 specified path, or smaller number of contacts looking into 320 the future. 322 Block Validated 323 When the block has been validated, it indicates that at least 324 the next N hops have been validated, based on the look-ahead 325 associated with the validation procedure. All contacts in 326 the block that represent the portion of the path prior to the 327 current BPA are assumed correct since they always represent 328 the path taken to the current BPA. Based on the validated 329 contacts, the local graph may be updated using the Local 330 Graph Update procedure. 332 Block Optimized 333 Once the path in the block has been validated, a local 334 optimization may be made to determine whether there is a 335 faster way to get to the next hop. Since this optimization 336 only considers ways to get to the next hop in the path, this 337 does not risk falling into a routing loop. 339 Block Sent 340 The local BPA may add the CGR-EB to any outgoing bundle in 341 accordance will associated processing flags. There is no 342 requirement for positioning of the block within the bundle. 343 The only constraint on the bundle is that only a single CGR- 344 EB may exist in a bundle at any time. 346 4. Processing Procedures 348 This section identifies the pseudo-code associated with the core 349 processing procedures. 351 4.1. Block Validation 353 The validate block procedure examines a subset of contacts in the 354 block, looks up their associated information from the local contact 355 graph, and matches them within some tolerance. There is no need to 356 check contacts that were traversed prior to reaching the current BPA. 357 The core variables and functions that comprise this procedure as 358 listed as follows. 360 LOOKAHEAD 361 The policy associated with a BPA may choose to evaluate only 362 the next hop in the path, the entire path, or some number of 363 hops in-between. 365 C[i] 366 The variable C[i] represents the ith set of contact 367 parameters encoded in the block. 369 FIND_CONTACT 370 The BPA must specify a look-up function that accepts a set of 371 contact parameters from a block and must produce the contact 372 in the local contact graph that matches these parameters, 373 within some specified tolerance. 375 The pseudo-code listing is as follows. 377 PROC VALIDATE_BLOCK() 379 MAX = MIN[ND,LOOKAHEAD] 380 MIN = Index of contact terminating in local node 382 FOR I = MIN..MAX 384 IF I > 0 THEN 385 CUR_TX = C[I-1].rxNode 386 ELSE 387 CUR_TX = Previous hop for this bundle. 388 END IF 390 LC = FIND_CONTACT(C[I].start, C[I].end, CUR_TX, C[I].rxNode) 392 IF LC = NIL 393 RETURN FALSE 394 END IF 396 IF LC does not have capacity for the bundle 397 RETURN FALSE 398 END IF 400 END FOR 402 RETURN TRUE 403 END PROC 405 4.2. Local Graph Update 407 The local graph update procedure examines those validated contacts in 408 the extension block and compares them to the contents of the local 409 contact graph. Two levels of update are performed by this function: 410 (1) newer contacts parameters from the block update contacts in the 411 graph and (2) the estimated capacity associated with transmitting the 412 bundle is propagated through the local contact graph. 414 The key functions and variables used by this procedure are as 415 follows: 417 NC The number of contacts from the extension block, starting 418 with the first in the block, that have been validated. Note 419 that all contacts in the block representing hops prior to the 420 current node are considered valid. 422 B The bundle being sent. 424 MAX The number of contacts inthe extension block. 426 COPY_PARAMS This helper function copies contact parameters from the 427 extension block into the local contact. 429 UPDATE_ECC This helper function reduces the contact's estimated 430 capacity consumption value by the anticipated capacity 431 necessary to transmit the bundle. This function is optional 432 to implement and may simply return an unupdated ECC value. 434 The pseudo-code listing is as follows. 436 PROC UPDATE_LOCAL_GRAPH(NC, B) 438 FOR I = 0..MAX 440 IF I > 0 THEN 441 CUR_TX = C[I-1].rxNode 442 ELSE 443 CUR_TX = Previous hop for this bundle. 444 END IF 446 LC = FIND_CONTACT(C[I].start, C[I].end, CUR_TX, C[I].rxNode) 448 IF I <= NC THEN 449 IF LC.Timestamp < C[I].Timestamp THEN 450 COPY_PARAMS(LC, C[I]) 451 END IF 452 END IF 454 UPDATE_ECC(LC, B) 455 END FOR 456 END PROC 458 5. Policy Considerations 460 This section identifies policy decisions available to BPAs processing 461 CGR blocks and provides non-normative guidance on the impact of these 462 decisions. 464 5.1. Validation Threshold 466 When attempting to match contact parameters in the CGR block with a 467 contact in the local contact graph there may be minor differences 468 between the paramater values. Differences in transmit and receive 469 node should not be tolerated, but minor differences in start and end 470 times and residual capacites may not be significant enough to claim 471 that a contact match was not made. The definition of matching 472 thresholds, and how they are applied when matching contacts is an 473 implementation matter left to a particular implementing bundle agent. 474 However, some thresholds shoudl be set for start times, end times, 475 and residual capacity. 477 5.2. Validation Lookahead 479 The block validation procedure has the option of validating every 480 future contact encoded in the block path or looking at some subset of 481 future contacts. 483 Validating the entire encoded path has the benefit of learning, very 484 early, whether or not a problem exists with routing the bundle as 485 originally planned at the bundle source. This is desirable is 486 relatively stable network topologies where even far-down-stream path 487 problems can be worked through by the local node's CGR algorithm. 488 For example, stable networks that evaluate a path based on congestion 489 forcasting may prefer vlaidating the entire remaining bundle path at 490 each hop in the network. 492 Validating only the immediate next hop, or some subset of hops, will 493 only ensure that the bundle can achieve incremental progress along 494 its path. This is desirable behavior in networks where local nodes 495 have more current information relating to their immediate N-hop 496 neighbors, where N is the coded lookahead value. In this 497 configuration problems with the bundle path are dealt with when they 498 present an immediate routing problem under the assumption that the 499 nodes closest to the path problem will have th emost up-to-date 500 information on how to best route around the problem. 502 5.3. Block Replacement 504 When a CGR block fails to validate, the local BPA must make the 505 decision to either abandon path encoding altogether or generate a new 506 block. It is recommended that the block be replaced in networks 507 whose routing cost functions are otherwise prone to routing loops. 508 However, networks that have periods of high topological change may 509 wish to abandon path routing until such time as the network 510 stabilizes. The detection of topological change and related 511 stabilization are implementation matters of the network. 513 5.4. Block Trimming 515 The validated CGR block may be sent to the next hop intact, or 516 trimmed. The value of sending the CGR block intact to the next hop 517 is that the previously-used contacts may be used to inform the local 518 graph update procedure for downstream nodes. However, if the local 519 contact graph update procedure is not to be used in the network, or 520 only used for to-be-traversed contacts, then the block size may be 521 reduced by trimming old contacts. 523 There is no change to the CGR block format when choosing to trim 524 contacts, as long as the remaining network diamater variable is 525 updated to reflect the new contact value. 527 5.5. Local Contact Replacement 529 Local BPAs must decide whether to use the information in the CGR 530 block to update contacts in the local contact graph. This requires 531 the ability to timestamp contacts in the block and in the local 532 contact graph. If the timestamp and residual capacity fields of the 533 contacts are not included in the block there is no additional 534 information outside of contact definition to update in the local 535 graph. 537 5.6. ECC Modification 539 The decision to update the local contact graph with the ECC 540 associated with the path of the bundle should reflect the confidence 541 that the bundle will actually follow the prescribed path. Much like 542 the lookahead decision when validating paths, network characteristics 543 must be considered when applying this update. Very stable topologies 544 may wish to update ECCs in the local contact graph for the entire 545 path. More dynamic topologies may wish to only update the ECC for 546 the next N hops. 548 6. IANA Considerations 550 This memo includes no request to IANA. 552 7. Security Considerations 554 Transport security is handled by the transport layer, for example the 555 Bundle Security Protocol [RFC6257] when using the Bundle Protocol 556 [RFC5050]. 558 8. References 559 8.1. Normative References 561 [CGR] Burleigh, S., "Contact Graph Routing ", draft-burleigh- 562 dtnrg-cgr-01, July 2010. 564 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 565 Requirement Levels", BCP 14, RFC 2119, March 1997. 567 [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol 568 Specification", RFC 5050, November 2007. 570 [RFC6257] Symington, S., Farrell, S., Weiss, H., and P. Lovell, 571 "Bundle Security Protocol Specification", RFC 6257, May 572 2011. 574 8.2. Informative References 576 [Acta] Birrane, E., Burleigh, S., and N. Kasch, "Analysis of the 577 contact graph routing algorithm: Bounding interplanetary 578 paths ", Acta Astronautica, Volume 75, Pages 108-119, ISSN 579 0094-5765, June-July 2012. 581 [IJAHUC] Birrane, E., "Building Routing Overlays in Disrupted 582 Networks: Inferring Contacts in Challenged Sensor 583 Internetworks ", International Journal of Ad Hoc and 584 Ubiquitous Computing (IJAHUC) Special Issue on Algorithms 585 and Protocols for Opportunistic and Delay Tolerant 586 Networks, Volume 11, No. 2/3, Pages 139-156, 2012. 588 [WD] Birrane, E., "Improving Graph-Based Overlay Routing in 589 Delay Tolerant Networks. ", IFIP Wireless Days (WD 2011), 590 October 2011. 592 Author's Address 594 Edward J. Birrane 595 Johns Hopkins University Applied Physics Laboratory 596 11100 Johns Hopkins Road 597 Laurel , Maryland 20723 598 USA 600 Phone: +1 410 778 7423 601 Email: Edward.Birrane@jhuapl.edu