in Index   Prev   Next

RFC 6693

Probabilistic Routing Protocol for Intermittently Connected Networks

Pages: 113
Part 1 of 4 – Pages 1 to 21
None   None   Next

Top   ToC   RFC6693 - Page 1
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 Networks


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
Top   ToC   RFC6693 - Page 2
   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

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
   ( 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.
Top   ToC   RFC6693 - Page 3

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
Top   ToC   RFC6693 - Page 4
   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  . . . . . . . 110

1. 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.
Top   ToC   RFC6693 - Page 5
   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

   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.
Top   ToC   RFC6693 - Page 6
   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.
Top   ToC   RFC6693 - Page 7
     +----------------------------+   +----------------------------+
     |                      ___   |   |                      ___   |
     |      ___            /   \  |   |                     /   \  |
     |     /   \          (  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
Top   ToC   RFC6693 - Page 8
   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

   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).
Top   ToC   RFC6693 - Page 9
   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
Top   ToC   RFC6693 - Page 10
   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.
Top   ToC   RFC6693 - Page 11

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.
Top   ToC   RFC6693 - Page 12

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 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
Top   ToC   RFC6693 - Page 13
   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.
Top   ToC   RFC6693 - Page 14
   P_encounter_max +  -  - .-------------------------------------
                   |      /
                   |     / .
                   |    /
                   |   /   .
                   |  /
                   | /     .
                   +-------+-------------------------------------> I

          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
Top   ToC   RFC6693 - Page 15
   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. 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.
Top   ToC   RFC6693 - Page 16
   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.
Top   ToC   RFC6693 - Page 17

2.1.3. Optional Delivery Predictability Optimizations 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. 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
Top   ToC   RFC6693 - Page 18
   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
Top   ToC   RFC6693 - Page 19
   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.
Top   ToC   RFC6693 - Page 20
   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

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.
Top   ToC   RFC6693 - Page 21

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)

Next Section