RFC 6693
Probabilistic Routing Protocol for Intermittently Connected Networks
Pages: 113
Experimental
Experimental
Part 1 of 4 – Pages 1 to 21
Internet Research Task Force (IRTF) A. Lindgren Request for Comments: 6693 SICS Category: Experimental A. Doria ISSN: 2070-1721 Technicalities E. Davies Folly Consulting S. Grasic Lulea University of Technology August 2012 Probabilistic Routing Protocol for Intermittently Connected NetworksAbstract
This document is a product of the Delay Tolerant Networking Research Group and has been reviewed by that group. No objections to its publication as an RFC were raised. This document defines PRoPHET, a Probabilistic Routing Protocol using History of Encounters and Transitivity. PRoPHET is a variant of the epidemic routing protocol for intermittently connected networks that operates by pruning the epidemic distribution tree to minimize resource usage while still attempting to achieve the best-case routing capabilities of epidemic routing. It is intended for use in sparse mesh networks where there is no guarantee that a fully connected path between the source and destination exists at any time, rendering traditional routing protocols unable to deliver messages between hosts. These networks are examples of networks where there is a disparity between the latency requirements of applications and the capabilities of the underlying network (networks often referred to as delay and disruption tolerant). The document presents an architectural overview followed by the protocol specification. Status of This Memo This document is not an Internet Standards Track specification; it is published for examination, experimental implementation, and evaluation. This document defines an Experimental Protocol for the Internet community. This document is a product of the Internet Research Task Force (IRTF). The IRTF publishes the results of Internet-related research and development activities. These results might not be suitable for deployment. This RFC represents the consensus of the Delay Tolerant Networking Research Group of the Internet Research
Task Force (IRTF). Documents approved for publication by the IRSG are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6693. Copyright Notice Copyright (c) 2012 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Relation to the Delay-Tolerant Networking Architecture . 7 1.2. Applicability of the Protocol . . . . . . . . . . . . . . 8 1.3. PRoPHET as Compared to Regular Routing Protocols . . . . 10 1.4. Requirements Notation . . . . . . . . . . . . . . . . . . 11 2. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1. PRoPHET . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1. Characteristic Time Interval . . . . . . . . . . . . 12 2.1.2. Delivery Predictability Calculation . . . . . . . . . 12 2.1.3. Optional Delivery Predictability Optimizations . . . 17 2.1.4. Forwarding Strategies and Queueing Policies . . . . . 18 2.2. Bundle Protocol Agent to Routing Agent Interface . . . . 19 2.3. PRoPHET Zone Gateways . . . . . . . . . . . . . . . . . . 20 2.4. Lower-Layer Requirements and Interface . . . . . . . . . 21 3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 22 3.1. Neighbor Awareness . . . . . . . . . . . . . . . . . . . 22 3.2. Information Exchange Phase . . . . . . . . . . . . . . . 23 3.2.1. Routing Information Base Dictionary . . . . . . . . . 25 3.2.2. Handling Multiple Simultaneous Contacts . . . . . . . 26 3.3. Routing Algorithm . . . . . . . . . . . . . . . . . . . . 28 3.4. Bundle Passing . . . . . . . . . . . . . . . . . . . . . 32 3.4.1. Custody . . . . . . . . . . . . . . . . . . . . . . . 33 3.5. When a Bundle Reaches Its Destination . . . . . . . . . . 33 3.6. Forwarding Strategies . . . . . . . . . . . . . . . . . . 34 3.7. Queueing Policies . . . . . . . . . . . . . . . . . . . . 36 4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 38 4.1. Header . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . 44 4.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . 45 4.3.2. Error TLV . . . . . . . . . . . . . . . . . . . . . . 47 4.3.3. Routing Information Base Dictionary TLV . . . . . . . 48 4.3.4. Routing Information Base TLV . . . . . . . . . . . . 50 4.3.5. Bundle Offer and Response TLVs (Version 2) . . . . . 51 5. Detailed Operation . . . . . . . . . . . . . . . . . . . . . 55 5.1. High-Level State Tables . . . . . . . . . . . . . . . . . 56 5.2. Hello Procedure . . . . . . . . . . . . . . . . . . . . . 59 5.2.1. Hello Procedure State Tables . . . . . . . . . . . . 61 5.3. Information Exchange Phase . . . . . . . . . . . . . . . 62 5.3.1. State Definitions for the Initiator Role . . . . . . 66 5.3.2. State Definitions for the Listener Role . . . . . . . 71 5.3.3. Recommendations for Information Exchange Timer Periods . . . . . . . . . . . . . . . . . . . . . . . 77 5.3.4. State Tables for Information Exchange . . . . . . . . 78 5.4. Interaction with Nodes Using Version 1 of PRoPHET . . . . 92
6. Security Considerations . . . . . . . . . . . . . . . . . . . 93 6.1. Attacks on the Operation of the Protocol . . . . . . . . 94 6.1.1. Black-Hole Attack . . . . . . . . . . . . . . . . . . 94 6.1.2. Limited Black-Hole Attack / Identity Spoofing . . . . 95 6.1.3. Fake PRoPHET ACKs . . . . . . . . . . . . . . . . . . 95 6.1.4. Bundle Store Overflow . . . . . . . . . . . . . . . . 96 6.1.5. Bundle Store Overflow with Delivery Predictability Manipulation . . . . . . . . . . . . . . . . . . . . 96 6.2. Interactions with External Routing Domains . . . . . . . 97 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 97 7.1. DTN Routing Protocol Number . . . . . . . . . . . . . . . 98 7.2. PRoPHET Protocol Version . . . . . . . . . . . . . . . . 98 7.3. PRoPHET Header Flags . . . . . . . . . . . . . . . . . . 99 7.4. PRoPHET Result Field . . . . . . . . . . . . . . . . . . 99 7.5. PRoPHET Codes for Success and Codes for Failure . . . . . 99 7.6. PRoPHET TLV Type . . . . . . . . . . . . . . . . . . . . 100 7.7. Hello TLV Flags . . . . . . . . . . . . . . . . . . . . . 101 7.8. Error TLV Flags . . . . . . . . . . . . . . . . . . . . . 101 7.9. RIB Dictionary TLV Flags . . . . . . . . . . . . . . . . 102 7.10. RIB TLV Flags . . . . . . . . . . . . . . . . . . . . . . 102 7.11. RIB Flags . . . . . . . . . . . . . . . . . . . . . . . . 103 7.12. Bundle Offer and Response TLV Flags . . . . . . . . . . . 103 7.13. Bundle Offer and Response B Flags . . . . . . . . . . . . 104 8. Implementation Experience . . . . . . . . . . . . . . . . . . 104 9. Deployment Experience . . . . . . . . . . . . . . . . . . . . 105 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 105 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 105 11.1. Normative References . . . . . . . . . . . . . . . . . . 105 11.2. Informative References . . . . . . . . . . . . . . . . . 106 Appendix A. PRoPHET Example . . . . . . . . . . . . . . . . . . 108 Appendix B. Neighbor Discovery Example . . . . . . . . . . . . . 110 Appendix C. PRoPHET Parameter Calculation Example . . . . . . . 1101. Introduction
The Probabilistic Routing Protocol using History of Encounters and Transitivity (PRoPHET) algorithm enables communication between participating nodes wishing to communicate in an intermittently connected network where at least some of the nodes are mobile. One of the most basic requirements for "traditional" (IP) networking is that there must exist a fully connected path between communication endpoints for the duration of a communication session in order for communication to be possible. There are, however, a number of scenarios where connectivity is intermittent so that this is not the case (thus rendering the end-to-end use of traditional networking protocols impossible), but where it still is desirable to allow communication between nodes.
Consider a network of mobile nodes using wireless communication with a limited range that is less than the typical excursion distances over which the nodes travel. Communication between a pair of nodes at a particular instant is only possible when the distance between the nodes is less than the range of the wireless communication. This means that, even if messages are forwarded through other nodes acting as intermediate routes, there is no guarantee of finding a viable continuous path when it is needed to transmit a message. One way to enable communication in such scenarios is by allowing messages to be buffered at intermediate nodes for a longer time than normally occurs in the queues of conventional routers (cf. Delay- Tolerant Networking [RFC4838]). It would then be possible to exploit the mobility of a subset of the nodes to bring messages closer to their destination by transferring them to other nodes as they meet. Figure 1 shows how the mobility of nodes in such a scenario can be used to eventually deliver a message to its destination. In this figure, the four sub-figures (a) - (d) represent the physical positions of four nodes (A, B, C, and D) at four time instants, increasing from (a) to (d). The outline around each letter represents the range of the radio communication used for communication by the nodes: communication is only possible when the ranges overlap. At the start time, node A has a message -- indicated by an asterisk (*) next to that node -- to be delivered to node D, but there does not exist a path between nodes A and D because of the limited range of available wireless connections. As shown in sub- figures (a) - (d), the mobility of the nodes allows the message to first be transferred to node B, then to node C, and when finally node C moves within range of node D, it can deliver the message to its final destination. This technique is known as "transitive networking". Mobility and contact patterns in real application scenarios are likely to be non-random, but rather be predictable, based on the underlying activities of the higher-level application (this could, for example, stem from human mobility having regular traffic patterns based on repeating behavioral patterns (e.g., going to work or the market and returning home) and social interactions, or from any number of other node mobility situations where a proportion of nodes are mobile and move in ways that are not completely random over time but have a degree of predictability over time). This means that if a node has visited a location or been in contact with a certain node several times before, it is likely that it will visit that location or meet that node again.
PRoPHET can also be used in some networks where such mobility as described above does not take place. Predictable patterns in node contacts can also occur among static nodes where varying radio conditions or power-saving sleeping schedules cause connection between nodes to be intermittent. In previously discussed mechanisms to enable communication in intermittently connected networks, such as Epidemic Routing [vahdat_00], very general approaches have been taken to the problem at hand. In an environment where buffer space and bandwidth are infinite, epidemic routing will give an optimal solution to the problem of routing in an intermittently connected network with regard to message delivery ratio and latency. However, in most cases, neither bandwidth nor buffer space is infinite, but instead they are rather scarce resources, especially in the case of sensor networks. PRoPHET is fundamentally an epidemic protocol with strict pruning. An epidemic protocol works by transferring its data to each and every node it meets. As data is passed from node to node, it is eventually passed to all nodes, including the target node. One of the advantages of an epidemic protocol is that by trying every path, it is guaranteed to try the best path. One of the disadvantages of an epidemic protocol is the extensive use of resources with every node needing to carry every packet and the associated transmission costs. PRoPHET's goal is to gain the advantages of an epidemic protocol without paying the price in storage and communication resources incurred by the basic epidemic protocol. That is, PRoPHET offers an alternative to basic epidemic routing, with lower demands on buffer space and bandwidth, with equal or better performance in cases where those resources are limited, and without loss of generality in scenarios where it is suitable to use PRoPHET. In a situation where PRoPHET is applicable, the patterns are expected to have a characteristic time (such as the expected time between encounters between mobile stations) that is in turn related to the expected time that traffic will take to reach its destination in the part of the network that is using PRoPHET. This characteristic time provides guidance for configuration of the PRoPHET protocol in a network. When appropriately configured, the PRoPHET protocol effectively builds a local model of the expected patterns in the network that can be used to optimize the usage of resources by reducing the amount of traffic sent to nodes that are unlikely to lead to eventual delivery of the traffic to its destination.
+----------------------------+ +----------------------------+ | ___ | | ___ | | ___ / \ | | / \ | | / \ ( D ) | | ( D ) | | ( B ) \___/ | | ___ \___/ | | \___/ ___ | | /___\ ___ | |___ / \ | | (/ B*\) / \ | | \ ( C ) | | (\_A_/) ( C ) | | A* ) \___/ | | \___/ \___/ | |___/ | | | +----------------------------+ +----------------------------+ (a) Time t (b) Time (t + dt) +----------------------------+ +----------------------------+ | _____ ___ | | ___ ___ | | / / \ \ / \ | | / \ /___\ | | ( (B C* ) ( D ) | | ( B ) (/ D*\) | | \_\_/_/ \___/ | | \___/ (\_C_/) | | ___ | | ___ \___/ | | / \ | | / \ | | ( A ) | | ( A ) | | \___/ | | \___/ | | | | | +----------------------------+ +----------------------------+ (c) Time (t + 2*dt) (d) Time (t + 3*dt) Figure 1: Example of transitive communication This document presents a framework for probabilistic routing in intermittently connected networks, using an assumption of non-random mobility of nodes to improve the delivery rate of messages while keeping buffer usage and communication overhead at a low level. First, a probabilistic metric called delivery predictability is defined. The document then goes on to define a probabilistic routing protocol using this metric.1.1. Relation to the Delay-Tolerant Networking Architecture
The Delay-Tolerant Networking (DTN) architecture [RFC4838] defines an architecture for communication in environments where traditional communication protocols cannot be used due to excessive delays, link outages, and other extreme conditions. The intermittently connected networks considered here are a subset of those covered by the DTN architecture. The DTN architecture defines routes to be computed based on a collection of "contacts" indicating the start time, duration, endpoints, forwarding capacity, and latency of a link in the topology graph. These contacts may be deterministic or may be
derived from estimates. The architecture defines some different types of intermittent contacts. The ones called "opportunistic" and "predicted" are the ones addressed by this protocol. Opportunistic contacts are those that are not scheduled, but rather present themselves unexpectedly and frequently arise due to node mobility. Predicted contacts are like opportunistic contacts, but, based on some information, it might be possible to draw some statistical conclusion as to whether or not a contact will be present soon. The DTN architecture also introduces the bundle protocol [RFC5050], which provides a way for applications to "bundle" an entire session, including both data and metadata, into a single message, or bundle, that can be sent as a unit. The bundle protocol also provides end- to-end addressing and acknowledgments. PRoPHET is specifically intended to provide routing services in a network environment that uses bundles as its data transfer mechanism but could be also be used in other intermittent environments.1.2. Applicability of the Protocol
The PRoPHET routing protocol is mainly targeted at situations where at least some of the nodes are mobile in a way that creates connectivity patterns that are not completely random over time but have a degree of predictability. Such connectivity patterns can also occur in networks where nodes switch off radios to preserve power. Human mobility patterns (often containing daily or weekly periodic activities) provide one such example where PRoPHET is expected to be applicable, but the applicability is not limited to scenarios including humans. In order for PRoPHET to benefit from such predictability in the contact patterns between nodes, it is expected that the network exist under similar circumstances over a longer timescale (in terms of node encounters) so that the predictability can be accurately estimated. The PRoPHET protocol expects nodes to be able to establish a local TCP link in order to exchange the information needed by the PRoPHET protocol. Protocol signaling is done out-of-band over this TCP link, without involving the bundle protocol agent [RFC5050]. However, the PRoPHET protocol is expected to interact with the bundle protocol agent to retrieve information about available bundles as well as to request that a bundle be sent to another node (it is expected that the associated bundle protocol agents are then able to establish a link (probably over the TCP convergence layer [CLAYER]) to perform this bundle transfer).
TCP provides a reliable bidirectional channel between two peers and guarantees in-order delivery of transmitted data. When using TCP, the guarantee of reliable, in-order delivery allows information exchanges of each category of information to be distributed across several messages without requiring the PRoPHET protocol layer to be concerned that all messages have been received before starting the exchange of the next category of information. At most, the last message of the category needs to be marked as such. This allows the receiver to process earlier messages while waiting for additional information and allows implementations to limit the size of messages so that IP fragmentation will be avoided and memory usage can be optimized if necessary. However, implementations MAY choose to build a single message for each category of information that is as large as necessary and rely on TCP to segment the message. While PRoPHET is currently defined to run over TCP, in future versions the information exchange may take place over other transport protocols, and these may not provide message segmentation or reliable, in-order delivery. The simple message division used with TCP MUST NOT be used when the underlying transport does not offer reliable, in-order delivery, as it would be impossible to verify that all the messages had arrived. Hence, the capability is provided to segment protocol messages into submessages directly in the PRoPHET layer. Submessages are provided with sequence numbers, and this, together with a capability for positive acknowledgements, would allow PRoPHET to operate over an unreliable protocol such as UDP or potentially directly over IP. Since TCP offers reliable delivery, it is RECOMMENDED that the positive acknowledgment capability is not used when PRoPHET is run over a TCP transport or similar protocol. When running over TCP, implementations MAY safely ignore positive acknowledgments. Whatever transport protocol is used, PRoPHET expects to use a bidirectional link for the information exchange; this allows for the information exchange to take place in both directions over the same link avoiding the need to establish a second link for information exchange in the reverse direction. In a large Delay- and Disruption-Tolerant Network (DTN), network conditions may vary widely, and in different parts of the network, different routing protocols may be appropriate. In this specification, we consider routing within a single "PRoPHET zone", which is a set of nodes among which messages are routed using PRoPHET. In many cases, a PRoPHET zone will not span the entire DTN, but there will be other parts of the network with other characteristics that run other routing protocols. To handle this, there may be nodes within the zone that act as gateways to other
nodes that are the destinations for bundles generated within the zone or that insert bundles into the zone. Thus, PRoPHET is not necessarily used end-to-end, but only within regions of the network where its use is appropriate.1.3. PRoPHET as Compared to Regular Routing Protocols
While PRoPHET uses a mechanism for pruning the epidemic forwarding tree that is similar to the mechanism used in metric-based vector routing protocols (where the metric might be distance or cost), it should not be confused with a metric vector protocol. In a traditional metric-based vector routing protocol, the information passed from node to node is used to create a single non- looping path from source to destination that is optimal given the metric used. The path consists of a set of directed edges selected from the complete graph of communications links between the network nodes. In PRoPHET, that information is used to prune the epidemic tree of paths by removing paths that look less likely to provide an effective route for delivery of data to its intended destination. One of the effects of this difference is that the regular notions of split horizon, as described in [RFC1058], do not apply to PRoPHET. The purpose of split horizon is to prevent a distance vector protocol from ever passing a packet back to the node that sent it the packet because it is well known that the source does not lie in that direction as determined when the directed path was computed. In an epidemic protocol, where that previous system already has the data, the notion of passing the data back to the node is redundant: the protocol can readily determine that such a transfer is not required. Further, given the mobility and constant churn of encounters possible in a DTN that is dominated by opportunistic encounters, it is quite possible that, on a future encounter, the node might have become a better option for reaching the destination. Such a later encounter may require a re-transfer of the data if resource constraints have resulted in the data being deleted from the original carrier between the encounters. The logic of metric routing protocols does not map directly onto the family of epidemic protocols. In particular, it is inappropriate to try to assess such protocols against the criteria used to assess conventional routing protocols such as the metric vector protocols; this is not to say that the family of epidemic protocols do not have weaknesses but they have to be considered independently of traditional protocols.
1.4. Requirements Notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].2. Architecture
2.1. PRoPHET
This section presents an overview of the main architecture of PRoPHET, a Probabilistic Routing Protocol using History of Encounters and Transitivity. The protocol leverages the observations made on the non-randomness of mobility patterns present in many application scenarios to improve routing performance. Instead of doing blind epidemic replication of bundles through the network as previous protocols have done, it applies "probabilistic routing". To accomplish this, a metric called "delivery predictability", 0 <= P_(A,B) <= 1, is established at every node A for each known destination B. This metric is calculated so that a node with a higher value for a certain destination is estimated to be a better candidate for delivering a bundle to that destination (i.e., if P_(A,B)>P_(C,B), bundles for destination B are preferable to forward to A rather than C). It is later used when making forwarding decisions. As routes in a DTN are likely to be asymmetric, the calculation of the delivery predictability reflects this, and P_(A,B) may be different from P_(B,A). The delivery predictability values in each node evolve over time both as a result of decay of the metrics between encounters between nodes and due to changes resulting from encounters when metric information for the encountered node is updated to reflect the encounter and metric information about other nodes is exchanged. When two PRoPHET nodes have a communication opportunity, they initially enter a two-part Information Exchange Phase (IEP). In the first part of the exchange, the delivery predictabilities for all destinations known by each node are shared with the encountered node. The exchanged information is used by each node to update the internal delivery predictability vector as described below. After that, the nodes exchange information (including destination and size) about the bundles each node carries, and the information is used in conjunction with the updated delivery predictabilities to decide which bundles to request to be forwarded from the other node based on the forwarding strategy used (as discussed in Section 2.1.4). The forwarding of bundles is carried out in the latter part of the Information Exchange Phase.
2.1.1. Characteristic Time Interval
When an application scenario makes PRoPHET applicable, the mobility pattern will exhibit a characteristic time interval that reflects the distribution of time intervals between encounters between nodes. The evolution of the delivery predictabilities, which reflects this mobility pattern, should reflect this same characteristic time interval. Accordingly, the parameters used in the equations that specify the evolution of delivery predictability (see Section 2.1.2) need to be configured appropriately so that the evolution reflects a model of the mobility pattern.2.1.2. Delivery Predictability Calculation
As stated above, PRoPHET relies on calculating a metric based on the probability of encountering a certain node, and using that to support the decision of whether or not to forward a bundle to a certain node. This section describes the operations performed on the metrics stored in a node when it encounters another node and a communications opportunity arises. In the operations described by the equations that follow, the updates are being performed by node A, P_(A,B) is the delivery predictability value that node A will have stored for the destination B after the encounter, and P_(A,B)_old is the corresponding value that was stored before the encounter. If no delivery predictability value is stored for a particular destination B, P_(A,B) is considered to be zero. As a special case, the metric value for a node itself is always defined to be 1 (i.e., P_(A,A)=1). The equations use a number of parameters that can be selected to match the characteristics of the mobility pattern in the PRoPHET zone where the node is located (see Section 2.1.1). Recommended settings for the various parameters are given in Section 3.3. The impact on the evolution of delivery predictabilities if encountering nodes have different parameter setting is discussed in Section 2.1.2.1. The calculation of the updates to the delivery predictabilities during an encounter has three parts. When two nodes meet, the first thing they do is to update the delivery predictability for each other, so that nodes that are often encountered have a high delivery predictability. If node B has not met node A for a long time or has never met node B, such that P_(A,B) < P_first_threshold, then P_(A,B) should be set to P_encounter_first. Because PRoPHET generally has no prior knowledge about whether this is an encounter that will be repeated relatively frequently or one that will be a rare event, P_encounter_first SHOULD
be set to 0.5 unless the node has extra information obtained other than through the PRoPHET protocol about the likelihood of future encounters. Otherwise, P_(A,B) should be calculated as shown in Equation 1, where 0 <= P_encounter <= 1 is a scaling factor setting the rate at which the predictability increases on encounters after the first, and delta is a small positive number that effectively sets an upper bound for P_(A,B). The limit is set so that predictabilities between different nodes stay strictly less than 1. The value of delta should normally be very small (e.g., 0.01) so as not to significantly restrict the range of available predictabilities, but it can be chosen to make calculations efficient where this is important. P_(A,B) = P_(A,B)_old + ( 1 - delta - P_(A,B)_old ) * P_encounter (Eq. 1) There are practical circumstances where an encounter that is logically a single encounter in terms of the proximity of the node hardware and/or from the point of view of the human users of the nodes results in several communication opportunities closely spaced in time. For example, mobile nodes communicating with each other using Wi-Fi ad hoc mode may produce apparent multiple encounters with a short interval between them but these are frequently due to artifacts of the underlying physical network when using wireless connections, where transmission problems or small changes in location may result in repeated reconnections. In this case, it would be inappropriate to increase the delivery predictability by the same amount for each opportunity as it would be increased when encounters occur at longer intervals in the normal mobility pattern. In order to reduce the distortion of the delivery predictability in these circumstances, P_encounter is a function of the interval since the last encounter resulted in an update of the delivery predictabilities. The form of the function is as shown in Figure 2.
P_encounter ^ | P_encounter_max + - - .------------------------------------- | / | / . | / | / . | / | / . |/ +-------+-------------------------------------> I I_typ Figure 2: P_encounter as function of time interval, I, between updates The form of the function is chosen so that both the increase of P_(A,B) resulting from Equation 1 and the decrease that results from Equation 2 are related to the interval between updates for short intervals. For intervals longer than the "typical" time (I_typ) between encounters, P_encounter is set to a fixed value P_encounter_max. The break point reflects the transition between the "normal" communication opportunity regime (where opportunities result from the overall mobility pattern) and the closely spaced opportunities that result from what are effectively local artifacts of the wireless technology used to deliver those opportunities. P_encounter_max is chosen so that the increment in P_(A,B) provided by Equation 1 significantly exceeds the decay of the delivery predictability over the typical interval between encounters resulting from Equation 2. Making P_encounter dependent on the interval time also avoids inappropriate extra increments of P_(A,B) in situations where node A is in communication with several other nodes simultaneously. In this case, updates from each of the communicating nodes have to be distributed to the other nodes, possibly leading to several updates being carried out in a short period. This situation is discussed in more detail in Section 3.2.2. If a pair of nodes do not encounter each other during an interval, they are less likely to be good forwarders of bundles to each other, thus the delivery predictability values must age, being reduced in the process. The second part of the updates of the metric values is application of the aging equation shown in Equation 2, where 0 <= gamma <= 1 is the aging constant, and K is the number of time units that have elapsed since the last time the metric was aged. The
time unit used can differ and should be defined based on the
application and the expected delays in the targeted network.
P_(A,B) = P_(A,B)_old * gamma^K (Eq. 2)
The delivery predictabilities are aged according to Equation 2 before
being passed to an encountered node so that they reflect the time
that has passed since the node had its last encounter with any other
node. The results of the aging process are sent to the encountered
peer for use in the next stage of the process. The aged results
received from node B in node A are referenced as P_(B,x)_recv.
The delivery predictability also has a transitive property that is
based on the observation that if node A frequently encounters node B,
and node B frequently encounters node C, then node C probably is a
good node to which to forward bundles destined for node A.
Equation 3 shows how this transitivity affects the delivery
predictability, where 0 <= beta <= 1 is a scaling constant that
controls how large an impact the transitivity should have on the
delivery predictability.
P_(A,C) = MAX( P_(A,C)_old, P_(A,B) * P_(B,C)_recv * beta ) (Eq. 3)
Node A uses Equation 3 and the metric values received from the
encountered node B (e.g., P_(B,C)_recv) in the third part of updating
the metric values stored in node A.
2.1.2.1. Impact of Encounters between Nodes with Different Parameter
Settings
The various parameters used in the three equations described in
Section 2.1.2 are set independently in each node, and it is therefore
possible that encounters may take place between nodes that have been
configured with different values of the parameters. This section
considers whether this could be problematic for the operation of
PRoPHET in that zone.
It is desirable that all the nodes operating in a PRoPHET zone should
use closely matched values of the parameters and that the parameters
should be set to values that are appropriate for the operating zone.
More details of how to select appropriate values are given in
Section 3.3. Using closely matched values means that delivery
predictabilities will evolve in the same way in each node, leading to
consistent decision making about the bundles that should be exchanged
during encounters.
Before going on to consider the impact of reasonable but different settings, it should be noted that malicious nodes can use inappropriate settings of the parameters to disrupt delivery of bundles in a PRoPHET zone as described in Section 6. Firstly and importantly, use of different, but legitimate, settings in encountering nodes will not cause problems in the protocol itself. Apart from P_encounter_first, the other parameters control the rate of change of the metric values or limit the range of valid values that will be stored in a node. None of the calculations in a node will be invalidated or result in illegal values if the metric values received from another node were calculated using different parameters. Furthermore, the protocol is designed so that it is not possible to carry delivery predictabilities outside the permissible range of 0 to 1. A node MAY consider setting received values greater than (1 - delta) to (1 - delta) if this would simplify operations. However, there are some special situations where it may be appropriate for the delivery predictability for another node to be 1. For example, if a DTN using PRoPHET has multiple gateways to the continuously connected Internet, the delivery predictability seen from PRoPHET in one gateway for the other gateway nodes can be taken as 1 since they are permanently connected through the Internet. This would allow traffic to be forwarded into the DTN through the most advantageous gateway even if it initially arrives at another gateway. Simulation work indicates that the update calculations are quite stable in the face of changes to the rate parameters, so that minor discrepancies will not have a major impact on the performance of the protocol. The protocol is explicitly designed to deal with situations where there are random factors in the opportunistic nature of node encounters, and this randomness dominates over the discrepancies in the parameters. More major discrepancies may lead to suboptimal behavior of the protocol, as certain paths might be more preferred or more deprecated inappropriately. However, since the protocol overall is epidemic in nature, this would not generally lead to non-delivery of bundles, as they would also be passed to other nodes and would still be delivered, though possibly not on the optimal path.
2.1.3. Optional Delivery Predictability Optimizations
2.1.3.1. Smoothing
To give the delivery predictability a smoother rate of change, a node MAY apply one of the following methods: 1. Keep a list of NUM_P values for each destination instead of only a single value. (The recommended value is 4, which has been shown in simulations to give a good trade-off between smoothness and rate of response to changes.) The list is held in order of acquisition. When a delivery predictability is updated, the value at the "newest" position in the list is used as input to the equations in Section 2.1.2. The oldest value in the list is then discarded and the new value is written in the "newest" position of the list. When a delivery predictability value is needed (either for sending to a peering PRoPHET node, or for making a forwarding decision), the average of the values in the list is calculated, and that value is then used. If less than NUM_P values have been entered into the list, only the positions that have been filled should be used for the averaging. 2. In addition to keeping the delivery predictability as described in Section 2.1.2, a node MAY also keep an exponential weighted moving average (EWMA) of the delivery predictability. The EWMA is then used to make forwarding decisions and to report to peering nodes, but the value calculated according to Section 2.1.2 is still used as input to the calculations of new delivery predictabilities. The EWMA is calculated according to Equation 4, where 0 <= alpha <= 1 is the weight of the most current value. P_ewma = P_ewma_old * (1 - alpha) + P * alpha (Eq. 4) The appropriate choice of alpha may vary depending on application scenario circumstances. Unless prior knowledge of the scenario is available, it is suggested that alpha is set to 0.5.2.1.3.2. Removal of Low Delivery Predictabilities
To reduce the data to be transferred between two nodes, a node MAY treat delivery predictabilities smaller than P_first_threshold, where P_first_threshold is a small number, as if they were zero, and thus they do not need to be stored or included in the list sent during the Information Exchange Phase. If this optimization is used, care must be taken to select P_first_threshold to be smaller than delivery predictability values normally present in the network for destinations for which this node is a forwarder. It is possible that
P_first_threshold could be calculated based on delivery predictability ranges and the amount they change historically, but this has not been investigated yet.2.1.4. Forwarding Strategies and Queueing Policies
In traditional routing protocols, choosing where to forward a message is usually a simple task; the message is sent to the neighbor that has the path to the destination with the lowest cost (often the shortest path). Normally, the message is also sent to only a single node since the reliability of paths is relatively high. However, in the settings we envision here, things are radically different. The first possibility that must be considered when a bundle arrives at a node is that there might not be a path to the destination available, so the node has to buffer the bundle, and upon each encounter with another node, the decision must be made whether or not to transfer a particular bundle. Furthermore, having duplicates of messages (on different nodes, as the bundle offer/request mechanism described in Section 4.3.5 ensures that a node does not receive a bundle it already carries) may also be sensible, as forwarding a bundle to multiple nodes can increase the delivery probability of that bundle. Unfortunately, these decisions are not trivial to make. In some cases, it might be sensible to select a fixed threshold and only give a bundle to nodes that have a delivery predictability over that threshold for the destination of the bundle. On the other hand, when encountering a node with a low delivery predictability, it is not certain that a node with a higher metric will be encountered within a reasonable time. Thus, there can also be situations where we might want to be less strict in deciding who to give bundles to. Furthermore, there is the problem of deciding how many nodes to give a certain bundle to. Distributing a bundle to a large number of nodes will of course increase the probability of delivering that particular bundle to its destination, but this comes at the cost of consuming more system resources for bundle storage and possibly reducing the probability of other bundles being delivered. On the other hand, giving a bundle to only a few nodes (maybe even just a single node) will use less system resources, but the probability of delivering a bundle is lower, and the delay incurred is high. When resources are constrained, nodes may suffer from storage shortage, and may have to drop bundles before they have been delivered to their destinations. They may also wish to consider the length of bundles being offered by an encountered node before accepting transfer of the bundle in order to avoid the need to drop the new bundle immediately or to ensure that there is adequate space to hold the bundle offered, which might require other bundles to be dropped. As with the decision as to whether or not to forward a
bundle, deciding which bundles to accept and/or drop to still maintain good performance might require different policies in different scenarios. Nodes MAY define their own forwarding strategies and queueing policies that take into account the special conditions applicable to the nodes, and local resource constraints. Some default strategies and policies that should be suitable for most normal operations are defined in Section 3.6 and Section 3.7.2.2. Bundle Protocol Agent to Routing Agent Interface
The bundle protocol [RFC5050] introduces the concept of a "bundle protocol agent" that manages the interface between applications and the "convergence layers" that provide the transport of bundles between nodes during communication opportunities. This specification extends the bundle protocol agent with a routing agent that controls the actions of the bundle protocol agent during an (opportunistic) communications opportunity. This specification defines the details of the PRoPHET routing agent, but the interface defines a more general interface that is also applicable to alternative routing protocols. To enable the PRoPHET routing agent to operate properly, it must be aware of the bundles stored at the node, and it must also be able to tell the bundle protocol agent of that node to send a bundle to a peering node. Therefore, the bundle protocol agent needs to provide the following interface/functionality to the routing agent: Get Bundle List Returns a list of the stored bundles and their attributes to the routing agent. Send Bundle Makes the bundle protocol agent send a specified bundle. Accept Bundle Gives the bundle protocol agent a new bundle to store. Bundle Delivered Tells the bundle protocol agent that a bundle was delivered to its destination. Drop Bundle Advice Advises the bundle protocol agent that a specified bundle should not be offered for forwarding in future and may be dropped by the bundle protocol agent if appropriate.
Route Import
Can be used by a gateway node in a PRoPHET zone to import
reachability information about endpoint IDs (EIDs) that are
external to the PRoPHET zone. Translation functions dependent
on the external routing protocol will be used to set the
appropriate delivery predictabilities for imported destinations
as described in Section 2.3.
Route Export
Can be used by a gateway node in a PRoPHET zone to export
reachability information (destination EIDs and corresponding
delivery predictabilities) for use by routing protocols in other
parts of the DTN.
Implementation Note: Depending on the distribution of functions in
a complete bundle protocol agent supporting PRoPHET, reception and
delivery of bundles may not be carried out directly by the PRoPHET
module. In this case, PRoPHET can inform the bundle protocol
agent about bundles that have been requested from communicating
nodes. Then, the Accept Bundle and Bundle Delivered functions can
be implemented as notifications of the PRoPHET module when the
relevant bundles arrive at the node or are delivered to local
applications.
2.3. PRoPHET Zone Gateways
PRoPHET is designed to handle routing primarily within a "PRoPHET
zone", i.e., a set of nodes that all implement the PRoPHET routing
scheme. However, since we recognize that a PRoPHET routing zone is
unlikely to encompass an entire DTN, there may be nodes within the
zone that act as gateways to other nodes that are the destinations
for bundles generated within the zone or that insert bundles into the
zone.
PRoPHET MAY elect to export and import routes across a bundle
protocol agent interface. The delivery predictability to use for
routes that are imported depends on the routing protocol used to
manage those routes. If a translation function between the external
routing protocol and PRoPHET exists, it SHOULD be used to set the
delivery predictability. If no such translation function exists, the
delivery predictability SHOULD be set to 1. For those routes that
are exported, the current delivery predictability will be exported
with the route.
2.4. Lower-Layer Requirements and Interface
PRoPHET can be run on a large number of underlying networking technologies. To accommodate its operation on all kinds of lower layers, it requires the lower layers to provide the following functionality and interfaces. Neighbor discovery and maintenance A PRoPHET node needs to know the identity of its neighbors and when new neighbors appear and old neighbors disappear. Some wireless networking technologies might already contain mechanisms for detecting neighbors and maintaining this state. To avoid redundancies and inefficiencies, neighbor discovery is thus not included as a part of PRoPHET, but PRoPHET relies on such a mechanism in lower layers. The lower layers MUST provide the two functions listed below. If the underlying networking technology does not support such services, a simple neighbor discovery scheme using local broadcasts of beacon messages could be run in between PRoPHET and the underlying layer. An example of a simple neighbor discovery mechanism that could be used is in Appendix B. New Neighbor Signals to the PRoPHET agent that a new node has become a neighbor. A neighbor is defined here as another node that is currently within communication range of the wireless networking technology in use. The PRoPHET agent should now start the Hello procedure as described in Section 5.2. Neighbor Gone Signals to the PRoPHET agent that one of its neighbors has left. Local Address An address used by the underlying communication layer (e.g., an IP or Media Access Control (MAC) address) that identifies the sender address of the current message. This address must be unique among the nodes that can currently communicate and is only used in conjunction with an Instance Number to identify a communicating pair of nodes as described in Section 4.1. This address and its format is dependent on the communication layer that is being used by the PRoPHET layer.
(next page on part 2)