idnits 2.17.1 draft-irtf-dtnrg-prophet-10.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 seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (May 22, 2012) is 4347 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 2285 -- Looks like a reference, but probably isn't: '1' on line 2285 == Missing Reference: '0xFFFF' is mentioned on line 2285, but not defined == Outdated reference: A later version (-09) exists of draft-irtf-dtnrg-tcp-clayer-02 -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 DTN Research Group A. Lindgren 3 Internet-Draft SICS 4 Intended status: Experimental A. Doria 5 Expires: November 23, 2012 Consultant 6 E. Davies 7 Folly Consulting 8 S. Grasic 9 Lulea University of Technology 10 May 22, 2012 12 Probabilistic Routing Protocol for Intermittently Connected Networks 13 draft-irtf-dtnrg-prophet-10 15 Abstract 17 This document is a product of the Delay Tolerant Networking Research 18 Group and has been reviewed by that group. No objections to its 19 publication as an RFC were raised. 21 This document defines PRoPHET, a Probabilistic Routing Protocol using 22 History of Encounters and Transitivity. PRoPHET is a variant of the 23 epidemic routing protocol for intermittently connected networks that 24 operates by pruning the epidemic distribution tree to minimize 25 resource usage while still attempting to achieve the best case 26 routing capabilities of epidemic routing. It is intended for use in 27 sparse mesh networks where there is no guarantee that a fully 28 connected path between source and destination exists at any time, 29 rendering traditional routing protocols unable to deliver messages 30 between hosts. These networks are examples of networks where there 31 is a disparity between the latency requirements of applications and 32 the capabilities of the underlying network (networks often referred 33 to as Delay- and Disruption-Tolerant). The document presents an 34 architectural overview followed by the protocol specification. 36 Status of this Memo 38 This Internet-Draft is submitted in full conformance with the 39 provisions of BCP 78 and BCP 79. 41 Internet-Drafts are working documents of the Internet Engineering 42 Task Force (IETF). Note that other groups may also distribute 43 working documents as Internet-Drafts. The list of current Internet- 44 Drafts is at http://datatracker.ietf.org/drafts/current/. 46 Internet-Drafts are draft documents valid for a maximum of six months 47 and may be updated, replaced, or obsoleted by other documents at any 48 time. It is inappropriate to use Internet-Drafts as reference 49 material or to cite them other than as "work in progress." 51 This Internet-Draft will expire on November 23, 2012. 53 Copyright Notice 55 Copyright (c) 2012 IETF Trust and the persons identified as the 56 document authors. All rights reserved. 58 This document is subject to BCP 78 and the IETF Trust's Legal 59 Provisions Relating to IETF Documents 60 (http://trustee.ietf.org/license-info) in effect on the date of 61 publication of this document. Please review these documents 62 carefully, as they describe your rights and restrictions with respect 63 to this document. Code Components extracted from this document must 64 include Simplified BSD License text as described in Section 4.e of 65 the Trust Legal Provisions and are provided without warranty as 66 described in the Simplified BSD License. 68 Table of Contents 70 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5 71 1.1. Relation to the Delay Tolerant Networking architecture . 7 72 1.2. Applicability of the protocol . . . . . . . . . . . . . . 8 73 1.3. PRoPHET as Compared to Regular Routing Protocols . . . . 10 74 1.4. Requirements notation . . . . . . . . . . . . . . . . . . 11 75 2. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 12 76 2.1. PRoPHET . . . . . . . . . . . . . . . . . . . . . . . . . 12 77 2.1.1. Characteristic Time Interval . . . . . . . . . . . . 12 78 2.1.2. Delivery Predictability Calculation . . . . . . . . . 13 79 2.1.3. Optional Delivery Predictability Optimizations . . . 17 80 2.1.4. Forwarding Strategies and Queueing Policies . . . . . 18 81 2.2. Bundle Agent to Routing Agent Interface . . . . . . . . . 19 82 2.3. PRoPHET Zone Gateways . . . . . . . . . . . . . . . . . . 20 83 2.4. Lower Layer Requirements and Interface . . . . . . . . . 21 84 3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 23 85 3.1. Neighbor Awareness . . . . . . . . . . . . . . . . . . . 23 86 3.2. Information Exchange Phase . . . . . . . . . . . . . . . 23 87 3.2.1. Routing Information Base Dictionary . . . . . . . . . 26 88 3.2.2. Handling Multiple Simultaneous Contacts . . . . . . . 27 89 3.3. Routing Algorithm . . . . . . . . . . . . . . . . . . . . 29 90 3.4. Bundle Passing . . . . . . . . . . . . . . . . . . . . . 33 91 3.4.1. Custody . . . . . . . . . . . . . . . . . . . . . . . 34 92 3.5. When a Bundle Reaches its Destination . . . . . . . . . . 34 93 3.6. Forwarding Strategies . . . . . . . . . . . . . . . . . . 35 94 3.7. Queueing Policies . . . . . . . . . . . . . . . . . . . . 37 95 4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 40 96 4.1. Header . . . . . . . . . . . . . . . . . . . . . . . . . 41 97 4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . 46 98 4.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . 46 99 4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . 46 100 4.3.2. Error TLV . . . . . . . . . . . . . . . . . . . . . . 48 101 4.3.3. Routing Information Base Dictionary TLV . . . . . . . 50 102 4.3.4. Routing Information Base TLV . . . . . . . . . . . . 52 103 4.3.5. Bundle Offer and Response TLVs (Version 2) . . . . . 53 104 5. Detailed Operation . . . . . . . . . . . . . . . . . . . . . 58 105 5.1. High Level State Tables . . . . . . . . . . . . . . . . . 58 106 5.2. Hello Procedure . . . . . . . . . . . . . . . . . . . . . 61 107 5.2.1. Hello Procedure State Tables . . . . . . . . . . . . 64 108 5.3. Information Exchange and Bundle Passing Phase . . . . . . 65 109 5.3.1. Initiator Role State Definitions . . . . . . . . . . 69 110 5.3.2. Listener Role State Definitions . . . . . . . . . . . 74 111 5.3.3. Recommendations for Information Exchange Timer 112 Periods . . . . . . . . . . . . . . . . . . . . . . . 79 113 5.3.4. Information Exchange State Tables . . . . . . . . . . 80 114 5.4. Interaction with Nodes Using Version 1 of PRoPHET . . . . 94 115 6. Security Considerations . . . . . . . . . . . . . . . . . . . 96 116 6.1. Attacks on the Operation of the Protocol . . . . . . . . 96 117 6.1.1. Black Hole Attack . . . . . . . . . . . . . . . . . . 96 118 6.1.2. Limited Black Hole Attack/Identity Spoofing . . . . . 97 119 6.1.3. Fake PRoPHET ACKs . . . . . . . . . . . . . . . . . . 98 120 6.1.4. Bundle Store Overflow . . . . . . . . . . . . . . . . 98 121 6.1.5. Bundle Store Overflow with Delivery Predictability 122 Manipulation . . . . . . . . . . . . . . . . . . . . 98 123 6.2. Interactions with External Routing Domains . . . . . . . 99 124 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 100 125 7.1. DTN Routing Protocol Number . . . . . . . . . . . . . . . 101 126 7.2. PRoPHET Protocol Version . . . . . . . . . . . . . . . . 101 127 7.3. PRoPHET Header Flags . . . . . . . . . . . . . . . . . . 102 128 7.4. PRoPHET Result Field . . . . . . . . . . . . . . . . . . 102 129 7.5. PRoPHET Codes for Success and Codes for Failure . . . . . 103 130 7.6. PRoPHET TLV Type . . . . . . . . . . . . . . . . . . . . 104 131 7.7. Hello TLV Flags . . . . . . . . . . . . . . . . . . . . . 105 132 7.8. Error TLV Flags . . . . . . . . . . . . . . . . . . . . . 106 133 7.9. RIB Dictionary TLV Flags . . . . . . . . . . . . . . . . 106 134 7.10. RIB TLV Flags . . . . . . . . . . . . . . . . . . . . . . 107 135 7.11. RIB Flags . . . . . . . . . . . . . . . . . . . . . . . . 108 136 7.12. Bundle Offer and Response TLV Flags . . . . . . . . . . . 109 137 7.13. Bundle Offer and Response B Flags . . . . . . . . . . . . 110 138 8. Implementation Experience . . . . . . . . . . . . . . . . . . 111 139 9. Deployment Experience . . . . . . . . . . . . . . . . . . . . 112 140 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 113 141 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 114 142 11.1. Normative References . . . . . . . . . . . . . . . . . . 114 143 11.2. Informative References . . . . . . . . . . . . . . . . . 114 144 Appendix A. PRoPHET Example . . . . . . . . . . . . . . . . . . 116 145 Appendix B. Neighbor Discovery Example . . . . . . . . . . . . . 118 146 Appendix C. PRoPHET Parameter Calculation Example . . . . . . . 119 147 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 122 149 1. Introduction 151 The Probabilistic Routing Protocol using History of Encounters and 152 Transitivity (PRoPHET) algorithm enables communication between 153 participating nodes wishing to communicate in an intermittently 154 connected network where at least some of the nodes are mobile. 156 One of the most basic requirements for "traditional" (IP) networking 157 is that there must exist a fully connected path between communication 158 endpoints for the duration of a communication session in order for 159 communication to be possible. There are, however, a number of 160 scenarios where connectivity is intermittent so that this is not the 161 case (thus rendering the end-to-end use of traditional networking 162 protocols impossible), but where it still is desirable to allow 163 communication between nodes. 165 Consider a network of mobile nodes using wireless communication with 166 a limited range which is less than the typical excursion distances 167 over which the nodes travel. Communication between a pair of nodes 168 at a particular instant is only possible when the distance between 169 the nodes is less than the range of the wireless communication. This 170 means that, even if messages are forwarded through other nodes acting 171 as intermediate routes, there is no guarantee of finding a viable 172 continuous path when it is needed to transmit a message. 174 One way to enable communication in such scenarios, is by allowing 175 messages to be buffered at intermediate nodes for a longer time than 176 normally occurs in the queues of conventional routers (c.f., Delay- 177 Tolerant Networking [RFC4838]). It would then be possible to exploit 178 the mobility of a subset of the nodes to bring messages closer to 179 their destination by transferring them to other nodes as they meet. 180 Figure 1 shows how the mobility of nodes in such a scenario can be 181 used to eventually deliver a message to its destination. In this 182 figure, the four sub-figures (a) - (d) represent the physical 183 positions of four nodes (A, B, C, and D) at four time instants, 184 increasing from (a) to (d) and associated radio ranges. At the start 185 time node A has a message (indicated by a * next to that node) to be 186 delivered to node D, but there does not exist a path between nodes A 187 and D because of the limited range of available wireless connections. 188 As shown in sub-figures (a) - (d), the mobility of the nodes allows 189 the message to first be transferred to node B, then to node C, and 190 when finally node C moves within range of node D, it can deliver the 191 message to its final destination. This technique is known as 192 "transitive networking". 194 Mobility and contact patterns in real application scenarios are 195 likely to be non-random, but rather be predictable, based on the 196 underlying activities of the higher level application (this could for 197 example stem from human mobility having regular traffic patterns 198 based on repeating behavioral patterns (e.g., going to work or the 199 market and returning home) and social interactions, or from any 200 number of other node mobility situations where a proportion of nodes 201 are mobile and move in ways that are not completely random over time 202 but have a degree of predictability over time). This means that if a 203 node has visited a location or been in contact with a certain node 204 several times before, it is likely that it will visit that location 205 or meet that node again. 207 PRoPHET can also be used in some networks where such mobility as 208 described above does not take place. Predictable patterns in node 209 contacts can also occur among static nodes where varying radio 210 conditions or power-saving sleeping schedules cause connection 211 between nodes to be intermittent. 213 In previously discussed mechanisms to enable communication in 214 intermittently connected networks, such as Epidemic Routing 215 [vahdat_00], very general approaches have been taken to the problem 216 at hand. In an environment where buffer space and bandwidth are 217 infinite, Epidemic Routing will give an optimal solution to the 218 problem of routing in an intermittently connected network with regard 219 to message delivery ratio and latency. However, in most cases 220 neither bandwidth nor buffer space is infinite, but instead they are 221 rather scarce resources, especially in the case of sensor networks. 223 PRoPHET is fundamentally an epidemic protocol with strict pruning. 224 An epidemic protocol works by transferring its data to each and every 225 node it meets. As data is passed from node to node, it is eventually 226 passed to all nodes, including the target node. One of the 227 advantages of an epidemic protocol is that by trying every path, it 228 is guaranteed to try the best path. One of the disadvantages of an 229 epidemic protocol is the extensive use of resources with every node 230 needing to carry every packet and the associated transmission costs. 231 PRoPHET's goal is to gain the advantages of an epidemic protocol 232 without paying the price in storage and communication resources 233 incurred by the basic epidemic protocol. That is, PRoPHET offers an 234 alternative to basic Epidemic Routing, with lower demands on buffer 235 space and bandwidth; with equal or better performance in cases where 236 those resources are limited; and without loss of generality in 237 scenarios where it is suitable to use PRoPHET. 239 In a situation where PRoPHET is applicable, the patterns are expected 240 to have a characteristic time such as the expected time between 241 encounters between mobile stations that is in turn related to the 242 expected time that traffic will take to reach its destination in the 243 part of the network that is using PRoPHET. This characteristic time 244 provides guidance for configuration of the PRoPHET protocol in a 245 network. When appropriately configured the PRoPHET protocol 246 effectively builds a local model of the expected patterns in the 247 network that can be used to optimize the usage of resources by 248 reducing the amount of traffic sent to nodes that are unlikely to 249 lead to eventual delivery of the traffic to its destination. 251 +----------------------------+ +----------------------------+ 252 | ___ | | ___ | 253 | ___ / \ | | / \ | 254 | / \ ( D ) | | ( D ) | 255 | ( B ) \___/ | | ___ \___/ | 256 | \___/ ___ | | /___\ ___ | 257 |___ / \ | | (/ B*\) / \ | 258 | \ ( C ) | | (\_A_/) ( C ) | 259 | A* ) \___/ | | \___/ \___/ | 260 |___/ | | | 261 +----------------------------+ +----------------------------+ 262 (a) Time t (b) Time (t + dt) 263 +----------------------------+ +----------------------------+ 264 | _____ ___ | | ___ ___ | 265 | / / \ \ / \ | | / \ /___\ | 266 | ( (B C* ) ( D ) | | ( B ) (/ D*\) | 267 | \_\_/_/ \___/ | | \___/ (\_C_/) | 268 | ___ | | ___ \___/ | 269 | / \ | | / \ | 270 | ( A ) | | ( A ) | 271 | \___/ | | \___/ | 272 | | | | 273 +----------------------------+ +----------------------------+ 274 (c) Time (t + 2*dt) (d) Time (t + 3*dt) 276 Figure 1: Example of transitive communication 278 This document presents a framework for probabilistic routing in 279 intermittently connected networks, using an assumption of non-random 280 mobility of nodes to improve the delivery rate of messages while 281 keeping buffer usage and communication overhead at a low level. 282 First, a probabilistic metric called delivery predictability is 283 defined. The document then goes on to define a probabilistic routing 284 protocol using this metric. 286 1.1. Relation to the Delay Tolerant Networking architecture 288 The Delay-Tolerant Networking (DTN) architecture [RFC4838] defines an 289 architecture for communication in environments where traditional 290 communication protocols can not be used due to excessive delays, link 291 outages and other extreme conditions. The intermittently connected 292 networks considered here are a subset of those covered by the DTN 293 architecture. The DTN architecture defines routes to be computed 294 based on a collection of "contacts" indicating the start time, 295 duration, endpoints, forwarding capacity and latency of a link in the 296 topology graph. These contacts may be deterministic, or may be 297 derived from estimates. The architecture defines some different 298 types of intermittent contacts. The ones called opportunistic and 299 predicted are the ones addressed by this protocol. 301 Opportunistic contacts are those that are not scheduled, but rather 302 present themselves unexpectedly and frequently arise due to node 303 mobility. Predicted contacts are like opportunistic contacts, but 304 based on some information, it might be possible to draw some 305 statistical conclusion as to whether or not a contact will be present 306 soon. 308 The DTN architecture also introduces the bundle protocol [RFC5050], 309 which provides a way for applications to "bundle" an entire session, 310 including both data and meta-data, into a single message, or bundle, 311 that can be sent as a unit. The bundle protocol also provides end- 312 to-end addressing and acknowledgments. PRoPHET is specifically 313 intended to provide routing services in a network environment that 314 uses bundles as its data transfer mechanism, but could be also be 315 used in other intermittent environments. 317 1.2. Applicability of the protocol 319 The PRoPHET routing protocol is mainly targeted at situations where 320 at least some of the nodes are mobile with mobility that creates 321 connectivity patterns that are not completely random over time but 322 have a degree of predictability. Such connectivity patterns can also 323 occur in networks where nodes switch off radios to preserve power. 324 Human mobility patterns (often containing daily or weekly periodic 325 activities) provide one such example where PRoPHET is expected to be 326 applicable, but the applicability is not limited to scenarios 327 including humans. 329 In order for PRoPHET to benefit from such predictability in the 330 contact patterns between nodes, it is expected the network exist 331 under similar circumstances over a longer time-scale (in terms of 332 node encounters) so that the predictability can be accurately 333 estimated. 335 The PRoPHET protocol expects nodes to be able to establish a local 336 TCP link in order to exchange the information needed by the PRoPHET 337 protocol. Protocol signaling is done out-of-band over this TCP link, 338 without involving the Bundle Protocol agent [RFC5050]. The PRoPHET 339 protocol is however expected to interact with the Bundle Protocol 340 agent to retrieve information about available bundles as well as 341 requesting that a bundle is sent to another node (it is expected that 342 the associated bundle agents are then able to establish a link 343 (probably over the TCP convergence layer [I-D.irtf-dtnrg-tcp-clayer]) 344 to perform this bundle transfer). 346 TCP provides a reliable bidirectional channel between two peers and 347 guarantees in order delivery of transmitted data. When using TCP, 348 the guarantee of reliable, in order delivery allows information 349 exchanges of each category of information to be distributed across 350 several messages without requiring the PRoPHET protocol layer to be 351 concerned that all messages have been received before starting the 352 exchange of the next category of information. At most the last 353 message of the category needs to be marked as such. This allows the 354 receiver to process earlier messages while waiting for additional 355 information and allows implementations to limit the size of messages 356 so that IP fragmentation will be avoided and memory usage can be 357 optimized if necessary. However implementations MAY choose to build 358 a single message for each category of information that is as large as 359 necessary and rely on TCP to segment the message. 361 While PRoPHET is currently defined to run over TCP, in future 362 versions the information exchange may take place over other transport 363 protocols as well and these may not provide message segmentation or 364 reliable, in order delivery. The simple message division used with 365 TCP MUST NOT be used when the underlying transport does not offer 366 reliable, in order delivery, as it would be impossible to verify that 367 all the messages had arrived. Hence the capability is provided to 368 segment protocol messages into submessages directly in the PRoPHET 369 layer. Submessages are provided with sequence numbers, and this, 370 together with a capability for positive acknowledgements would allow 371 PRoPHET to operate over an unreliable protocol such as UDP or 372 potentially directly over IP. 374 Since TCP offers reliable delivery, it is RECOMMENDED that the 375 positive acknowledgment capability is not used when PRoPHET is run 376 over a TCP transport or similar protocol. When running over TCP 377 implementations MAY safely ignore positive acknowledgments. 379 Whatever transport protocol is used, PRoPHET expects to use a 380 bidirectional link for the information exchange; this allows for the 381 information exchange to take place in both directions over the same 382 link avoiding the need to establish a second link for information 383 exchange in the reverse direction. 385 In a large Delay- and Disruption-Tolerant Network (DTN), network 386 conditions may vary widely, and in different parts of the network, 387 different routing protocols may be appropriate. In this 388 specification, we consider routing within a single "PRoPHET zone", 389 which is a set of nodes among which messages are routed using 390 PRoPHET. In many cases, a PRoPHET zone will not span the entire DTN, 391 but there will be other parts of the network with other 392 characteristics that run other routing protocols. To handle this, 393 there may be nodes within the zone that act as gateways to other 394 nodes that are the destinations for bundles generated within the zone 395 or that insert bundles into the zone. Thus, PRoPHET is not 396 necessarily used end-to-end, but only within regions of the network 397 where its use is appropriate. 399 1.3. PRoPHET as Compared to Regular Routing Protocols 401 While PRoPHET uses a mechanism for pruning the epidemic forwarding 402 tree that is similar to the mechanism used in Metric-based Vector 403 Routing protocols (where the metric might be distance or cost), it 404 should not be confused with a metric vector protocol. 406 In a traditional metric-based vector routing protocol, the 407 information passed from node to node is used to create a single non- 408 looping path from source to destination that is optimal given the 409 metric used. The path consists of a set of directed edges selected 410 from the complete graph of communications links between the network 411 nodes. 413 In PRoPHET, that information is used to prune the epidemic tree of 414 paths by removing paths that look less likely to provide an effective 415 route for delivery of data to its intended destination. One of the 416 effects of this difference is that the regular notions of split 417 horizon, as described in [RFC1058], do not apply to PRoPHET. The 418 purpose of split horizon is to prevent a distance vector protocol 419 from ever passing a packet back to the node that sent it the packet 420 because it is well known that the source does not lie in that 421 direction as determined when the directed path was computed. 423 In an epidemic protocol, where that previous system already has the 424 data, the notion of passing the data back to the node is redundant: 425 the protocol can readily determine that such a transfer is not 426 required. Further, given the mobility and constant churn of 427 encounters possible in a DTN that is dominated by opportunistic 428 encounters, it is quite possible that on a future encounter, that 429 node might have become a better option for reaching the destination. 430 Such a later encounter may require a re-transfer of the data if 431 resource constraints have resulted in the data being deleted from the 432 original carrier between the encounters. 434 The logic of metric routing protocols does not map directly onto the 435 family of epidemic protocols. In particular it is inappropriate to 436 try to assess such protocols against the criteria used to assess 437 conventional routing protocols such as the metric vector protocols; 438 this is not to say that the family of epidemic protocols do not have 439 weaknesses but they have to be considered independently of 440 traditional protocols. 442 1.4. Requirements notation 444 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 445 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 446 document are to be interpreted as described in RFC 2119 [RFC2119]. 448 2. Architecture 450 2.1. PRoPHET 452 This section presents an overview of the main architecture of 453 PRoPHET, a Probabilistic Routing Protocol using History of Encounters 454 and Transitivity. The protocol leverages the observations made on 455 the non-randomness of mobility patterns present in many application 456 scenarios to improve routing performance. Instead of doing blind 457 epidemic replication of bundles through the network as previous 458 protocols have done, it applies "probabilistic routing". 460 To accomplish this, a metric called "delivery predictability", 461 0 <= P_(A,B) <= 1, is established at every node A for each known 462 destination B. This metric is calculated so that a node with a higher 463 value for a certain destination is estimated to be a better candidate 464 for delivering a bundle to that destination (i.e., if 465 P_(A,B)>P_(C,B), bundles for destination B are preferable to forward 466 to A rather than C). It is later used when making forwarding 467 decisions. As routes in a DTN are likely to be asymmetric, the 468 calculation of the delivery predictability reflects this, and P_(A,B) 469 may be different from P_(B,A). 471 The delivery predictability values in each node evolve over time both 472 as a result of decay of the metrics between encounters between nodes 473 and due to changes resulting from encounters when metric information 474 for the encountered node is updated to reflect the encounter and 475 metric information about other nodes is exchanged. 477 When two PRoPHET nodes have a communication opportunity, they first 478 exchange the delivery predictabilities for all destinations known by 479 the nodes. This information is used by the nodes to update the 480 internal delivery predictability vector as described below. After 481 that, the nodes exchange information (including destination and size) 482 about the bundles each node carries and the information is used in 483 conjunction with the updated delivery predictabilities to decide 484 which bundles to request to be forwarded from the other node based on 485 the forwarding strategy used (as discussed in Section 2.1.4). 487 2.1.1. Characteristic Time Interval 489 When an application scenario makes PRoPHET applicable, the mobility 490 pattern will exhibit a characteristic time interval that reflects the 491 distribution of time intervals between encounters between nodes. The 492 evolution of the delivery predictabilities, which reflects this 493 mobility pattern, should reflect this same characteristic time 494 interval. Accordingly the parameters used in the equations that 495 specify the evolution of delivery predictability (see Section 2.1.2) 496 need to be configured appropriately so that the evolution reflects a 497 model of the mobility pattern. 499 2.1.2. Delivery Predictability Calculation 501 As stated above, PRoPHET relies on calculating a metric based on the 502 probability of encountering a certain node, and using that to support 503 the decision of whether or not to forward a bundle to a certain node. 504 This section describes the operations performed on the metrics stored 505 in a node when it encounters another node and a communications 506 opportunity arises. In the operations described by the equations 507 that follow, the updates are being performed by node A, P_(A,B) is 508 the delivery predictability value that node A will have stored for 509 the destination B after the encounter and P_(A,B)_old is the 510 corresponding value that was stored before the encounter. If no 511 delivery predictability value is stored for a particular destination 512 B, P_(A,B) is considered to be zero. 514 As a special case, the metric value for a node itself is always 515 defined to be 1 (i.e., P_(A,A)=1). 517 The equations use a number of parameters that can be selected to 518 match the characteristics of the mobility pattern in the PRoPHET zone 519 where the node is located (see Section 2.1.1. Recommended settings 520 for the various parameters are given in Section 3.3. The impact on 521 the evolution of delivery predictabilities if encountering nodes have 522 different parameter setting is discussed in Section 2.1.2.1. 524 The calculation of the updates to the delivery predictabilities 525 during an encounter has three parts. 527 When two nodes meet, the first thing they do is to update the 528 delivery predictability for each other, so that nodes that are often 529 encountered have a high delivery predictability. If node B has not 530 met node A for a long time or has never met node B, such that 531 P_(A,B) < P_first_threshold, then P_(A,B) should be set to 532 P_encounter_first. Because PRoPHET generally has no prior knowledge 533 about whether this is an encounter that will be repeated relatively 534 frequently or one that will be a rare event, P_encounter_first SHOULD 535 be set to 0.5 unless the node has extra information obtained other 536 than through the PRoPHET protocol about the likelihood of future 537 encounters. Otherwise, P_(A,B) should be calculated as shown in 538 Equation 1, where 0 <= P_encounter <= 1 is a scaling factor setting 539 the rate at which the predictability increases on encounters after 540 the first and delta is a small positive number that effectively sets 541 an upper bound for P_(A,B). The limit is set so that 542 predictabilities between different nodes stay strictly less than 1. 543 The value of delta should normally be very small (e.g., 0.01) so as 544 not to significantly restrict the range of available 545 predictabilities, but can be chosen to make calculations efficient 546 where this is important. 548 P_(A,B) = P_(A,B)_old + ( 1 - delta - P_(A,B)_old ) * P_encounter (1) 550 There are practical circumstances where an encounter that is 551 logically a single encounter in terms of the proximity of the node 552 hardware and/or from the point of view of the human users of the 553 nodes results in several communication opportunities closely spaced 554 in time. For example mobile nodes communicating with each other 555 using Wi-Fi ad hoc mode may produce apparent multiple encounters with 556 a short interval between them but these are frequently due to 557 artifacts of the underlying physical network when using wireless 558 connections, where transmission problems or small changes in location 559 may result in repeated reconnections. In this case it would be 560 inappropriate to increase the delivery predictability by the same 561 amount for each opportunity as it would be increased when encounters 562 occur at longer intervals in the normal mobility pattern. 564 In order to reduce the distortion of the delivery predictability in 565 these circumstances, P_encounter is a function of the interval since 566 the last encounter resulted in an update of the delivery 567 predictabilities. The form of the function is as shown in Figure 2. 569 P_encounter 570 ^ 571 | 572 P_encounter_max + - - .------------------------------------- 573 | / 574 | / . 575 | / 576 | / . 577 | / 578 | / . 579 |/ 580 +-------+-------------------------------------> I 581 I_typ 583 Figure 2: P_encounter as function of time interval, I, between 584 updates 586 The form of the function is chosen so that both the increase of 587 P_(A,B) resulting from Equation 1 and the decrease that results from 588 Equation 2 are related to the interval between updates for short 589 intervals. For intervals longer than the "typical" time (I_typ) 590 between encounters P_encounter is set to a fixed value 591 P_encounter_max. The break point reflects the transition between the 592 "normal" communication opportunity regime where opportunities result 593 from the overall mobility pattern and the closely spaced 594 opportunities that result from what are effectively local artifacts 595 of the wireless technology used to deliver those opportunities. 597 P_encounter_max is chosen so that the increment in P_(A,B) provided 598 by equation (1) significantly exceeds the decay of the delivery 599 predictability over the typical interval between encounters resulting 600 from Equation 2. 602 Making P_encounter dependent on the interval time also avoids 603 inappropriate extra increments of P_(A,B) in situations where node A 604 is in communication with several other nodes simultaneously. In this 605 case updates from each of the communicating nodes have to be 606 distributed to the other nodes possibly leading to several updates 607 being carried out in a short period. This situation is discussed in 608 more detail in Section 3.2.2. 610 If a pair of nodes do not encounter each other during an interval, 611 they are less likely to be good forwarders of bundles to each other, 612 thus the delivery predictability values must age, being reduced in 613 the process. The second part of the updates of the metric values is 614 application of the aging equation shown in Equation 2, where 615 0 <= gamma <= 1 is the aging constant, and K is the number of time 616 units that have elapsed since the last time the metric was aged. The 617 time unit used can differ, and should be defined based on the 618 application and the expected delays in the targeted network. 620 P_(A,B) = P_(A,B)_old * gamma^K (2) 622 The delivery predictabilities are aged according to Equation 2 before 623 being passed to an encountered node so that they reflect the time 624 that has passed since the node had its last encounter with any other 625 node. The results of the aging process are sent to the encountered 626 peer for use in the next stage of the process. The aged results 627 received from node B in node A are referenced as P_(B,x)_recv. 629 The delivery predictability also has a transitive property, that is 630 based on the observation that if node A frequently encounters node B, 631 and node B frequently encounters node C, then node C probably is a 632 good node to which to forward bundles destined for node A. Equation 3 633 shows how this transitivity affects the delivery predictability, 634 where 0 <= beta <= 1 is a scaling constant that controls how large an 635 impact the transitivity should have on the delivery predictability. 637 P_(A,C) = MAX( P_(A,C)_old, P_(A,B) * P_(B,C)_recv * beta ) (3) 638 Node A uses Equation 3 and the metric values received from the 639 encountered node B (e.g., P_(B,C)_recv) in the third part of updating 640 the metric values stored in node A. 642 2.1.2.1. Impact of Encounters Between Nodes with Different Parameter 643 Settings 645 The various parameters used in the three equations described in 646 Section 2.1.2 are set independently in each node and it is therefore 647 possible that encounters may take place between nodes that have been 648 configured with different values of the parameters. This section 649 considers whether this could be problematic for the operation of 650 PRoPHET in that zone. 652 It is desirable that all the nodes operating in a PRoPHET zone should 653 use closely matched values of the parameters and that the parameters 654 should be set to values that are appropriate for the operating zone. 655 More details of how to select appropriate values are given in 656 Section 3.3. Using closely matched values means that delivery 657 predictabilities will evolve in the same way in each node leading to 658 consistent decision making about the bundles that should be exchanged 659 during encounters. 661 Before going on to consider the impact of reasonable but different 662 settings, it should be noted that malicious nodes can use 663 inappropriate settings of the parameters to disrupt delivery of 664 bundles in a PRoPHET zone as described in Section 6. 666 Firstly and importantly, use of different, but legitimate, settings 667 in encountering nodes will not cause problems in the protocol itself. 668 Apart from P_encounter_first, the other parameters control the rate 669 of change of the the metric values or limit the range of valid values 670 that will be stored in a node. None of the calculations in a node 671 will be invalidated or result in illegal values if the metric values 672 received from another node had been calculated using different 673 parameters. Furthermore, the protocol is designed so that it is not 674 possible to carry delivery predictabilities outside the permissible 675 range of 0 to 1. 677 A node MAY consider setting received values greater than (1 - delta) 678 to (1 - delta) if this would simplify operations. However there are 679 some special situations where it may be appropriate for the delivery 680 predictability for another node to be 1. For example if a DTN using 681 PRoPHET has multiple gateways to the continuously connected Internet, 682 the delivery predictability seen from PRoPHET in one gateway for the 683 other gateway nodes can be taken as 1 since they are permanently 684 connected through the Internet. This would allow traffic to be 685 forwarded into the DTN through the most advantageous gateway even if 686 it initially arrives at another gateway. 688 Simulation work indicates that the update calculations are quite 689 stable in the face of changes to the rate parameters, so that minor 690 discrepancies will not have a major impact on the performance of the 691 protocol. The protocol is explicitly designed to deal with 692 situations where there are random factors in the opportunistic nature 693 of node encounters and this randomness dominates over the 694 discrepancies in the parameters. 696 More major discrepancies may lead to sub-optimal behavior of the 697 protocol as certain paths might be more preferred or more deprecated 698 inappropriately. However, since the protocol overall is epidemic in 699 nature, this would not generally lead to non-delivery of bundles as 700 they would also be passed to other nodes and would still be delivered 701 though possibly not on the optimal path. 703 2.1.3. Optional Delivery Predictability Optimizations 705 2.1.3.1. Smoothing 707 To give the delivery predictability a smoother rate of change, a node 708 MAY apply one of the following methods to smooth the metric: 710 1. Keep a list of NUM_P (the recommended value is 4, which has been 711 shown in simulations to give a good trade off between smoothness 712 and rate of response to changes) values for each destination 713 instead of only a single value. The list is held in order of 714 acquisition. When a delivery predictability is updated, the 715 value at the "newest" position in the list is used as input to 716 the equations in Section 2.1.2. The oldest value in the list is 717 then discarded and the new value is written in the "newest" 718 position of the list. When a delivery predictability value is 719 needed (either for sending to a peering PRoPHET node, or for 720 making a forwarding decision), the average of the values in the 721 list is calculated, and that value is then used. If less than 722 NUM_P values have been entered into the list, only the positions 723 that have been filled should be used for the averaging. 725 2. In addition to keeping the delivery predictability as described 726 in Section 2.1.2, a node MAY also keep an exponential weighted 727 moving average (EWMA) of the delivery predictability. The EWMA 728 is then used for making forwarding decisions and to report to 729 peering nodes, but the value calculated according to 730 Section 2.1.2 is still used as input to the calculations of new 731 delivery predictabilities. The EWMA is calculated according to 732 Equation 4, where 0 <= alpha <= 1 is the weight of the most 733 current value. 735 P_ewma = P_ewma_old * (1 - alpha) + P * alpha (4) 737 The appropriate choice of alpha may vary depending on application 738 scenario circumstances. Unless prior knowledge of the scenario is 739 available, it is suggested that alpha is set to 0.5. 741 2.1.3.2. Removal of Low Delivery Predictabilities 743 To reduce the data to be transferred between two nodes, a node MAY 744 treat delivery predictabilities smaller than P_first_threshold, where 745 P_first_threshold is a small number, as if they were zero, and thus 746 they do not need to be stored or included in the list sent during the 747 information exchange phase. If this optimization is used, care must 748 be taken to select P_first_threshold to be smaller than delivery 749 predictability values normally present in the network for 750 destinations for which this node is a forwarder. It is possible that 751 P_first_threshold could be calculated based on delivery 752 predictability ranges and the amount they change historically, but 753 this has not been investigated yet. 755 2.1.4. Forwarding Strategies and Queueing Policies 757 In traditional routing protocols, choosing where to forward a message 758 is usually a simple task; the message is sent to the neighbor that 759 has the path to the destination with the lowest cost (often the 760 shortest path). Normally the message is also only sent to a single 761 node since the reliability of paths is relatively high. However, in 762 the settings we envision here, things are radically different. The 763 first possibility that must be considered when a bundle arrives at a 764 node is that there might not be a path to the destination available, 765 so the node has to buffer the bundle and upon each encounter with 766 another node, the decision must be made whether or not to transfer a 767 particular bundle. Furthermore, having duplicates of messages (on 768 different nodes, as the bundle offer/request mechanism described in 769 Section 4.3.5 ensures that a node does not receive a bundle it 770 already carries) may also be sensible, as forwarding a bundle to 771 multiple nodes can increase the delivery probability of that bundle. 773 Unfortunately, these decisions are not trivial to make. In some 774 cases it might be sensible to select a fixed threshold and only give 775 a bundle to nodes that have a delivery predictability over that 776 threshold for the destination of the bundle. On the other hand, when 777 encountering a node with a low delivery predictability, it is not 778 certain that a node with a higher metric will be encountered within 779 reasonable time. Thus, there can also be situations where we might 780 want to be less strict in deciding who to give bundles to. 781 Furthermore, there is the problem of deciding how many nodes to give 782 a certain bundle to. Distributing a bundle to a large number of 783 nodes will of course increase the probability of delivering that 784 particular bundle to its destination, but this comes at the cost of 785 consuming more system resources for bundle storage and possibly 786 reducing the probability of other bundles being delivered. On the 787 other hand, giving a bundle to only a few nodes (maybe even just a 788 single node) will use less system resources, but the probability of 789 delivering a bundle is lower, and the delay incurred high. 791 When resources are constrained, nodes may suffer from storage 792 shortage, and may have to drop bundles before they have been 793 delivered to their destinations. They may also wish to consider the 794 length of bundles being offered by an encountered node before 795 accepting transfer of the bundle in order to avoid the need to drop 796 the new bundle immediately or to ensure that there is adequate space 797 to hold the bundle offered, which might require other bundles to be 798 dropped. As with the decision as to whether or not to forward a 799 bundle, deciding which bundles to accept and/or drop to still 800 maintain good performance might require different policies in 801 different scenarios. 803 Nodes MAY define their own forwarding strategies and queueing 804 policies that take into account the special conditions applicable to 805 the nodes, and local resource constraints. Some default strategies 806 and policies that should be suitable for most normal operation are 807 defined in Section 3.6 and Section 3.7. 809 2.2. Bundle Agent to Routing Agent Interface 811 The bundle protocol [RFC5050] introduces the concept of a "bundle 812 agent" that manages the interface between applications and the 813 "convergence layers" that provide the transport of bundles between 814 nodes during communication opportunities. This specification extends 815 the bundle agent with a routing agent that controls the actions of 816 the bundle agent during an (opportunistic) communications 817 opportunity. 819 This specification defines the details of the PRoPHET routing agent, 820 but the interface defines a more general interface that is also 821 applicable to alternative routing protocols. 823 To enable the PRoPHET routing agent to operate properly, it must be 824 aware of the bundles stored at the node, and it must also be able to 825 tell the bundle agent of that node to send a bundle to a peering 826 node. Therefore, the bundle agent needs to provide the following 827 interface/functionality to the routing agent: 829 Get Bundle List 830 Returns a list of the stored bundles and their attributes to the 831 routing agent. 833 Send Bundle 834 Makes the bundle agent send a specified bundle. 836 Accept Bundle 837 Gives the bundle agent a new bundle to store. 839 Bundle Delivered 840 Tells the bundle agent that a bundle was delivered to its 841 destination. 843 Drop Bundle Advice 844 Advises the bundle agent that a specified bundle should not be 845 offered for forwarding in future and may be dropped by the 846 bundle agent if appropriate. 848 Route Import 849 Can be used by a gateway node in a PRoPHET zone to import 850 reachability information about EIDs that are external to the 851 PRoPHET zone. Translation functions dependent on the external 852 routing protocol will be used to set the appropriate delivery 853 predictabilities for imported destinations as described in 854 Section 2.3. 856 Route Export 857 Can be used by a gateway node in a PRoPHET zone to export 858 reachability information (destination EIDs and corresponding 859 delivery predictabilities) for use by routing protocols in other 860 parts of the DTN. 862 Implementation Note: Depending on the distribution of functions in 863 a complete bundle agent supporting PRoPHET, reception and delivery 864 of bundles may not be carried out directly by the PRoPHET module. 865 In this case PRoPHET can inform the bundle agent about bundles 866 that have been requested from communicating nodes. Then the 867 Accept Bundle and Bundle Delivered functions can be implemented as 868 notifications of the PRoPHET module when the relevant bundles 869 arrive at the node or are delivered to local applications. 871 2.3. PRoPHET Zone Gateways 873 PRoPHET is designed to handle routing primarily within a "PRoPHET 874 zone," i.e., a set of nodes that all implement the PRoPHET routing 875 scheme. However, since we recognise that a PRoPHET routing zone is 876 unlikely to encompass an entire DTN, there may be nodes within the 877 zone that act as gateways to other nodes that are the destinations 878 for bundles generated within the zone or that insert bundles into the 879 zone. 881 PRoPHET MAY elect to export and import routes across a bundle agent 882 interface. The delivery predictability to use for routes that are 883 imported depends on the routing protocol used to manage those routes. 884 If a translation function between the external routing protocol and 885 PRoPHET exists, it SHOULD be used to set the delivery predictability. 886 If no such translation function exists, the delivery predictability 887 SHOULD be set to 1. For those routes that are exported, the current 888 delivery predictability will be exported with the route. 890 2.4. Lower Layer Requirements and Interface 892 PRoPHET can be run on a large number of underlying networking 893 technologies. To accommodate its operation on all kinds of lower 894 layers, it requires the lower layers to provide the following 895 functionality and interfaces. 897 Neighbor discovery and maintenance 898 A PRoPHET node needs to know the identity of its neighbors and 899 when new neighbors appear and old neighbors disappear. Some 900 wireless networking technologies might already contain 901 mechanisms for detecting neighbors and maintaining this state. 902 To avoid redundancies and inefficiencies, neighbor discovery is 903 thus not included as a part of PRoPHET, but PRoPHET relies on 904 such a mechanism in lower layers. The lower layers MUST provide 905 the two functions listed below. If the underlying networking 906 technology does not support such services, a simple neighbor 907 discovery scheme using local broadcasts of beacon messages could 908 be run in-between PRoPHET and the underlying layer. An example 909 of a simple neighbor discovery mechanism that could be used is 910 shown in Appendix B. 912 New Neighbor 913 Signals to the PRoPHET agent that a new node has become a 914 neighbor. A neighbor is here defined as another node that 915 is currently within communication range of the wireless 916 networking technology in use. The PRoPHET agent should now 917 start the Hello procedure as described in Section 5.2. 919 Neighbor Gone 920 Signals to the PRoPHET agent that one of its neighbors have 921 left. 923 Local Address 924 An address used by the underlying communication layer (e.g., an 925 IP or MAC address) that identifies the sender address of the 926 current message. This address must be unique among the nodes 927 that can currently communicate, and is only used in conjunction 928 with an Instance Number to identify a communicating pair of 929 nodes as described in Section 4.1. This address and its format 930 is dependent on the communication layer that is being used by 931 the PRoPHET layer. 933 3. Protocol Overview 935 3.1. Neighbor Awareness 937 Since the operation of the protocol is dependent on the encounters of 938 nodes running PRoPHET, the nodes must be able to detect when a new 939 neighbor is present. The protocol may be run on several different 940 networking technologies, and as some of them might already have 941 methods available for detecting neighbors, PRoPHET does not include a 942 mechanism for neighbor discovery. Instead, it requires the 943 underlying layer to provide a mechanism to notify the protocol of 944 when neighbors appear and disappear as described in Section 2.4. 946 When a new neighbor has been detected, the protocol starts to set up 947 a link with that node through the Hello message exchange as described 948 in Section 5.2. The Hello message exchange allows for negotiation of 949 capabilities between neighbors. At present the only capability is a 950 request that the offering node should or should not include bundle 951 payload lengths with all offered bundles rather than just for 952 fragments. Once the link has been set up the protocol may continue 953 to the Information Exchange Phase (see Section 3.2). Once this has 954 been completed the nodes will normally recalculate the delivery 955 predictabilities using the equations and mechanisms described in 956 Section 2.1.2 and Section 2.1.3. 958 As described in Section 2.1.2, there are some circumstances in which 959 a single logical encounter may result in several actual communication 960 opportunities. To avoid the delivery predictability of the 961 encountered node being increased excessively under these 962 circumstances the value of P_encounter is dependent on the interval 963 time between delivery predictability updates for intervals less than 964 the typical interval between encounters. 966 In order to make use of this time dependence, PRoPHET maintains a 967 list of recently encountered nodes identified by the Endpoint 968 Identifier (EID) that the node uses to identify the communication 969 session and containing the start time of the last communication 970 session with that node. The size of this list is controlled because 971 nodes that are not in contact and started their last connection more 972 than a time I_typ before the present can be dropped from the list. 973 It also maintains a record of the time at which the decay function 974 (Equation 2) was last applied to the delivery predictabilities in the 975 node. 977 3.2. Information Exchange Phase 979 The Information Exchange Phase involves the transfer of sets of four 980 types of information between the pair of connected nodes: 982 o Routing Information Base Dictionary (RIB Dictionary or RIBD), 984 o Routing Information Base (RIB), 986 o Bundle Offers, and 988 o Bundle Responses. 990 During a communication opportunity several sets of each type of 991 information may be transferred in each direction as explained in the 992 rest of this section. Each set can be transferred in one or more 993 messages. When (and only when) using a connection oriented reliable 994 transport protocol such as TCP as envisaged in this draft, a set can 995 be be partitioned across messages by the software layer above the 996 PRoPHET protocol engine. 998 In this case the last message in a set is flagged in the protocol. 999 This allows the higher level software to minimize the buffer memory 1000 requirements by avoiding the need to build very large messages in one 1001 go, and allows the message size to be controlled outside of PRoPHET. 1002 However, this scheme is only usable if the transport protocol 1003 provides reliable, in-order delivery of messages as the messages are 1004 not explicitly sequence numbered and the overall size of the set is 1005 not passed explicitly. 1007 The specification of PRoPHET also provides a sub-message mechanism 1008 and retransmission that allows large messages specified by the higher 1009 level to be transmitted in smaller chunks. This mechanism was 1010 originally provided to allow PRoPHET to operate over unreliable 1011 transport protocols such as UDP, but can also be used with reliable 1012 transports if the higher level software does not want to handle 1013 message fragmentation. However, the sequencing and length adds 1014 overhead that is redundant if the transport protocol already provides 1015 reliable, in-order delivery. 1017 The first step in the Information Exchange Phase is for the protocol 1018 to send one or more messages containing a RIB Dictionary TLV (Type- 1019 Length-Value message component) to the node it is peering with. This 1020 set of messages contain a dictionary of the Endpoint Identifiers 1021 (EIDs) of the nodes that will be listed in the Routing Information 1022 Base (RIB - see Section 3.2.1 for more information about this 1023 dictionary). After this, one or more messages containing a Routing 1024 Information Base TLV are sent. This TLV contains a list of the EIDs 1025 that the node has knowledge of, and the corresponding delivery 1026 predictabilities for those nodes, together with flags describing the 1027 capabilities of the sending node. Upon reception of a complete set 1028 of these messages, the peer node updates its delivery predictability 1029 table according to the equations in Section 2.1.2. the peer node then 1030 applies its forwarding strategy (see Section 2.1.4) to determine 1031 which of its stored bundles it wishes to offer the node that sent the 1032 RIB, which will then be the receiver for any bundles to be 1033 transferred. 1035 After making this decision, one or more Bundle Offer TLVs are 1036 prepared, listing the bundle identifiers and their destinations for 1037 all bundles the peer node wishes to offer to the receiver node that 1038 sent the RIB. As described in [RFC5050], a bundle identifier 1039 consists of up to five component parts. For a complete bundle the 1040 identifier consists of 1042 o Source EID, 1044 o Creation Timestamp - Time of creation, and 1046 o Creation Timestamp - Sequence Number. 1048 Additionally, for a bundle fragment, the identifier also contains 1050 o Offset within the payload at which the fragment payload data 1051 starts, and 1053 o Length of the fragment payload data. 1055 If any of the Bundle Offer TLVs lists a bundle for which the source 1056 or destination EID was not included in the previous set of RIB 1057 Dictionary information sent, one or more new RIBD TLVs are sent next 1058 with an incremental update of the dictionary. When the receiver node 1059 has a dictionary with all necessary EIDs, the Bundle Offer TLVs are 1060 sent to it. The Bundle Offer TLVs also contain a list of PRoPHET 1061 ACKs (see Section 3.5). If requested by the receiver node during the 1062 Hello phase the Bundle Offer TLV will also specify the payload length 1063 for all bundles rather than just for fragments. This information can 1064 be used by the receiving node to assist with the selection of bundles 1065 to be accepted from the offered list, especially if the available 1066 bundle storage capacity is limited. 1068 The receiving node then examines the list of offered bundles and 1069 selects bundles that it will accept according to its own policies, 1070 considering the bundles already present in the node and the current 1071 availability of resources in the node. The list is sorted according 1072 to the priority that the policies apply to the selected bundles, with 1073 the highest priority bundle first in the list. The offering node 1074 will forward the selected bundles in this order. The prioritized 1075 list is sent to the offering node in one or more Bundle Response TLVs 1076 using the same EID dictionary as was used for the Bundle Offer TLV. 1078 When a new bundle arrives at a node, the node MAY inspect its list of 1079 available neighbors, and if one of them is a candidate to forward the 1080 bundle, a new Bundle Offer TLV MAY be sent to that node. If two 1081 nodes remain connected over a longer period of time, the Information 1082 Exchange Phase will be periodically re-initiated when the 1083 next_exchange timer expires to allow new delivery predictability 1084 information to be spread through the network and new bundle exchanges 1085 to take place. 1087 The Information Exchange phase of the protocol is described in more 1088 detail in Section 5.3. 1090 3.2.1. Routing Information Base Dictionary 1092 To reduce the overhead of the protocol, the Routing Information Base 1093 and Bundle Offer/Response TLVs utilize an EID dictionary. This 1094 dictionary maps variable length EIDs as defined in [RFC4838], which 1095 may potentially be quite long, to shorter numerical identifiers, 1096 coded as Self-Delimiting Numeric Values (SDNVs - see Section 4.1. of 1097 RFC 5050 [RFC5050]),that are used in place of the EIDs in subsequent 1098 TLVs. 1100 This dictionary is a shared resource between the two peering nodes. 1101 Each can add to the dictionary by sending a RIB Dictionary TLV to its 1102 peer. To allow either node to add to the dictionary at any time, the 1103 identifiers used by each node are taken from disjoint sets: 1104 identifiers originated by the node that started the Hello procedure 1105 have the least significant bit set to 0 (i.e., are even numbers) 1106 whereas those originated by the other peer have the least significant 1107 bit set to 1 (i.e., are odd numbers). This means that the dictionary 1108 can be expanded by either node at any point in the information 1109 exchange phase and the new identifiers can then be used in subsequent 1110 TLVs until the dictionary is reinitialized. 1112 The dictionary that is established only persists through a single 1113 encounter with a node (i.e., while the same link set up by the Hello 1114 procedure, with the same instance numbers, remains open). 1116 Having more then one identifier for the same EID does not cause any 1117 problems. This means that it is possible for the peers to create 1118 their dictionary entries independently if required by an 1119 implementation, but this may be inefficient as a dictionary entry for 1120 an EID might be sent in both directions between the peers. 1121 Implementers can choose to inspect entries sent by the node that 1122 started the Hello procedure and thereby eliminate any duplicates 1123 before sending the dictionary entries from the other peer. Whether 1124 postponing sending the other peer's entries is more efficient depends 1125 on the nature of the physical link technology and the transport 1126 protocol used. With a genuinely full duplex link it may be faster to 1127 accept possible duplication and send dictionary entries concurrently 1128 in both directions. If the link is effectively half-duplex (e.g., 1129 Wi-Fi), then it will generally be more efficient to wait and 1130 eliminate duplicates. 1132 If a node receives a RIB Dictionary TLV containing an identifier that 1133 is already in use, the node MUST confirm that the EID referred to is 1134 identical to the EID in the existing entry. Otherwise the node must 1135 send an error response to the message with the TLV containing the 1136 error and ignore the TLV containing the error. If a node receives a 1137 RIB, Bundle Offer or Bundle Response TLV that uses an identifier that 1138 is not in its dictionary, the node MUST send an error response and 1139 ignore the TLV containing the error. 1141 3.2.2. Handling Multiple Simultaneous Contacts 1143 From time to time a mobile node may, for example, be in wireless 1144 range of more than one other mobile node. The PRoPHET neighbor 1145 awareness protocol will establish multiple simultaneous contacts with 1146 these nodes and commence information exchanges with each of them. 1148 When updating the delivery predictabilities as described in 1149 Section 2.1.2 using the values passed from each of the contacts in 1150 turn, some extra considerations apply when multiple contacts are in 1151 progress: 1153 SC1 When aging the delivery predictabilities according to Equation 1154 2, the value of K to be used in each set of calculations is 1155 always the amount of time since the last aging was done. For 1156 example if node Z makes contact with node A and then with node 1157 B, the value of K used when the delivery predictsbilities are 1158 aged in node Z for the contact with node B will be the time 1159 since the delivery predictabilities were aged for the contact 1160 with node A. 1162 SC2 When a a new contact starts, the value of P_encounter used when 1163 applying Equation 1 for the newly contacted node is always 1164 selected according to the time since the last encounter with 1165 that node. Thus the application of Equation 1 to update P_(Z,A) 1166 when the contact of Z and A starts in the aging example just 1167 given and the updating of P_(Z,B) when the contact of Z and B 1168 starts will use the appropriate value of P_encounter according 1169 to how long it is since node Z previously encountered node A and 1170 node B respectively. 1172 SC3 If, as with the contact between nodes Z and B, there is another 1173 active contact in progress, such as with node A when the contact 1174 with node B starts, Equation 1 should *also* be applied to 1175 P_(z,x) for all the nodes "x" which have ongoing contacts with 1176 node Z (i.e., node A in the example given). However the value 1177 of P_encounter used will be selected according to the time since 1178 the previous update of the delivery predictabilities as a result 1179 of information received from any other node. In the example 1180 given here, P_(Z,A) would also have Equation 1 applied when the 1181 delivery predictabilities are received from node B, but the 1182 value of P_encounter used would be selected according to the 1183 time since the updates done when the encounter between nodes Z 1184 and A started rather than the time since the previous encounter 1185 between nodes A and Z. 1187 If these simultaneous contacts persist for some time, then, as 1188 described in Section 3.2, the information exchange process will be 1189 periodically rerun for each contact according to the configured timer 1190 interval. When the delivery predictability values are recalculated 1191 during each rerun, Equation 1 will be applied as in special 1192 consideration SC3 above, but it will be applied to the delivery 1193 predictability for each active contact using the P_encounter value 1194 selected according to time since the last set of updates were 1195 performed on the delivery predictabilities irrespective of which 1196 nodes triggered either the previous or current updates. This means 1197 that in the example discussed here P_(Z,A) and P_(Z.B) will be 1198 updated using the same value of P_encounter whether node A or node B 1199 initiated the update while the three nodes remain connected. 1201 The interval between reruns of the information exchange will be 1202 generally be set to a small fraction of the expected time between 1203 independent encounters of pairs of nodes. This ensures that, for 1204 example, the delivery predictability information obtained by node Z 1205 from node A will be passed on to node B whether or not nodes A and B 1206 can communicate directly during this encounter. This avoids problems 1207 that may arise from peculiarities of radio propagation during this 1208 sort of encounter, but the scaling of the P_encounter factor 1209 according to the time between updates of the delivery 1210 predictabilities means that the predictabilities for the nodes that 1211 are in contact are not increased excessively as would be the case if 1212 each information exchange was treated as a separate encounter with 1213 the value of P_encounter_max used each time. In conjunction with the 1214 form of Equation 3 where a "max" function is used, the scaling of 1215 P_encounter results in the delivery predictabilities in each node 1216 stabilizing after a few exchanges in a situation where several nodes 1217 are in mutual contact. This has been demonstrated by simulation. 1219 The effect of the updates of the delivery predictabilities when there 1220 are multiple simultaneous contacts is that the information about good 1221 routes on which to forward bundles is correctly passed between sets 1222 of nodes that are simultaneously in contact through the transitive 1223 update of Equation 3 during each information exchange but the 1224 delivery predictabilities for the direct contacts are not 1225 exaggerated. 1227 3.3. Routing Algorithm 1229 The basic routing algorithm of the protocol is described in 1230 Section 2.1. The algorithm uses some parameter values in the 1231 calculation of the delivery predictability metric. These parameters 1232 are configurable depending on the usage scenario, but Figure 3 1233 provides some recommended default values. A brief explanation of the 1234 parameters and some advice on setting appropriate values is given 1235 below. 1237 I_typ 1238 I_typ provides a fundamental timescale for the mobility pattern 1239 in the PRoPHET scenario where the protocol is being applied. It 1240 represents the typical or mean time interval between encounters 1241 between a given pair of nodes in the normal course of mobility. 1242 The interval should reflect the "logical" time between 1243 encounters and should not give significant weight to multiple 1244 connection events as explained in Section 2.1.2. This time 1245 interval informs the settings of many of the other parameters 1246 but is not necessarily directly used as a parameter. 1247 Consideration needs to be given to the higher moments of the 1248 distribution of intervals between encounters and the nature of 1249 that distribution. 1251 P_encounter_max 1252 P_encounter_max is used as the upper limit of a scaling factor 1253 that increases the delivery predictability for a destination 1254 when the destination node is encountered. A larger value of 1255 P_encounter_max will increase the delivery predictability faster 1256 and fewer encounters will be required for the delivery 1257 predictability to reach a certain level. Given that relative 1258 rather than absolute delivery predictability values are what is 1259 interesting for the forwarding mechanisms defined, the protocol 1260 is very robust to different values of P_encounter as long as the 1261 same value is chosen for all nodes. The value should be chosen 1262 so that increase in the delivery predictability resulting from 1263 using P_encounter_max in Equation 1 more than compensates for 1264 the decay of the delivery predictability resulting from Equation 1265 3 with a time interval of I_typ. 1267 P_encounter(intvl) 1268 As explained in Section 2.1.2, the parameter P_encounter used in 1269 Equation 1 is a function of the time interval "intvl". The 1270 function should be an approximation to 1272 P_encounter(intvl) = 1273 P_encounter_max * (intvl / I_typ) for 0<= intvl <= I_typ 1274 P_encounter_max for intvl > I_typ 1276 The function can be quantized and adapted to suit the mobility 1277 pattern and to make implementation easier. The overall effect 1278 should be that be that if Equation 1 is applied a number of 1279 times during a long lived communication opportunity lasting 1280 I_typ, the overall increase in the delivery predictability 1281 should be approximately the same as if there had been two 1282 distinct encounters spaced I_typ apart. This second case would 1283 result in one application of Equation 1 using P_encounter_max. 1285 P_first_threshold 1286 As described in Section 2.1.2, the delivery predictability for a 1287 destination is gradually reduced over time unless increased as a 1288 result of direct encounters or through the transitivity 1289 property. If the delivery predictability falls below the value 1290 P_first_threshold, then the node MAY discard the delivery 1291 predictability information for the destination and treat 1292 subsequent encounters as if they had never encountered the node 1293 previously. This allows the node to reduce the storage needed 1294 for delivery predictabilities and decreases the amount of 1295 information that has to be exchanged between nodes; otherwise 1296 the reduction algorithm would result in very small but non-zero 1297 predictabilities being maintained for nodes that were last 1298 encountered a long time ago. 1300 P_encounter_first 1301 As described in Section 2.1.2, PRoPHET does not, by default, 1302 make any assumptions about the likelihood that an encountered 1303 node will be a encountered repeatedly in the future or, 1304 alternatively, that this is a once-off chance encounter that is 1305 unlikely to be repeated. During an encounter where the 1306 encountering node has no delivery predictability information for 1307 the encountered destination node, either because this is really 1308 the first encounter between the nodes or because the previous 1309 encounter was so long ago that the predictability had fallen 1310 below P_first_threshold and therefore been discarded, the 1311 encountering node sets the delivery predictability for the 1312 destination node to P_encounter_first. The suggested value for 1313 P_encounter_first is 0.5: this value is RECOMMENDED as 1314 appropriate in the usual case where PRoPHET has no extra (e.g., 1315 out-of-band) information about whether future encounters with 1316 this node will be regular or otherwise. 1318 alpha 1319 The alpha parameter is used in the optional smoothing of the 1320 delivery predictabilities described in Section 2.1.3.1. It is 1321 used to determine the weight of the most current P-value in the 1322 calculation of an EWMA. 1324 beta 1325 The beta parameter adjusts the weight of the transitive property 1326 of PRoPHET, that is, how much consideration should be given to 1327 information about destinations that is received from encountered 1328 nodes. If beta is set to zero, the transitive property of 1329 PRoPHET will not be active and only direct encounters will be 1330 used in the calculation of the delivery predictability. The 1331 higher the value of beta the more rapidly encounters will 1332 increase predictabilities through the transitive rule. 1334 gamma 1335 The gamma parameter determines how quickly delivery 1336 predictabilities age. A lower value of gamma will cause the 1337 delivery predictability to age faster. The value of gamma 1338 should be chosen according to the scenario and environment in 1339 which the protocol will be used. If encounters are expected to 1340 be very frequent, a lower value should be chosen for gamma than 1341 if encounters are expected to be rare. 1343 delta 1344 The delta parameter sets the maximum value that the delivery 1345 predictability for a destination other than for the node itself 1346 (i.e., P_(A,B) for all cases except P_(A,A)) as (1 - delta). 1347 Delta should be set to a small value to allow the maximum 1348 possible range for predictabilities but can be configured to 1349 make calculation efficient if needed. 1351 To set an appropriate gamma value, one should consider the "average 1352 expected delivery" time I_aed in the PRoPHET zone where the protocol 1353 is to be used, and the time unit used (the resolution with which the 1354 delivery predictability is being updated). The I_aed time interval 1355 can be estimated according to the average number of hops that bundles 1356 have to pass and average interval between encounters I_typ. Clearly 1357 if bundles have a time to live (TTL - i.e., the time left until the 1358 expiry time stored in the bundle occurs) that is less than I_aed they 1359 are unlikely to survive in the network to be delivered to a node in 1360 this PRoPHET zone, but the TTL for bundles created in nodes in this 1361 zone should not be chosen solely on this basis because they may pass 1362 through other networks. 1364 After estimating I_aed and selecting how much we want the delivery 1365 predictability to age in one I_aed time period (call this A), we can 1366 calculate K, the number of time units in one I_aed, using 1367 K = (I_aed / time unit). This can then be used to calculate gamma as 1368 gamma = K'th-root( A ). 1370 I_typ, I_aed, K, and gamma can then be used to inform the settings of 1371 P_encounter_first, P_encounter_max, P_first_threshold and delta, and 1372 the detailed form of the function P_encounter(intvl). 1374 First, considering the evolution of the delivery predictability 1375 P_(A,B) after a single encounter between nodes A and B, P_(A,B) is 1376 initially set to P_encounter_first and will then steadily decay until 1377 it reaches P_first_threshold. The ratio between P_encounter_first 1378 and P_first_threshold should be set so that P_first_threshold is 1379 reached after a small multiple (e.g., 3 to 5) of I_aed has elapsed, 1380 making it likely that any subsequent encounter between the nodes 1381 would have occurred before P_(A,B) decays below P_first_threshold. 1382 If the statistics of the distribution of times between encounters is 1383 known then a small multiple of the standard deviation of the 1384 distribution would be a possible period instead of using a multiple 1385 of I_aed. 1387 Second, if a second encounter between A and B occurs, the setting of 1388 P_encounter_max should be sufficiently high to reverse the decay that 1389 would have occurred during I_typ and increase P_(A,B) above the value 1390 of P_encounter_first. After several further encounters P_(A,B) will 1391 reach (1 - delta), its upper limit. As with setting up 1392 P_first_threshold, P_encounter_max should be set so that the upper 1393 limit is reached after a small number of encounters spaced apart by 1394 I_typ have occurred but this should generally be more than 2 or 3. 1396 Finally beta can be chosen to give some smoothing of the influence of 1397 transitivity. 1399 These instructions on how to set the parameters are only given as a 1400 possible method for selecting appropriate values, but network 1401 operators are free to set parameters as they choose. Appendix C goes 1402 into some more detail on linking the parameters defined here and the 1403 more conventional ways of expressing the mobility model in terms of 1404 distributions of times between events of various types. 1406 Recommended starting parameter values when specific network 1407 measurements have not been done are below. Note: there are no "one 1408 size fits all" default values and the ideal values vary based on 1409 network characteristics. It is not inherently necessary for the 1410 parameter values to be identical at all nodes, but it is recommended 1411 that similar values are used at all nodes within a PRoPHET zone as 1412 discussed in Section 2.1.2.1. 1414 +========================================+ 1415 | Parameter | Recommended value | 1416 +========================================+ 1417 | P_encounter_max | 0.7 | 1418 +----------------------------------------+ 1419 | P_encounter_first | 0.5 | 1420 +----------------------------------------+ 1421 | P_first_threshold | 0.1 | 1422 +----------------------------------------+ 1423 | alpha | 0.5 | 1424 +----------------------------------------+ 1425 | beta | 0.9 | 1426 +----------------------------------------+ 1427 | gamma | 0.999 | 1428 +----------------------------------------+ 1429 | delta | 0.01 | 1430 +========================================+ 1432 Figure 3: Default parameter settings 1434 3.4. Bundle Passing 1436 Upon reception of the Bundle Offer TLV, the node inspects the list of 1437 bundles and decides which bundles it is willing to store for future 1438 forwarding, or that it is able to deliver to their destination. This 1439 decision has to be made using local policies and considering 1440 parameters such as available buffer space and, if the node requested 1441 bundle lengths, the lengths of the offered bundles. For each such 1442 acceptable bundle, the node sends a Bundle Response TLV to its 1443 peering node, which in response to that sends the requested bundle. 1444 If a node has some bundles it would prefer to receive ahead of others 1445 offered (e.g., bundles that it can deliver to their final 1446 destination), it MAY request the bundles in that priority order. 1447 This is often desirable as there is no guarantee that the nodes will 1448 remain in contact with each other for long enough to transfer all the 1449 acceptable bundles. Otherwise, the node SHOULD assume that the 1450 bundles are listed in a priority order determined by the peering 1451 node's forwarding strategy, and request bundles in that order. 1453 3.4.1. Custody 1455 To free up local resources, a node may give custody of a bundle to 1456 another node that offers custody. This is done to move the 1457 retransmission requirement further toward the destination. The 1458 concept of custody transfer, and more details on the motivation for 1459 its use can be found in [RFC4838]. PRoPHET takes no responsibilities 1460 for making custody decisions. Such decisions should be made by a 1461 higher layer. 1463 3.5. When a Bundle Reaches its Destination 1465 When a bundle reaches its destination within the PRoPHET zone (i.e., 1466 within the part of the network where PRoPHET is used for routing; not 1467 necessarily the final destination of the bundle), a PRoPHET ACK for 1468 that bundle is issued. A PRoPHET ACK is a confirmation that a bundle 1469 has been delivered to its destination in the PRoPHET zone (bundles 1470 might traverse several different types of networks using different 1471 routing protocols; thus, this might not be the final destination of 1472 the bundle). When nodes exchange Bundle Offer TLVs, bundles that 1473 have been ACKed are also listed, having the "PRoPHET ACK" flag set. 1474 The node that receives this list updates its own list of ACKed 1475 bundles to be the union of its previous list and the received list. 1476 To prevent the list of ACKed bundles growing indefinitely, each 1477 PRoPHET ACK should have a timeout that MUST NOT be longer than the 1478 timeout of the bundle to which the ACK corresponds. 1480 When a node receives a PRoPHET ACK for a bundle it is carrying, it 1481 MAY delete that bundle from its storage, unless the node holds 1482 custody of that bundle. The PRoPHET ACK only indicates that a bundle 1483 has been delivered to its destination within the PRoPHET zone, so the 1484 reception of a PRoPHET ACK is not a guarantee that the bundle has 1485 been delivered to its final destination. 1487 Nodes MAY keep track of which nodes they have sent PRoPHET ACKs for 1488 certain bundles to, and MAY in that case refrain from sending 1489 multiple PRoPHET ACKs for the same bundle to the same node. 1491 If necessary in order to preserve system resources, nodes MAY drop 1492 PRoPHET ACKs prematurely, but SHOULD refrain from doing so if 1493 possible. 1495 It is important to keep in mind that PRoPHET ACKs and bundle 1496 ACKs[RFC5050] are different things. PRoPHET ACKs are only valid 1497 within the PRoPHET part of the network, while bundle ACKs are end-to- 1498 end acknowledgments that may go outside of the PRoPHET zone. 1500 3.6. Forwarding Strategies 1502 During the information exchange phase, nodes need to decide on which 1503 bundles they wish to exchange with the peering node. Because of the 1504 large number of scenarios and environments that PRoPHET can be used 1505 in, and because of the wide range of devices that may be used, it is 1506 not certain that this decision will be based on the same strategy in 1507 every case. Therefore, each node MUST operate a _forwarding 1508 strategy_ to make this decision. Nodes may define their own 1509 strategies, but this section defines a few basic forwarding 1510 strategies that nodes can use. Note: If the node being encountered 1511 is the destination of any of the bundles being carried, those bundles 1512 SHOULD be offered to the destination, even if that would violate the 1513 forwarding strategy. Some of the forwarding strategies listed here 1514 have been evaluated (together with a number of queueing policies) 1515 through simulations, and more information about that and 1516 recommendations on which strategies to use in different situations 1517 can be found in [lindgren_06]. If not chosen differently due to the 1518 characteristics of the deployment scenario, nodes SHOULD choose GRTR 1519 as the default forwarding strategy. 1521 The short names applied to the Forwarding Strategies should be read 1522 as mnemonic handles rather as specific acronyms for any set of words 1523 in the specification. 1525 We use the following notation in our descriptions below. A and B are 1526 the nodes that encounter each other, and the strategies are described 1527 as they would be applied by node A. The destination node is D. 1528 P_(X,Y) denotes the delivery predictability stored at node X for 1529 destination Y, and NF is the number of times A has given the bundle 1530 to some other node. 1532 GRTR 1533 Forward the bundle only if P_(B,D) > P_(A,D). 1535 When two nodes meet, a bundle is sent to the other node if the 1536 delivery predictability of the destination of the bundle is 1537 higher at the other node. The first node does not delete the 1538 bundle after sending it as long as there is sufficient buffer 1539 space available (since it might encounter a better node, or even 1540 the final destination of the bundle in the future). 1542 GTMX 1543 Forward the bundle only if P_(B,D) > P_(A,D) && NF < NF_max. 1545 This strategy is like the previous one, but each bundle is given 1546 to at most NF_max other nodes apart from the destination. 1548 GTHR 1549 Forward the bundle only if 1550 P_(B,D) > P_(A,D) OR P_(B,D) > FORW_thres, 1551 where FORW_thres is a threshold value, above which a bundle 1552 should always be given to the node unless it is already present 1553 at the other node. 1555 This strategy is similar to GRTR, but among nodes with very high 1556 delivery predictability, bundles for that particular destination 1557 are spread epidemically. 1559 GRTR+ 1560 Forward the bundle only if Equation 5 holds, where P_max is the 1561 largest delivery predictability reported by a node to which the 1562 bundle has been sent so far. 1564 P_(B,D) > P_(A,D) && P_(B,D) > P_max (5) 1566 This strategy is like GRTR, but nodes keep track of the largest 1567 delivery predictability of any node it has forwarded this bundle 1568 to, and only forward the bundle again if the currently 1569 encountered node has a greater delivery predictability than the 1570 maximum previously encountered. 1572 GTMX+ 1573 Forward the bundle only if Equation 6 holds. 1575 P_(B,D) > P_(A,D) && P_(B,D) > P_max && NF < NF_max (6) 1577 This strategy is like GTMX, but nodes keep track of P_max as in 1578 GRTR+. 1580 GRTRSort 1581 Select bundles in descending order of the value of 1582 P_(B,D) - P_(A,D). 1583 Forward the bundle only if P_(B,D) > P_(A,D). 1585 This strategy is like GRTR, but instead of just going through 1586 the bundle queue linearly, this strategy looks at the difference 1587 in delivery predictabilities for each bundle between the two 1588 nodes, and forwards the bundles with the largest difference 1589 first. As bandwidth limitations or disrupted connections may 1590 result in not all bundles that would be desirable being 1591 exchanged, it could be desirable to first send bundles that get 1592 a large improvement in delivery predictability. 1594 GRTRMax 1595 Select bundles in descending order of P_(B,D). 1596 Forward the bundle only if P_(B,D) > P_(A,D). 1598 This strategy begins by considering the bundles for which the 1599 encountered node has the highest delivery predictability. The 1600 motivation for doing this is the same as in GRTRSort, but based 1601 on the idea that it is better to give bundles to nodes with high 1602 absolute delivery predictabilities, instead of trying to 1603 maximize the improvement. 1605 3.7. Queueing Policies 1607 Because of limited buffer resources, nodes may need to drop some 1608 bundles. As is the case with the forwarding strategies, which bundle 1609 to drop is also dependent on the scenario. Therefore, each node MUST 1610 also operate a queueing policy that determines how its bundle queue 1611 is handled. This section defines a few basic queueing policies, but 1612 nodes MAY use other policies if desired. Some of the queueing 1613 policies listed here have been evaluated (together with a number of 1614 forwarding strategies) through simulations. More information about 1615 that and recommendations on which policies to use in different 1616 situations can be found in [lindgren_06]. If not chosen differently 1617 due to the characteristics of the deployment scenario, nodes SHOULD 1618 choose FIFO as the default queueing policy. 1620 The short names applied to the Queueing Policies should be read as 1621 mnemonic handles rather as specific acronyms for any set of words in 1622 the specification. 1624 FIFO 1625 Handle the queue in a First In First Out (FIFO) order. 1627 The bundle that was first entered into the queue is the first 1628 bundle to be dropped. 1630 MOFO - Evict most forwarded first 1631 In an attempt to maximize the delivery rate of bundles, this 1632 policy requires that the routing agent keeps track of the number 1633 of times each bundle has been forwarded to some other node. The 1634 bundle that has been forwarded the largest number of times is 1635 the first to be dropped. 1637 MOPR - Evict most favorably forwarded first 1638 Keep a variable FAV for each bundle in the queue, initialized to 1639 zero. Each time the bundle is forwarded, update FAV according 1640 to Equation 7, where P is the predictability metric the node the 1641 bundle is forwarded to has for its destination. 1643 FAV_new = FAV_old + ( 1 - FAV_old ) * P (7) 1645 The bundle with the highest FAV value is the first to be 1646 dropped. 1648 Linear MOPR - Evict most favorably forwarded first; linear increase 1649 Keep a variable FAV for each bundle in the queue, initialized to 1650 zero. Each time the bundle is forwarded, update FAV according 1651 to Equation 8, where P is the predictability metric the node the 1652 bundle is forwarded to has for its destination. 1654 FAV_new = FAV_old + P (8) 1656 The bundle with the highest FAV value is the first to be 1657 dropped. 1659 SHLI - Evict shortest life time first 1660 As described in [RFC5050], each bundle has a timeout value 1661 specifying when it no longer is meaningful to its application 1662 and should be deleted. Since bundles with short remaining time 1663 to life will soon be dropped anyway, this policy decides to drop 1664 the bundle with the shortest remaining life time first. To 1665 successfully use a policy like this, there needs to be some form 1666 of time synchronization between nodes so that it is possible to 1667 know the exact lifetimes of bundles. This is however not 1668 specific to this routing protocol, but a more general DTN 1669 problem. 1671 LEPR - Evict least probable first 1672 Since the node is least likely to deliver a bundle for which it 1673 has a low delivery predictability, drop the bundle for which the 1674 node has the lowest delivery predictability, and that has been 1675 forwarded at least MF times, which is a minimum number of 1676 forwards that a bundle must have been forwarded before being 1677 dropped (if such a bundle exists). 1679 More than one queueing policy MAY be combined in an ordered set, 1680 where the first policy is used primarily, the second only being used 1681 if there is a need to tie-break between bundles given the same 1682 eviction priority by the primary policy, and so on. As an example, 1683 one could select the queueing policy to be {MOFO; SHLI; FIFO}, which 1684 would start by dropping the bundle that has been forwarded the 1685 largest number of times. If more than one bundle has been forwarded 1686 the same number of times, the one with the shortest remaining life 1687 time will be dropped, and if that also is the same, the FIFO policy 1688 will be used to drop the bundle first received. 1690 It is worth noting that obviously nodes MUST NOT drop bundles for 1691 which it has custody unless the lifetime expires. 1693 4. Message Formats 1695 This section defines the message formats of the PRoPHET routing 1696 protocol. In order to allow for variable length fields, many numeric 1697 fields are encoded as Self-Delimiting Numeric Values (SDNVs). The 1698 format of SDNVs is defined in [RFC5050]. Since many of the fields 1699 are coded as SDNVs the size and alignment of fields indicated in many 1700 of the specification diagrams below are indicative rather than 1701 prescriptive. Where SDNVs and/or text strings are used, the octets 1702 of the fields will be packed as closely as possible with no 1703 intervening padding between fields. 1705 Explicit length fields are specified for all variable length string 1706 fields. Accordingly, strings are not null-terminated and just 1707 contain the exact set of octets in the string. 1709 The basic message format shown in Figure 4 consists of a header (see 1710 Section 4.1) followed by a sequence of one or more Type-Length-Value 1711 components (TLVs) taken from the specifications in Section 4.2 1713 0 1 2 3 1714 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1716 | | 1717 ~ Header ~ 1718 | | 1719 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1720 | | 1721 ~ TLV 1 ~ 1722 | | 1723 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1724 | . | 1725 ~ . ~ 1726 | . | 1727 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1728 | | 1729 ~ TLV n ~ 1730 | | 1731 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1733 Figure 4: Basic PRoPHET Message Format 1735 4.1. Header 1737 0 1 2 3 1738 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1739 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1740 |Protocol Number|Version| Flags | Result | Code | 1741 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1742 | Receiver Instance | Sender Instance | 1743 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1744 | Transaction Identifier | 1745 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1746 |S| SubMessage Number | Length (SDNV) | 1747 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1748 | | 1749 ~ Message Body ~ 1750 | | 1751 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1753 Figure 5: PRoPHET Message Header 1755 Protocol Number 1756 The DTN Routing Protocol Number encoded as 8 bit unsigned 1757 integer in network bit order. The value of this field is 0. 1758 The PRoPHET header is organized in this way so that in principle 1759 PRoPHET messages could be sent as the Protocol Data Unit of an 1760 IP packet if an IP protocol number was allocated for PRoPHET. 1761 At present PRoPHET is only specified to use a TCP transport for 1762 carriage of PRoPHET packets so that the protocol number serves 1763 only to identify the PRoPHET protocol within DTN. Transmitting 1764 PRoPHET packets directly as an IP protocol on a public IP 1765 network such as the Internet would generally not work well 1766 because middle boxes such as firewalls and NAT boxes would be 1767 unlikely to allow the protocol to pass through and the protocol 1768 does not provide any congestion control. However it could be so 1769 used on private networks for experimentation or in situations 1770 where all communications are between isolated pairs of nodes. 1771 Also in future other protocols that require transmission of 1772 metadat between DTN nodes could potentially use the same format 1773 and protocol state machinery but with a different Protocol 1774 Number. 1776 Version 1777 The Version of the PRoPHET Protocol. Encoded as a four bit 1778 unsigned integer in network bit order. This document defines 1779 version 2. 1781 Flags 1782 Reserved field of 4 bits. 1784 Result 1785 Field that is used to indicate whether a response is required to 1786 the request message if the outcome is successful. A value of 1787 "NoSuccessAck" indicates that the request message does not 1788 expect a response if the outcome is successful, and a value of 1789 "AckAll" indicates that a response is expected if the outcome is 1790 successful. In both cases a failure response MUST be generated 1791 if the request fails. If running over a TCP transport or 1792 similar protocol that offers reliable in order delivery, 1793 deployments MAY choose not to send "Success" responses when an 1794 outcome is successful. To achieve this the Result field is set 1795 to the "NoSuccessAck" value in all request messages. 1797 In a response message, the result field can have two values: 1798 "Success," and "Failure". The "Success" results indicates a 1799 success response. All messages that belong to the same success 1800 response will have the same Transaction Identifier. The 1801 "Success" result indicates a success response that may be 1802 contained in a single message or the final message of a success 1803 response spanning multiple messages. 1805 ReturnReceipt is a value of the result field used to indicate 1806 that an acknowledgement is required for the message. The 1807 default for Messages is that the controller will not acknowledge 1808 responses. In the case where an acknowledgement is required, it 1809 will set the Result Field to ReturnReceipt in the header of the 1810 Message. 1812 The result field is encoded as an 8 bit unsigned integer in 1813 network bit order. The following values are currently defined: 1815 NoSuccessAck: Result = 1 1816 AckAll: Result = 2 1817 Success: Result = 3 1818 Failure: Result = 4 1819 ReturnReceipt Result = 5 1821 Code 1822 This field gives further information concerning the result in a 1823 response message. It is mostly used to pass an error code in a 1824 failure response but can also be used to give further 1825 information in a success response message or an event message. 1826 In a request message, the code field is not used and is set to 1827 zero. 1829 If the Code field indicates that the Error TLV is included in 1830 the message, further information on the error will be found in 1831 the Error TLV, which MUST be the the first TLV after the header. 1833 The Code field is encoded as an 8 bit unsigned integer in 1834 network bit order. Separate number code spaces are used for 1835 success and failure response messages. In each case a range of 1836 values is provided reserved for use in specifications and 1837 another range for private and experimental use. For success 1838 messages the following values are defined: 1840 Generic Success 0x00 1841 Submessage Received 0x01 1842 Reserved 0x02 - 0x7F 1843 Private/Experimental Use 0x80 - 0xFF 1845 The Submessage Received code is used to acknowledge reception of 1846 a message segment. The Generic Success code is used to 1847 acknowledge receipt of a complete message and successful 1848 processing of the contents. 1850 For failure messages, the following values are defined: 1852 Reserved 0x00 - 0x01 1853 Unspecified Failure 0x02 1854 Reserved 0x03 - 0x7F 1855 Private/Experimental Use 0x80 - 0xFE 1856 Error TLV in message 0xFF 1858 The Unspecified Failure code can be used to report a failure for 1859 which there is no more specific code or Error TLV value defined. 1861 Sender Instance 1862 For messages during the Hello phase with the Hello SYN, Hello 1863 SYNACK, and Hello ACK functions (which are explained in 1864 Section 5.2), it is the sender's instance number for the link. 1865 It is used to detect when the link comes back up after going 1866 down or when the identity of the entity at the other end of the 1867 link changes. The instance number is a 16-bit number that is 1868 guaranteed to be unique within the recent past and to change 1869 when the link or node comes back up after going down. Zero is 1870 not a valid instance number. For the RSTACK function (also 1871 explained in detail in Section 5.2), the Sender Instance field 1872 is set to the value of the Receiver Instance field from the 1873 incoming message that caused the RSTACK function to be 1874 generated. Messages sent after the Hello phase is completed 1875 should use the sender's instance number for the link. The 1876 Sender Instance is encoded as a 16 bit unsigned integer in 1877 network bit order. 1879 Receiver Instance 1880 For messages during the Hello phase with the Hello SYN, Hello 1881 SYNACK, and Hello ACK functions, is what the sender believes is 1882 the current instance number for the link, allocated by the 1883 entity at the far end of the link. If the sender of the message 1884 does not know the current instance number at the far end of the 1885 link, this field MUST be set to zero. For the RSTACK message, 1886 the Receiver Instance field is set to the value of the Sender 1887 Instance field from the incoming message that caused the RSTACK 1888 message to be generated. Messages sent after the Hello phase is 1889 completed should use what the sender believes is the current 1890 instance number for the link, allocated by the entity at the far 1891 end of the link. The Sender Instance is encoded as a 16 bit 1892 unsigned integer in network bit order. 1894 Transaction Identifier 1895 Used to associate a message with its response message. This 1896 should be set in request messages to a value that is unique for 1897 the sending host within the recent past. Reply messages contain 1898 the Transaction Identifier of the request they are responding 1899 to. The Transaction Identifier is a 32 bit bit pattern. 1901 S-flag 1902 If S is set (value 1) then the SubMessage Number field indicates 1903 the total number of SubMessage segments that compose the entire 1904 message. If it is not set (value 0) then the SubMessage Number 1905 field indicates the sequence number of this SubMessage segment 1906 within the whole message. the S field will only be set in the 1907 first sub-message of a sequence. 1909 SubMessage Number 1910 When a message is segmented because it exceeds the MTU of the 1911 link layer or otherwise, each segment will include a SubMessage 1912 Number to indicate its position. Alternatively, if it is the 1913 first sub-message in a sequence of sub-messages, the S flag will 1914 be set and this field will contain the total count of SubMessage 1915 segments. The SubMessage Number is encoded as a 15-bit unsigned 1916 integer in network bit order. The SubMessage number is zero- 1917 based, i.e., for a message divided into n sub-messages, they are 1918 numbered from 0 to (n - 1). For a message that it is not 1919 divided into sub-messages the single message has the S-flag 1920 cleared (0) and the SubMessage Number is set to 0 (zero). 1922 Length 1923 Length in octets of this message including headers and message 1924 body. If the message is fragmented, this field contains the 1925 length of this SubMessage. The Length is encoded as an SDNV. 1927 Message Body 1928 As specified in Section 4, the Message Body consists of a 1929 sequence of one or more of the TLVs specified in Section 4.2. 1931 The protocol also requires extra information about the link that the 1932 underlying communication layer MUST provide. This information is 1933 used in the Hello procedure described in more detail in Section 5.2. 1934 Since this information is available from the underlying layer, there 1935 is no need to carry it in PRoPHET messages. The following values are 1936 defined to be provided by the underlying layer: 1938 Sender Local Address 1939 An address used by the underlying communication layer as 1940 described in Section 2.4 that identifies the sender address of 1941 the current message. This address must be unique among the 1942 nodes that can currently communicate, and is only used in 1943 conjunction with the Receiver Local Address and the Receiver 1944 Instance and Sender Instance to identify a communicating pair of 1945 nodes. 1947 Receiver Local Address 1948 An address used by the underlying communication layer as 1949 described in Section 2.4 that identifies the receiver address of 1950 the current message. This address must be unique among the 1951 nodes that can currently communicate, and is only used in 1952 conjunction with the Sender Local Address and the Receiver 1953 Instance and Sender Instance to identify a communicating pair of 1954 nodes. 1956 When PRoPHET is run over TCP, the IP addresses of the communicating 1957 nodes are used as Sender and Receiver Local Addresses. 1959 4.2. TLV Structure 1961 All TLVs have the following format, and can be nested. 1963 0 1 2 3 1964 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 1965 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1966 | TLV Type | TLV Flags | TLV Length (SDNV) | 1967 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1968 | | 1969 ~ TLV Data ~ 1970 | | 1971 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1973 Figure 6: TLV Format 1975 TLV Type 1976 Specific TLVs are defined in Section 4.3. The TLV Type is 1977 encoded as an 8 bit unsigned integer in network bit order. Each 1978 TLV will have fields defined that are specific to the function 1979 of that TLV. 1981 TLV Flags 1982 These are defined per TLV type. Flag n corresponds to bit 15-n 1983 in the TLV. Any flags which are specified as reserved in 1984 specific TLVs SHOULD be transmitted as 0 and ignored on receipt. 1986 TLV Length 1987 Length of the TLV in octets, including the TLV header and any 1988 nested TLVs. Encoded as an SDNV. Note that TLVs are not padded 1989 to any specific alignment unless explicitly required in the 1990 description of the TLV. No TLVs in this document specify any 1991 padding. 1993 4.3. TLVs 1995 This section describes the various TLVs that can be used in PRoPHET 1996 messages. 1998 4.3.1. Hello TLV 2000 The Hello TLV is used to set up and maintain a link between two 2001 PRoPHET nodes. Hello messages with the SYN function are transmitted 2002 periodically as beacons or keep alives. The Hello TLV is the first 2003 TLV exchanged between two PRoPHET nodes when they encounter each 2004 other. No other TLVs can be exchanged until the first Hello sequence 2005 is completed. 2007 Once a communication link is established between two PRoPHET nodes, 2008 the Hello TLV will be sent once for each interval as defined in the 2009 interval timer. If a node experiences the lapse of HELLO_DEAD Hello 2010 intervals without receiving a Hello TLV on a connection in the 2011 INFO_EXCH state (as defined in the state machine in Section 5.1), the 2012 connection SHOULD be assumed broken. 2014 0 1 2 3 2015 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2016 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2017 | TLV Type=0x01 |L| Resv | HF | TLV Length (SDNV) | 2018 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2019 | Timer (SDNV) |EID Length,SDNV| Sender EID (variable length) | 2020 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2022 Figure 7: Hello TLV Format 2024 TLV Flags 2025 The TLV Flags field contains two single bit flags (S and L) and 2026 a three bit Hello Function (HF) number that specifies one of 2027 four functions for the Hello TLV. The remaining three bits 2028 (Resv) are unused and reserved: 2030 HF 2031 TLV Flags bits 0, 1, and 2 are treated as an unsigned 3 bit 2032 integer coded in network bit order. The value of the 2033 integer specifies the Hello Function (HF) of the Hello TLV. 2034 Four functions are specified for the Hello TLV. 2036 The encoding of the Hello Function is: 2038 SYN: HF = 1 2039 SYNACK: HF = 2 2040 ACK: HF = 3 2041 RSTACK: HF = 4 2043 The remaining values (0, 5, 6 and 7) are unused and 2044 reserved. If a Hello TLV with any of these values is 2045 received, the link should be reset. 2047 Resv 2048 TLV Flags bits 3, 4, 5, and 6 are reserved. They SHOULD be 2049 set to 0 on transmission and ignored on reception. 2051 L 2052 The L bit flag (TLV Flags bit 7) is set (1) to request that 2053 the Bundle Offer TLV sent during the Information Exchange 2054 phase contains bundle payload lengths for all bundles, 2055 rather than only for bundle fragments if the L flag is 2056 cleared (0), when carried in a Hello TLV with Hello 2057 Function SYN or SYNACK. The flag is ignored for other 2058 Hello Function values. 2060 TLV Data 2062 Timer 2063 The Timer field is used to inform the receiver of the timer 2064 value used in the Hello processing of the sender. The 2065 timer specifies the nominal time between periodic Hello 2066 messages. It is a constant for the duration of a session. 2067 The timer field is specified in units of 100ms and is 2068 encoded as an SDNV. 2070 EID Length 2071 The EID Length field is used to specify the length of the 2072 Sender EID field in octets. If the Endpoint Identifier 2073 (EID) has already been sent at least once in a message with 2074 the current Sender Instance, a node MAY choose to set this 2075 field to zero, omitting the Sender EID from the Hello TLV. 2076 The EID Length is encoded as an SDNV and the field is thus 2077 of variable length. 2079 Sender EID 2080 The Sender EID field specifies the DTN endpoint identifier 2081 (EID) of the sender that is to be used in updating routing 2082 information and making forwarding decisions. If a node has 2083 multiple EIDs, one should be chosen for PRoPHET routing. 2084 This field is of variable length. 2086 4.3.2. Error TLV 2088 0 1 2 3 2089 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2090 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2091 | TLV type=0x02 | TLV Flags | TLV Length (SDNV) | 2092 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2093 | | 2094 ~ TLV Data ~ 2095 | | 2096 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2098 Figure 8: Error TLV Format 2100 TLV Flags 2101 For Error TLVs the TLV Flags field carries an identifier for the 2102 Error TLV type as an 8 bit unsigned integer encoded in network 2103 bit order. A range of values is available for private and 2104 experimental use in addition to the values defined here. The 2105 following Error TLV types are defined: 2107 Dictionary Conflict 0x00 2108 Bad String ID 0x01 2109 Reserved 0x02 - 0x7F 2110 Private/Experimental Use 0x80 - 0xFF 2112 TLV Data 2113 The contents and interpretation of the TLV Data field are 2114 specific to the type of Error TLV. For the Error TLVs defined 2115 in this document the TLV Data is defined as follows: 2117 Dictionary Conflict 2118 The TLV Data consists of the String ID causing the conflict 2119 encoded as an SDNV followed by the Endpoint Identifier 2120 string that conflicts with the previously installed value. 2121 The Endpoint Identifier is NOT null terminated. The length 2122 of the Endpoint Identifier can be determined by subtracting 2123 the length of the TLV Header and the length of the SDNV 2124 containing the String ID. 2126 Bad String ID 2127 The TLV Data consists of the String ID that is not found in 2128 the dictionary encoded as an SDNV. 2130 4.3.3. Routing Information Base Dictionary TLV 2132 The Routing Information Base Dictionary includes the list of endpoint 2133 identifiers used in making routing decisions. The referents remain 2134 constant for the duration of a session over a link where the instance 2135 numbers remain the same and can be used by both the Routing 2136 Information Base messages and the bundle offer/response messages. 2137 The dictionary is a shared resource (see Section 3.2.1) built in each 2138 of the paired peers from the contents of one or more incoming TLVs of 2139 this type and the information used to create outgoing TLVs of this 2140 type. 2142 0 1 2 3 2143 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2144 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2145 | TLV type=0xA0 | TLV Flags | TLV Length (SDNV) | 2146 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2147 | RIBD Entry Count (SDNV) | 2148 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2149 ~ ~ 2150 ~ Variable Length Routing Address Strings ~ 2151 ~ ~ 2152 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2154 ~ Routing Address String 1 ~ 2156 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2157 | String ID 1 (SDNV) | Length (SDNV) | 2158 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2159 ~ Endpoint Identifier 1 (variable length) ~ 2160 | | 2161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2162 | . | 2163 ~ Routing Address String n . ~ 2164 | . | 2165 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2166 | String ID n (SDNV) | Length (SDNV) | 2167 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2168 | | 2169 ~ Endpoint Identifier n (variable length) ~ 2170 | | 2171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2173 Figure 9: Routing Information Base Dictionary TLV Format 2175 TLV Flags 2176 The encoding of the Header flag field relates to the 2177 capabilities of the Source node sending the RIB Dictionary: 2179 Flag 0: Sent by Listener 0b1 2180 Flag 1: Reserved 0b1 2181 Flag 2: Reserved 0b1 2182 Flag 3: Reserved 0b1 2183 Flag 4: Reserved 0b1 2184 Flag 5: Reserved 0b1 2185 Flag 6: Reserved 0b1 2186 Flag 7: Reserved 0b1 2188 The Sent by Listener flag is set to 0 if this TLV was sent by a 2189 node in the Initiator role and set to 1 if this TLV was sent by 2190 a node in the Listener role (see Section 3.2 for explanations of 2191 these roles). 2193 TLV Data 2195 RIBD Entry Count 2196 Number of entries in the database. Encoded as SDNV. 2198 String ID 2199 SDNV identifier that is constant for the duration of a 2200 session. String ID zero is predefined as the node 2201 initiating the session through sending the Hello SYN 2202 message, and String ID one is predefined as the node 2203 responding with the Hello SYNACK message. These entries do 2204 not need to be sent explicitly as the EIDs are exchanged 2205 during the Hello procedure. 2207 In order to ensure that the String IDs originated by the 2208 two peers do not conflict, the String IDs generated in the 2209 node that sent the Hello SYN message MUST have their least 2210 significant bit set to 0 (i.e., are even numbers) and the 2211 String IDs generated in the node that responded with the 2212 Hello SYNACK message MUST have their least significant bit 2213 set to 1 (i.e., they are odd numbers). 2215 Length 2216 Length of Endpoint Identifier in this entry. Encoded as 2217 SDNV. 2219 Endpoint Identifier 2220 Text string representing the Endpoint Identifier. Note 2221 that it is NOT null terminated as the entry contains the 2222 length of the identifier. 2224 4.3.4. Routing Information Base TLV 2226 The Routing Information Base lists the destinations (endpoints) a 2227 node knows of, and the delivery predictabilities it has associated 2228 with them. This information is needed by the PRoPHET algorithm to 2229 make decisions on routing and forwarding. 2231 0 1 2 3 2232 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2234 | TLV Type=0xA1 | TLV Flags | TLV Length (SDNV) | 2235 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2236 | RIB String Count (SDNV) | 2237 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2238 | RIBD String ID 1 (SDNV) | P-Value | 2239 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2240 | RIB Flags 1 | . ~ 2241 +-+-+-+-+-+-+-+-+ . ~ 2242 ~ . ~ 2243 ~ . ~ 2244 ~ . ~ 2245 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2246 | RIBD String ID n (SDNV) | P-Value | 2247 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2248 | RIB Flags n | 2249 +-+-+-+-+-+-+-+-+ 2251 Figure 10: Routing Information Base TLV Format 2253 TLV Flags 2254 The encoding of the Header flag field relates to the 2255 capabilities of the Source node sending the RIB: 2257 Flag 0: More RIB TLVs 0b1 2258 Flag 1: Reserved 0b1 2259 Flag 2: Reserved 0b1 2260 Flag 3: Reserved 0b1 2261 Flag 4: Reserved 0b1 2262 Flag 5: Reserved 0b1 2263 Flag 6: Reserved 0b1 2264 Flag 7: Reserved 0b1 2266 The "More RIB TLVs" flag is set to 1 if the RIB requires more 2267 TLVs to be sent in order to be fully transferred. This flag is 2268 set to 0 if this is the final TLV of this RIB. 2270 TLV Data 2272 RIB String Count 2273 Number of routing entries in the TLV. Encoded as SDNV. 2275 RIBD String ID 2276 String ID of the endpoint identifier of the destination for 2277 which this entry specifies the delivery predictability as 2278 predefined in a dictionary TLV. Encoded as SDNV. 2280 P-value 2281 Delivery predictability for the destination of this entry 2282 as calculated from previous encounters according to the 2283 equations in Section 2.1.2, encoded as a 16-bit unsigned 2284 integer. The encoding of this field is a linear mapping 2285 from [0,1] to [0, 0xFFFF] (e.g., for a P-value of 0.75, the 2286 mapping would be 0.75*65535=49151=0xBFFF; thus the P-value 2287 would be encoded as 0xBFFF). 2289 RIB Flag 2290 The encoding of the 8 bit RIB Flag field is: 2292 Flag 0: Reserved 0b1 2293 Flag 1: Reserved 0b1 2294 Flag 2: Reserved 0b1 2295 Flag 3: Reserved 0b1 2296 Flag 4: Reserved 0b1 2297 Flag 5: Reserved 0b1 2298 Flag 6: Reserved 0b1 2299 Flag 7: Reserved 0b1 2301 4.3.5. Bundle Offer and Response TLVs (Version 2) 2303 After the routing information has been passed, the node will ask the 2304 other node to review available bundles and determine which bundles it 2305 will accept for relay. The source relay will determine which bundles 2306 to offer based on relative delivery predictabilities as explained in 2307 Section 3.6. 2309 Note: The original versions of these TLVs (TLV Types 0xA2 and 2310 0xA3) used in verion 1 of the PRoPHET protocol have been 2311 deprecated as they did not contain the complete information 2312 needed to uniquely identify bundles and could not handle bundle 2313 fragments. 2315 Depending on the bundles stored in the offering node, the Bundle 2316 Offer TLV might contain descriptions of both complete bundles and 2317 bundle fragments. In order to correctly identify bundle fragments, a 2318 bundle fragment descriptor MUST contain the offset of the payload 2319 fragment in the bundle payload and the length of the payload 2320 fragment. If requested by the receiving node by setting the L flag 2321 in the SYN or SYNACK message during the neighbor awareness phase, the 2322 offering node MUST include the length of the payload in the 2323 descriptor for complete bundles. The appropriate flags MUST be set 2324 in the B_flags for the descriptor to indicate if the descriptor 2325 contains the payload length field (set for fragments in all cases and 2326 for complete bundles if the L flag was set) and if the descriptor 2327 contains a payload offset field (fragments only). 2329 The Bundle Offer TLV also lists the bundles that a PRoPHET 2330 acknowledgement has been issued for. Those bundles have the PRoPHET 2331 ACK flag set in their entry in the list. When a node receives a 2332 PRoPHET ACK for a bundle, it SHOULD, if possible, signal to the 2333 bundle agent that this bundle is no longer required for transmission 2334 by PRoPHET. Despite no longer transmitting the bundle, it SHOULD 2335 keep an entry of the acknowledged bundle to be able to further 2336 propagate the PRoPHET ACK. 2338 The Response TLV format is identical to the Offer TLV with the 2339 exception of the TLV Type field. Bundles that are being accepted 2340 from the corresponding Offer are explicitly marked with a B_flag. 2341 Specifications for bundles that are not being accepted MAY either be 2342 omitted or left in but not marked as accepted. The payload length 2343 field MAY be omitted for complete bundles in the Response message 2344 even if it was included in the Offer message. The B_flags payload 2345 length flag MUST be set correctly to indicate if the length field is 2346 included or not. The Response message MUST include both payload 2347 offset and payload length fields for bundle fragments, and the 2348 B_flags MUST be set to indicate that both are present. 2350 0 1 2 3 2351 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2352 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2353 | TLV Type | TLV Flags | TLV Length (SDNV) | 2354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2355 | Bundle Offer Count (SDNV) | 2356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2357 | B_flags | Bundle Source | Bundle Destination | 2358 | | String Id 1 (SDNV) | String Id 1 (SDNV) | 2359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2360 | Bundle 1 Creation Timestamp Time | 2361 | (SDNV) | 2362 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2363 | Bundle 1 Creation Timestamp Sequence Number | 2364 | (SDNV) | 2365 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2366 | Bundle 1 Payload Offset - only present if bundle is a fragment| 2367 | (SDNV) | 2368 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2369 | Bundle 1 Payload Length - only present if bundle is a fragment| 2370 | or transmission of length requested (SDNV) | 2371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2372 ~ . ~ 2373 ~ . ~ 2374 ~ . ~ 2375 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2376 | B_flags | Bundle Source | Bundle Destination | 2377 | | String Id n (SDNV) | String Id n (SDNV) | 2378 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2379 | Bundle n Creation Timestamp Time | 2380 | (SDNV) | 2381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2382 | Bundle n Creation Timestamp Sequence Number | 2383 | (SDNV) | 2384 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2385 | Bundle n Payload Offset - only present if bundle is a fragment| 2386 | (SDNV) | 2387 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2388 | Bundle n Payload Length - only present if bundle is a fragment| 2389 | or transmission of length requested (SDNV) | 2390 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 2392 Figure 11: Bundle Offer and Response TLV Format 2394 TLV Type 2395 The TLV Type for a Bundle Offer is 0xA4. The TLV Type for a 2396 Bundle Response is 0xA5. 2398 TLV Flags 2399 The encoding of the Header flag field relates to the 2400 capabilities of the Source node sending the RIB: 2402 Flag 0: More Offer/Response 2403 TLVs Following 0b1 2404 Flag 1: Reserved 0b1 2405 Flag 2: Reserved 0b1 2406 Flag 3: Reserved 0b1 2407 Flag 4: Reserved 0b1 2408 Flag 5: Reserved 0b1 2409 Flag 6: Reserved 0b1 2410 Flag 7: Reserved 0b1 2412 If the Bundle Offers or Bundle Responses are divided between 2413 several TLVs, the More Offer/Response TLVs Following flag MUST 2414 be set to 1 in all but the last TLV in the sequence where it 2415 MUST be set to 0. 2417 TLV Data 2419 Bundle Offer Count 2420 Number of bundle offer/response entries. Encoded as an 2421 SDNV. Note that 0 is an acceptable value. In particular a 2422 Bundle Response TLV with 0 entries is used to signal that a 2423 cycle of information exchange and bundle passing is 2424 completed. 2426 B-Flags 2427 The encoding of the B_Flags is: 2429 Flag 0: Bundle Accepted 0b1 2430 Flag 1: Bundle is a Fragment 0b1 2431 Flag 2: Bundle Payload Length 2432 included in TLV 0b1 2433 Flag 3: Reserved 0b1 2434 Flag 4: Reserved 0b1 2435 Flag 5: Reserved 0b1 2436 Flag 6: Reserved 0b1 2437 Flag 7: PRoPHET ACK 0b1 2439 Bundle Source String Id 2440 String ID of the source EID of the bundle as predefined in 2441 a dictionary TLV. Encoded as an SDNV. 2443 Bundle Destination String Id 2444 String ID of the destination EID of the bundle as 2445 predefined in a dictionary TLV. Encoded as an SDNV. 2447 Bundle Creation Timestamp Time 2448 Time component of the Bundle Creation Timestamp for the 2449 bundle. Encoded as an SDNV. 2451 Bundle Creation Timestamp Sequence Number 2452 Sequence Number component of the Bundle Creation Timestamp 2453 for the bundle. Encoded as an SDNV. 2455 Bundle Payload Offset 2456 Only included if the bundle is a fragment and the fragment 2457 bit is set (value 1) in the bundle B_flags. Offset of the 2458 start of the fragment payload in the complete bundle 2459 payload. Encoded as an SDNV. 2461 Bundle Payload Length 2462 Only included if the bundle length included bit is set 2463 (value 1) in the bundle B_flags. Length of the payload in 2464 the bundle specified. This is either the total payload 2465 length if the bundle is a complete bundle or the bundle 2466 fragment payload length if the bundle is a fragment. 2467 Encoded as an SDNV. 2469 5. Detailed Operation 2471 In this section, some more details on the operation of PRoPHET are 2472 given along with state tables to help in implementing the protocol. 2474 As explained in Section 1.2. it is RECOMMENDED that "Success" 2475 responses should not be requested or sent when operating over a 2476 reliable, in order transport protocol such as TCP. If in future 2477 PRoPHET was operated over an unreliable transport protocol, positive 2478 acknowledgements would be necessary to signal successful delivery of 2479 (sub)messages. In this section the phrase "send a message" should be 2480 read as *successful* sending of a message, signaled by receipt of the 2481 appropriate "Success" response if running over an unreliable 2482 protocol, but guaranteed by TCP or other reliable protocol otherwise. 2483 Hence the state descriptions below do not explicitly mention positive 2484 acknowledgements, whether they are being sent or not. 2486 5.1. High Level State Tables 2488 This section gives high level state tables for the operation of 2489 PRoPHET. The following sections will describe each part of the 2490 operation in more detail (including state tables for the internal 2491 states of those procedures). 2493 The following main or high level states are used in the state tables: 2495 WAIT_NB This is the state all nodes start in. Nodes remain in this 2496 state until they are notified that a new neighbor is available. 2497 At that point, the hello procedure should be started with the 2498 new neighbor, and the node transitions into the HELLO state. 2499 Nodes SHOULD be able to handle multiple neighbors in parallel, 2500 maintaining separate state machines for each neighbor. This 2501 could be handled by creating a new thread or process during the 2502 transition to the HELLO state that then takes care of the 2503 communication with the new neighbor while the parent remains in 2504 state WAIT_NB waiting for additional neighbors to communicate. 2505 In this case when the neighbor can no longer be communicated 2506 with (described as 'neighbor gone' in the tables below), the 2507 thread or process created is destroyed and, when a connection 2508 oriented protocol is being used to communicate with the 2509 neighbor, the connection is closed. The current version of the 2510 protocol is specified to use TCP for neighbor connections so 2511 that these will be closed when the neighbor is no longer 2512 accessible. 2514 HELLO Nodes are in the HELLO state from when a new neighbor is 2515 detected until the Hello procedure is completed and a link is 2516 established (which happens when the Hello procedure enters the 2517 ESTAB state as described in Section 5.2 - during this 2518 procedure, the states ESTAB, SYNSENT, and SYNRCVD will be used, 2519 but these are internal to the Hello procedure and are not 2520 listed here). If the node is notified that the neighbor is no 2521 longer in range before a link has been established, it returns 2522 to the WAIT_NB state and, if appropriate, any additional 2523 process or thread created to handle the neighbor MAY be 2524 destroyed. 2526 INFO_EXCH After a link has been set up by the Hello procedure, the 2527 node transitions to the INFO_EXCH state in which the 2528 information exchange and bundle passing are done. The node 2529 remains in this state as long as Information Exchange Phase 2530 TLVs (Routing RIB, Routing RIB Dictionary) and bundle passing 2531 TLVs (Bundle Offer, Bundle Response) are being received. If 2532 the node is notified that the neighbor is no longer in range 2533 before all information and bundles have been exchanged, any 2534 associated connection is closed and the node returns to the 2535 WAIT_NB state to await new neighbors. 2537 In the INFO_EXCH state the nodes at both ends of the 2538 established link are able to update their delivery 2539 predictability information using data from the connected peer 2540 and then make offers of bundles for exchange which may be 2541 accepted or not by the peer. To manage these processes, each 2542 node acts both as an Initiator and a Listener for the 2543 information exchange and bundle passing processes, maintaining 2544 subsidiary state machines for the two roles. The Initiator and 2545 Listener terms refer to the sending of the Routing RIB 2546 information: it is perhaps counterintuitive that the Listener 2547 becomes the bundle offeror and the Initiator the bundle 2548 acceptor during the bundling passing part. 2550 The protocol is designed so that the two exchanges MAY be 2551 carried out independently but concurrently with the messages 2552 multiplexed onto on a single bidirectional link (such as is 2553 provided by the TCP connection). Alternatively, the exchanges 2554 MAY be carried out partially or wholly sequentially if 2555 appropriate for the implementation. The information exchange 2556 process is explained in more detail in Section 3.2 2558 When an empty Bundle Response TLV (i.e., no more bundles to 2559 send) is received, the node starts the next_exchange timer. 2560 When this timer expires, assuming that the neighbor is still 2561 connected, the Initiator reruns the information exchange 2562 process. If there is only one neighbor connected at this time, 2563 this will have the effect of further increasing the delivery 2564 predictability for this node in the neighbor and consequent 2565 changes to the delivery predictabilities as a result of the 2566 transitive property, Equation 3. If there is more than one 2567 neighbor connected or other communication opportunities have 2568 happened since the previous information exchange occurred, then 2569 the changes resulting from these other encounters will be 2570 passed on the connected neighbor. The next_exchange timer is 2571 restarted once the information exchange has completed again. 2573 If one or more new bundles are receieved by this node while 2574 waiting for the next_exchange timer to expire and the delivery 2575 predictabilities indicate that it would be appropriate to 2576 forward some or all of the bundles to the connected node, the 2577 bundles SHOULD be immediately offered to the connected neighbor 2578 and transferred if accepted. 2580 State: WAIT_NB 2582 +==================================================================+ 2583 | Condition | Action | New State | 2584 +==================+===================================+===========+ 2585 | New Neighbor | Start Hello procedure for neighbor| HELLO | 2586 | | Keep waiting for more neighbors | WAIT_NB | 2587 +==================================================================+ 2589 State: HELLO 2591 +==================================================================+ 2592 | Condition | Action | New State | 2593 +==================+===================================+===========+ 2594 | Hello TLV rcvd | | HELLO | 2595 +------------------+-----------------------------------+-----------+ 2596 | Enter ESTAB state| Start Information Exchange Phase | INFO_EXCH | 2597 +------------------+-----------------------------------+-----------+ 2598 | Neighbor Gone | | WAIT_NB | 2599 +==================================================================+ 2600 State: INFO_EXCH 2602 +==================================================================+ 2603 | Condition | Action | New State | 2604 +==================+===================================+===========+ 2605 | On entry | Start keep alive timer | | 2606 | | Uses Hello Timer interval | INFO_EXCH | 2607 +------------------+-----------------------------------+-----------+ 2608 |Info Exch TLV rcvd| (processed by subsidiary state | | 2609 | | machines) | INFO_EXCH | 2610 +------------------+-----------------------------------+-----------+ 2611 | No more bundles | Start next_exchange timer | INFO_EXCH | 2612 +------------------+-----------------------------------+-----------+ 2613 | Keep Alive expiry| Send Hello SYN message | INFO_EXCH | 2614 +------------------+-----------------------------------+-----------+ 2615 | Hello SYN rcvd | Record reception, restart timer | INFO_EXCH | 2616 +------------------+-----------------------------------+-----------+ 2617 | Neighbor Gone | | WAIT_NB | 2618 +==================================================================+ 2620 The Keep Alive messages (messages with Hello SYN TLV) are processed 2621 by the high level state machine in the INFO_EXCH state. All other 2622 messages are delegated to the subsidiary state machines of the 2623 information exchange phase described in Section 5.3. The receipt of 2624 Keep Alive messages is recorded and may be used by the subsidiary 2625 machines to check if the peer is still functioning. The connection 2626 will be aborted as described in Section 4.3.1 if several Keep Alive 2627 messages are not received. 2629 5.2. Hello Procedure 2631 The hello procedure is described by the following rules and state 2632 tables. In this section the messages sent consist of the PRoPHET 2633 header (see Figure 4 and a single Hello TLV (see Section 4.3.1) with 2634 the HF (Hello Function) field set to the specified value (SYN, 2635 SYNACK, ACK or RSTACK). 2637 The state of the L flag in the latest SYN or SYNACK message is 2638 recorded in the node that receives the message If the L flag is set 2639 (1) the receiving node MUST send the payload length for exch bundle 2640 that it offers to the peer during the information exchange phase. 2642 The rules and state tables use the following operations: 2644 o The "Update Peer Verifier" operation is defined as storing the 2645 values of the Sender Instance and Sender Local Address fields from 2646 a Hello SYN or Hello SYNACK function message received from the 2647 entity at the far end of the link. 2649 o The procedure "Reset the link" is defined as: 2651 When using TCP or other reliable connection-oriented transport: 2652 Close the connection and terminate any separate thread or 2653 process managing the connection. 2655 Otherwise: 2657 1. Generate a new instance number for the link. 2659 2. Delete the peer verifier (set to zero the values of 2660 Sender Instance and Sender Local Address previously 2661 stored by the Update Peer Verifier operation). 2663 3. Send a SYN message. 2665 4. Transition to the SYNSENT state. 2667 o The state tables use the following Boolean terms and operators: 2669 A The Sender Instance in the incoming message matches the value 2670 stored from a previous message by the "Update Peer Verifier" 2671 operation. 2673 B The Sender Instance and Sender Local Address fields in the 2674 incoming message match the values stored from a previous 2675 message by the "Update Peer Verifier" operation. 2677 C The Receiver Instance and Receiver Local Address fields in 2678 the incoming message match the values of the Sender Instance 2679 and Sender Local Address used in outgoing Hello SYN, Hello 2680 SYNACK, and Hello ACK messages. 2682 SYN A Hello SYN message has been received. 2684 SYNACK 2685 A Hello SYNACK message has been received. 2687 ACK A Hello ACK message has been received. 2689 "&&" Represents the logical AND operation 2691 "||" Represents the logical OR operation 2692 "!" Represents the logical negation (NOT) operation. 2694 o A timer is required for the periodic generation of Hello SYN, 2695 Hello SYNACK, and Hello ACK messages. The value of the timer is 2696 announced in the Timer field. To avoid synchronization effects, 2697 uniformly distributed random jitter of +/-5% of the Timer field 2698 SHOULD be added to the actual interval used for the timer. 2700 There are two independent events: the timer expires, and a packet 2701 arrives. The processing rules for these events are: 2703 Timer Expires: Reset Timer 2704 If state = SYNSENT Send SYN message 2705 If state = SYNRCVD Send SYNACK message 2706 If state = ESTAB Send ACK message 2708 Packet Arrives: 2709 If incoming message is an RSTACK message: 2710 If (A && C && !SYNSENT) Reset the link 2711 Else discard the message. 2712 If incoming message is a SYN, SYNACK, or ACK message: 2713 Response defined by the following State Tables. 2714 If incoming message is any other PRoPHET TLV and 2715 state != ESTAB: 2716 Discard incoming message. 2717 If state = SYNSENT Send SYN message(Note 1) 2718 If state = SYNRCVD Send SYNACK message(Note 1) 2720 Note 1: No more than two SYN or SYNACK messages should be 2721 sent within any time period of length defined by the timer. 2723 o A connection across a link is considered to be achieved when the 2724 protocol reaches the ESTAB state. All TLVs, other than Hello 2725 TLVs, that are received before synchronization is achieved, will 2726 be discarded. 2728 5.2.1. Hello Procedure State Tables 2730 State: SYNSENT 2732 +==================================================================+ 2733 | Condition | Action | New State | 2734 +==================+===================================+===========+ 2735 | SYNACK && C | Update Peer Verifier; | ESTAB | 2736 | | Send ACK message | | 2737 +------------------+-----------------------------------+-----------+ 2738 | SYNACK && !C | Send RSTACK message | SYNSENT | 2739 +------------------+-----------------------------------+-----------+ 2740 | SYN | Update Peer Verifier; | SYNRCVD | 2741 | | Send SYNACK message | | 2742 +------------------+-----------------------------------+-----------+ 2743 | ACK | Send RSTACK message | SYNSENT | 2744 +==================================================================+ 2746 State: SYNRCVD 2748 +==================================================================+ 2749 | Condition | Action | New State | 2750 +==================+===================================+===========+ 2751 | SYNACK && C | Update Peer Verifier; | ESTAB | 2752 | | Send ACK message | | 2753 +------------------+-----------------------------------+-----------+ 2754 | SYNACK && !C | Send RSTACK message | SYNRCVD | 2755 +------------------+-----------------------------------+-----------+ 2756 | SYN | Update Peer Verifier; | SYNRCVD | 2757 | | Send SYNACK message | | 2758 +------------------+-----------------------------------+-----------+ 2759 | ACK && B && C | Send ACK message | ESTAB | 2760 +------------------+-----------------------------------+-----------+ 2761 | ACK && !(B && C) | Send RSTACK message | SYNRCVD | 2762 +==================================================================+ 2763 State: ESTAB 2765 +==================================================================+ 2766 | Condition | Action | New State | 2767 +=================+====================================+===========+ 2768 | SYN || SYNACK | Send ACK message (notes 2, and 3) | ESTAB | 2769 +-----------------+------------------------------------+-----------+ 2770 | ACK && B && C | Send ACK message (note 3) | ESTAB | 2771 +-----------------+------------------------------------+-----------+ 2772 | ACK && !(B && C)| Send RSTACK message | ESTAB | 2773 +==================================================================+ 2775 Note 2: No more than two ACK messages should be sent within any 2776 time period of length defined by the timer. Thus, one ACK message 2777 MUST be sent every time the timer expires. In addition, one 2778 further ACK message may be sent between timer expirations if the 2779 incoming message is a SYN or SYNACK. This additional ACK allows 2780 the Hello functions to reach synchronization more quickly. 2782 Note 3: No more than one ACK message should be sent within any 2783 time period of length defined by the timer. 2785 5.3. Information Exchange and Bundle Passing Phase 2787 After the Hello messages have been exchanged, and the nodes are in 2788 the ESTAB state, the information exchange and bundle passing phase is 2789 initiated. This section describes the procedure and shows the state 2790 transitions necessary in this phase, and the following sections 2791 describe the various TLVs passed in this phase in detail. On 2792 reaching the ESTAB state in the high level HELLO state there is an 2793 automatic transition to the INFO_EXCH high level state. 2795 PRoPHET runs over a bidirectional transport as documented in 2796 Section 1.2 so that when a pair of nodes (A and B) have reached the 2797 ESTAB state they are able to perform the information exchange and 2798 bundle passing processes for both the A to B and B to A directions 2799 over the link that has just been established. In principle, these 2800 two processes are independent of each other and can be performed 2801 concurrently. However complete concurrency may not be the most 2802 efficient way to implement the complete process. As explained in 2803 Section 3.2.1, the Routing Information Base Dictionary is a shared 2804 resource assembled from a combination of information generated 2805 locally on each node and information passed from the peer node. 2806 Overlaps in this information and, hence the amount of information 2807 that has to be passed between the nodes, can be minimized by 2808 sequential rather than concurrent operation of the dictionary 2809 generation and update processes. It may also be possible to reduce 2810 the number of bundles that need to be offered by the second offeror 2811 by examining the offers received from the first offeror - there is no 2812 need for the second offeror to offer a bundle that is already present 2813 in the first offeror's offer list, as it will inevitably be refused. 2815 All implementations MUST be capable of operating in a fully 2816 concurrent manner. Each implementation needs to define a policy, 2817 which SHOULD be configurable, as to whether it will operate in a 2818 concurrent or sequential manner during the information exchange and 2819 bundle passing phase. If it is to operate sequentially, then further 2820 choices can be made as to whether to interleave dictionary, offer and 2821 response exchange parts or complete all parts in one direction before 2822 initiating the other direction. 2824 Sequential operation will generally minimize the amount of data 2825 transferred across the PRoPHET link and is especially appropriate if 2826 the link is half-duplex. However it is probably not desirable to 2827 postpone starting the information exchange in the second direction 2828 until the exchange of bundles has completed. If the contact between 2829 the nodes ends before all possible bundles have been exchanged, it is 2830 possible that postponing the start of bundle exchange in the second 2831 direction can lead to bundle exchange being skewed in favor of one 2832 direction over the other. It may be preferable to share the 2833 available contact time and bandwidth between directions by 2834 overlapping the information exchange processes and running the actual 2835 bundle exchanges concurrently if possible. Also if encounters 2836 expected in the current PRoPHET zone are expected to be relatively 2837 short, it MAY not be appropraite to use sequential operation. 2839 One possible interleaving strategy is to alternate between sending 2840 from the two nodes. For example, if the Hello SYN node sends its 2841 initial dictionary entries while the Hello SYNACK node waits until 2842 this is complete, the Hello SYNACK node can then prune its proposed 2843 dictionary entries before sending to avoid duplication. This 2844 approach can be repeated for the second tranche of dictionary entries 2845 needed for the Bundle Offers and Responses, and also for the Bundle 2846 Offers, where any bundles that are offered by the Hello SYN node that 2847 are already present in the Hello SYNACK node need not be offered to 2848 the Hello SYN node. This approach is well suited to a transport 2849 protocol and physical medium that is effectively half-duplex. 2851 The decision to operate concurrently or sequentially is purely a 2852 matter of local policy in each node at present. If nodes have 2853 inconsistent policies, the behavior at each encounter will depend on 2854 which node takes the SYN role which is a matter of chance depending 2855 on random timing of the start of communications during the encounter. 2857 To manage the information transfer, two subsidiary state machines are 2858 created in each node to control the stages of the information 2859 exchange and bundle passing process within the INFO_EXCH high level 2860 state as shown in Figure 12. Each subsidiary state machine consists 2861 of two essentially independent components known as the "Initiator 2862 role" and the "Listener role". One of these components is 2863 instantiated in each node. The Initiator role starts the information 2864 exchange process in each node and the Listener role responds to the 2865 initial messages, but it is not a passive listener as it also 2866 originates messages. The transition from the ESTAB state is a 2867 "forking" transition in that it starts both subsidiary state 2868 machines. The two subsidiary state machines operate in parallel for 2869 as long as the neighbor remains in range and connected. 2871 + - - - - - - - - + + - - - - - - - - + 2873 | SYN node | PRoPHET messages with: | SYNACK node | 2875 | +-------------+ | A. Delivery Predictabilities | +-------------+ | 2876 | Subsidiary |--->---->---->---->---->---->---->| Subsidiary | 2877 | | State | | C. Bundle Responses | | State | | 2878 | Machine 1: | | Machine 1: | 2879 | | Initiator | | B. Bundle Offers | | Listener | | 2880 | Role |<----<----<----<----<----<----<---| Role | 2881 | +-------------+ | D. Requested Bundles | +-------------+ | 2883 | +-------------+ | A. Delivery Predictabilities | +-------------+ | 2884 | Subsidiary |<----<----<----<----<----<----<---| Subsidiary | 2885 | | State | | C. Bundle Responses | | State | | 2886 | Machine 2: | | Machine 2: | 2887 | | Listener | | B. Bundle Offers | | Initiator | | 2888 | Role |--->---->---->---->---->---->---->| Role | 2889 | +-------------+ | D. Requested Bundles | +-------------+ | 2891 + - - - - - - - - + + - - - - - - - - + 2893 The letters (A - D) indicate the sequencing of messages. 2895 Figure 12: Information Exchange Subsidiary State Machines 2897 These subsidiary state machines can be thought of as mirror images: 2898 for each state machine one node takes on the Initiator role while the 2899 other node takes on the Listener role. TLVs sent by a node from the 2900 Initiator role will be processed by the peer node in the Listener 2901 role and vice versa. As indicated in Figure 12 the Initiator role 2902 handles sending that node's current set of delivery predictabilities 2903 for known destinations to the Listener role node. The Listener role 2904 node uses the supplied values to update its delivery predictabilities 2905 according to the update algorithms described in Section 2.1.2. It 2906 then decides which bundles that it has in store should be offered for 2907 transfer to the Initiator role node as a result of comparing the 2908 local predictabilities and those supplied by the Initiator node. 2909 When these offers are delivered to the Initiator role node, it 2910 decides which ones to accept and supplies the Listener node role with 2911 a prioritized list of bundles that it wishes to accept. The Listener 2912 role node then sends the requested bundles. 2914 These exchanges are repeated periodically for as long as the nodes 2915 remain in contact. Additionally, if new bundles arrive from other 2916 sources they may be offered, accepted and sent in between these 2917 exchanges. 2919 The PRoPHET protocol is designed so that in most cases the TLV type 2920 determines the role in which it will be processed on reception. The 2921 only exception to this is that both roles may send RIB Dictionary 2922 TLVs: the Initiator role sends dictionary entries for use in the 2923 subsequent RIB TLV(s) and the Listener role may send additional 2924 dictionary entries for use in subsequent Bundle Offer TLVs. The two 2925 cases are distinguished by a TLV flag to ensure that they are 2926 processed in the right role context on reception. If this flag was 2927 not provided there are states where both roles could accept the RIB 2928 Dictionary TLV making it impossible to ensure that the correct role 2929 state machine took action. Note that the correct updates would be 2930 made to the dictionary whichever role processed the TLV and that the 2931 ambiguity would not arise if the roles are adopted completely 2932 sequentially, i.e., if the information exchange and associated bundle 2933 passing run to completion in one direction before the process for the 2934 reverse direction is started. 2936 If sequential operation is selected, the node which sent the Hello 2937 SYN function message MUST be the node which sends the first message 2938 in the information exchange process. This ensures that there is a 2939 well-defined order of events with the Initiator role in the Hello SYN 2940 node (i.e., the node identified by String ID 0) starting first. The 2941 Hello SYNACK node MAY then postpone sending its first message until 2942 the Listener role state machine in the Hello SYNACK node has reached 2943 any of a number of points in its state progression according to 2944 locally configured policy and the nature of the physical link for the 2945 current encounter between the nodes as described above. If 2946 concurrent operation is selected, the Hello SYNACK node can start 2947 sending messages immediately without waiting to receive messages from 2948 the peer. 2950 The original design of the PRoPHET protocol allowed it to operate 2951 over unreliable datagram type transports as well as the reliable, in- 2952 order delivery transport of TCP that is currently specified. When 2953 running over TCP protocol errors and repeated timeouts during the 2954 information exchange phase SHOULD result in the connection being 2955 terminated. 2957 5.3.1. Initiator Role State Definitions 2959 The state machine component with the Initiator role in each node 2960 starts the transfer of information from one node to its peer during 2961 the information exchange process. The process from the Initiator's 2962 point of view does the following: 2964 o The Initiator role determines the set of delivery predictabilities 2965 to be sent to the peer node, sends RIB dictionary entries 2966 necessary to interpret the set of RIB predictability values that 2967 are sent after the dictionary updates. On second and subsequent 2968 executions of this state machine during a single session with the 2969 same peer there may be no RIB dictionary entries to send. Either 2970 an empty TLV can be sent or the TLV can be omitted. 2972 o The Initiator then waits to receive any RIB dictionary updates 2973 followed by bundle offers from the Listener role on the peer node. 2975 o The Initiator determines which of the bundle offers should be 2976 accepted and, if necessary, reorders the offers to suit its own 2977 priorities. The possibly reordered list of accepted bundles is 2978 sent to the peer node using one or more bundle responses. 2980 o The peer then sends the accepted bundles to the Initiator in turn. 2982 o Assuming that the link remains open during the bundle sending 2983 process, the Initiator signals that the bundle passing phase is 2984 complete by sending a message with an empty Bundle Response TLV 2985 (i.e, with the Bundle Offer Count set to 0 and no bundle offers 2986 following the TLV header). 2988 o When the bundle transfer is complete, the Initiator starts the 2989 next_exchange timer. Assuming that the connection to the neighbor 2990 remains open, when the timer expires the Initiator restarts the 2991 information exchange process. During this period, Hello SYN 2992 messages are exchanged as keep alives to check that the neighbor 2993 is still present. The keep alive mechanism is common to the 2994 Initiator and Listener machines and is handled in the high level 2995 state machine (see Section 5.1. 2997 A timer is provided which restarts the Initiator role state machine 2998 if Bundle Offers are not received after sending the RIB. If this 2999 node receives a Hello ACK message containing an Error TLV indicating 3000 there has been a protocol problem then the connection MUST be 3001 terminated. 3003 The following states are used: 3005 CREATE_DR 3006 The initial transition to this state from the ESTAB state is 3007 immediate and automatic for the node that sent the Hello SYN 3008 message. For the peer (Hello SYNACK sender) node it may be 3009 immediate for nodes implementing a fully concurrent process or may 3010 be postponed until the corresponding Listener has reached a 3011 specified state if a sequential process is configured in the node 3012 policy. 3014 The local dictionary is initialized when this state is entered for 3015 the first time from the ESTAB state. The initial state of the 3016 dictionary contains two entries: the EID of the node that sent the 3017 Hello SYN (String ID 0) and the EID of the node that sent the 3018 Hello SYNACK (String ID 1). If the peer reports via a Hello ACK 3019 message containing an Error TLV reporting a Dictionary Conflict or 3020 Bad String ID error then the connection MUST be terminated. 3022 The CREATE_DR state will be entered in the same way from the 3023 REQUEST state when the Timer(next_exchange) expires, signaling the 3024 start of a new round of information exchange and bundle passing. 3026 When in this state: 3028 * Determine the destination EIDs for which delivery 3029 predictabilities will be sent to the peer in a RIB TLV, if any. 3030 Record the prior state of the local dictionary (assuming that 3031 String IDs are numbers allocated sequentially, the state 3032 information needed is just the highest ID used before this 3033 process started) so that the process can be restarted if 3034 necessary. Update the local dictionary if any new EIDS are 3035 required, format one or more RIB Dictionary TLVs and one or 3036 more RIB TLVs and send them to the peer. If there are no 3037 dictionary entries to send, TLVs with zero entries MAY be sent, 3038 or the TLV can be omitted, but an empty RIB TLV MUST be sent if 3039 there is no data to send. The RIB Dictionary TLVs generated 3040 here MUST have the Sent by Listener flag set to 0 to indicate 3041 that they were sent by the Initiator. 3043 * If an Error TLV indicating a Dictionary Conflict or 3044 Bad String ID is received during or after sending the RIB 3045 Dictionary TLVs and/or the RIB TLVs, abort any in progress 3046 Initiator or Listener process, and terminate the connection to 3047 the peer. 3049 * Start a timer (known as Timer(info)) and transition to the 3050 SEND_DR state. 3052 Note that when (and only when) running over a transport protocol 3053 such as TCP, both the RIB Dictionary and RIB information MAY be 3054 spread across multiple TLVs and messages if required by known 3055 constraints of the transport protocol or to reduce the size of 3056 memory buffers. Alternatively the information can be formatted 3057 into single RIB Dictionary and RIB TLVs and the submessage 3058 capability of PRoPHET or the inherent capabilities of the 3059 transport protocol used to segment the message if required. This 3060 discussion of segmentation applies to the other states and the 3061 Bundle Offer and Bundle Response messages and will not be 3062 repeated. 3064 If more than one RIB TLV is to be used, all but the last one have 3065 the "More RIB TLVs" flag set to 1 in the TLV flags. It is not 3066 necessary to distinguish the last RIB Dictionary TLV because the 3067 actions taken at the receiver are essentially passive (recording 3068 the contents) and the sequence is ended by the sending of the 3069 first RIB TLV. 3071 SEND_DR 3072 In this state the Initiator node expects to be receiving Bundle 3073 Offers and sending Bundle Responses: 3075 * Clear the set of bundles offered by the peer on entry to the 3076 state. 3078 * If the Timer(info) expires, resend the RIB Dictionary and RIB 3079 information sent in the previous CREATE_DR state using the 3080 stored state to recreate the information. The RIB dictionary 3081 update process in the peer is idempotent provided that the 3082 mappings between the EID and the String ID in the resent RIB 3083 Dictionary TLVs are the same as in the original. This means 3084 that it does not matter if some of the RIB Dictionary TLVs had 3085 already been processed in the peer. Similarly resending RIB 3086 TLVs will not cause a problem. 3088 * If a message with a RIB Dictionary TLV marked as sent by a 3089 Listener is received, update the local dictionary based on the 3090 received TLV. If any of the entries in the RIB Dictionary TLV 3091 conflict with existing entries (i.e., an entry is received that 3092 uses the same String ID as some previously received entry but 3093 the EID in the entry is different), send a Response message 3094 with an Error TLV containing a Dictionary Conflict indicator, 3095 abort any in progress Initiator or Listener process, and 3096 terminate the connection to the peer. Note that in some 3097 circumstances no dictionary updates are needed and the first 3098 message received in this state will carry a Bundle Offer TLV. 3100 * If a message with a Bundle Offer TLV is received, restart the 3101 Timer(info) if the More Offer/Response TLVs Following flag is 3102 set in the TLV or otherwise stop the Timer(info). Then process 3103 any PRoPHET Acks in the TLV by informing the Bundle Agent, and 3104 add the bundles offered in the TLV to the set of bundles 3105 offered. If the More Offer/Response TLVs Following flag is set 3106 in the TLV wait for further Bundle Offer TLVs. If a Bundle 3107 Offer TLV is received with a String ID that is not in the 3108 dictionary send a message with an Error TLV containing a 3109 Bad String ID indicator, abort any in progress Initiator or 3110 Listener process, and terminate the connection to the peer. 3112 * If the More Offer/Response TLVs Following flag is clear in the 3113 last Bundle Offer TLV received, inspect the set of bundles 3114 offered to determine the set of bundles that are to be accepted 3115 using the configured queuing policy. Record the set of bundles 3116 accepted so that reception can be checked in the bundle passing 3117 phase. Format one or more Bundle Response TLVs flagging the 3118 accepted offers and send them to the peer. If more than one 3119 Bundle Response TLV is sent, all but the last one should have 3120 the More Offer/Response TLVs Following TLV flag set to 1. At 3121 least one Bundle Response TLV MUST be sent even if the node 3122 does not wish to accept any of the offers. In this case the 3123 Bundle Response TLV contains an emoty set of acceptances. 3125 * If an Error TLV indicating a Bad String ID is received during 3126 or after sending the Bundle Response TLVs, abort any in 3127 progress Initiator or Listener process, reinitialize the local 3128 dictionary and terminate the connection to the peer. 3130 * Restart the Timer(info) timer in case the peer does not start 3131 sending the requested bundles. 3133 * Transition to state REQUEST. 3135 REQUEST 3136 In this state the Initiator node expects to be receiving the 3137 bundles accepted in the Bundle Response TLV(s): 3139 * Keep track of the bundles received and delete them from the set 3140 of bundles accepted. 3142 * If the Timer(info) expires while waiting for bundles, format 3143 and send one or more Bundle Response TLVs listing the bundles 3144 previously accepted but not yet received. If more than one 3145 Bundle Response TLV is sent, all but the last one should have 3146 the More Offer/Response TLVs Following TLV flag set to 1. 3148 * If an Error TLV indicating a Bad String ID is received during 3149 or after sending the Bundle Response TLVs, abort any in 3150 progress Initiator or Listener process, reinitialize the local 3151 dictionary and terminate the connection to the peer. 3153 * Restart the Timer(info) timer after each bundle is received in 3154 case the peer does not continue sending the requested bundles. 3156 * When all the requested bundles have been received, format a 3157 Bundle Response TLV with the Bundle Offer Count set to zero and 3158 with the More Offer/Response TLVs Following flag cleared to 0 3159 to signal completion to the peer node. Also signal the 3160 Listener in this node that the Initiator has completed. If the 3161 peer node is using a sequential policy, the Listener may still 3162 be in the initial state in which case it needs to start a timer 3163 to ensure that it detects if the peer fails to start the 3164 Initiator state machine. Thereafter coordinate with the 3165 Listener state machine in the same node: when the Listener has 3166 received the completion notification from the peer node and 3167 this Initiator has sent its completion notification, start a 3168 Timer(next_exchange). 3170 * If the Timer(next_exchange) expires, transition to state 3171 CREATE_DR to restart the information exchange process. 3173 Note that if Timer(info) timeout occurs a number of times 3174 (configurable, typically 3) without any bundles being received 3175 then this SHOULD generally be interpreted as a problem that 3176 indicates that the link to the peer is no longer functional and 3177 the session should be terminated. However, some bundles may be 3178 very large and take a long time to transmit. Before terminating 3179 the session this state machine needs to check if a large bundle is 3180 actually being received although no new completed bundles have 3181 been received since the last expiry of the timer. In this case 3182 the timer should be restarted without sending the Bundle Response 3183 TLV. Also if the bundles are being exchanged over a transport 3184 protocol that can detect link failure, then the session MUST be 3185 terminated if the bundle exchange link is shut down because it has 3186 failed. 3188 5.3.2. Listener Role State Definitions 3190 The state machine component with the Listener role in each node 3191 initially waits to receive a RIB Dictionary update followed by a set 3192 of RIB delivery predictabilities during the information exchange 3193 process. The process from the point of view of the Listener does the 3194 following: 3196 o Receive RIB Dictionary updates and RIB values from the peer. Note 3197 that in some circumstances no dictionary updates are needed and 3198 RIBD dictionary TLV will contain no entries or may be omitted 3199 completely. 3201 o When all RIB messages have been received, the delivery 3202 predictability update algorithms are run (see Section 2.1.2) using 3203 the values received from the Initiator node and applying any of 3204 the optional optimizations configured for this node (see 3205 Section 2.1.3). 3207 o Using the updated delivery predictabilities and the queuing policy 3208 and forwarding strategy configured for this node (see 3209 Section 2.1.4) examine the set of bundles currently stored in the 3210 Listener node to determine the set of bundles to be offered to the 3211 Initiator and order the list according to the forwarding strategy 3212 in use. The Bundle Offer TLVs are also used to notify the peer of 3213 any PRoPHET Acks that have been received by this node. 3215 o Send the list of bundles in one or more bundle offers, preceded if 3216 necessary by one or more RIB dictionary updates to add any EIDs 3217 required for the source or destination EIDs of the offered 3218 bundles. These updates MUST be marked as being sent by the 3219 Listener role so that they will be processed by the Initiator role 3220 in the peer. 3222 o Wait for the Initiator to send a bundle responses indicating which 3223 bundles should be sent and possibly a modified order for the 3224 sending. Send the bundles accepted in the specified order. The 3225 bundle sending will normally be carried out over a separate 3226 connection using a suitable DTN convergence layer. 3228 o On completion of the sending, wait for a message with an empty 3229 Bundle Response TLV indicating correct completion of the process. 3231 o The Listener process will be notified if any new bundles or 3232 PRoPHET ACKs are received by the node after the completion of the 3233 bundle sending resulting from this information exchange. The 3234 forwarding policy and the current delivery predictabilities will 3235 then be applied to determine if this information should be sent to 3236 the peer. If it is determined that one or more bundles and/or 3237 ACKs ought to be forwarded, a new set of bundle offers are sent to 3238 the peer. If the peer accepts them by sending bundle responses, 3239 the bundles and/or ACKS are transferred as previously 3241 o Periodically, the Initiator in the peer will restart the complete 3242 information exchange by sending a RIB TLV that may be, optionally, 3243 preceded by RIB Dictionary entries if they are required for the 3244 updated RIB. 3246 Timers are used to ensure that the Listener does not lock up if 3247 messages are not received from the Initiator in a timely fashion. 3248 The Listener is restarted if the RIB is not received and a Hello Ack 3249 message is sent to force the Initiator to restart. If Bundle 3250 Response messages are not received in a timely fashion, the Listener 3251 resends the Bundle Offers and associated dictionary updates. The 3252 following states are used: 3254 WAIT_DICT 3255 The Listener subsidiary state machine transitions to this state 3256 automatically and immediately from the state ESTAB in both peers. 3257 This state will be entered in the same way if the 3258 Timer(next_exchange) expires in the peer, signaling the start of a 3259 new round of information exchange and bundle passing. This will 3260 result in one or more RIB TLVs being sent to the Listener by the 3261 peer node's Initiator. 3263 * When a RIB Dictionary TLV is received, use the TLV to update 3264 the local dictionary, start or, if it is running, restart the 3265 Timer(peer) and transition to state WAIT_RIB. If any of the 3266 entries in the RIB Dictionary TLV conflict with existing 3267 entries (i.e., an entry is received that uses the same String 3268 ID as some previously received entry but the EID in the entry 3269 is different), send a Rersponse message with an Error TLV 3270 containing a Dictionary Conflict indicator, abort any in 3271 progress Initiator or Listener process, and terminate the 3272 connection to the peer. 3274 * If a Hello ACK message is received from the peer node, 3275 transition to state WAIT_DICT and restart the process. 3277 If multiple timeouts occur (configurable, typically 3), assume 3278 that the link is broken and terminate the session. Note that the 3279 RIB Dictionary and RIB TLVs may be combined into a single message. 3280 The RIB TLV should be passed on to be processed in the WAIT_RIB 3281 state. 3283 WAIT_RIB 3284 In this state the Listener expects to be receiving one or more RIB 3285 TLVs and possibly additional RIB Dictionary TLVs. 3287 * On entry to this state clear the set of received delivery 3288 predictabilities. 3290 * Whenever a new message is received, restart the Timer(peer) 3291 timer. 3293 * If a RIB dictionary TLV is received, use it to update the local 3294 dictionary and remain in this state. If any of the entries in 3295 the RIB Dictionary TLV conflict with existing entries (i.e., an 3296 entry is received that uses the same String ID as some 3297 previously received entry but the EID in the entry is 3298 different), send a message with an Error TLV containing a 3299 Dictionary Conflict indicator, abort any in progress Initiator 3300 or Listener process, and terminate the connection to the peer. 3302 * If a RIB TLV is received, record the received delivery 3303 predictabilities for use in recalculating the local delivery 3304 predictabilities. If a delivery predictability value is 3305 received for an EID that is already in the set of received 3306 delivery predictabilities, overwrite the previously received 3307 value with the latest value. If a delivery predictability 3308 value is received with a String ID that is not in the 3309 dictionary send a message with an Error TLV containing a 3310 Bad String ID indicator, abort any in progress Initiator or 3311 Listener process, and terminate the connection to the peer. 3313 * When a RIB TLV is received with the More RIB TLVs flag cleared, 3314 initiate the recalculation of delivery predictabilities and 3315 stop the Timer(peer). Use the revised delivery 3316 predictabilities and the configured queueing and forwarding 3317 strategies to create a list of bundles to be offered to the 3318 peer node. 3320 * Record the state of the local dictionary in case the offer 3321 procedure has to be restarted. Determine if any new dictionary 3322 entries are required for use in the Bundle Offer TLV(s). If so 3323 record them in the local dictionary, then format and send RIB 3324 Dictionary entries in zero or more RIB Dictionary TLV messages 3325 to update the dictionary in the peer if necessary. 3327 * Format and send Bundle Offer TLV(s) carrying the identifiers of 3328 the bundles to be offered together with any PRoPHET ACKs 3329 received or generated by this node. If more than one Bundle 3330 Offer TLV is sent, all but the last Bundle Offer TLV sent MUST 3331 have the More Offer/Response TLVs Following flag set to 1. 3333 * When all Bundle Offer TLVs have been sent start the Timer(info) 3334 and transition to state OFFER. 3336 * If the Timer(peer) expires, send a Hello ACK TLV to the peer, 3337 restart the timer and transition to state WAIT_DICT. 3339 * If an Error TLV indicating a Dictionary Conflict or 3340 Bad String ID is received during or after sending the RIB 3341 Dictionary TLVs and/or the Bundle Offer TLVs, abort any in 3342 progress Initiator or Listener process, and terminate the 3343 connection to the peer. 3345 * If a Hello ACK message is received from the peer node, 3346 transition to state WAIT_DICT and restart the process. 3348 OFFER 3349 In this state the Listener expects to be receiving one or more 3350 Bundle Response TLVs detailing the bundles accepted by the 3351 Initiator node. The ordered list of accepted bundles is 3352 communicated to the Bundle Protocol Agent which controls sending 3353 them to the peer node over a separate connection. 3355 * When a Bundle Response TLV is received with a non-zero count of 3356 Bundle Offers, extract the list of accepted bundles and send 3357 the list to the Bundle Protocol Agent so that it can start 3358 transmission to the peer node. Ensure that the order of offers 3359 from the TLV is maintained. Restart the Timer(info) unless the 3360 last Bundle Response TLV received has the More Offer/ 3361 Response TLVs Following flag set to 0. If a Bundle Response 3362 TLV is received with a String ID that is not in the dictionary 3363 send a message with an Error TLV containing a Bad String ID 3364 indicator, abort any in progress Initiator or Listener process, 3365 and terminate the connection to the peer. 3367 * After receiving a Bundle Response TLV with the More Offer/ 3368 Response TLVs Following flag set to 0 stop the Timer(info) and 3369 transition to state SND_BUNDLE. 3371 * If the Timer(info) expires, send a Hello ACK TLV to the peer, 3372 restart the timer and transition to state WAIT_DICT. 3374 * If a Hello ACK message is received from the peer node, 3375 transition to state WAIT_DICT and restart the process. 3377 SND_BUNDLE 3378 In this state the Listener monitors the sending of bundles to the 3379 Initiator peer node. In the event of disruption in transmission, 3380 the Initiator node will, if possible, resend the list of bundles 3381 that were accepted but have not yet been received. The Bundle 3382 Protocol Agent has to be informed of any updates to the list of 3383 bundles to send (this is likely to involve resending one or more 3384 bundles). Otherwise the Listener is quiescent in this state. 3386 * When a Bundle Response TLV is received with a non-zero count of 3387 Bundle Offers, extract the list of accepted bundles and update 3388 the list previously passed to the Bundle Protocol Agent so that 3389 it can (re)start transmission to the peer node. Ensure that 3390 the order of offers from the TLV is maintained so far as is 3391 possible. Restart the Timer(info) unless the last Bundle 3392 Response TLV received has the More Offer/ 3393 Response TLVs Following flag set to 0. If a Bundle Response 3394 TLV is received with a String ID that is not in the dictionary 3395 send a message with an Error TLV containing a Bad String ID 3396 indicator, abort any in progress Initiator or Listener process, 3397 reinitialize the local dictionary and restart the information 3398 exchange process as if the ESTAB state had just been reached. 3400 * After receiving a Bundle Response TLV with the More Offer/ 3401 Response TLVs Following flag set to 0 stop the Timer(info) and 3402 wait for completion of bundle sending. 3404 * If the Timer(info) expires, send a Hello ACK TLV to the peer, 3405 restart the timer and transition to state WAIT_DICT. 3407 * If a Hello ACK message is received from the peer node, 3408 transition to state WAIT_DICT and restart the process. 3410 * When a Bundle Response TLV is received with a zero count of 3411 Bundle Offers, the bundle passing phase is complete. Notify 3412 the Initiator that the Listener process is complete and 3413 transition to state WAIT_MORE. 3415 As explained in the Initiator state REQUEST description, depending 3416 on the transport protocol (convergence layer) used to send the 3417 bundles to the peer node, it may be necessary to monitor the 3418 liveness of the connection to the peer node in the Initiator 3419 process during the bundle sending process using a timer. 3421 WAIT_MORE 3422 In this state the Listener monitors the reception of new bundles 3423 that might be received from a number of sources, including 3424 * local applications on the node, 3426 * other mobile nodes that connect to the node while this 3427 connection is open, and 3429 * permanent connections such as might occur at an Intenet 3430 gateway. 3432 When the Listener is notified of received bundles, it determines 3433 if they should be offered to the peer. The peer may also 3434 reinitiate the information exchange process periodically. 3436 * When the Bundle Protocol Agent notifies the Listener that new 3437 bundles and/or new PRoPHET ACKs have been received, the 3438 Listener applies the selected forwarding policy and the current 3439 delivery predictabilities to determine if any of the items 3440 ought to be offered to the connected peer. If so it carries 3441 out the same operations as are described in the WAIT_RIB state 3442 to build and send any necessary RIB Dictionary TLVs and RIB 3443 TLVs to the Initiator in the peer. 3445 * When all Bundle Offer TLVs have been sent start the Timer(info) 3446 and transition to state OFFER. 3448 * If a RIB dictionary TLV is received, use it to update the local 3449 dictionary and transition to state WAIT_RIB. If any of the 3450 entries in the RIB Dictionary TLV conflict with existing 3451 entries (i.e., an entry is received that uses the same String 3452 ID as some previously received entry but the EID in the entry 3453 is different), send a message with an Error TLV containing a 3454 Dictionary Conflict indicator, abort any in progress Initiator 3455 or Listener process, and terminate the connection to the peer. 3457 Note that the RIB Dictionary and RIB TLVs may be combined into a 3458 single message. The RIB TLV should be passed on to be processed 3459 in the WAIT_RIB state. 3461 5.3.3. Recommendations for Information Exchange Timer Periods 3463 The information exchange process state definitions define a number of 3464 timers. This section provides advice and recommendations for the 3465 periods that are appropriate for these timers. 3467 Both Timer(info) and Timer(peer) are used to ensure that the state 3468 machines do not become locked into inappropriate states if the peer 3469 node does not apparently respond to messages sent in a timely fashion 3470 either because of message loss in the network or unresponsiveness 3471 from the peer. The appropriate values are to some extent dependent 3472 on the speed of the network connection between the nodes and the 3473 capabilities of the nodes executing the PRoPHET implementations. 3474 Values in the range 1 to 10 seconds SHOULD be used, with a value of 5 3475 seconds RECOMMENDED as default. The period should not be set to too 3476 low a value as this might to inappropriate restarts if the hardware 3477 is relatively slow or there are large numbers of pieces of 3478 information to process before responding. When using a reliable 3479 transport protocol such as TCP, these timers effectively provide a 3480 keepalive mechanism and ensure that a failed connection is detected 3481 as rapidly as possible so that remedial action can be taken if 3482 possible or the connection shut down tidily if the peer node has 3483 moved out of range. 3485 Timer(next_exchange) is used to determine the maximum frequency of 3486 (i.e., minimum period between) successive reexecutions of the 3487 information exchange state machines during a single session between a 3488 pair of nodes. Selection of the timer period SHOULD reflect the 3489 trade off between load on the node processor and desire for timely 3490 forwarding of bundles received from other nodes. It is RECOMMENDED 3491 that the timer periods used should be randomized over a range from 3492 50% to 150% of the base value to avoid any risk of synchronization 3493 between multiple nodes occurring. Consideration SHOULD be given to 3494 the expected length of typical encounters and the likelihood of 3495 encounters between groups of nodes when setting this period. Base 3496 values in the range of 20 to 60 seconds are RECOMMENDED. 3498 5.3.4. Information Exchange State Tables 3500 This section shows the state transitions that nodes go through during 3501 the information exchange and bundle passing phase. State tables are 3502 given for the Initiator role and for the Listener role of the 3503 subsidiary state machines. Both nodes will be running machines in 3504 each role during the information exchange and bundle passing phase 3505 and this can be done either concurrently or sequentially, depending 3506 on the implementation, as explained in Section 5.3. The state tables 3507 in this section should be read in conjunction with the state 3508 descriptions in Sections 5.3.1 and 5.3.2. 3510 5.3.4.1. Common Notation, Operations and Events 3512 The following notation is used: 3514 nS Node that sent the Hello SYN message. 3516 nA Node that sent the Hello SYNACK message. 3518 The following events are common to the Initiator and Listener state 3519 tables:: 3521 ErrDC Dictionary Conflict Error TLV received. 3523 ErrBadSI Bad String ID Error TLV received. 3525 HelloAck Hello ACK TLV received. This message is delivered to 3526 both Initiator and Listener roles in order to cause a 3527 restart of the information exchange process in the 3528 event of message loss or protocol problems. 3530 InitStart Sent by Listener role to Initiator role to signal the 3531 Initiator role to commence sending messages to peer. 3532 If the Listener instance is running in the node that 3533 sent the Hello SYN (nS) then InitStart is signaled 3534 immediately the state is entered. For the node that 3535 sent the Hello SYNACK (nA), InitStart may be signaled 3536 immediately if the operational policy requires 3537 concurrent operation of the Initiator and Listener 3538 roles or postponed until the Listener role state 3539 machine has reached a state defined by the configured 3540 policy. 3542 RIBnotlast RIB TLV received with More RIBs Follow flag set to 1. 3544 RIBlast RIB TLV received with More RIBs Follow flag set to 0. 3546 REQnotlast Bundle Response TLV received with More Offer/Response 3547 TLVs Following flag set to 1. 3549 REQlast Bundle Response TLV received with More Offer/Response 3550 TLVs Following flag set to 0. 3552 RIBDi RIBD TLV received with Sent by Listener flag set to 0 3553 (i.e., it was sent by Initiator role). 3555 RIBDl RIBD TLV received with Sent by Listener flag set to 1 3556 (i.e., it was sent by Listener role). 3558 Timeout(info) The Timer(info) has expired. 3560 Timeout(peer) The Timer(peer) has expired. 3562 Both the Initiator and Listener state tables use the following common 3563 operations: 3565 o The "Initialize Dictionary" operation is defined as emptying any 3566 existing local dictionary and inserting the two initial entries: 3567 the EID of the node that sent the Hello SYN (String ID 0) and the 3568 EID of the node that sent the Hello SYNACK (String ID 1). 3570 o The "Send RIB Dictionary Updates" operation is defined as: 3572 1. Determining what dictionary updates will be needed for any 3573 extra EIDs in the previously selected RIB entries set that are 3574 not already in the dictionary and updating the local 3575 dictionary with these EIDs. The set of dictionary updates may 3576 be empty if no extra EIDs are needed. The set may be empty 3577 even on the first execution if sequential operation has been 3578 selected, this is the second node to start and the necessary 3579 EIDs were in the set previously sent by the first node to 3580 start. 3582 2. Formatting zero or more RIBD TLVs for the set of dictionary 3583 updates identified in the "Build RIB Entries" operation and 3584 sends them to the peer. The RIBD TLVs MUST have the "Sent by 3585 Listener" flag set to 0 if the updates are sent by the 3586 Initiator role and to 1 if sent by the Listener role. In the 3587 case of the Initiator role an empty RIBD TLV MUST be sent even 3588 if the set of updates is empty in order to trigger the 3589 Listener state machine. 3591 o The "Update Dictionary" operation uses received RIBD TLV entries 3592 to update the local dictionary. The received entries are checked 3593 against the existing dictionary. If the String ID in the entry is 3594 already in use, the entry is accepted if the EID in the received 3595 entry is identical to that stored in the dictionary previously. 3596 If it is identical, the entry is unchanged, but if it is not a 3597 Response message with an Error TLV indicating "Dictionary 3598 Conflict" is sent to the peer in an Error Response message, the 3599 whole received RIBD TLV is ignored and the Initiator and Listener 3600 processes are restarted as if the ESTAB state has just been 3601 reached. 3603 o The "Abort Exchange" operation is defined as aborting any in 3604 progress information exchange state machines, terminating the 3605 connection to the peer. 3607 o The Start TI" operation is defined as (re)starting the Timer(info) 3608 timer. 3610 o The "Start TP" operation is defined as (re)starting the 3611 Timer(peer) timer. 3613 o The "Cancel TI" operation is defined as canceling the Timer(info) 3614 timer. 3616 o The "Cancel TP" operation is defined as canceling the Timer(info) 3617 timer. 3619 5.3.4.2. Initiator Role State Tables 3621 The rules and state tables for the Initiator role use the following 3622 operations: 3624 o The "Build RIB Entries" operation is defined as: 3626 1. Recording the state of the local dictionary. 3628 2. Determining the set of EIDs for which RIB entries should be 3629 sent during this execution of the Initiator role state machine 3630 component. If this is a second or subsequent run of the state 3631 machine in this node during the current session with the 3632 connected peer then the set of EIDs may be empty if no changes 3633 have occurred since the previous run of the state machine. 3635 3. Determining and extracting the current delivery predictability 3636 information for the set of EIDs selected. 3638 o The "Send RIB Entries" operation formats one or more RIB TLVs with 3639 the set of RIB entries identified in the "Build RIB Entries" 3640 operation and sends them to the peer. If the set is empty, a 3641 single RIB TLV with zero entries is sent. If more than one RIB 3642 TLV is sent, all but the last one MUST have the "More RIB TLVs" 3643 flag set to 1; the last or only one MUST have the flag set to 0. 3645 o The "Clear Bundle Lists" operation is defined as emptying the 3646 lists of bundles offered by and bundles requested from the peer. 3648 o The "Notify Acks" operation is defined as informing the bundle 3649 agent that PRoPHET Acks has been received for one or more bundles 3650 in a Bundle Offer TLV using the Bundle Delivered interface (see 3651 Section 2.2). 3653 o The "Record Offers" operation is defined as recording all the 3654 bundles offered in a Bundle Offer TLV in the list of bundles 3655 offers. 3657 o The "Select for Request" operation prunes and sorts the list of 3658 offered bundles held into the list of requested bundles according 3659 to policy and available resources ready for sending to the 3660 offering node. 3662 o The "Send Requests" operation is defined as formatting one or more 3663 non-empty Bundle Response TLVs and sending them to the offering 3664 node.If more than one Bundle Offer TLV is sent, all but the last 3665 one MUST have the More Offer/ 3666 Response TLVs Following flag set to 1; the last or only 3667 one MUST have the flag set to 0. 3669 o The "Record Bundle Received" operation deletes a successfully 3670 received bundle from the list of requests. 3672 o The "All Requests Done" operation is defined as formatting and 3673 sending an empty Bundle Offer TLV, with the More Offer/ 3674 Response TLVs Following flag set to 0, to the offering 3675 node. 3677 o The "Check Receiving" operation is defined as checking with the 3678 node bundle agent if bundle reception from the peer node is 3679 currently in progress. Needed in case a timeout occurs while 3680 waiting for bundle reception and a very large bundle is being 3681 processed. 3683 The following events are specific to the Initiator role state 3684 machine: 3686 LastBndlRcvd Bundle received from peer that is the only remaining 3687 bundle in Bundle Requests List. 3689 NotLastBndlRcvd Bundle received from peer that is not the only 3690 remaining bundle in Bundle Requests List. 3692 OFRnotlast Bundle Offer TLV received with More Offer/Response TLVs 3693 Following flag set to 1. 3695 OFRlast Bundle Offer TLV received with More Offer/Response TLVs 3696 Following flag set to 0 3698 Timeout(next_exch) The Timer(next_exchange) has expired 3699 State: CREATE_DR 3701 +==================================================================+ 3702 | Condition | Action | New State | 3703 +==================+===================================+===========+ 3704 | On Entry | If previous state was ESTAB: | | 3705 | | Initialize Dictionary | | 3706 | | Always: | | 3707 | | Build RIB Entries | | 3708 | | Wait for Init Start | CREATE_DR | 3709 +------------------+-----------------------------------+-----------+ 3710 | InitStart | Send RIB Dictionary Updates | | 3711 | | Send RIB Entries | | 3712 | | Start TI | SEND_DR | 3713 +------------------+-----------------------------------+-----------+ 3714 | ErrDC | Abort Exchange |(finished) | 3715 +------------------+-----------------------------------+-----------+ 3716 | ErrBadSI | Abort Exchange |(finished) | 3717 +------------------+-----------------------------------+-----------+ 3718 | HelloAck | Abort Exchange | CREATE_DR | 3719 +==================================================================+ 3720 State: SEND_DR 3722 +==================================================================+ 3723 | Condition | Action | New State | 3724 +==================+===================================+===========+ 3725 | On Entry | Clear Bundle Lists | SEND_DR | 3726 +------------------+-----------------------------------+-----------+ 3727 | Timeout(info) | Send RIB Dictionary Updates | | 3728 | | Send RIB Entries (note 1) | SEND_DR | 3729 +------------------+-----------------------------------+-----------+ 3730 | RIBDl received | Update Dictionary (note 2) | | 3731 | | If Dictionary Conflict found: | | 3732 | | Abort Exchange | CREATE_DR | 3733 | | Else: | | 3734 | | Start TI | SEND_DR | 3735 +------------------+-----------------------------------+-----------+ 3736 | OFRnotlast | Notify Acks | | 3737 | | Record Offers | | 3738 | | Start TI | SEND_DR | 3739 +------------------+-----------------------------------+-----------+ 3740 | OFRlast | Cancel TI | | 3741 | | Notify Acks | | 3742 | | Record Offers | | 3743 | | Select for Request | | 3744 | | Send Requests | | 3745 | | Start TI | REQUEST | 3746 +------------------+-----------------------------------+-----------+ 3747 | ErrDC | Abort Exchange |(finished) | 3748 +------------------+-----------------------------------+-----------+ 3749 | ErrBadSI | Abort Exchange |(finished) | 3750 +------------------+-----------------------------------+-----------+ 3751 | HelloAck | Abort Exchange | CREATE_DR | 3752 +==================================================================+ 3753 State: REQUEST 3755 +==================================================================+ 3756 | Condition | Action | New State | 3757 +==================+===================================+===========+ 3758 | Timeout(info) | Check Receiving | | 3759 | | If bundle reception in progress: | | 3760 | | Start TI | REQUEST | 3761 | | Otherwise: | | 3762 | | Send Requests | | 3763 | | Start TI (note 3) | REQUEST | 3764 +------------------+-----------------------------------+-----------+ 3765 | NotLastBndlRcvd | Record Bundle Received | | 3766 | | Start TI | REQUEST | 3767 +------------------+-----------------------------------+-----------+ 3768 | LastBndlRecd | Cancel TI | | 3769 | | All Requests Done | | 3770 | | Start next_exchange timer | REQUEST | 3771 +------------------+-----------------------------------+-----------+ 3772 |Timeout(next_exch)| | CREATE_DR | 3773 +------------------+-----------------------------------+-----------+ 3774 | HelloAck | Abort Exchange | CREATE_DR | 3775 +==================================================================+ 3777 Note 1: 3778 No response to the RIB has been received before the timer expired, 3779 so we resend the dictionary and RIB TLVs. If the timeout occurs 3780 repeatedly it is likely that communication has failed and the 3781 connection MUST be terminated. 3783 Note 2: 3784 If a Dictionary Conflict error has to be sent the state machine 3785 will be aborted. If this event occurs repeatedly it is likely 3786 that there is either a serious software problem or a security 3787 issue. The connection MUST be terminated. 3789 Note 3: 3790 Remaining requested bundles have not arrived before the timer 3791 expired, so we resend the list of outstanding requests. If the 3792 timeout occurs repeatedly it is likely that communication has 3793 failed and the connection MUST be terminated. 3795 5.3.4.3. Listener Role State Tables 3797 The rules and state tables for the Listener role use the following 3798 operations: 3800 o The "Clear Supplied RIBs" operation is defined as setting up a an 3801 empty container to hold the set of RIBs supplied by the peer node. 3802 Note that any existing set of delivery predictabilities should be 3803 retained in case an empty set is supplied meaning that the 3804 existing set should be reused. 3806 o The "Record RIBs Supplied" operation is defined as: 3808 1. Taking the RIB entries from a received RIB TLV. 3810 2. Verifying that the String ID used in each entry is present in 3811 the dictionary. If not an Error TLV containing the offending 3812 String ID is sent to the peer, the Initiator and Listener 3813 processes are aborted and restarted as if the ESTAB state had 3814 just been reached. 3816 3. If all the String IDs are present in the dictionary, record 3817 the delivery predictabilities for each EID in the entries. 3819 o The "Recalc Dlvy Predictabilities" operation uses the algorithms 3820 defined in Section 2.1.2 to update the local set of delivery 3821 predictabilities using the using the set of delivery 3822 predictabilities supplied by the peer in RIB TLVs. 3824 o The "Determine Offers" operation determines the set of bundles to 3825 be offered to the peer. The local delivery predictabilities and 3826 the delivery predictabilities supplied by the peer are compared 3827 and a prioritized choice of the bundles stored in this node to be 3828 offered to the peer is made according to the configured queuing 3829 policy and forwarding strategy. 3831 o The "Determine Acks" operation is defined as obtaining the set of 3832 PRoPHET Acks recorded by the bundle agent that need to be 3833 forwarded to the peer. The list of PRoPHET ACks is maintained 3834 internally by the PRoPHET protocol implementation rather than the 3835 main bundle agent (see Section 3.5). 3837 o The "Determine Offer Dict Updates" operation is defined as 3838 determining any extra EIDs that are not already in the dictionary, 3839 recording the previous state of the local dictionary and then 3840 adding the required extra entries to the dictionary. 3842 o The "Send Offers" operation is defined as formatting one or more 3843 non-empty Bundle Offer TLVs incorporating the sets of Offers and 3844 PRoPHET Acks previously determined and sending them to the peer 3845 node. If more than one Bundle Offer TLV is sent, all but the last 3846 one MUST have the More Offer/Response TLVs Following flag set to 3847 1; the last or only one MUST have the flag set to 0. 3849 o The "Record Requests" operation is defined as recording all the 3850 bundles offered in a Bundle Offer TLV in the list of bundles 3851 offers. Duplicates MUST be ignored. The order of requests in the 3852 TLVs MUST be maintained so far as is possible (it is potentially 3853 possible that a bundle has to be resent and this may result in out 3854 of order delivery>) 3856 o The "Send Bundles" operation is defined as sending, in the order 3857 requested, the bundles in the requested list. This requires the 3858 list to be communicated to the bundle agent (see Section 2.2). 3860 o The "Check Initiator Start Point" operation is defined as checking 3861 the configured sequential operation policy to determine if the 3862 Listener role has reached the point where the Initiator role 3863 should be started. If so the InitStart notification is sent to 3864 the Initiator role in the same node. 3866 The following events are specific to the Listener role state machine: 3868 RIBnotlast RIB TLV received with More RIB TLVs flag set to 1. 3870 RIBlast RIB TLV received with More RIB TLVs flag set to 0 and a 3871 non-zero count of RIB Entries. 3873 REQnotlast Bundle Response TLV received with More Offer/Response 3874 TLVs Following flag set to 1. 3876 REQlast Bundle Response TLV received with More Offer/Response 3877 TLVs Following flag set to 0 and a non-zero count of 3878 Bundle Offers. 3880 REQempty Bundle Response TLV received with More Offer/Response 3881 TLVs Following flag set to 0 and a zero count of Bundle 3882 Offers. 3884 State: WAIT_DICT 3886 +==================================================================+ 3887 | Condition | Action | New State | 3888 +==================+===================================+===========+ 3889 | On Entry | Check Initiator Start Point | WAIT_DICT | 3890 +------------------+-----------------------------------+-----------+ 3891 | RIBDi | Update Dictionary (note 1) | | 3892 | | If Dictionary Conflict found: | | 3893 | | Abort Exchange |(finished) | 3894 | | Else: | | 3895 | | Start TP | WAIT_RIB | 3896 +------------------+-----------------------------------+-----------+ 3897 | HelloAck | Abort Exchange | WAIT_DICT | 3898 +==================================================================+ 3899 State: WAIT_RIB 3901 +==================================================================+ 3902 | Condition | Action | New State | 3903 +==================+===================================+===========+ 3904 | On Entry | Clear Supplied RIBS | WAIT_RIB | 3905 +------------------+-----------------------------------+-----------+ 3906 | RIBDi | Update Dictionary (note 1) | | 3907 | | If Dictionary Conflict found: | | 3908 | | Abort Exchange |(finished) | 3909 | | Else: | | 3910 | | Start TP | WAIT_RIB | 3911 +------------------+-----------------------------------+-----------+ 3912 | RIBnotlast | Record RIBS Supplied (note 2) | | 3913 | | If EID missing in dictionary: | | 3914 | | Abort Exchange |(finished) | 3915 | | Else: | | 3916 | | Start TP | WAIT_RIB | 3917 +------------------+-----------------------------------+----------- 3918 | RIBlast | Check Initiator Start Point | | 3919 | | Record RIBS Supplied (note 2) | | 3920 | | If EID missing in dictionary: | | 3921 | | Abort Exchange |(finished) | 3922 | | Otherwise | | 3923 | | Recalc Dlvy | | 3924 | | Predictabilities | | 3925 | | Cancel TP | | 3926 | | Determine Offers | | 3927 | | Determine Acks | | 3928 | | Determine Offer | | 3929 | | Dict Updates | | 3930 | | Send RIB Dictionary | | 3931 | | Updates | | 3932 | | Send Offers | | 3933 | | Start TI | OFFER | 3934 +------------------+-----------------------------------+-----------+ 3935 | HelloAck | Abort Exchange | WAIT_DICT | 3936 +------------------+-----------------------------------+-----------+ 3937 |Any Other TLV rcvd| Abort Exchange |(finished) | 3938 +------------------+-----------------------------------+-----------+ 3939 | Timeout(peer) | Send RIB Dictionary Updates | | 3940 | | Send Offers | | 3941 | | Start TI (note 3) | OFFER | 3942 +==================================================================+ 3943 State: OFFER 3945 +==================================================================+ 3946 | Condition | Action | New State | 3947 +==================+===================================+===========+ 3948 | REQnotlast | Send Bundles | | 3949 | | Start TI | OFFER | 3950 +------------------+-----------------------------------+-----------+ 3951 | REQlast | Cancel TI | | 3952 | | Check Initiator Start Point | | 3953 | | Send Bundles | SND_BUNDLE| 3954 +------------------+-----------------------------------+-----------+ 3955 | REQempty | Cancel TI | | 3956 | | Check Initiator Start Point | WAIT_MORE| 3957 +------------------+-----------------------------------+-----------+ 3958 | HelloAck | Abort Exchange | WAIT_DICT | 3959 +------------------+-----------------------------------+-----------+ 3960 | Timeout(info) | Send RIB Dictionary Updates | | 3961 | | Send Offers | | 3962 | | Start TI (note 3) | OFFER | 3963 +==================================================================+ 3965 State: SND_BUNDLE 3967 +==================================================================+ 3968 | Condition | Action | New State | 3969 +==================+===================================+===========+ 3970 | REQnotlast | Send Bundles | | 3971 | | Start TI | SND_BUNDLE| 3972 +------------------+-----------------------------------+-----------+ 3973 | REQlast | Cancel TI | | 3974 | | Send Bundles | SND_BUNDLE| 3975 +------------------+-----------------------------------+-----------+ 3976 | REQempty | Cancel TI | | 3977 | | Check Initiator Start Point | WAIT_MORE| 3978 +------------------+-----------------------------------+-----------+ 3979 | HelloAck | Abort Exchange | WAIT_DICT | 3980 +------------------+-----------------------------------+-----------+ 3981 | Timeout(info) | Send RIB Dictionary Updates | | 3982 | | Send Offers | | 3983 | | Start TI (note 3) | OFFER | 3984 +==================================================================+ 3985 State: WAIT_MORE 3987 +==================================================================+ 3988 | Condition | Action | New State | 3989 +==================+===================================+===========+ 3990 | More Bundles | Determine Offers | | 3991 | | Determine Acks | | 3992 | | Determine Offer | | 3993 | | Dict Updates | | 3994 | | Send RIB Dictionary | | 3995 | | Updates | | 3996 | | Send Offers | | 3997 | | Start TI | OFFER | 3998 +------------------+-----------------------------------+-----------+ 3999 | RIBDi | Update Dictionary (note 1) | | 4000 | | If Dictionary Conflict found: | | 4001 | | Abort Exchange |(finished) | 4002 | | Else: | | 4003 | | Start TP | WAIT_RIB | 4004 +------------------+-----------------------------------+-----------+ 4005 | REQnotlast | Send Bundles | | 4006 | | Start TI | SND_BUNDLE| 4007 +------------------+-----------------------------------+-----------+ 4008 | REQlast | Cancel TI | | 4009 | | Send Bundles | SND_BUNDLE| 4010 +------------------+-----------------------------------+-----------+ 4011 | REQempty | Cancel TI | | 4012 | | Check Initiator Start Point | SND_BUNDLE| 4013 +------------------+-----------------------------------+-----------+ 4014 | HelloAck | Abort Exchange | WAIT_DICT | 4015 +------------------+-----------------------------------+-----------+ 4016 | Timeout(info) | Send RIB Dictionary Updates | | 4017 | | Send Offers | | 4018 | | Start TI (note 3) | OFFER | 4019 +==================================================================+ 4021 Note 1: Both the dictionary and the RIB TLVs may come in the same 4022 PRoPHET message. In that case, the state will change to WAIT_RIB 4023 and the RIB will then immediately be processed. 4025 Note 2: Send an ACK if the timer for the peering node expires. 4026 Either the link has been broken, and then the link setup will 4027 restart, or it will trigger the information exchange phase to 4028 restart. 4030 Note 3: When the RIB is received it is possible for the PRoPHET 4031 agent to update its delivery predictabilities according to 4032 Section 2.1.2. The delivery predictabilities and the RIB is then 4033 used together with the forwarding strategy in use to create a 4034 bundle offer TLV. This is sent to the peering node. 4036 Note 4: No more bundles are requested by the other node, transfer 4037 is complete. 4039 Note 5: No response to the bundle offer has been received before 4040 the timer expired, so we resend the bundle offer. 4042 5.4. Interaction with Nodes Using Version 1 of PRoPHET 4044 There are existing implementations of PRoPHET based on drafts of this 4045 specification prior to version 06 that use version 1 of the protocol. 4046 There are a number of significant areas of difference between version 4047 1 and version 2 as described in this document: 4049 o the delivery predictability update equations were significantly 4050 different, and in the case of the transitivity equation (Equation 4051 3) could lead to degraded performance or non-delivery of bundles 4052 in some circumstances in version 1, 4054 o constraints were placed on the String IDs generated by each node 4055 to ensure that it was not possible for there to be a conflict if 4056 the IDs were generated concurrently and independently in the two 4057 nodes, 4059 o a flag has been added to the Routing Information Base Dictionary 4060 TLV to distinguish dictionary updates sent by the Initiator role 4061 and by the Listener role, 4063 o the Bundle Offer and Response TLVs have been significantly 4064 revised. The version 2 TLVs have been allocated new TLV Type 4065 numbers and the version 1 TLVs (types 0xA2 and 0xA3) are now 4066 deprecated. For each bundle specifier the source EID is 4067 transmitted in addition to the creation timestamp by version 2 to 4068 ensure that the bundle is uniquely identified. Version 2 also 4069 transmits the fragment payload offset and length when the offered 4070 bundle is a bundle fragment. The payload length can optionally be 4071 transmitted for each bundle whether or not it is a fragment to 4072 give the receiver additional information that can be useful when 4073 determining which bundle offers to accept. 4075 o The behaviour of the system after the first information exchange 4076 process has been better defined. The state machine has been 4077 altered to better describe how the ongoing operations work. This 4078 has involved the removal of the high level state WAIT_INFO and the 4079 addition of two states in the Listener role subsidiary state 4080 machine (SND_BUNDLE and WAIT_MORE). The protocol on the wire has 4081 not been altered by this change to the description of the state 4082 machine. However, the specification of the later stages of 4083 operation was slightly vague and might have been interpreted 4084 differently by various implementers. 4086 A node implementing version 2 of the PRoPHET protocol as defined in 4087 this document MAY choose either to ignore a communication opportunity 4088 with a node that sends a HELLO message indicating that it uses 4089 version 1 or it MAY partially downgrade and respond to messages as if 4090 it were a version 1 node. This means that the version field in all 4091 message headers MUST contain 1. 4093 It is RECOMMENDED that the version 2 node use the metric update 4094 equations defined in this document even when communicating with a 4095 version 1 node as this will partially inhibit the problems with the 4096 transitivity equation in version 1, and that the version 2 node 4097 should modify any received metrics that are greater than (1 - delta) 4098 to be (1 - delta) to avoid becoming a 'sink' for bundles that are not 4099 destined for this node. Also version 1 nodes cannot be explicitly 4100 offered bundle fragments and an exchange with a node supporting 4101 version 1 MUST use the, now deprecated, previous versions of the 4102 Bundle Offer and Response TLVs. 4104 Generally, nodes using version 1 should be upgraded if at all 4105 possible because of problems that have been identified. 4107 6. Security Considerations 4109 Currently, PRoPHET does not specify any special security measures. 4110 As a routing protocol for intermittently connected networks, PRoPHET 4111 is a target for various attacks. The various known possible 4112 vulnerabilities are discussed in this section. 4114 The attacks described here are not problematic if all nodes in the 4115 network can be trusted and are working towards a common goal. If 4116 there exist such a set of nodes, but there also exist malicious 4117 nodes, these security problems can be solved by introducing an 4118 authentication mechanism when two nodes meet, for example using a 4119 public key system. Thus, only nodes that are known to be members of 4120 the trusted group of nodes are allowed to participate in the routing. 4121 This of course introduces the additional problem of key distribution, 4122 but that is not addressed here. 4124 Where suitable, the mechanisms (such as key management and bundle 4125 authentication or integrity checks) and terminology specified by the 4126 Bundle Security Protocol [RFC6257] is to be used. 4128 6.1. Attacks on the Operation of the Protocol 4130 There are a number of kinds of attacks on the operation of the 4131 protocol that it would be possible to stage on a PRoPHET network. 4132 The attacks and possible remedies are listed here. 4134 6.1.1. Black Hole Attack 4136 A malicious node sets its delivery predictabilities for all 4137 destinations to a value close to or exactly equal to 1 and/or 4138 requests all bundles from nodes it meets, and does not forward any 4139 bundles. This has two effects, both causing messages to be drawn 4140 towards the black hole, instead of to its correct destination. 4142 1. A node encountering a malicious node will try to forward all its 4143 bundles to the malicious node, creating the belief that the 4144 bundle has been very favorably forwarded. Depending on the 4145 forwarding strategy and queueing policy in use, this might hamper 4146 future forwarding of the bundle and/or lead to premature dropping 4147 of the bundle. 4149 2. Due to the transitivity, the delivery predictabilities reported 4150 by the malicious node will affect the delivery predictabilities 4151 of other nodes. This will create a gradient for all destinations 4152 with the black hole as the "center of gravity" towards which all 4153 bundles traverse. This should be particularly severe in 4154 connected parts of the network. 4156 6.1.1.1. Attack detection 4158 A node receiving a set of delivery predictabilities that are all at 4159 or close to 1 should be suspicious. Similarly, a node which accepts 4160 all bundles and offers none might be considered suspicious. However 4161 these conditions are not impossible in normal operation. 4163 6.1.1.2. Attack prevention/solution 4165 To prevent this attack, authentication between nodes that meet needs 4166 to be present. Nodes can also inspect the received metrics and 4167 bundle acceptances/offers for suspicious patterns and terminate 4168 communications with nodes that appear suspicious. The natural 4169 evolution of delivery predictabilities should mean that a genuine 4170 node would not be permanently ostracized even if the values lead to 4171 termination of a communication opportunity on one occasion. The 4172 epidemic nature of PRoPHET would mean that such a termination would 4173 not generally lead to non-delivery of bundles. 4175 6.1.2. Limited Black Hole Attack/Identity Spoofing 4177 A malicious node misrepresents itself by claiming to be someone else. 4178 The effects of this attack are: 4180 1. The effects of the black hole attack listed above hold for this 4181 attack as well, with the exception that only the delivery 4182 predictabilities and bundles for one particular destination are 4183 affected. This could be used to "steal" the data that should be 4184 going to a particular node. 4186 2. In addition to the above problems, PRoPHET ACKs will be issued 4187 for the bundles that are delivered to the malicious node. This 4188 will cause these bundles to be removed from the network, reducing 4189 the chance that they will reach their real destination. 4191 6.1.2.1. Attack Detection 4193 It is possible for the destination to detect that this kind of attack 4194 has occurred (but it will not be able to prevent it) if it receives a 4195 PRoPHET ACK for a bundle destined to itself but for which it did not 4196 receive the corresponding bundle. 4198 6.1.2.2. Attack Prevention/Solution 4200 To prevent this attack, authentication between nodes that meet needs 4201 to be present. 4203 6.1.3. Fake PRoPHET ACKs 4205 A malicious node may issue fake PRoPHET ACKs for all bundles (or only 4206 bundles for a certain destination if the attack is targeted at a 4207 single node) carried by nodes it meet. The affected bundles will be 4208 deleted from the network, greatly reducing their probability of being 4209 delivered to the destination. 4211 6.1.3.1. Attack Prevention/Solution 4213 If a public key cryptography system is in place, this attack can be 4214 prevented by mandating that all PRoPHET ACKs be signed by the 4215 destination. Similarly to other solutions using public key 4216 cryptography, this introduces the problem of key distribution. 4218 6.1.4. Bundle Store Overflow 4220 After encountering and receiving the delivery predictability 4221 information from the victim, a malicious node may generate a large 4222 number of fake bundles for the destination for which the victim has 4223 the highest delivery predictability. This will cause the victim to 4224 most likely accept these bundles, filling up its bundle storage, 4225 possibly at the expense of other, legitimate, bundles. This problem 4226 is transient as the messages will be removed when the victim meets 4227 the destination and delivers the messages. 4229 6.1.4.1. Attack Detection 4231 If it is possible for the destination to figure out that the bundles 4232 it is receiving are fake, it could report that malicious actions are 4233 underway. 4235 6.1.4.2. Attack Prevention/Solution 4237 This attack could be prevented by requiring sending nodes to sign all 4238 bundles they send. By doing this, intermediate nodes could verify 4239 the integrity of the messages before accepting them for forwarding. 4241 6.1.5. Bundle Store Overflow with Delivery Predictability Manipulation 4243 A more sophisticated version of the attack in the previous section 4244 can be attempted. The effect of the previous attack was lessened 4245 since the destination node of the fake bundles existed. This caused 4246 fake bundles to be purged from the network when the destination was 4247 encountered. The malicious node may now use the transitive property 4248 of the protocol to boost the victim's delivery predictabilities for a 4249 non-existent destination. After this, it creates a large number of 4250 fake bundles for this non-existent destination and offers them to the 4251 victim. As before, these bundles will fill up the bundle storage of 4252 the victim. The impact of this attack will be greater as there is no 4253 probability of the destination being encountered and the bundles 4254 being acknowledged. Thus, they will remain in the bundle storage 4255 until they time out (the malicious node may set the timeout to a 4256 large value) or until they are evicted by the queueing policy. 4258 The delivery predictability for the fake destination may spread in 4259 the network due to the transitivity, but this is not a problem, as it 4260 will eventually age and fade away. 4262 The impact of this attack could be increased if multiple malicious 4263 nodes collude, as network resources can be consumed at a greater 4264 speed and at many different places in the network simultaneously. 4266 6.2. Interactions with External Routing Domains 4268 Users may opt to connect two regions of sparsely connected nodes 4269 through a connected network such as the Internet where another 4270 routing protocol is running. To this network, PRoPHET traffic would 4271 look like any other application layer data. Extra care must be taken 4272 in setting up these gateway nodes and their interconnections to make 4273 sure that malicious nodes cannot use them to launch attacks on the 4274 infrastructure of the connected network. In particular, the traffic 4275 generated should not be significantly more than what a single regular 4276 user end host could create on the network. 4278 7. IANA Considerations 4280 Following the policies outlined in "Guidelines for Writing an IANA 4281 Considerations Section in RFCs" (RFC 5226 [RFC5226]), the following 4282 name spaces are defined in PRoPHET: 4284 o For fields in the PRoPHET message header (Section 4.1): 4286 * DTN Routing Protocol Number 4288 * PRoPHET Protocol Version 4290 * PRoPHET Header Flags 4292 * PRoPHET Result Field 4294 * PRoPHET Codes for Success and Codes for Failure 4296 o Identifiers for TLVs carried in PRoPHET messages: 4298 * PRoPHET TLV Type (Section 4.2) 4300 o Definitions of TLV Flags and other flag fields in TLVs: 4302 * Hello TLV Flags (Section 4.3.1) 4304 * Error TLV Flags (Section 4.3.2) 4306 * Routing Information Base (RIB) Dictionary TLV Flags 4307 (Section 4.3.3) 4309 * Routing Information Base (RIB) TLV Flags (Section 4.3.4) 4311 * Routing Information Base (RIB) Flags per entry (Section 4.3.4) 4313 * Bundle Offer and Response TLV Flags (Section 4.3.5) 4315 * Bundle Offer and Response B Flags per offer or response 4316 (Section 4.3.5) 4318 The following subsections lists the registries that are requested to 4319 be created. Initial values for the registries are given below; 4320 future assignments are to be made through the Specification Required 4321 policy. Where specific values are defined in the IANA registries to 4322 be setup according to the specifications in the sub-sections below, 4323 the registry should refer to this document as defining the 4324 allocation. 4326 7.1. DTN Routing Protocol Number 4328 The encoding of the Protocol Number field in the PRoPHET header 4329 (Section 4.1) is: 4331 +--------------------------+-----------+------------------------+ 4332 | Protocol | Value | Allocation Control | 4333 +--------------------------+-----------+------------------------+ 4334 | PRoPHET Protocol | 0x00 | This document | 4335 | | | | 4336 | Reserved | 0x01-0xEF | Specification required | 4337 | | | | 4338 | Private/Experimental use | 0xF0-0xFE | Experimental | 4339 +--------------------------+-----------+------------------------+ 4341 7.2. PRoPHET Protocol Version 4343 The encoding of the PRoPHET Version field in the PRoPHET header 4344 (Section 4.1) is: 4346 +------------------------------+-----------+------------------------+ 4347 | Version | Value | Allocation Control | 4348 +------------------------------+-----------+------------------------+ 4349 | Reserved | 0x00 | (Do not allocate) | 4350 | | | | 4351 | Earlier Drafts | 0x01 | This document | 4352 | | | | 4353 | This protocol | 0x02 | This document | 4354 | | | | 4355 | Reserved | 0x03-0xEF | Specification required | 4356 | | | | 4357 | Private | 0xF0-0xFE | Experimental | 4358 | | | | 4359 | Reserved for future | 0xFF | Specification required | 4360 | expansion | | | 4361 +------------------------------+-----------+------------------------+ 4363 7.3. PRoPHET Header Flags 4365 The following Flags are defined for the PRoPHET Header (Section 4.1): 4367 +----------+--------------+------------------------+ 4368 | Meaning | Bit Position | Explanation | 4369 +----------+--------------+------------------------+ 4370 | Reserved | Bit 0 | Specification required | 4371 | | | | 4372 | Reserved | Bit 1 | Specification required | 4373 | | | | 4374 | Reserved | Bit 2 | Specification required | 4375 | | | | 4376 | Reserved | Bit 3 | Specification required | 4377 +----------+--------------+------------------------+ 4379 7.4. PRoPHET Result Field 4381 The encoding of the Result field in the PRoPHET header (Section 4.1) 4382 is: 4384 +--------------------------+-------------+------------------------+ 4385 | Result Value | Value | Allocation Control | 4386 +--------------------------+-------------+------------------------+ 4387 | NoSuccessAck | 0x01 | This document | 4388 | | | | 4389 | AckAll | 0x02 | This document | 4390 | | | | 4391 | Success | 0x03 | This document | 4392 | | | | 4393 | Failure | 0x04 | This document | 4394 | | | | 4395 | ReturnReceipt | 0x05 | This document | 4396 | | | | 4397 | Reserved | 0x06 - 0x7F | Specification required | 4398 | | | | 4399 | Private/Experimental Use | 0x80 - 0xFF | Experimental | 4400 +--------------------------+-------------+------------------------+ 4402 7.5. PRoPHET Codes for Success and Codes for Failure 4404 The encoding for Code field in the PRoPHET header (Section 4.1) for 4405 "Success" messages is: 4407 +--------------------------+-------------+------------------------+ 4408 | Code Name | Values | Allocation Control | 4409 +--------------------------+-------------+------------------------+ 4410 | Generic Success | 0x00 | This document | 4411 | | | | 4412 | Submessage Received | 0x01 | This document | 4413 | | | | 4414 | Reserved | 0x02 - 0x7F | Specification required | 4415 | | | | 4416 | Private/Experimental Use | 0x80 - 0xFF | Experimental | 4417 +--------------------------+-------------+------------------------+ 4419 The encoding for Code in the PRoPHET header (Section 4.1) for 4420 "Failure" messages is: 4422 +--------------------------+-------------+------------------------+ 4423 | Code Name | Values | Allocation Control | 4424 +--------------------------+-------------+------------------------+ 4425 | Reserved | 0x00 - 0x01 | (Do not allocate) | 4426 | | | | 4427 | Unspecified Failure | 0x02 | This document | 4428 | | | | 4429 | Reserved | 0x03 - 0x7F | Specification required | 4430 | | | | 4431 | Private/Experimental Use | 0x80 - 0xFE | Experimental | 4432 | | | | 4433 | Error TLV in message | 0xFF | This document | 4434 +--------------------------+-------------+------------------------+ 4436 7.6. PRoPHET TLV Type 4438 The TLV Types defined for PRoPHET (Section 4.2) are: 4440 +--------------------------+-------------+------------------------+ 4441 | Type | Value | Allocation Control | 4442 +--------------------------+-------------+------------------------+ 4443 | Hello TLV | 0x01 | This document | 4444 | | | | 4445 | Error TLV | 0x02 | This document | 4446 | | | | 4447 | Reserved | 0x03 - 0x9F | Specification required | 4448 | | | | 4449 | RIB dictionary TLV | 0xA0 | This document | 4450 | | | | 4451 | RIB TLV | 0xA1 | This document | 4452 | | | | 4453 | Bundle Offer | 0xA2 | (Deprecated) | 4454 | | | | 4455 | Bundle Response | 0xA3 | (Deprecated) | 4456 | | | | 4457 | Bundle Offer (v2) | 0xA4 | This document | 4458 | | | | 4459 | Bundle Response (v2) | 0xA5 | This document | 4460 | | | | 4461 | Reserved | 0xA6 - 0xCF | Specification required | 4462 | | | | 4463 | Private/Experimental Use | 0xD0 - 0xFF | Experimental | 4464 +--------------------------+-------------+------------------------+ 4466 7.7. Hello TLV Flags 4468 The following TLV Flags are defined for the Hello TLV 4469 (Section 4.3.1). Flag numbers 0, 1 and 2 are treated as a three bit 4470 unsigned integer with five of the eight possible values allocated and 4471 the other three reserved. The remaining bits are treated 4472 individually: 4474 +----------+-------------------+------------------------+ 4475 | Meaning | Value | Allocation Control | 4476 +----------+-------------------+------------------------+ 4477 | | (Flags 0,1 and 2) | | 4478 | | | | 4479 | Reserved | 0b000 | Do not allocate | 4480 | | | | 4481 | SYN | 0b001 | This document | 4482 | | | | 4483 | SYNACK | 0b010 | This document | 4484 | | | | 4485 | ACK | 0b011 | This document | 4486 | | | | 4487 | RSTACK | 0x100 | This document | 4488 | | | | 4489 | Reserved | 0b101 - 0b111 | Specification required | 4490 | | | | 4491 | | (Flags 3 - 7) | | 4492 | | | | 4493 | Reserved | Flag 3 | Specification required | 4494 | | | | 4495 | Reserved | Flag 4 | Specification required | 4496 | | | | 4497 | Reserved | Flag 5 | Specification required | 4498 | | | | 4499 | Reserved | Flag 6 | Specification required | 4500 | | | | 4501 | L Flag | Flag 7 | This document | 4502 +----------+-------------------+------------------------+ 4504 7.8. Error TLV Flags 4506 The TLV Flags field in the Error TLV (Section 4.3.2) is treated as an 4507 unsigned 8 bit integer encoding the Error TLV number. The following 4508 values are defined: 4510 +---------------------+------------------+------------------------+ 4511 | Error TLV Name | Error TLV Number | Allocation Control | 4512 +---------------------+------------------+------------------------+ 4513 | Dictionary Conflict | 0x00 | This document | 4514 | | | | 4515 | Bad String ID | 0x01 | This document | 4516 | | | | 4517 | Reserved | 0x02 - 0x7F | Specification required | 4518 | | | | 4519 | Private | 0x80 - 0xFF | Experimental | 4520 +---------------------+------------------+------------------------+ 4522 7.9. RIB Dictionary TLV Flags 4524 The following TLV Flags are defined for the RIB Base Dictionary TLV 4525 (Section 4.3.3): 4527 +------------------+--------------+------------------------+ 4528 | Meaning | Bit Position | Allocation Control | 4529 +------------------+--------------+------------------------+ 4530 | Sent by Listener | Flag 0 | This document | 4531 | | | | 4532 | Reserved | Flag 1 | Reserved | 4533 | | | | 4534 | Reserved | Flag 2 | Reserved | 4535 | | | | 4536 | Reserved | Flag 3 | Specification required | 4537 | | | | 4538 | Reserved | Flag 4 | Specification required | 4539 | | | | 4540 | Reserved | Flag 5 | Specification required | 4541 | | | | 4542 | Reserved | Flag 6 | Specification required | 4543 | | | | 4544 | Reserved | Flag 7 | Specification required | 4545 +------------------+--------------+------------------------+ 4547 7.10. RIB TLV Flags 4549 The following TLV Flags are defined for the RIB TLV (Section 4.3.4): 4551 +---------------+--------------+------------------------+ 4552 | Meaning | Bit Position | Allocation Control | 4553 +---------------+--------------+------------------------+ 4554 | More RIB TLVs | Flag 0 | This document | 4555 | | | | 4556 | Reserved | Flag 1 | Reserved | 4557 | | | | 4558 | Reserved | Flag 2 | Reserved | 4559 | | | | 4560 | Reserved | Flag 3 | Specification required | 4561 | | | | 4562 | Reserved | Flag 4 | Specification required | 4563 | | | | 4564 | Reserved | Flag 5 | Specification required | 4565 | | | | 4566 | Reserved | Flag 6 | Specification required | 4567 | | | | 4568 | Reserved | Flag 7 | Specification required | 4569 +---------------+--------------+------------------------+ 4571 7.11. RIB Flags 4573 The following RIB Flags are defined for the individual entries in the 4574 RIB TLV (Section 4.3.4): 4576 +----------+--------------+------------------------+ 4577 | Meaning | Bit Position | Allocation Control | 4578 +----------+--------------+------------------------+ 4579 | Reserved | Flag 0 | Specification required | 4580 | | | | 4581 | Reserved | Flag 1 | Specification required | 4582 | | | | 4583 | Reserved | Flag 2 | Specification required | 4584 | | | | 4585 | Reserved | Flag 3 | Specification required | 4586 | | | | 4587 | Reserved | Flag 4 | Specification required | 4588 | | | | 4589 | Reserved | Flag 5 | Specification required | 4590 | | | | 4591 | Reserved | Flag 6 | Specification required | 4592 | | | | 4593 | Reserved | Flag 7 | Specification required | 4594 +----------+--------------+------------------------+ 4596 7.12. Bundle Offer and Response TLV Flags 4598 The following TLV Flags are defined for the Bundle Offer and Response 4599 TLV (Section 4.3.5): 4601 +------------------------------+-------------+----------------------+ 4602 | Meaning | Bit | Allocation Control | 4603 | | Position | | 4604 +------------------------------+-------------+----------------------+ 4605 | More Offer/Response TLVs | Flag 0 | This document | 4606 | Following | | | 4607 | | | | 4608 | Reserved | Flag 1 | Specification | 4609 | | | required | 4610 | | | | 4611 | Reserved | Flag 2 | Specification | 4612 | | | required | 4613 | | | | 4614 | Reserved | Flag 3 | Specification | 4615 | | | required | 4616 | | | | 4617 | Reserved | Flag 4 | Specification | 4618 | | | required | 4619 | | | | 4620 | Reserved | Flag 5 | Specification | 4621 | | | required | 4622 | | | | 4623 | Reserved | Flag 6 | Specification | 4624 | | | required | 4625 | | | | 4626 | Reserved | Flag 7 | Specification | 4627 | | | required | 4628 +------------------------------+-------------+----------------------+ 4630 7.13. Bundle Offer and Response B Flags 4632 The following B Flags are defined for each Bundle Offer in the Bundle 4633 Offer and Response TLV (Section 4.3.5): 4635 +--------------------------------+------------+---------------------+ 4636 | Meaning | Bit | Allocation Control | 4637 | | Position | | 4638 +--------------------------------+------------+---------------------+ 4639 | Bundle Accepted | Flag 0 | This document | 4640 | | | | 4641 | Bundle is a Fragment | Flag 1 | This document | 4642 | | | | 4643 | Bundle Payload Length Included | Flag 2 | This document | 4644 | in TLV | | | 4645 | | | | 4646 | Reserved | Flag 3 | Specification | 4647 | | | required | 4648 | | | | 4649 | Reserved | Flag 4 | Specification | 4650 | | | required | 4651 | | | | 4652 | Reserved | Flag 5 | Specification | 4653 | | | required | 4654 | | | | 4655 | Reserved | Flag 6 | Specification | 4656 | | | required | 4657 | | | | 4658 | PRoPHET Ack | Flag 7 | This document | 4659 +--------------------------------+------------+---------------------+ 4661 8. Implementation Experience 4663 Multiple independent implementations of the PRoPHET protocol exist. 4665 The first implementation is written in Java, and has been optimized 4666 to run on the Lego MindStorms platform that has very limited 4667 resources. Due to the resource constraints, some parts of the 4668 protocol have been simplified or omitted, but the implementation 4669 contains all the important mechanisms to ensure proper protocol 4670 operation. The implementation is also highly modular and can be run 4671 on another system with only minor modifications (it has currently 4672 been shown to run on the Lego MindStorms platform and on regular 4673 laptops). 4675 Another implementation is written in C++ and runs in the OmNet++ 4676 simulator to enable testing and evaluation of the protocol and new 4677 features. Experience and feedback from the implementers on early 4678 versions of the protocol have been incorporated into the current 4679 version. 4681 An implementation compliant to version 2 of the predecessor draft 4682 (draft-lindgren-prophet-02.txt) has been written at Baylor 4683 University. This implementation has been integrated into the DTN2 4684 reference implementation. 4686 An implementation of the protocol in C++ was developed by one of the 4687 authors (Samo Grasic) at Lulea University of Technology (LTU) as part 4688 of the Saami Networking Connectivity project (see Section 9) and 4689 continues to track the development of the protocol. This work is now 4690 part of the Networking for Communications Challenged Communities 4691 (N4C) project and is used in N4C testbeds. 4693 9. Deployment Experience 4695 During a week in August 2006, a proof-of-concept deployment of a DTN 4696 system, using the LTU PRoPHET implementation for routing was made in 4697 the Swedish mountains - the target area for the Saami Network 4698 Connectivity project [ccnc07][doria_02]. Four fixed camps with 4699 application gateways, one Internet gateway, and seven mobile relays 4700 were deployed. The deployment showed PRoPHET to be able to route 4701 bundles generated by different applications such as e-mail and web 4702 caching. 4704 Within the realms of the SNC and N4C projects, multiple other 4705 deployments, both during summer and winter conditions have been done 4706 at various scales during 2007-20010. [winsdr08] 4708 An implementation has been made for Android-based mobile telephones 4709 in the Bytewalla project [bytewalla]. 4711 10. Acknowledgements 4713 The authors would like to thank Olov Schelen and Kaustubh S. Phanse 4714 for contributing with valuable feedback regarding various aspects of 4715 the protocol. We would also like to thank all other reviewers and 4716 the DTNRG chairs for the feedback in the process of developing the 4717 protocol. The Hello TLV mechanism is loosely based on Adjacency 4718 message developed for RFC3292. Luka Birsa and Jeff Wilson have 4719 provided us with feedback from doing implementations of the protocol 4720 based on various preliminary versions of the draft. Their feedback 4721 has helped us make the draft easier to read for an implementer and 4722 has improved the protocol. 4724 11. References 4726 11.1. Normative References 4728 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 4729 Requirement Levels", BCP 14, RFC 2119, March 1997. 4731 [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol 4732 Specification", RFC 5050, November 2007. 4734 11.2. Informative References 4736 [I-D.irtf-dtnrg-tcp-clayer] 4737 Demmer, M. and J. Ott, "Delay Tolerant Networking TCP 4738 Convergence Layer Protocol", 4739 draft-irtf-dtnrg-tcp-clayer-02 (work in progress), 4740 November 2008. 4742 [RFC1058] Hedrick, C., "Routing Information Protocol", RFC 1058, 4743 June 1988. 4745 [RFC4838] Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, 4746 R., Scott, K., Fall, K., and H. Weiss, "Delay-Tolerant 4747 Networking Architecture", RFC 4838, April 2007. 4749 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 4750 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 4751 May 2008. 4753 [RFC6257] Symington, S., Farrell, S., Weiss, H., and P. Lovell, 4754 "Bundle Security Protocol Specification", RFC 6257, 4755 May 2011. 4757 [bytewalla] 4758 Prasad, M., "Bytewalla 3: Network architecture and PRoPHET 4759 implementation", Bytewalla Project, KTH Royal Institute of 4760 Technology, Stockholm, Sweden , October 2010, . 4764 [ccnc07] Lindgren, A. and A. Doria, "Experiences from Deploying a 4765 Real-life DTN System", Proceedings of the 4th Annual IEEE 4766 CONSUMER COMMUNICATIONS and NETWORKING CONFERENCE (CCNC 4767 2007), Las Vegas, Nevada, USA , January 2007. 4769 [doria_02] 4770 Doria, A., Uden, M., and D. Pandey, "Providing 4771 connectivity to the Saami nomadic community", Proceedings 4772 of the 2nd International Conference on Open Collaborative 4773 Design for Sustainable Innovation (dyd 02), Bangalore, 4774 India , December 2002. 4776 [lindgren_06] 4777 Lindgren, A. and K. Phanse, "Evaluation of Queueing 4778 Policies and Forwarding Strategies for Routing in 4779 Intermittently Connected Networks", Proceedings of 4780 COMSWARE 2006 , January 2006. 4782 [vahdat_00] 4783 Vahdat, A. and D. Becker, "Epidemic Routing for Partially 4784 Connected Ad Hoc Networks", Duke University Technical 4785 Report CS-200006, April 2000. 4787 [winsdr08] 4788 Lindgren, A., Doria, A., Lindblom, J., and M. Ek, 4789 "Networking in the Land of Northern Lights - Two Years of 4790 Experiences from DTN System Deployments", Proceedings of 4791 the ACM Wireless Networks and Systems for Developing 4792 Regions Workshop(WiNS-DR), San Francisco, California, 4793 USA , September 2008. 4795 Appendix A. PRoPHET Example 4797 To help grasp the concepts of PRoPHET, an example is provided to give 4798 a understanding of the transitive property of the delivery 4799 predictability, and the basic operation of PRoPHET. In Figure 13, we 4800 revisit the scenario where node A has a message it wants to send to 4801 node D. In the bottom right corner of subfigures a)-c), the delivery 4802 predictability tables for the nodes are shown. Assume that nodes C 4803 and D encounter each other frequently (Figure 13a) ), making the 4804 delivery predictability values they have for each other high. Now 4805 assume that node C also frequently encounters node B (Figure 13b) ). 4806 B and C will get high delivery predictability values for each other, 4807 and the transitive property will also increase the value B has for D 4808 to a medium level. Finally, node B meets node A (Figure 13c) ) that 4809 has a message for node D. Figure 13d) shows the message exchange 4810 between node A and node B. Summary vectors and delivery 4811 predictability information is exchanged, delivery predictabilities 4812 are updated, and node A then realized that P_(b,d) > P_(a,d), and 4813 thus forwards the message for D to node B. 4815 +----------------------------+ +----------------------------+ 4816 | | | | 4817 | C | | D | 4818 | D | | | 4819 | B | | B C | 4820 | | | | 4821 | | | | 4822 | | | | 4823 | | | | 4824 | A* | | A* | 4825 +-------------+--------------+ +-------------+--------------+ 4826 | A | B | C | D | | A | B | C | D | 4827 |B:low |A:low |A:low |A:low | |B:low |A:low |A:low |A:low | 4828 |C:low |C:low |B:low |B:low | |C:low |C:high|B:high |B:low | 4829 |D:low |D:low |D:high |C:high| |D:low |D:med |D:high |C:high| 4830 +-------------+--------------+ +-------------+--------------+ 4831 a) b) 4832 +----------------------------+ A B 4833 | | | | 4834 | D | |Summary vector&delivery pred| 4835 | | |--------------------------->| 4836 | C | |Summary vector&delivery pred| 4837 | | |<---------------------------| 4838 | | | | 4839 | B* | Update delivery predictabilities 4840 | A | | | 4841 | | Packet for D not in SV | 4842 +-------------+--------------+ P(b,d)>P(a,d) | 4843 | A | B | C | D | Thus, send | 4844 |B:low |A:low |A:low |A:low | | | 4845 |C:med |C:high|B:high |B:low | | Packet for D | 4846 |D:low+|D:med |D:high |C:high| |--------------------------->| 4847 +-------------+--------------+ | | 4848 c) d) 4850 Figure 13: PRoPHET example 4852 Appendix B. Neighbor Discovery Example 4854 This section outlines an example of a simple neighbor discovery 4855 protocol that can be run in-between PRoPHET and underlying layer in 4856 case lower layers do not provide methods for neighbor discovery. It 4857 assumes that the underlying layer supports broadcast messages as 4858 would be the case if a wireless infrastructure was involved. 4860 Each node needs to maintain a list of its active neighbors. The 4861 operation of the protocol is as follows: 4863 1. Every BEACON_INTERVAL milliseconds, the node does a local 4864 broadcast of a beacon that contains its identity and address, as 4865 well as the BEACON_INTERVAL value used by the node. 4867 2. Upon reception of a beacon, the following can happen: 4869 1. The sending node is already in the list of active neighbors. 4870 Update its entry in the list with the current time, and the 4871 node's BEACON_INTERVAL if it has changed. 4873 2. The sending node is not in the list of active neighbors. Add 4874 the node to the list of active neighbors and record the 4875 current time and the node's BEACON_INTERVAL. Notify the 4876 PRoPHET agent that a new neighbor is available ("New 4877 Neighbor", as described in Section 2.4). 4879 3. If a beacon has not been received from a node in the list of 4880 active neighbors within a time period of NUM_ACCEPTED_LOSSES * 4881 BEACON_INTERVAL (for the BEACON_INTERVAL used by that node), it 4882 should be assumed that this node is no longer a neighbor. The 4883 entry for this node should be removed from the list of active 4884 neighbors, and the PRoPHET agent should be notified that a 4885 neighbor has left ("Neighbor Gone", as described in Section 2.4). 4887 Appendix C. PRoPHET Parameter Calculation Example 4889 The evolution of the delivery predictabilities in a PRoPHET node is 4890 controlled by three main equations defined in Section 2.1.2. These 4891 equations use a number of parameters that need to be appropriately 4892 configured to ensure that the delivery predictabilities evolve in a 4893 way that mirrors the mobility model that applies in the PRoPET zone 4894 where the node is operating. 4896 When trying to describe the mobility model, it is more likely that 4897 the model will be couched in terms of statistical distribution of 4898 times between encounters and times to deliver a bundle in the zone. 4899 In this section one possible way of deriving the PRoPHET parameters 4900 from a more usual description of the model is presented. It should 4901 be remembered that this may not be the only solution, and its 4902 appropriateness will depend both on the overall mobility model and 4903 the distribution of the times involved. There is an implicit 4904 assumption in this work that these distributions can be characterized 4905 by a normal-type distribution with a well-defined first moment 4906 (mean). The exact form of the distribution is not considered here, 4907 but more detailed models may wish to use more specific knowledge 4908 about the distributions to refine the derivation of the parameters. 4910 To characterize the model we consider the following parameters: 4912 P1 The time resolution of the model. 4914 P2 The average time between encounters between nodes, I_typ, where 4915 the identity of the nodes is not taken into account. 4917 P3 The average number of encounters that a node has between meeting 4918 a particular node and meeting the same node again. 4920 P4 The average number of encounters needed to deliver a bundle in 4921 this zone. 4923 P5 The multiple of the average number of encounters needed to 4924 deliver a bundle (P4) after which it can be assumed that a node 4925 is not going to encounter a particular node again in the 4926 foreseeable future so that the delivery predictability ought to 4927 be decayed below P_first_threshold. 4929 P6 The number of encounters between a particular pair of nodes that 4930 should result in the delivery predictability of the encountered 4931 node getting close to the maximum possible delivery 4932 predictability (1 - delta). 4934 We can use these parameters to derive appropriate values for gamma 4935 and P_encounter_max which are the key parameters in the evolution of 4936 the delivery predictabilities. The values of the other parameters 4937 P_encounter_first (0.5), P_first_threshold (0.1) and delta (0.01), 4938 with the default values suggested in Figure 3, are generally not 4939 mobility model specific although in special cases P_encounter_first 4940 may be different if extra information is available. 4942 To select a value for gamma: 4943 After a single, unrepeated encounter, the delivery predictability of 4944 the encountered node should decay from P_encounter_first to 4945 P_first_threshold in the expected time for P4 * P5 encounters. Thus 4947 P_first_threshold = P_encounter_first * gamma ^ ((P2 * P4 * P5)/P1) 4949 which can be rearranged as 4951 gamma = 4952 exp(ln(P_first_threshold/P_encounter_first) * P1 / (P2* P4 * P5)). 4954 Typical values of gamma will be less than but very close to 1, 4955 usually greater than 0.99. The value has to be stored to several 4956 decimal places of accuracy, but implementations can create a table of 4957 values for specific intervals to reduce the amount of on-the-fly 4958 calculation required. 4960 Selecting a value for P_encounter_max: 4961 Once gamma has been determined, the decay factor for the average time 4962 between encounters between a specific pair of nodes can be 4963 calculated: 4964 Decay_typ = gamma ^ ((P2 * P3)/P1) 4966 Starting with P_encounter_first, using Decay_typ and applying 4967 Equation 1 from Section 2.1.2 (P6 -1) times, we can calculate the 4968 typical delivery predictability for the encountered node after P6 4969 encounters. The nature of Equation 1 is such that it is not easy to 4970 produce a closed form that generates a value of P_encounter_max from 4971 the parameter values, but using a spreadsheet to apply the equation 4972 repeatedly and tabulate the results will allow a suitable value of 4973 P_encounter_max to be chosen very simply. The evolution is not very 4974 sensitive to the value of P_encounter_max and values in the range 0.4 4975 to 0.8 will generally be appropriate. A value of 0.7 is recommended 4976 as a default. 4978 Once a PRoPHET zone has been in operation for some time, the logs of 4979 the actual encounters can and should be used to check that the 4980 selected parameters were appropriate, and to tune them as necessary. 4981 In the longer term, it may prove possible to install a learning mode 4982 in nodes so that the parameters can be adjusted dynamically to 4983 maintain best congruence with the mobility model that may itself 4984 change over time. 4986 Authors' Addresses 4988 Anders F. Lindgren 4989 Swedish Institute of Computer Science 4990 Box 1263 4991 Kista SE-164 29 4992 SE 4994 Phone: +46707177269 4995 Email: andersl@sics.se 4996 URI: http://www.sics.se/~andersl 4998 Avri Doria 4999 Consultant 5000 Providence RI 5001 US 5003 Phone: 5004 Email: avri@acm.org 5005 URI: http://psg.com/~avri 5007 Elwyn Davies 5008 Folly Consulting 5009 Soham 5010 UK 5012 Phone: 5013 Email: elwynd@folly.org.uk 5014 URI: 5016 Samo Grasic 5017 Lulea University of Technology 5018 Lulea SE-971 87 5019 SE 5021 Phone: 5022 Email: samo.grasic@ltu.se 5023 URI: