tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 6693

Experimental
Pages: 113
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: IRTF

Probabilistic Routing Protocol for Intermittently Connected Networks

Part 1 of 4, p. 1 to 21
None       Next RFC Part

 


Top       ToC       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

Abstract

   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

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
   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.

Top       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       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       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
   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.

Top      ToC       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       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       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
   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).

Top      ToC       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       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       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       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 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

Top      ToC       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       Page 14 
              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

Top      ToC       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.

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.

Top      ToC       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       Page 17 
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

Top      ToC       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       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       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
      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.

Top      ToC       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 RFC Part