GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools


rfc:rfc6693

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

Lindgren, et al. Experimental [Page 1] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 2] RFC 6693 PRoPHET August 2012

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

Lindgren, et al. Experimental [Page 3] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 4] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 5] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 6] RFC 6693 PRoPHET August 2012

   +----------------------------+   +----------------------------+
   |                      ___   |   |                      ___   |
   |      ___            /   \  |   |                     /   \  |
   |     /   \          (  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

Lindgren, et al. Experimental [Page 7] RFC 6693 PRoPHET August 2012

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

Lindgren, et al. Experimental [Page 8] RFC 6693 PRoPHET August 2012

 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

Lindgren, et al. Experimental [Page 9] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 10] RFC 6693 PRoPHET August 2012

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.

Lindgren, et al. Experimental [Page 11] RFC 6693 PRoPHET August 2012

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

Lindgren, et al. Experimental [Page 12] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 13] RFC 6693 PRoPHET August 2012

            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

Lindgren, et al. Experimental [Page 14] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 15] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 16] RFC 6693 PRoPHET August 2012

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

Lindgren, et al. Experimental [Page 17] RFC 6693 PRoPHET August 2012

 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

Lindgren, et al. Experimental [Page 18] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 19] RFC 6693 PRoPHET August 2012

 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.

Lindgren, et al. Experimental [Page 20] RFC 6693 PRoPHET August 2012

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.

Lindgren, et al. Experimental [Page 21] RFC 6693 PRoPHET August 2012

3. Protocol Overview

 The PRoPHET protocol involves two principal phases:
 o  becoming aware of new neighbors that implement the protocol and
    establishing a point-to-point connection between each pair of
    encountering nodes, and
 o  using the connection for information exchange needed to establish
    PRoPHET routing and to exchange bundles.

3.1. Neighbor Awareness

 Since the operation of the protocol is dependent on the encounters of
 nodes running PRoPHET, the nodes must be able to detect when a new
 neighbor is present.  The protocol may be run on several different
 networking technologies, and as some of them might already have
 methods available for detecting neighbors, PRoPHET does not include a
 mechanism for neighbor discovery.  Instead, it requires the
 underlying layer to provide a mechanism to notify the protocol of
 when neighbors appear and disappear as described in Section 2.4.
 When a new neighbor has been detected, the protocol starts to set up
 a link with that node through the Hello message exchange as described
 in Section 5.2.  The Hello message exchange allows for negotiation of
 capabilities between neighbors.  At present, the only capability is a
 request that the offering node should or should not include bundle
 payload lengths with all offered bundles rather than just for
 fragments.  Once the link has been set up, the protocol may continue
 to the Information Exchange Phase (see Section 3.2).  Once this has
 been completed, the nodes will normally recalculate the delivery
 predictabilities using the equations and mechanisms described in
 Sections 2.1.2 and 2.1.3.
 As described in Section 2.1.2, there are some circumstances in which
 a single logical encounter may result in several actual communication
 opportunities.  To avoid the delivery predictability of the
 encountered node being increased excessively under these
 circumstances, the value of P_encounter is made dependent on the
 interval time between delivery predictability updates when the
 interval is less than the typical interval between encounters, but it
 is a constant for longer intervals.
 In order to make use of this time dependence, PRoPHET maintains a
 list of recently encountered nodes identified by the Endpoint
 Identifier (EID) that the node uses to identify the communication
 session and containing the start time of the last communication
 session with that node.  The size of this list is controlled because

Lindgren, et al. Experimental [Page 22] RFC 6693 PRoPHET August 2012

 nodes that are not in contact and that started their last connection
 more than a time I_typ before the present can be dropped from the
 list.  It also maintains a record of the time at which the decay
 function (Equation 2) was last applied to the delivery
 predictabilities in the node.

3.2. Information Exchange Phase

 The Information Exchange Phase involves two parts:
 o  establishing the Router Information Base (RIB Exchange Sub-Phase),
    and
 o  exchanging bundles using this information (Bundle Passing Sub-
    Phase).
 Four types of information are exchanged during this process:
 o  Routing Information Base Dictionary (RIB Dictionary or RIBD),
 o  Routing Information Base (RIB),
 o  Bundle Offers, and
 o  Bundle Responses.
 During a communication opportunity, several sets of each type of
 information may be transferred in each direction as explained in the
 rest of this section.  Each set can be transferred in one or more
 messages.  When (and only when) using a connection-oriented reliable
 transport protocol such as TCP as envisaged in this document, a set
 can be partitioned across messages by the software layer above the
 PRoPHET protocol engine.
 In this case, the last message in a set is flagged in the protocol.
 This allows the higher-level software to minimize the buffer memory
 requirements by avoiding the need to build very large messages in one
 go and allows the message size to be controlled outside of PRoPHET.
 However, this scheme is only usable if the transport protocol
 provides reliable, in-order delivery of messages, as the messages are
 not explicitly sequence numbered and the overall size of the set is
 not passed explicitly.
 The specification of PRoPHET also provides a submessage mechanism and
 retransmission that allows large messages specified by the higher
 level to be transmitted in smaller chunks.  This mechanism was
 originally provided to allow PRoPHET to operate over unreliable
 transport protocols such as UDP, but can also be used with reliable

Lindgren, et al. Experimental [Page 23] RFC 6693 PRoPHET August 2012

 transports if the higher-level software does not want to handle
 message fragmentation.  However, the sequencing and length adds
 overhead that is redundant if the transport protocol already provides
 reliable, in-order delivery.
 The first step in the Information Exchange Phase is for the protocol
 to send one or more messages containing a RIB Dictionary TLV (Type-
 Length-Value message component) to the node with which it is peering.
 This set of messages contain a dictionary of the Endpoint Identifiers
 (EIDs) of the nodes that will be listed in the Routing Information
 Base (RIB); see Section 3.2.1 for more information about this
 dictionary.  After this, one or more messages containing a Routing
 Information Base TLV are sent.  This TLV contains a list of the EIDs
 that the node has knowledge of, and the corresponding delivery
 predictabilities for those nodes, together with flags describing the
 capabilities of the sending node.  Upon reception of a complete set
 of these messages, the peer node updates its delivery predictability
 table according to the equations in Section 2.1.2.  The peer node
 then applies its forwarding strategy (see Section 2.1.4) to determine
 which of its stored bundles it wishes to offer the node that sent the
 RIB; that node will then be the receiver for any bundles to be
 transferred.
 After making this decision, one or more Bundle Offer TLVs are
 prepared, listing the bundle identifiers and their destinations for
 all bundles the peer node wishes to offer to the receiver node that
 sent the RIB.  As described in [RFC5050], a bundle identifier
 consists of up to five component parts.  For a complete bundle, the
 identifier consists of
 o  source EID,
 o  creation timestamp - time of creation, and
 o  creation timestamp - sequence number.
 Additionally, for a bundle fragment, the identifier also contains
 o  offset within the payload at which the fragment payload data
    starts, and
 o  length of the fragment payload data.
 If any of the Bundle Offer TLVs lists a bundle for which the source
 or destination EID was not included in the previous set of RIBD
 information sent, one or more new RIBD TLVs are sent next with an
 incremental update of the dictionary.  When the receiver node has a
 dictionary with all necessary EIDs, the Bundle Offer TLVs are sent to

Lindgren, et al. Experimental [Page 24] RFC 6693 PRoPHET August 2012

 it.  The Bundle Offer TLVs also contain a list of PRoPHET ACKs (see
 Section 3.5).  If requested by the receiver node during the Hello
 phase, the Bundle Offer TLV will also specify the payload length for
 all bundles rather than for just fragments.  This information can be
 used by the receiving node to assist with the selection of bundles to
 be accepted from the offered list, especially if the available bundle
 storage capacity is limited.
 The receiving node then examines the list of offered bundles and
 selects bundles that it will accept according to its own policies,
 considering the bundles already present in the node and the current
 availability of resources in the node.  The list is sorted according
 to the priority that the policies apply to the selected bundles, with
 the highest priority bundle first in the list.  The offering node
 will forward the selected bundles in this order.  The prioritized
 list is sent to the offering node in one or more Bundle Response TLVs
 using the same EID dictionary as was used for the Bundle Offer TLV.
 When a new bundle arrives at a node, the node MAY inspect its list of
 available neighbors, and if one of them is a candidate to forward the
 bundle, a new Bundle Offer TLV MAY be sent to that node.  If two
 nodes remain connected over a longer period of time, the Information
 Exchange Phase will be periodically re-initiated to allow new
 delivery predictability information to be spread through the network
 and new bundle exchanges to take place.
 The Information Exchange Phase of the protocol is described in more
 detail in Section 5.3.

3.2.1. Routing Information Base Dictionary

 To reduce the overhead of the protocol, the Routing Information Base
 and Bundle Offer/Response TLVs utilize an EID dictionary.  This
 dictionary maps variable-length EIDs (as defined in [RFC4838]), which
 may potentially be quite long, to shorter numerical identifiers,
 coded as Self-Delimiting Numeric Values (SDNVs -- see Section 4.1. of
 RFC 5050 [RFC5050]), which are used in place of the EIDs in
 subsequent TLVs.
 This dictionary is a shared resource between the two peering nodes.
 Each can add to the dictionary by sending a RIB Dictionary TLV to its
 peer.  To allow either node to add to the dictionary at any time, the
 identifiers used by each node are taken from disjoint sets:
 identifiers originated by the node that started the Hello procedure
 have the least significant bit set to 0 (i.e., are even numbers)
 whereas those originated by the other peer have the least significant
 bit set to 1 (i.e., are odd numbers).  This means that the dictionary

Lindgren, et al. Experimental [Page 25] RFC 6693 PRoPHET August 2012

 can be expanded by either node at any point in the Information
 Exchange Phase and the new identifiers can then be used in subsequent
 TLVs until the dictionary is re-initialized.
 The dictionary that is established only persists through a single
 encounter with a node (i.e., while the same link set up by the Hello
 procedure, with the same instance numbers, remains open).
 Having more then one identifier for the same EID does not cause any
 problems.  This means that it is possible for the peers to create
 their dictionary entries independently if required by an
 implementation, but this may be inefficient as a dictionary entry for
 an EID might be sent in both directions between the peers.
 Implementers can choose to inspect entries sent by the node that
 started the Hello procedure and thereby eliminate any duplicates
 before sending the dictionary entries from the other peer.  Whether
 postponing sending the other peer's entries is more efficient depends
 on the nature of the physical link technology and the transport
 protocol used.  With a genuinely full-duplex link, it may be faster
 to accept possible duplication and send dictionary entries
 concurrently in both directions.  If the link is effectively half-
 duplex (e.g., Wi-Fi), then it will generally be more efficient to
 wait and eliminate duplicates.
 If a node receives a RIB Dictionary TLV containing an identifier that
 is already in use, the node MUST confirm that the EID referred to is
 identical to the EID in the existing entry.  Otherwise, the node must
 send an error response to the message with the TLV containing the
 error and ignore the TLV containing the error.  If a node receives a
 RIB, Bundle Offer, or Bundle Response TLV that uses an identifier
 that is not in its dictionary, the node MUST send an error response
 and ignore the TLV containing the error.

3.2.2. Handling Multiple Simultaneous Contacts

 From time to time, a mobile node may, for example, be in wireless
 range of more than one other mobile node.  The PRoPHET neighbor
 awareness protocol will establish multiple simultaneous contacts with
 these nodes and commence information exchanges with each of them.
 When updating the delivery predictabilities as described in
 Section 2.1.2 using the values passed from each of the contacts in
 turn, some special considerations apply when multiple contacts are in
 progress:

Lindgren, et al. Experimental [Page 26] RFC 6693 PRoPHET August 2012

 SC1  When aging the delivery predictabilities according to
      Equation 2, the value of K to be used in each set of
      calculations is always the amount of time since the last aging
      was done.  For example, if node Z makes contact with node A and
      then with node B, the value of K used when the delivery
      predictabilities are aged in node Z for the contact with node B
      will be the time since the delivery predictabilities were aged
      for the contact with node A.
 SC2  When a new contact starts, the value of P_encounter used when
      applying Equation 1 for the newly contacted node is always
      selected according to the time since the last encounter with
      that node.  Thus, the application of Equation 1 to update
      P_(Z,A) when the contact of nodes Z and A starts (in the aging
      example just given) and the updating of P_(Z,B) when the contact
      of nodes Z and B starts will use the appropriate value of
      P_encounter according to how long it is since node Z previously
      encountered node A and node B, respectively.
 SC3  If, as with the contact between nodes Z and B, there is another
      active contact in progress, such as with node A when the contact
      with node B starts, Equation 1 should *also* be applied to
      P_(z,x) for all the nodes "x" that have ongoing contacts with
      node Z (i.e., node A in the example given).  However, the value
      of P_encounter used will be selected according to the time since
      the previous update of the delivery predictabilities as a result
      of information received from any other node.  In the example
      given here, P_(Z,A) would also have Equation 1 applied when the
      delivery predictabilities are received from node B, but the
      value of P_encounter used would be selected according to the
      time since the updates done when the encounter between nodes Z
      and A started rather than the time since the previous encounter
      between nodes A and Z.
 If these simultaneous contacts persist for some time, then, as
 described in Section 3.2, the Information Exchange Phase will be
 periodically rerun for each contact according to the configured timer
 interval.  When the delivery predictability values are recalculated
 during each rerun, Equation 1 will be applied as in special
 consideration SC3 above, but it will be applied to the delivery
 predictability for each active contact using the P_encounter value
 selected according to the time since the last set of updates were
 performed on the delivery predictabilities, irrespective of which
 nodes triggered either the previous or current updates.  This means
 that, in the example discussed here, P_(Z,A) and P_(Z,B) will be
 updated using the same value of P_encounter whether node A or node B
 initiated the update while the three nodes remain connected.

Lindgren, et al. Experimental [Page 27] RFC 6693 PRoPHET August 2012

 The interval between reruns of the information exchange will
 generally be set to a small fraction of the expected time between
 independent encounters of pairs of nodes.  This ensures that, for
 example, the delivery predictability information obtained by node Z
 from node A will be passed on to node B whether or not nodes A and B
 can communicate directly during this encounter.  This avoids problems
 that may arise from peculiarities of radio propagation during this
 sort of encounter, but the scaling of the P_encounter factor
 according to the time between updates of the delivery
 predictabilities means that the predictabilities for the nodes that
 are in contact are not increased excessively as would be the case if
 each information exchange were treated as a separate encounter with
 the value of P_encounter_max used each time.  When several nodes are
 in mutual contact, the delivery predictabilities in each node
 stabilize after a few exchanges due to the scaling of P_encounter as
 well as the form of Equation 3 where a "max" function is used.  This
 has been demonstrated by simulation.
 The effect of the updates of the delivery predictabilities when there
 are multiple simultaneous contacts is that the information about good
 routes on which to forward bundles is correctly passed between sets
 of nodes that are simultaneously in contact through the transitive
 update of Equation 3 during each information exchange, but the
 delivery predictabilities for the direct contacts are not
 exaggerated.

3.3. Routing Algorithm

 The basic routing algorithm of the protocol is described in
 Section 2.1.  The algorithm uses some parameter values in the
 calculation of the delivery predictability metric.  These parameters
 are configurable depending on the usage scenario, but Figure 3
 provides some recommended default values.  A brief explanation of the
 parameters and some advice on setting appropriate values is given
 below.
 I_typ
      I_typ provides a fundamental timescale for the mobility pattern
      in the PRoPHET scenario where the protocol is being applied.  It
      represents the typical or mean time interval between encounters
      between a given pair of nodes in the normal course of mobility.
      The interval should reflect the "logical" time between
      encounters and should not give significant weight to multiple
      connection events as explained in Section 2.1.2.  This time
      interval informs the settings of many of the other parameters
      but is not necessarily directly used as a parameter.
      Consideration needs to be given to the higher statistical
      moments (e.g., standard deviation) as well as the mean (first

Lindgren, et al. Experimental [Page 28] RFC 6693 PRoPHET August 2012

      moment) of the distribution of intervals between encounters and
      the nature of that distribution (e.g., how close to a normal
      distribution it is).  There is further discussion of this point
      later in this section and in Appendix C.
 P_encounter_max
      P_encounter_max is used as the upper limit of a scaling factor
      that increases the delivery predictability for a destination
      when the destination node is encountered.  A larger value of
      P_encounter_max will increase the delivery predictability
      faster, and fewer encounters will be required for the delivery
      predictability to reach a certain level.  Given that relative
      rather than absolute delivery predictability values are what is
      interesting for the forwarding mechanisms defined, the protocol
      is very robust to different values of P_encounter as long as the
      same value is chosen for all nodes.  The value should be chosen
      so that the increase in the delivery predictability resulting
      from using P_encounter_max in Equation 1 more than compensates
      for the decay of the delivery predictability resulting from
      Equation 3 with a time interval of I_typ.
 P_encounter(intvl)
      As explained in Section 2.1.2, the parameter P_encounter used in
      Equation 1 is a function of the time interval "intvl".  The
      function should be an approximation to
           P_encounter(intvl) =
           P_encounter_max * (intvl / I_typ) for 0<= intvl <= I_typ
           P_encounter_max for intvl > I_typ
      The function can be quantized and adapted to suit the mobility
      pattern and to make implementation easier.  The overall effect
      should be that be that if Equation 1 is applied a number of
      times during a long-lived communication opportunity lasting
      I_typ, the overall increase in the delivery predictability
      should be approximately the same as if there had been two
      distinct encounters spaced I_typ apart.  This second case would
      result in one application of Equation 1 using P_encounter_max.
 P_first_threshold
      As described in Section 2.1.2, the delivery predictability for a
      destination is gradually reduced over time unless increased as a
      result of direct encounters or through the transitive property.
      If the delivery predictability falls below the value
      P_first_threshold, then the node MAY discard the delivery
      predictability information for the destination and treat
      subsequent encounters as if they had never encountered the node
      previously.  This allows the node to reduce the storage needed

Lindgren, et al. Experimental [Page 29] RFC 6693 PRoPHET August 2012

      for delivery predictabilities and decreases the amount of
      information that has to be exchanged between nodes; otherwise,
      the reduction algorithm would result in very small but non-zero
      predictabilities being maintained for nodes that were last
      encountered a long time ago.
 P_encounter_first
      As described in Section 2.1.2, PRoPHET does not, by default,
      make any assumptions about the likelihood that an encountered
      node will be encountered repeatedly in the future or,
      alternatively, that this is a one-off chance encounter that is
      unlikely to be repeated.  During an encounter where the
      encountering node has no delivery predictability information for
      the encountered destination node, either because this is really
      the first encounter between the nodes or because the previous
      encounter was so long ago that the predictability had fallen
      below P_first_threshold and therefore had been discarded, the
      encountering node sets the delivery predictability for the
      destination node to P_encounter_first.  The suggested value for
      P_encounter_first is 0.5: this value is RECOMMENDED as
      appropriate in the usual case where PRoPHET has no extra (e.g.,
      out-of-band) information about whether future encounters with
      this node will be regular or otherwise.
 alpha
      The alpha parameter is used in the optional smoothing of the
      delivery predictabilities described in Section 2.1.3.1.  It is
      used to determine the weight of the most current P-value in the
      calculation of an EWMA.
 beta
      The beta parameter adjusts the weight of the transitive property
      of PRoPHET, that is, how much consideration should be given to
      information about destinations that is received from encountered
      nodes.  If beta is set to zero, the transitive property of
      PRoPHET will not be active, and only direct encounters will be
      used in the calculation of the delivery predictability.  The
      higher the value of beta, the more rapidly encounters will
      increase predictabilities through the transitive rule.
 gamma
      The gamma parameter determines how quickly delivery
      predictabilities age.  A lower value of gamma will cause the
      delivery predictability to age faster.  The value of gamma
      should be chosen according to the scenario and environment in
      which the protocol will be used.  If encounters are expected to
      be very frequent, a lower value should be chosen for gamma than
      if encounters are expected to be rare.

Lindgren, et al. Experimental [Page 30] RFC 6693 PRoPHET August 2012

 delta
      The delta parameter sets the maximum value of the delivery
      predictability for a destination other than for the node itself
      (i.e., P_(A,B) for all cases except P_(A,A)) as (1 - delta).
      Delta should be set to a small value to allow the maximum
      possible range for predictabilities but can be configured to
      make the calculation efficient if needed.
 To set an appropriate gamma value, one should consider the "average
 expected delivery" time I_aed in the PRoPHET zone where the protocol
 is to be used, and the time unit used (the resolution with which the
 delivery predictability is being updated).  The I_aed time interval
 can be estimated according to the average number of hops that bundles
 have to pass and the average interval between encounters I_typ.
 Clearly, if bundles have a Time To Live (TTL), i.e., the time left
 until the expiry time stored in the bundle occurs, that is less than
 I_aed, they are unlikely to survive in the network to be delivered to
 a node in this PRoPHET zone.  However, the TTL for bundles created in
 nodes in this zone should not be chosen solely on this basis because
 they may pass through other networks.
 After estimating I_aed and selecting how much we want the delivery
 predictability to age in one I_aed time period (call this A), we can
 calculate K, the number of time units in one I_aed, using
 K = (I_aed / time unit).  This can then be used to calculate gamma as
 gamma = K'th-root( A ).
 I_typ, I_aed, K, and gamma can then be used to inform the settings of
 P_encounter_first, P_encounter_max, P_first_threshold, delta, and the
 detailed form of the function P_encounter(intvl).
 First, considering the evolution of the delivery predictability
 P_(A,B) after a single encounter between nodes A and B, P_(A,B) is
 initially set to P_encounter_first and will then steadily decay until
 it reaches P_first_threshold.  The ratio between P_encounter_first
 and P_first_threshold should be set so that P_first_threshold is
 reached after a small multiple (e.g., 3 to 5) of I_aed has elapsed,
 making it likely that any subsequent encounter between the nodes
 would have occurred before P_(A,B) decays below P_first_threshold.
 If the statistics of the distribution of times between encounters is
 known, then a small multiple of the standard deviation of the
 distribution would be a possible period instead of using a multiple
 of I_aed.
 Second, if a second encounter between A and B occurs, the setting of
 P_encounter_max should be sufficiently high to reverse the decay that
 would have occurred during I_typ and to increase P_(A,B) above the
 value of P_encounter_first.  After several further encounters,

Lindgren, et al. Experimental [Page 31] RFC 6693 PRoPHET August 2012

 P_(A,B) will reach (1 - delta), its upper limit.  As with setting up
 P_first_threshold, P_encounter_max should be set so that the upper
 limit is reached after a small number of encounters spaced apart by
 I_typ have occurred, but this should generally be more than 2 or 3.
 Finally, beta can be chosen to give some smoothing of the influence
 of transitivity.
 These instructions on how to set the parameters are only given as a
 possible method for selecting appropriate values, but network
 operators are free to set parameters as they choose.  Appendix C goes
 into some more detail on linking the parameters defined here and the
 more conventional ways of expressing the mobility model in terms of
 distributions of times between events of various types.
 Recommended starting parameter values when specific network
 measurements have not been done are below.  Note: There are no "one
 size fits all" default values, and the ideal values vary based on
 network characteristics.  It is not inherently necessary for the
 parameter values to be identical at all nodes, but it is recommended
 that similar values are used at all nodes within a PRoPHET zone as
 discussed in Section 2.1.2.1.
   +========================================+
   |      Parameter     | Recommended value |
   +========================================+
   |   P_encounter_max  |       0.7         |
   +----------------------------------------+
   |  P_encounter_first |       0.5         |
   +----------------------------------------+
   |  P_first_threshold |       0.1         |
   +----------------------------------------+
   |        alpha       |       0.5         |
   +----------------------------------------+
   |        beta        |       0.9         |
   +----------------------------------------+
   |        gamma       |       0.999       |
   +----------------------------------------+
   |        delta       |       0.01        |
   +========================================+
                 Figure 3: Default parameter settings

3.4. Bundle Passing

 Upon reception of the Bundle Offer TLV, the node inspects the list of
 bundles and decides which bundles it is willing to store for future
 forwarding or that it is able to deliver to their destinations.  This

Lindgren, et al. Experimental [Page 32] RFC 6693 PRoPHET August 2012

 decision has to be made using local policies and considering
 parameters such as available buffer space and, if the node requested
 bundle lengths, the lengths of the offered bundles.  For each such
 acceptable bundle, the node sends a Bundle Response TLV to its
 peering node, which responds by sending the requested bundle.  If a
 node has some bundles it would prefer to receive ahead of others
 offered (e.g., bundles that it can deliver to their final
 destination), it MAY request the bundles in that priority order.
 This is often desirable as there is no guarantee that the nodes will
 remain in contact with each other for long enough to transfer all the
 acceptable bundles.  Otherwise, the node SHOULD assume that the
 bundles are listed in a priority order determined by the peering
 node's forwarding strategy and request bundles in that order.

3.4.1. Custody

 To free up local resources, a node may give custody of a bundle to
 another node that offers custody.  This is done to move the
 retransmission requirement further toward the destination.  The
 concept of custody transfer, and more details on the motivation for
 its use can be found in [RFC4838].  PRoPHET takes no responsibilities
 for making custody decisions.  Such decisions should be made by a
 higher layer.

3.5. When a Bundle Reaches Its Destination

 A PRoPHET ACK is only a confirmation that a bundle has been delivered
 to its destination in the PRoPHET zone (within the part of the
 network where PRoPHET is used for routing, bundles might traverse
 several different types of networks using different routing
 protocols; thus, this might not be the final destination of the
 bundle).  When nodes exchange Bundle Offer TLVs, bundles that have
 been ACKed are also listed, having the "PRoPHET ACK" flag set.  The
 node that receives this list updates its own list of ACKed bundles to
 be the union of its previous list and the received list.  To prevent
 the list of ACKed bundles growing indefinitely, each PRoPHET ACK
 should have a timeout that MUST NOT be longer than the timeout of the
 bundle to which the ACK corresponds.
 When a node receives a PRoPHET ACK for a bundle it is carrying, it
 MAY delete that bundle from its storage, unless the node holds
 custody of that bundle.  The PRoPHET ACK only indicates that a bundle
 has been delivered to its destination within the PRoPHET zone, so the
 reception of a PRoPHET ACK is not a guarantee that the bundle has
 been delivered to its final destination.

Lindgren, et al. Experimental [Page 33] RFC 6693 PRoPHET August 2012

 Nodes MAY track to which nodes they have sent PRoPHET ACKs for
 certain bundles, and MAY in that case refrain from sending multiple
 PRoPHET ACKs for the same bundle to the same node.
 If necessary in order to preserve system resources, nodes MAY drop
 PRoPHET ACKs prematurely but SHOULD refrain from doing so if
 possible.
 It is important to keep in mind that PRoPHET ACKs and bundle ACKs
 [RFC5050] are different things.  PRoPHET ACKs are only valid within
 the PRoPHET part of the network, while bundle ACKs are end-to-end
 acknowledgments that may go outside of the PRoPHET zone.

3.6. Forwarding Strategies

 During the Information Exchange Phase, nodes need to decide on which
 bundles they wish to exchange with the peering node.  Because of the
 large number of scenarios and environments that PRoPHET can be used
 in, and because of the wide range of devices that may be used, it is
 not certain that this decision will be based on the same strategy in
 every case.  Therefore, each node MUST operate a _forwarding
 strategy_ to make this decision.  Nodes may define their own
 strategies, but this section defines a few basic forwarding
 strategies that nodes can use.  Note: If the node being encountered
 is the destination of any of the bundles being carried, those bundles
 SHOULD be offered to the destination, even if that would violate the
 forwarding strategy.  Some of the forwarding strategies listed here
 have been evaluated (together with a number of queueing policies)
 through simulations, and more information about that and
 recommendations on which strategies to use in different situations
 can be found in [lindgren_06].  If not chosen differently due to the
 characteristics of the deployment scenario, nodes SHOULD choose GRTR
 as the default forwarding strategy.
 The short names applied to the forwarding strategies should be read
 as mnemonic handles rather than as specific acronyms for any set of
 words in the specification.
 We use the following notation in our descriptions below.  A and B are
 the nodes that encounter each other, and the strategies are described
 as they would be applied by node A.  The destination node is D.
 P_(X,Y) denotes the delivery predictability stored at node X for
 destination Y, and NF is the number of times node A has given the
 bundle to some other node.

Lindgren, et al. Experimental [Page 34] RFC 6693 PRoPHET August 2012

 GRTR
      Forward the bundle only if P_(B,D) > P_(A,D).
      When two nodes meet, a bundle is sent to the other node if the
      delivery predictability of the destination of the bundle is
      higher at the other node.  The first node does not delete the
      bundle after sending it as long as there is sufficient buffer
      space available (since it might encounter a better node, or even
      the final destination of the bundle in the future).
 GTMX
      Forward the bundle only if P_(B,D) > P_(A,D) && NF < NF_max.
      This strategy is like the previous one, but each bundle is given
      to at most NF_max other nodes in addition to the destination.
 GTHR
      Forward the bundle only if
      P_(B,D) > P_(A,D) OR P_(B,D) > FORW_thres,
      where FORW_thres is a threshold value above which a bundle
      should always be given to the node unless it is already present
      at the other node.
      This strategy is similar to GRTR, but among nodes with very high
      delivery predictability, bundles for that particular destination
      are spread epidemically.
 GRTR+
      Forward the bundle only if Equation 5 holds, where P_max is the
      largest delivery predictability reported by a node to which the
      bundle has been sent so far.
           P_(B,D) > P_(A,D) && P_(B,D) > P_max  (Eq. 5)
      This strategy is like GRTR, but each node forwarding a bundle
      keeps track of the largest delivery predictability of any node
      it has forwarded this bundle to, and only forwards the bundle
      again if the currently encountered node has a greater delivery
      predictability than the maximum previously encountered.
 GTMX+
      Forward the bundle only if Equation 6 holds.
          P_(B,D) > P_(A,D) && P_(B,D) > P_max && NF < NF_max  (Eq. 6)
      This strategy is like GTMX, but nodes keep track of P_max as in
      GRTR+.

Lindgren, et al. Experimental [Page 35] RFC 6693 PRoPHET August 2012

 GRTRSort
      Select bundles in descending order of the value of
      P_(B,D) - P_(A,D).
      Forward the bundle only if P_(B,D) > P_(A,D).
      This strategy is like GRTR, but instead of just going through
      the bundle queue linearly, this strategy looks at the difference
      in delivery predictabilities for each bundle between the two
      nodes and forwards the bundles with the largest difference
      first.  As bandwidth limitations or disrupted connections may
      result in not all bundles that would be desirable being
      exchanged, it could be desirable to first send bundles that get
      a large improvement in delivery predictability.
 GRTRMax
      Select bundles in descending order of P_(B,D).
      Forward the bundle only if P_(B,D) > P_(A,D).
      This strategy begins by considering the bundles for which the
      encountered node has the highest delivery predictability.  The
      motivation for doing this is the same as in GRTRSort, but based
      on the idea that it is better to give bundles to nodes with high
      absolute delivery predictabilities, instead of trying to
      maximize the improvement.

3.7. Queueing Policies

 Because of limited buffer resources, nodes may need to drop some
 bundles.  As is the case with the forwarding strategies, which bundle
 to drop is also dependent on the scenario.  Therefore, each node MUST
 also operate a queueing policy that determines how its bundle queue
 is handled.  This section defines a few basic queueing policies, but
 nodes MAY use other policies if desired.  Some of the queueing
 policies listed here have been evaluated (together with a number of
 forwarding strategies) through simulations.  More information about
 that and recommendations on which policies to use in different
 situations can be found in [lindgren_06].  If not chosen differently
 due to the characteristics of the deployment scenario, nodes SHOULD
 choose FIFO as the default queueing policy.
 The short names applied to the queueing policies should be read as
 mnemonic handles rather than as specific acronyms for any set of
 words in the specification.
 FIFO - First In First Out.
      The bundle that was first entered into the queue is the first
      bundle to be dropped.

Lindgren, et al. Experimental [Page 36] RFC 6693 PRoPHET August 2012

 MOFO - Evict most forwarded first.
      In an attempt to maximize the delivery rate of bundles, this
      policy requires that the routing agent keep track of the number
      of times each bundle has been forwarded to some other node.  The
      bundle that has been forwarded the largest number of times is
      the first to be dropped.
 MOPR - Evict most favorably forwarded first.
      Keep a variable FAV for each bundle in the queue, initialized to
      zero.  Each time the bundle is forwarded, update FAV according
      to Equation 7, where P is the predictability metric that the
      node the bundle is forwarded to has for its destination.
           FAV_new = FAV_old + ( 1 - FAV_old ) * P  (Eq. 7)
      The bundle with the highest FAV value is the first to be
      dropped.
 Linear MOPR - Evict most favorably forwarded first; linear increase.
      Keep a variable FAV for each bundle in the queue, initialized to
      zero.  Each time the bundle is forwarded, update FAV according
      to Equation 8, where P is the predictability metric that the
      node the bundle is forwarded to has for its destination.
           FAV_new = FAV_old + P  (Eq. 8)
      The bundle with the highest FAV value is the first to be
      dropped.
 SHLI - Evict shortest life time first.
      As described in [RFC5050], each bundle has a timeout value
      specifying when it no longer is meaningful to its application
      and should be deleted.  Since bundles with short remaining Time
      To Live will soon be dropped anyway, this policy decides to drop
      the bundle with the shortest remaining lifetime first.  To
      successfully use a policy like this, there needs to be some form
      of time synchronization between nodes so that it is possible to
      know the exact lifetimes of bundles.  However, this is not
      specific to this routing protocol, but a more general DTN
      problem.
 LEPR - Evict least probable first.
      Since the node is least likely to deliver a bundle for which it
      has a low delivery predictability, drop the bundle for which the
      node has the lowest delivery predictability, and that has been
      forwarded at least MF times, where MF is a minimum number of
      forwards that a bundle must have been forwarded before being
      dropped (if such a bundle exists).

Lindgren, et al. Experimental [Page 37] RFC 6693 PRoPHET August 2012

 More than one queueing policy MAY be combined in an ordered set,
 where the first policy is used primarily, the second only being used
 if there is a need to tie-break between bundles given the same
 eviction priority by the primary policy, and so on.  As an example,
 one could select the queueing policy to be {MOFO; SHLI; FIFO}, which
 would start by dropping the bundle that has been forwarded the
 largest number of times.  If more than one bundle has been forwarded
 the same number of times, the one with the shortest remaining
 lifetime will be dropped, and if that also is the same, the FIFO
 policy will be used to drop the bundle first received.
 It is worth noting that a node MUST NOT drop bundles for which it has
 custody unless the bundle's lifetime expires.

4. Message Formats

 This section defines the message formats of the PRoPHET routing
 protocol.  In order to allow for variable-length fields, many numeric
 fields are encoded as Self-Delimiting Numeric Values (SDNVs).  The
 format of SDNVs is defined in [RFC5050].  Since many of the fields
 are coded as SDNVs, the size and alignment of fields indicated in
 many of the specification diagrams below are indicative rather than
 prescriptive.  Where SDNVs and/or text strings are used, the octets
 of the fields will be packed as closely as possible with no
 intervening padding between fields.
 Explicit-length fields are specified for all variable-length string
 fields.  Accordingly, strings are not null terminated and just
 contain the exact set of octets in the string.
 The basic message format shown in Figure 4 consists of a header (see
 Section 4.1) followed by a sequence of one or more Type-Length-Value
 components (TLVs) taken from the specifications in Section 4.2.

Lindgren, et al. Experimental [Page 38] RFC 6693 PRoPHET August 2012

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                            Header                             ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                             TLV 1                             ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                .                              |
    ~                                .                              ~
    |                                .                              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                             TLV n                             ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                Figure 4: Basic PRoPHET Message Format

4.1. Header

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |Protocol Number|Version| Flags |     Result    |     Code      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |      Receiver Instance        |      Sender Instance          |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Transaction Identifier                     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |S|      SubMessage Number      |         Length (SDNV)         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                          Message Body                         ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                   Figure 5: PRoPHET Message Header
 Protocol Number
      The DTN Routing Protocol Number encoded as 8-bit unsigned
      integer in network bit order.  The value of this field is 0.
      The PRoPHET header is organized in this way so that in principle
      PRoPHET messages could be sent as the Protocol Data Unit of an
      IP packet if an IP protocol number was allocated for PRoPHET.

Lindgren, et al. Experimental [Page 39] RFC 6693 PRoPHET August 2012

      At present, PRoPHET is only specified to use a TCP transport for
      carriage of PRoPHET packets, so that the protocol number serves
      only to identify the PRoPHET protocol within DTN.  Transmitting
      PRoPHET packets directly as an IP protocol on a public IP
      network such as the Internet would generally not work well
      because middleboxes (such as firewalls and NAT boxes) would be
      unlikely to allow the protocol to pass through, and the protocol
      does not provide any congestion control.  However, it could be
      so used on private networks for experimentation or in situations
      where all communications are between isolated pairs of nodes.
      Also, in the future, other protocols that require transmission
      of metadata between DTN nodes could potentially use the same
      format and protocol state machinery but with a different
      Protocol Number.
 Version
      The version of the PRoPHET Protocol.  Encoded as a 4-bit
      unsigned integer in network bit order.  This document defines
      version 2.
 Flags
      Reserved field of 4 bits.
 Result
      Field that is used to indicate whether a response is required to
      the request message if the outcome is successful.  A value of
      "NoSuccessAck" indicates that the request message does not
      expect a response if the outcome is successful, and a value of
      "AckAll" indicates that a response is expected if the outcome is
      successful.  In both cases, a failure response MUST be generated
      if the request fails.  If running over a TCP transport or
      similar protocol that offers reliable in order delivery,
      deployments MAY choose not to send "Success" responses when an
      outcome is successful.  To achieve this, the Result field is set
      to the "NoSuccessAck" value in all request messages.
      In a response message, the result field can have two values:
      "Success" and "Failure".  The "Success" result indicates a
      success response.  All messages that belong to the same success
      response will have the same Transaction Identifier.  The
      "Success" result indicates a success response that may be
      contained in a single message or the final message of a success
      response spanning multiple messages.

Lindgren, et al. Experimental [Page 40] RFC 6693 PRoPHET August 2012

      ReturnReceipt is a value of the result field used to indicate
      that an acknowledgement is required for the message.  The
      default for messages is that the controller will not acknowledge
      responses.  In the case where an acknowledgement is required, it
      will set the Result Field to ReturnReceipt in the header of the
      Message.
      The result field is encoded as an 8-bit unsigned integer in
      network bit order.  The following values are currently defined:
         NoSuccessAck:       Result = 1
         AckAll:             Result = 2
         Success:            Result = 3
         Failure:            Result = 4
         ReturnReceipt       Result = 5
 Code
      This field gives further information concerning the result in a
      response message.  It is mostly used to pass an error code in a
      failure response but can also be used to give further
      information in a success response message or an event message.
      In a request message, the code field is not used and is set to
      zero.
      If the Code field indicates that the Error TLV is included in
      the message, further information on the error will be found in
      the Error TLV, which MUST be the first TLV after the header.
      The Code field is encoded as an 8-bit unsigned integer in
      network bit order.  Separate number code spaces are used for
      success and failure response messages.  In each case, a range of
      values is reserved for use in specifications and another range
      for private and experimental use.  For success messages, the
      following values are defined:
                Generic Success                  0x00
                Submessage Received              0x01
                Unassigned                   0x02 - 0x7F
                Private/Experimental Use     0x80 - 0xFF
      The Submessage Received code is used to acknowledge reception of
      a message segment.  The Generic Success code is used to
      acknowledge receipt of a complete message and successful
      processing of the contents.

Lindgren, et al. Experimental [Page 41] RFC 6693 PRoPHET August 2012

      For failure messages, the following values are defined:
                Reserved                     0x00 - 0x01
                Unspecified Failure              0x02
                Unassigned                   0x03 - 0x7F
                Private/Experimental Use     0x80 - 0xFE
                Error TLV in message             0xFF
      The Unspecified Failure code can be used to report a failure for
      which there is no more specific code or Error TLV value defined.
 Sender Instance
      For messages during the Hello phase with the Hello SYN, Hello
      SYNACK, and Hello ACK functions (which are explained in
      Section 5.2), it is the sender's instance number for the link.
      It is used to detect when the link comes back up after going
      down or when the identity of the entity at the other end of the
      link changes.  The instance number is a 16-bit number that is
      guaranteed to be unique within the recent past and to change
      when the link or node comes back up after going down.  Zero is
      not a valid instance number.  For the RSTACK function (also
      explained in detail in Section 5.2), the Sender Instance field
      is set to the value of the Receiver Instance field from the
      incoming message that caused the RSTACK function to be
      generated.  Messages sent after the Hello phase is completed
      should use the sender's instance number for the link.  The
      Sender Instance is encoded as a 16-bit unsigned integer in
      network bit order.
 Receiver Instance
      For messages during the Hello phase with the Hello SYN, Hello
      SYNACK, and Hello ACK functions, it is what the sender believes
      is the current instance number for the link, allocated by the
      entity at the far end of the link.  If the sender of the message
      does not know the current instance number at the far end of the
      link, this field MUST be set to zero.  For the RSTACK message,
      the Receiver Instance field is set to the value of the Sender
      Instance field from the incoming message that caused the RSTACK
      message to be generated.  Messages sent after the Hello phase is
      completed should use what the sender believes is the current
      instance number for the link, allocated by the entity at the far
      end of the link.  The Sender Instance is encoded as a 16-bit
      unsigned integer in network bit order.

Lindgren, et al. Experimental [Page 42] RFC 6693 PRoPHET August 2012

 Transaction Identifier
      Used to associate a message with its response message.  This
      should be set in request messages to a value that is unique for
      the sending host within the recent past.  Reply messages contain
      the Transaction Identifier of the request to which they are
      responding.  The Transaction Identifier is a bit pattern of 32
      bits.
 S-flag
      If S is set (value 1), then the SubMessage Number field
      indicates the total number of SubMessage segments that compose
      the entire message.  If it is not set (value 0), then the
      SubMessage Number field indicates the sequence number of this
      SubMessage segment within the whole message.  The S field will
      only be set in the first submessage of a sequence.
 SubMessage Number
      When a message is segmented because it exceeds the MTU of the
      link layer or otherwise, each segment will include a SubMessage
      Number to indicate its position.  Alternatively, if it is the
      first submessage in a sequence of submessages, the S-flag will
      be set, and this field will contain the total count of
      SubMessage segments.  The SubMessage Number is encoded as a
      15-bit unsigned integer in network bit order.  The SubMessage
      number is zero-based, i.e., for a message divided into n
      submessages, they are numbered from 0 to (n - 1).  For a message
      that is not divided into submessages, the single message has the
      S-flag cleared (value 0), and the SubMessage Number is set to 0
      (zero).
 Length
      Length in octets of this message including headers and message
      body.  If the message is fragmented, this field contains the
      length of this SubMessage.  The Length is encoded as an SDNV.
 Message Body
      As specified in Section 4, the Message Body consists of a
      sequence of one or more of the TLVs specified in Section 4.2.
 The protocol also requires extra information about the link that the
 underlying communication layer MUST provide.  This information is
 used in the Hello procedure described in more detail in Section 5.2.
 Since this information is available from the underlying layer, there
 is no need to carry it in PRoPHET messages.  The following values are
 defined to be provided by the underlying layer:

Lindgren, et al. Experimental [Page 43] RFC 6693 PRoPHET August 2012

 Sender Local Address
      An address that is used by the underlying communication layer as
      described in Section 2.4 and identifies the sender address of
      the current message.  This address must be unique among the
      nodes that can currently communicate, and it is only used in
      conjunction with the Receiver Local Address, Receiver Instance,
      and Sender Instance to identify a communicating pair of nodes.
 Receiver Local Address
      An address that is used by the underlying communication layer as
      described in Section 2.4 and identifies the receiver address of
      the current message.  This address must be unique among the
      nodes that can currently communicate, and is only used in
      conjunction with the Sender Local Address, Receiver Instance,
      and Sender Instance to identify a communicating pair of nodes.
 When PRoPHET is run over TCP, the IP addresses of the communicating
 nodes are used as Sender and Receiver Local Addresses.

4.2. TLV Structure

 All TLVs have the following format, and can be nested.
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |    TLV Type   |   TLV Flags   |       TLV Length (SDNV)       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                           TLV Data                            ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                         Figure 6: TLV Format
 TLV Type
      Specific TLVs are defined in Section 4.3.  The TLV Type is
      encoded as an 8-bit unsigned integer in network bit order.  Each
      TLV will have fields defined that are specific to the function
      of that TLV.
 TLV Flags
      These are defined per TLV type.  Flag n corresponds to bit 15-n
      in the TLV.  Any flags that are specified as reserved in
      specific TLVs SHOULD be transmitted as 0 and ignored on receipt.

Lindgren, et al. Experimental [Page 44] RFC 6693 PRoPHET August 2012

 TLV Length
      Length of the TLV in octets, including the TLV header and any
      nested TLVs.  Encoded as an SDNV.  Note that TLVs are not padded
      to any specific alignment unless explicitly required in the
      description of the TLV.  No TLVs in this document specify any
      padding.

4.3. TLVs

 This section describes the various TLVs that can be used in PRoPHET
 messages.

4.3.1. Hello TLV

 The Hello TLV is used to set up and maintain a link between two
 PRoPHET nodes.  Hello messages with the SYN function are transmitted
 periodically as beacons or keep-alives.  The Hello TLV is the first
 TLV exchanged between two PRoPHET nodes when they encounter each
 other.  No other TLVs can be exchanged until the first Hello sequence
 is completed.
 Once a communication link is established between two PRoPHET nodes,
 the Hello TLV will be sent once for each interval as defined in the
 interval timer.  If a node experiences the lapse of HELLO_DEAD Hello
 intervals without receiving a Hello TLV on a connection in the
 INFO_EXCH state (as defined in the state machine in Section 5.1), the
 connection SHOULD be assumed broken.
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | TLV Type=0x01 |L|  Resv | HF  |       TLV Length (SDNV)       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Timer (SDNV)  |EID Length,SDNV|  Sender EID (variable length) |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                      Figure 7: Hello TLV Format
 TLV Flags
      The TLV Flags field contains two 1-bit flags (S and L) and a
      3-bit Hello Function (HF) number that specifies one of four
      functions for the Hello TLV.  The remaining 3 bits (Resv) are
      unused and reserved:

Lindgren, et al. Experimental [Page 45] RFC 6693 PRoPHET August 2012

      HF
           TLV Flags bits 0, 1, and 2 are treated as an unsigned 3-bit
           integer coded in network bit order.  The value of the
           integer specifies the Hello Function (HF) of the Hello TLV.
           Four functions are specified for the Hello TLV.
           The encoding of the Hello Function is:
                SYN:     HF = 1
                SYNACK:  HF = 2
                ACK:     HF = 3
                RSTACK:  HF = 4
 The remaining values (0, 5, 6 and 7) are unused and reserved.  If a
 Hello TLV with any of these values is received, the link should be
 reset.
      Resv
           TLV Flags bits 3, 4, 5, and 6 are reserved.  They SHOULD be
           set to 0 on transmission and ignored on reception.
      L
           The L bit flag (TLV Flags bit 7) is set (value 1) to
           request that the Bundle Offer TLV sent during the
           Information Exchange Phase contains bundle payload lengths
           for all bundles, rather than only for bundle fragments as
           when the L flag is cleared (value 0), when carried in a
           Hello TLV with Hello Function SYN or SYNACK.  The flag is
           ignored for other Hello Function values.
 TLV Data
      Timer
           The Timer field is used to inform the receiver of the timer
           value used in the Hello processing of the sender.  The
           timer specifies the nominal time between periodic Hello
           messages.  It is a constant for the duration of a session.
           The timer field is specified in units of 100 ms and is
           encoded as an SDNV.
      EID Length
           The EID Length field is used to specify the length of the
           Sender EID field in octets.  If the Endpoint Identifier
           (EID) has already been sent at least once in a message with
           the current Sender Instance, a node MAY choose to set this
           field to zero, omitting the Sender EID from the Hello TLV.
           The EID Length is encoded as an SDNV, and the field is thus
           of variable length.

Lindgren, et al. Experimental [Page 46] RFC 6693 PRoPHET August 2012

      Sender EID
           The Sender EID field specifies the DTN endpoint identifier
           (EID) of the sender that is to be used in updating routing
           information and making forwarding decisions.  If a node has
           multiple EIDs, one should be chosen for PRoPHET routing.
           This field is of variable length.

4.3.2. Error TLV

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | TLV type=0x02 |   TLV Flags |         TLV Length (SDNV)       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                          TLV Data                            ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                      Figure 8: Error TLV Format
 TLV Flags
      For Error TLVs, the TLV Flags field carries an identifier for
      the Error TLV type as an 8-bit unsigned integer encoded in
      network bit order.  A range of values is available for private
      and experimental use in addition to the values defined here.
      The following Error TLV types are defined:
                Dictionary Conflict               0x00
                Bad String ID                     0x01
                Reserved                       0x02 - 0x7F
                Private/Experimental Use       0x80 - 0xFF
 TLV Data
      The contents and interpretation of the TLV Data field are
      specific to the type of Error TLV.  For the Error TLVs defined
      in this document, the TLV Data is defined as follows:
      Dictionary Conflict
           The TLV Data consists of the String ID that is causing the
           conflict encoded as an SDNV followed by the EID string that
           conflicts with the previously installed value.  The
           Endpoint Identifier is NOT null terminated.  The length of
           the EID can be determined by subtracting the length of the
           TLV Header and the length of the SDNV containing the String
           ID from the TLV Length.

Lindgren, et al. Experimental [Page 47] RFC 6693 PRoPHET August 2012

      Bad String ID
           The TLV Data consists of the String ID that is not found in
           the dictionary encoded as an SDNV.

4.3.3. Routing Information Base Dictionary TLV

 The Routing Information Base Dictionary includes the list of endpoint
 identifiers used in making routing decisions.  The referents remain
 constant for the duration of a session over a link where the instance
 numbers remain the same and can be used by both the Routing
 Information Base messages and the bundle offer/response messages.
 The dictionary is a shared resource (see Section 3.2.1) built in each
 of the paired peers from the contents of one or more incoming TLVs of
 this type and from the information used to create outgoing TLVs of
 this type.
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | TLV type=0xA0 |   TLV Flags   |       TLV Length (SDNV)       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                     RIBD Entry Count (SDNV)                   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    ~                                                               ~
    ~           Variable-Length Routing Address Strings             ~
    ~                                                               ~
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    ~ Routing Address String 1                                      ~
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        String ID 1 (SDNV)     |         Length (SDNV)         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    ~            Endpoint Identifier 1 (variable length)            ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                               .                               |
    ~ Routing Address String n      .                               ~
    |                               .                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        String ID n (SDNV)     |         Length (SDNV)         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~            Endpoint Identifier n (variable length)            ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       Figure 9: Routing Information Base Dictionary TLV Format

Lindgren, et al. Experimental [Page 48] RFC 6693 PRoPHET August 2012

 TLV Flags
      The encoding of the Header flag field relates to the
      capabilities of the source node sending the RIB Dictionary:
           Flag 0: Sent by Listener    0b1
           Flag 1: Reserved            0b1
           Flag 2: Reserved            0b1
           Flag 3: Unassigned          0b1
           Flag 4: Unassigned          0b1
           Flag 5: Unassigned          0b1
           Flag 6: Unassigned          0b1
           Flag 7: Unassigned          0b1
      The "Sent by Listener" flag is set to 0 if this TLV was sent by
      a node in the Initiator role and set to 1 if this TLV was sent
      by a node in the Listener role (see Section 3.2 for explanations
      of these roles).
 TLV Data
      RIBD Entry Count
           Number of entries in the database.  Encoded as SDNV.
      String ID
           SDNV identifier that is constant for the duration of a
           session.  String ID zero is predefined as the node that
           initiates the session through sending the Hello SYN
           message, and String ID one is predefined as the node that
           responds with the Hello SYNACK message.  These entries do
           not need to be sent explicitly as the EIDs are exchanged
           during the Hello procedure.
           In order to ensure that the String IDs originated by the
           two peers do not conflict, the String IDs generated in the
           node that sent the Hello SYN message MUST have their least
           significant bit set to 0 (i.e., are even numbers), and the
           String IDs generated in the node that responded with the
           Hello SYNACK message MUST have their least significant bit
           set to 1 (i.e., they are odd numbers).
      Length
           Length of Endpoint Identifier in this entry.  Encoded as
           SDNV.
      Endpoint Identifier
           Text string representing the Endpoint Identifier.  Note
           that it is NOT null terminated as the entry contains the
           length of the identifier.

Lindgren, et al. Experimental [Page 49] RFC 6693 PRoPHET August 2012

4.3.4. Routing Information Base TLV

 The Routing Information Base lists the destinations (endpoints) a
 node knows of and the delivery predictabilities it has associated
 with them.  This information is needed by the PRoPHET algorithm to
 make decisions on routing and forwarding.
     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | TLV Type=0xA1 |   TLV Flags   |       TLV Length (SDNV)       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                     RIB String Count (SDNV)                   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |     RIBD String ID 1 (SDNV)   |            P-value            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  RIB Flags 1  |               .                               ~
    +-+-+-+-+-+-+-+-+               .                               ~
    ~                               .                               ~
    ~                               .                               ~
    ~                               .                               ~
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |     RIBD String ID n (SDNV)   |            P-value            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  RIB Flags n  |
    +-+-+-+-+-+-+-+-+
            Figure 10: Routing Information Base TLV Format
 TLV Flags
      The encoding of the Header flag field relates to the
      capabilities of the Source node sending the RIB:
           Flag 0: More RIB TLVs       0b1
           Flag 1: Reserved            0b1
           Flag 2: Reserved            0b1
           Flag 3: Unassigned          0b1
           Flag 4: Unassigned          0b1
           Flag 5: Unassigned          0b1
           Flag 6: Unassigned          0b1
           Flag 7: Unassigned          0b1
      The "More RIB TLVs" flag is set to 1 if the RIB requires more
      TLVs to be sent in order to be fully transferred.  This flag is
      set to 0 if this is the final TLV of this RIB.

Lindgren, et al. Experimental [Page 50] RFC 6693 PRoPHET August 2012

 TLV Data
      RIB String Count
           Number of routing entries in the TLV.  Encoded as an SDNV.
      RIBD String ID
           String ID of the endpoint identifier of the destination for
           which this entry specifies the delivery predictability as
           predefined in a dictionary TLV.  Encoded as an SDNV.
      P-value
           Delivery predictability for the destination of this entry
           as calculated from previous encounters according to the
           equations in Section 2.1.2, encoded as a 16-bit unsigned
           integer.  The encoding of this field is a linear mapping
           from [0,1] to [0, 0xFFFF] (e.g., for a P-value of 0.75, the
           mapping would be 0.75*65535=49151=0xBFFF; thus, the P-value
           would be encoded as 0xBFFF).
      RIB Flag
           The encoding of the 8-bit RIB Flag field is:
           Flag 0: Unassigned          0b1
           Flag 1: Unassigned          0b1
           Flag 2: Unassigned          0b1
           Flag 3: Unassigned          0b1
           Flag 4: Unassigned          0b1
           Flag 5: Unassigned          0b1
           Flag 6: Unassigned          0b1
           Flag 7: Unassigned          0b1

4.3.5. Bundle Offer and Response TLVs (Version 2)

 After the routing information has been passed, the node will ask the
 other node to review available bundles and determine which bundles it
 will accept for relay.  The source relay will determine which bundles
 to offer based on relative delivery predictabilities as explained in
 Section 3.6.
      Note: The original versions of these TLVs (TLV Types 0xA2 and
      0xA3) used in version 1 of the PRoPHET protocol have been
      deprecated, as they did not contain the complete information
      needed to uniquely identify bundles and could not handle bundle
      fragments.
 Depending on the bundles stored in the offering node, the Bundle
 Offer TLV might contain descriptions of both complete bundles and
 bundle fragments.  In order to correctly identify bundle fragments, a

Lindgren, et al. Experimental [Page 51] RFC 6693 PRoPHET August 2012

 bundle fragment descriptor MUST contain the offset of the payload
 fragment in the bundle payload and the length of the payload
 fragment.  If requested by the receiving node by setting the L flag
 in the SYN or SYNACK message during the neighbor awareness phase, the
 offering node MUST include the length of the payload in the
 descriptor for complete bundles.  The appropriate flags MUST be set
 in the B_flags for the descriptor to indicate if the descriptor
 contains the payload length field (set for fragments in all cases and
 for complete bundles if the L flag was set) and if the descriptor
 contains a payload offset field (fragments only).
 The Bundle Offer TLV also lists the bundles for which a PRoPHET
 acknowledgement has been issued.  Those bundles have the PRoPHET ACK
 flag set in their entry in the list.  When a node receives a PRoPHET
 ACK for a bundle, it SHOULD, if possible, signal to the bundle
 protocol agent that this bundle is no longer required for
 transmission by PRoPHET.  Despite no longer transmitting the bundle,
 it SHOULD keep an entry for the acknowledged bundle to be able to
 further propagate the PRoPHET ACK.
 The Response TLV format is identical to the Offer TLV with the
 exception of the TLV Type field.  Bundles that are being accepted
 from the corresponding Offer are explicitly marked with a B_flag.
 Specifications for bundles that are not being accepted MAY either be
 omitted or left in but not marked as accepted.  The payload length
 field MAY be omitted for complete bundles in the Response message
 even if it was included in the Offer message.  The B_flags payload
 length flag MUST be set correctly to indicate if the length field is
 included or not.  The Response message MUST include both payload
 offset and payload length fields for bundle fragments, and the
 B_flags MUST be set to indicate that both are present.

Lindgren, et al. Experimental [Page 52] RFC 6693 PRoPHET August 2012

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |    TLV Type   |   TLV Flags   |       TLV Length (SDNV)       |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                    Bundle Offer Count (SDNV)                  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |    B_flags    |       Bundle Source     |  Bundle Destination |
    |               |     String ID 1 (SDNV)  |  String ID 1 (SDNV) |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Bundle 1 Creation Timestamp Time              |
    |                             (SDNV)                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Bundle 1 Creation Timestamp Sequence Number         |
    |                             (SDNV)                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Bundle 1 Payload Offset - only present if bundle is a fragment|
    |                             (SDNV)                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Bundle 1 Payload Length - only present if bundle is a fragment|
    |         or transmission of length requested (SDNV)            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    ~                               .                               ~
    ~                               .                               ~
    ~                               .                               ~
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |    B_flags    |       Bundle Source     |  Bundle Destination |
    |               |     String ID n (SDNV)  |  String ID n (SDNV) |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                 Bundle n Creation Timestamp Time              |
    |                             (SDNV)                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Bundle n Creation Timestamp Sequence Number         |
    |                             (SDNV)                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Bundle n Payload Offset - only present if bundle is a fragment|
    |                             (SDNV)                            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | Bundle n Payload Length - only present if bundle is a fragment|
    |         or transmission of length requested (SDNV)            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            Figure 11: Bundle Offer and Response TLV Format

Lindgren, et al. Experimental [Page 53] RFC 6693 PRoPHET August 2012

 TLV Type
      The TLV Type for a Bundle Offer is 0xA4.  The TLV Type for a
      Bundle Response is 0xA5.
 TLV Flags
      The encoding of the Header flag field relates to the
      capabilities of the source node sending the RIB:
           Flag 0: More Offer/Response
                   TLVs Following      0b1
           Flag 1: Unassigned          0b1
           Flag 2: Unassigned          0b1
           Flag 3: Unassigned          0b1
           Flag 4: Unassigned          0b1
           Flag 5: Unassigned          0b1
           Flag 6: Unassigned          0b1
           Flag 7: Unassigned          0b1
      If the Bundle Offers or Bundle Responses are divided between
      several TLVs, the "More Offer/Response TLVs Following" flag MUST
      be set to 1 in all but the last TLV in the sequence where it
      MUST be set to 0.
 TLV Data
      Bundle Offer Count
           Number of bundle offer/response entries.  Encoded as an
           SDNV.  Note that 0 is an acceptable value.  In particular,
           a Bundle Response TLV with 0 entries is used to signal that
           a cycle of information exchange and bundle passing is
           completed.
      B Flags
           The encoding of the B Flags is:
           Flag 0: Bundle Accepted       0b1
           Flag 1: Bundle is a Fragment  0b1
           Flag 2: Bundle Payload Length
                   included in TLV       0b1
           Flag 3: Unassigned            0b1
           Flag 4: Unassigned            0b1
           Flag 5: Unassigned            0b1
           Flag 6: Unassigned            0b1
           Flag 7: PRoPHET ACK           0b1
      Bundle Source String ID
           String ID of the source EID of the bundle as predefined in
           a dictionary TLV.  Encoded as an SDNV.

Lindgren, et al. Experimental [Page 54] RFC 6693 PRoPHET August 2012

      Bundle Destination String ID
           String ID of the destination EID of the bundle as
           predefined in a dictionary TLV.  Encoded as an SDNV.
      Bundle Creation Timestamp Time
           Time component of the Bundle Creation Timestamp for the
           bundle.  Encoded as an SDNV.
      Bundle Creation Timestamp Sequence Number
           Sequence Number component of the Bundle Creation Timestamp
           for the bundle.  Encoded as an SDNV.
      Bundle Payload Offset
           Only included if the bundle is a fragment and the fragment
           bit is set (value 1) in the bundle B Flags.  Offset of the
           start of the fragment payload in the complete bundle
           payload.  Encoded as an SDNV.
      Bundle Payload Length
           Only included if the bundle length included bit is set
           (value 1) in the bundle B Flags.  Length of the payload in
           the bundle specified.  This is either the total payload
           length if the bundle is a complete bundle or the bundle
           fragment payload length if the bundle is a fragment.
           Encoded as an SDNV.

5. Detailed Operation

 In this section, some more details on the operation of PRoPHET are
 given along with state tables to help in implementing the protocol.
 As explained in Section 1.2, it is RECOMMENDED that "Success"
 responses should not be requested or sent when operating over a
 reliable, in-order transport protocol such as TCP.  If in the future
 PRoPHET were operated over an unreliable transport protocol, positive
 acknowledgements would be necessary to signal successful delivery of
 (sub)messages.  In this section, the phrase "send a message" should
 be read as *successful* sending of a message, signaled by receipt of
 the appropriate "Success" response if running over an unreliable
 protocol, but guaranteed by TCP or another reliable protocol
 otherwise.  Hence, the state descriptions below do not explicitly
 mention positive acknowledgements, whether they are being sent or
 not.

Lindgren, et al. Experimental [Page 55] RFC 6693 PRoPHET August 2012

5.1. High-Level State Tables

 This section gives high-level state tables for the operation of
 PRoPHET.  The following sections will describe each part of the
 operation in more detail (including state tables for the internal
 states of those procedures).
 The following main or high-level states are used in the state tables:
 WAIT_NB  This is the state all nodes start in.  Nodes remain in this
       state until they are notified that a new neighbor is available.
       At that point, the Hello procedure should be started with the
       new neighbor, and the node transitions into the HELLO state.
       Nodes SHOULD be able to handle multiple neighbors in parallel,
       maintaining separate state machines for each neighbor.  This
       could be handled by creating a new thread or process during the
       transition to the HELLO state that then takes care of the
       communication with the new neighbor while the parent remains in
       state WAIT_NB waiting for additional neighbors to communicate.
       In this case, when the neighbor can no longer be communicated
       with (described as "Neighbor Gone" in the tables below), the
       thread or process created is destroyed and, when a connection-
       oriented protocol is being used to communicate with the
       neighbor, the connection is closed.  The current version of the
       protocol is specified to use TCP for neighbor connections so
       that these will be closed when the neighbor is no longer
       accessible.
 HELLO Nodes are in the HELLO state from when a new neighbor is
       detected until the Hello procedure is completed and a link is
       established (which happens when the Hello procedure enters the
       ESTAB state as described in Section 5.2; during this procedure,
       the states ESTAB, SYNSENT, and SYNRCVD will be used, but these
       are internal to the Hello procedure and are not listed here).
       If the node is notified that the neighbor is no longer in range
       before a link has been established, it returns to the WAIT_NB
       state, and, if appropriate, any additional process or thread
       created to handle the neighbor MAY be destroyed.
 INFO_EXCH  After a link has been set up by the Hello procedure, the
       node transitions to the INFO_EXCH state in which the
       Information Exchange Phase is done.  The node remains in this
       state as long as Information Exchange Phase TLVs (Routing RIB,
       Routing RIB Dictionary, Bundle Offer, Bundle Response) are
       being received.  If the node is notified that the neighbor is
       no longer in range before all information and bundles have been
       exchanged, any associated connection is closed and the node

Lindgren, et al. Experimental [Page 56] RFC 6693 PRoPHET August 2012

       returns to the WAIT_NB state to await new neighbors.  The
       Timer(keep_alive) is used to ensure that the connection remains
       active.
       In the INFO_EXCH state, the nodes at both ends of the
       established link are able to update their delivery
       predictability information using data from the connected peer
       and then make offers of bundles for exchange which may be
       accepted or not by the peer.  To manage these processes, each
       node acts both as an Initiator and a Listener for the
       Information Exchange Phase processes, maintaining subsidiary
       state machines for the two roles.  The Initiator and Listener
       terms refer to the sending of the Routing RIB information: it
       is perhaps counterintuitive that the Listener becomes the
       bundle offeror and the Initiator the bundle acceptor during the
       bundling passing part.
       The protocol is designed so that the two exchanges MAY be
       carried out independently but concurrently, with the messages
       multiplexed onto on a single bidirectional link (such as is
       provided by the TCP connection).  Alternatively, the exchanges
       MAY be carried out partially or wholly sequentially if
       appropriate for the implementation.  The Information Exchange
       Phase is explained in more detail in Section 3.2.
       When an empty Bundle Response TLV (i.e., no more bundles to
       send) is received, the node starts the Timer(next_exchange).
       When this timer expires, assuming that the neighbor is still
       connected, the Initiator reruns the Information Exchange Phase.
       If there is only one neighbor connected at this time, this will
       have the effect of further increasing the delivery
       predictability for this node in the neighbor, and changing the
       delivery predictabilities as a result of the transitive
       property (Equation 3).  If there is more than one neighbor
       connected or other communication opportunities have happened
       since the previous information exchange occurred, then the
       changes resulting from these other encounters will be passed on
       to the connected neighbor.  The next_exchange timer is
       restarted once the information exchange has completed again.
       If one or more new bundles are received by this node while
       waiting for the Timer(next_exchange) to expire and the delivery
       predictabilities indicate that it would be appropriate to
       forward some or all of the bundles to the connected node, the
       bundles SHOULD be immediately offered to the connected neighbor
       and transferred if accepted.

Lindgren, et al. Experimental [Page 57] RFC 6693 PRoPHET August 2012

  State: WAIT_NB
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |   New Neighbor   | Start Hello procedure for neighbor|   HELLO   |
  |                  |  Keep waiting for more neighbors  |  WAIT_NB  |
  +==================================================================+
  State: HELLO
  +==================================================================+
  |    Condition     |               Action              | New State |
  +==================+===================================+===========+
  |  Hello TLV rcvd  |                                   |   HELLO   |
  +------------------+-----------------------------------+-----------+
  | Enter ESTAB state|  Start Information Exchange Phase | INFO_EXCH |
  +------------------+-----------------------------------+-----------+
  |  Neighbor Gone   |                                   |  WAIT_NB  |
  +==================================================================+
  State: INFO_EXCH
  +==================================================================+
  |    Condition     |               Action              | New State |
  +==================+===================================+===========+
  |     On entry     |     Start Timer(keep-alive)       |           |
  |                  |        Uses Hello Timer interval  | INFO_EXCH |
  +------------------+-----------------------------------+-----------+
  |Info Exch TLV rcvd| (processed by subsidiary state    |           |
  |                  |                         machines) | INFO_EXCH |
  +------------------+-----------------------------------+-----------+
  | No more bundles  |     Start Timer(next_exchange)    | INFO_EXCH |
  +------------------+-----------------------------------+-----------+
  | Keep-alive expiry|     Send Hello SYN message        | INFO_EXCH |
  +------------------+-----------------------------------+-----------+
  |  Hello SYN rcvd  |     Record reception              |           |
  |                  |     Restart Timer(keep-alive)     | INFO_EXCH |
  +------------------+-----------------------------------+-----------+
  |  Neighbor Gone   |                                   |  WAIT_NB  |
  +==================================================================+

Lindgren, et al. Experimental [Page 58] RFC 6693 PRoPHET August 2012

 The keep-alive messages (messages with Hello SYN TLV) are processed
 by the high-level state machine in the INFO_EXCH state.  All other
 messages are delegated to the subsidiary state machines of the
 Information Exchange Phase described in Section 5.3.  The receipt of
 keep-alive messages is recorded and may be used by the subsidiary
 machines to check if the peer is still functioning.  The connection
 will be aborted (as described in Section 4.3.1) if several keep-alive
 messages are not received.

5.2. Hello Procedure

 The Hello procedure is described by the following rules and state
 tables.  In this section, the messages sent consist of the PRoPHET
 header and a single Hello TLV (see Figure 4 and Section 4.3.1) with
 the HF (Hello Function) field set to the specified value (SYN,
 SYNACK, ACK or RSTACK).
 The state of the L flag in the latest SYN or SYNACK message is
 recorded in the node that receives the message.  If the L flag is set
 (value 1), the receiving node MUST send the payload length for each
 bundle that it offers to the peer during the Information Exchange
 Phase.
 The rules and state tables use the following operations:
 o  The "Update Peer Verifier" operation is defined as storing the
    values of the Sender Instance and Sender Local Address fields from
    a Hello SYN or Hello SYNACK function message received from the
    entity at the far end of the link.
 o  The procedure "Reset the link" is defined as:
    When using TCP or other reliable connection-oriented transport:
         Close the connection and terminate any separate thread or
         process managing the connection.
    Otherwise:
         1.   Generate a new instance number for the link.
         2.   Delete the peer verifier (set to zero the values of
              Sender Instance and Sender Local Address previously
              stored by the Update Peer Verifier operation).
         3.   Send a SYN message.
         4.   Transition to the SYNSENT state.

Lindgren, et al. Experimental [Page 59] RFC 6693 PRoPHET August 2012

 o  The state tables use the following Boolean terms and operators:
    A    The Sender Instance in the incoming message matches the value
         stored from a previous message by the "Update Peer Verifier"
         operation.
    B    The Sender Instance and Sender Local Address fields in the
         incoming message match the values stored from a previous
         message by the "Update Peer Verifier" operation.
    C    The Receiver Instance and Receiver Local Address fields in
         the incoming message match the values of the Sender Instance
         and Sender Local Address used in outgoing Hello SYN, Hello
         SYNACK, and Hello ACK messages.
    SYN    A Hello SYN message has been received.
    SYNACK A Hello SYNACK message has been received.
    ACK    A Hello ACK message has been received.
    &&     Represents the logical AND operation
    ||     Represents the logical OR operation
    !      Represents the logical negation (NOT) operation.
 o  A timer is required for the periodic generation of Hello SYN,
    Hello SYNACK, and Hello ACK messages.  The value of the timer is
    announced in the Timer field.  To avoid synchronization effects,
    uniformly distributed random jitter of +/-5% of the Timer field
    SHOULD be added to the actual interval used for the timer.
    There are two independent events: the timer expires, and a packet
    arrives.  The processing rules for these events are:
           Timer Expires:  Reset Timer
                           If state = SYNSENT Send SYN message
                           If state = SYNRCVD Send SYNACK message
                           If state = ESTAB   Send ACK message

Lindgren, et al. Experimental [Page 60] RFC 6693 PRoPHET August 2012

           Packet Arrives:
               If incoming message is an RSTACK message:
                   If (A && C && !SYNSENT) Reset the link
                   Else discard the message.
               If incoming message is a SYN, SYNACK, or ACK message:
                   Response defined by the following State Tables.
               If incoming message is any other PRoPHET TLV and
                   state != ESTAB:
                   Discard incoming message.
                   If state = SYNSENT Send SYN message(Note 1)
                   If state = SYNRCVD Send SYNACK message(Note 1)
          Note 1: No more than two SYN or SYNACK messages should be
          sent within any time period of length defined by the timer.
 o  A connection across a link is considered to be achieved when the
    protocol reaches the ESTAB state.  All TLVs, other than Hello
    TLVs, that are received before synchronization is achieved will be
    discarded.

5.2.1. Hello Procedure State Tables

  State: SYNSENT
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |   SYNACK && C    |       Update Peer Verifier;       |   ESTAB   |
  |                  |       Send ACK message            |           |
  +------------------+-----------------------------------+-----------+
  |   SYNACK && !C   |       Send RSTACK message         |  SYNSENT  |
  +------------------+-----------------------------------+-----------+
  |       SYN        |       Update Peer Verifier;       |  SYNRCVD  |
  |                  |       Send SYNACK message         |           |
  +------------------+-----------------------------------+-----------+
  |       ACK        |       Send RSTACK message         |  SYNSENT  |
  +==================================================================+

Lindgren, et al. Experimental [Page 61] RFC 6693 PRoPHET August 2012

  State: SYNRCVD
  +==================================================================+
  |    Condition     |               Action              | New State |
  +==================+===================================+===========+
  |   SYNACK && C    |       Update Peer Verifier;       |   ESTAB   |
  |                  |       Send ACK message            |           |
  +------------------+-----------------------------------+-----------+
  |   SYNACK && !C   |       Send RSTACK message         |  SYNRCVD  |
  +------------------+-----------------------------------+-----------+
  |       SYN        |       Update Peer Verifier;       |  SYNRCVD  |
  |                  |       Send SYNACK message         |           |
  +------------------+-----------------------------------+-----------+
  |  ACK && B && C   |       Send ACK message            |   ESTAB   |
  +------------------+-----------------------------------+-----------+
  | ACK && !(B && C) |       Send RSTACK message         |  SYNRCVD  |
  +==================================================================+
  State: ESTAB
  +==================================================================+
  |    Condition    |               Action               | New State |
  +=================+====================================+===========+
  |  SYN || SYNACK  | Send ACK message (notes 2 and 3)  |   ESTAB   |
  +-----------------+------------------------------------+-----------+
  |  ACK && B && C  | Send ACK message (note 3)          |   ESTAB   |
  +-----------------+------------------------------------+-----------+
  | ACK && !(B && C)|          Send RSTACK message       |   ESTAB   |
  +==================================================================+
    Note 2: No more than two ACK messages should be sent within any
    time period of length defined by the timer.  Thus, one ACK message
    MUST be sent every time the timer expires.  In addition, one
    further ACK message may be sent between timer expirations if the
    incoming message is a SYN or SYNACK.  This additional ACK allows
    the Hello functions to reach synchronization more quickly.
    Note 3: No more than one ACK message should be sent within any
    time period of length defined by the timer.

5.3. Information Exchange Phase

 After the Hello messages have been exchanged, and the nodes are in
 the ESTAB state, the Information Exchange Phase, consisting of the
 RIB Exchange and Bundle Passing Sub-Phases, is initiated.  This
 section describes the procedure and shows the state transitions

Lindgren, et al. Experimental [Page 62] RFC 6693 PRoPHET August 2012

 necessary in these sub-phases; the following sections describe in
 detail the various TLVs passed in these phases.  On reaching the
 ESTAB state in the high-level HELLO state, there is an automatic
 transition to the INFO_EXCH high-level state.
 PRoPHET runs over a bidirectional transport as documented in
 Section 1.2 so that when a pair of nodes (A and B) have reached the
 ESTAB state, they are able to perform the Information Exchange Phase
 processes for both the A-to-B and B-to-A directions over the link
 that has just been established.  In principle, these two processes
 are independent of each other and can be performed concurrently.
 However, complete concurrency may not be the most efficient way to
 implement the complete process.  As explained in Section 3.2.1, the
 Routing Information Base Dictionary is a shared resource assembled
 from a combination of information generated locally on each node and
 information passed from the peer node.  Overlaps in this information,
 and hence the amount of information that has to be passed between the
 nodes, can be minimized by sequential rather than concurrent
 operation of the dictionary generation and update processes.  It may
 also be possible to reduce the number of bundles that need to be
 offered by the second offeror by examining the offers received from
 the first offeror -- there is no need for the second offeror to offer
 a bundle that is already present in the first offeror's offer list,
 as it will inevitably be refused.
 All implementations MUST be capable of operating in a fully
 concurrent manner.  Each implementation needs to define a policy,
 which SHOULD be configurable, as to whether it will operate in a
 concurrent or sequential manner during the Information Exchange
 Phase.  If it is to operate sequentially, then further choices can be
 made as to whether to interleave dictionary, offer, and response
 exchange parts, or to complete all parts in one direction before
 initiating the other direction.
 Sequential operation will generally minimize the amount of data
 transferred across the PRoPHET link and is especially appropriate if
 the link is half-duplex.  However it is probably not desirable to
 postpone starting the information exchange in the second direction
 until the exchange of bundles has completed.  If the contact between
 the nodes ends before all possible bundles have been exchanged, it is
 possible that postponing the start of bundle exchange in the second
 direction can lead to bundle exchange being skewed in favor of one
 direction over the other.  It may be preferable to share the
 available contact time and bandwidth between directions by
 overlapping the Information Exchange Phases and running the actual
 bundle exchanges concurrently if possible.  Also, if encounters
 expected in the current PRoPHET zone are expected to be relatively
 short, it MAY not be appropriate to use sequential operation.

Lindgren, et al. Experimental [Page 63] RFC 6693 PRoPHET August 2012

 One possible interleaving strategy is to alternate between sending
 from the two nodes.  For example, if the Hello SYN node sends its
 initial dictionary entries while the Hello SYNACK node waits until
 this is complete, the Hello SYNACK node can then prune its proposed
 dictionary entries before sending in order to avoid duplication.
 This approach can be repeated for the second tranche of dictionary
 entries needed for the Bundle Offers and Responses, and also for the
 Bundle Offers, where any bundles that are offered by the Hello SYN
 node that are already present in the Hello SYNACK node need not be
 offered to the Hello SYN node.  This approach is well suited to a
 transport protocol and physical medium that is effectively half-
 duplex.
 At present, the decision to operate concurrently or sequentially is
 purely a matter of local policy in each node.  If nodes have
 inconsistent policies, the behavior at each encounter will depend on
 which node takes the SYN role; this is a matter of chance depending
 on random timing of the start of communications during the encounter.
 To manage the information transfer, two subsidiary state machines are
 created in each node to control the stages of the RIB Exchange Sub-
 Phase and Bundle Passing Sub-Phase processes within the INFO_EXCH
 high-level state as shown in Figure 12.  Each subsidiary state
 machine consists of two essentially independent components known as
 the "Initiator role" and the "Listener role".  One of these
 components is instantiated in each node.  The Initiator role starts
 the Information Exchange Phase in each node and the Listener role
 responds to the initial messages, but it is not a passive listener as
 it also originates messages.  The transition from the ESTAB state is
 a "forking" transition in that it starts both subsidiary state
 machines.  The two subsidiary state machines operate in parallel for
 as long as the neighbor remains in range and connected.

Lindgren, et al. Experimental [Page 64] RFC 6693 PRoPHET August 2012

 + - - - - - - - - +                              + - - - - - - - - +
 |    SYN node     |    PRoPHET messages with:    |   SYNACK node   |
 | +-------------+ | A. Delivery Predictabilities | +-------------+ |
   | Subsidiary  |--->---->---->---->---->---->---->| Subsidiary  |
 | |   State     | | C. Bundle Responses          | |   State     | |
   | Machine 1:  |                                  | Machine 1:  |
 | |  Initiator  | | B. Bundle Offers             | |  Listener   | |
   |    Role     |<----<----<----<----<----<----<---|    Role     |
 | +-------------+ | D. Requested Bundles         | +-------------+ |
 | +-------------+ | A. Delivery Predictabilities | +-------------+ |
   | Subsidiary  |<----<----<----<----<----<----<---| Subsidiary  |
 | |   State     | | C. Bundle Responses          | |   State     | |
   | Machine 2:  |                                  | Machine 2:  |
 | |  Listener   | | B. Bundle Offers             | |  Initiator  | |
   |    Role     |--->---->---->---->---->---->---->|    Role     |
 | +-------------+ | D. Requested Bundles         | +-------------+ |
 + - - - - - - - - +                              + - - - - - - - - +
       The letters (A - D) indicate the sequencing of messages.
    Figure 12: Information Exchange Phase Subsidiary State Machines
 These subsidiary state machines can be thought of as mirror images:
 for each state machine, one node takes on the Initiator role while
 the other node takes on the Listener role.  TLVs sent by a node from
 the Initiator role will be processed by the peer node in the Listener
 role and vice versa.  As indicated in Figure 12, the Initiator role
 handles sending that node's current set of delivery predictabilities
 for known destinations to the Listener role node.  The Listener role
 node uses the supplied values to update its delivery predictabilities
 according to the update algorithms described in Section 2.1.2.  It
 then decides which bundles that it has in store should be offered for
 transfer to the Initiator role node as a result of comparing the
 local predictabilities and those supplied by the Initiator node.
 When these offers are delivered to the Initiator role node, it
 decides which ones to accept and supplies the Listener role node with
 a prioritized list of bundles that it wishes to accept.  The Listener
 role node then sends the requested bundles.
 These exchanges are repeated periodically for as long as the nodes
 remain in contact.  Additionally, if new bundles arrive from other
 sources, they may be offered, accepted, and sent in between these
 exchanges.

Lindgren, et al. Experimental [Page 65] RFC 6693 PRoPHET August 2012

 The PRoPHET protocol is designed so that in most cases the TLV type
 determines the role in which it will be processed on reception.  The
 only exception to this is that both roles may send RIB Dictionary
 TLVs: the Initiator role sends dictionary entries for use in the
 subsequent RIB TLV(s), and the Listener role may send additional
 dictionary entries for use in subsequent Bundle Offer TLVs.  The two
 cases are distinguished by a TLV flag to ensure that they are
 processed in the right role context on reception.  If this flag was
 not provided, there are states where both roles could accept the RIB
 Dictionary TLV, making it impossible to ensure that the correct role
 state machine accepts the RIB Dictionary TLV.  Note that the correct
 updates would be made to the dictionary whichever role processed the
 TLV and that the ambiguity would not arise if the roles are adopted
 completely sequentially, i.e., if the RIB Exchange Sub-Phase and
 associated Bundle Passing Sub-Phase run to completion in one
 direction before the process for the reverse direction is started.
 If sequential operation is selected, the node that sent the Hello SYN
 function message MUST be the node that sends the first message in the
 Information Exchange Phase process.  This ensures that there is a
 well-defined order of events with the Initiator role in the Hello SYN
 node (i.e., the node identified by String ID 0) starting first.  The
 Hello SYNACK node MAY then postpone sending its first message until
 the Listener role state machine in the Hello SYNACK node has reached
 any of a number of points in its state progression according to
 locally configured policy and the nature of the physical link for the
 current encounter between the nodes as described above.  If
 concurrent operation is selected, the Hello SYNACK node can start
 sending messages immediately without waiting to receive messages from
 the peer.
 The original design of the PRoPHET protocol allowed it to operate
 over unreliable datagram-type transports as well as the reliable, in-
 order delivery transport of TCP that is currently specified.  When
 running over TCP, protocol errors and repeated timeouts during the
 Information Exchange Phase SHOULD result in the connection being
 terminated.

5.3.1. State Definitions for the Initiator Role

 The state machine component with the Initiator role in each node
 starts the transfer of information from one node to its peer during
 the Information Exchange Phase.  The process from the Initiator's
 point of view does the following:
 o  The Initiator role determines the set of delivery predictabilities
    to be sent to the peer node and sends RIB dictionary entries
    necessary to interpret the set of RIB predictability values that

Lindgren, et al. Experimental [Page 66] RFC 6693 PRoPHET August 2012

    are sent after the dictionary updates.  On second and subsequent
    executions of this state machine during a single session with the
    same peer, there may be no RIB Dictionary entries to send.  Either
    an empty TLV can be sent or the TLV can be omitted.
 o  The Initiator then waits to receive any RIB Dictionary updates
    followed by bundle offers from the Listener role on the peer node.
 o  The Initiator determines which of the bundle offers should be
    accepted and, if necessary, reorders the offers to suit its own
    priorities.  The possibly reordered list of accepted bundles is
    sent to the peer node using one or more bundle responses.
 o  The peer then sends the accepted bundles to the Initiator in turn.
 o  Assuming that the link remains open during the bundle sending
    process, the Initiator signals that the Bundle Passing Sub-Phase
    is complete by sending a message with an empty Bundle Response TLV
    (i.e, with the Bundle Offer Count set to 0 and no bundle offers
    following the TLV header).
 o  When the bundle transfer is complete, the Initiator starts the
    Timer(next_exchange).  Assuming that the connection to the
    neighbor remains open, when the timer expires, the Initiator
    restarts the Information Exchange Phase.  During this period,
    Hello SYN messages are exchanged as keep-alives to check that the
    neighbor is still present.  The keep-alive mechanism is common to
    the Initiator and Listener machines and is handled in the high-
    level state machine (see Section 5.1.
 A timer is provided that restarts the Initiator role state machine if
 Bundle Offers are not received after sending the RIB.  If this node
 receives a Hello ACK message containing an Error TLV indicating there
 has been a protocol problem, then the connection MUST be terminated.
 The following states are used:
 CREATE_DR
    The initial transition to this state from the ESTAB state is
    immediate and automatic for the node that sent the Hello SYN
    message.  For the peer (Hello SYNACK sender) node, it may be
    immediate for nodes implementing a fully concurrent process or may
    be postponed until the corresponding Listener has reached a
    specified state if a sequential process is configured in the node
    policy.

Lindgren, et al. Experimental [Page 67] RFC 6693 PRoPHET August 2012

    The local dictionary is initialized when this state is entered for
    the first time from the ESTAB state.  The initial state of the
    dictionary contains two entries: the EID of the node that sent the
    Hello SYN (String ID 0) and the EID of the node that sent the
    Hello SYNACK (String ID 1).  If the peer reports via a Hello ACK
    message containing an Error TLV reporting a Dictionary Conflict or
    Bad String ID error, then the connection MUST be terminated.
    The CREATE_DR state will be entered in the same way from the
    REQUEST state when the Timer(next_exchange) expires, signaling the
    start of a new round of information exchange and bundle passing.
    When in this state:
  • Determine the destination EIDs for which delivery

predictabilities will be sent to the peer in a RIB TLV, if any.

       Record the prior state of the local dictionary (assuming that
       String IDs are numbers allocated sequentially, the state
       information needed is just the highest ID used before this
       process started) so that the process can be restarted if
       necessary.  Update the local dictionary if any new EIDS are
       required; format one or more RIB Dictionary TLVs and one or
       more RIB TLVs and send them to the peer.  If there are no
       dictionary entries to send, TLVs with zero entries MAY be sent,
       or the TLV can be omitted, but an empty RIB TLV MUST be sent if
       there is no data to send.  The RIB Dictionary TLVs generated
       here MUST have the Sent by Listener flag set to 0 to indicate
       that they were sent by the Initiator.
  • If an Error TLV indicating a Dictionary Conflict or

Bad String ID is received during or after sending the RIB

       Dictionary TLVs and/or the RIB TLVs, abort any in-progress
       Initiator or Listener process, and terminate the connection to
       the peer.
  • Start a timer (known as Timer(info)) and transition to the

SEND_DR state.

    Note that when (and only when) running over a transport protocol
    such as TCP, both the RIB Dictionary and RIB information MAY be
    spread across multiple TLVs and messages if required by known
    constraints of the transport protocol or to reduce the size of
    memory buffers.  Alternatively, the information can be formatted
    using a single RIB Dictionary TLV and a single RIB TLV.  These
    TLVs may be quite large, so it may be necessary to segment the
    message either using the PRoPHET submessage capability or, if the
    transport protocol has appropriate capabilities, using those
    inherent capabilities.  This discussion of segmentation applies to

Lindgren, et al. Experimental [Page 68] RFC 6693 PRoPHET August 2012

    the other states and the bundle offer and bundle response messages
    and will not be repeated.
    If more than one RIB TLV is to be used, all but the last one have
    the "More RIB TLVs" flag set to 1 in the TLV flags.  It is not
    necessary to distinguish the last RIB Dictionary TLV because the
    actions taken at the receiver are essentially passive (recording
    the contents), and the sequence is ended by the sending of the
    first RIB TLV.
 SEND_DR
    In this state, the Initiator node expects to be receiving Bundle
    Offers and sending Bundle Responses.  The Initiator node builds a
    list of bundles offered by the peer while in this state:
  • Clear the set of bundles offered by the peer on entry to the

state.

  • If the Timer(info) expires, re-send the RIB Dictionary and RIB

information sent in the previous CREATE_DR state using the

       stored state to re-create the information.  The RIB dictionary
       update process in the peer is idempotent provided that the
       mappings between the EID and the String ID in the re-sent RIB
       Dictionary TLVs are the same as in the original.  This means
       that it does not matter if some of the RIB Dictionary TLVs had
       already been processed in the peer.  Similarly, re-sending RIB
       TLVs will not cause a problem.
  • If a message with a RIB Dictionary TLV marked as sent by a

Listener is received, update the local dictionary based on the

       received TLV.  If any of the entries in the RIB Dictionary TLV
       conflict with existing entries (i.e., an entry is received that
       uses the same String ID as some previously received entry but
       the EID in the entry is different), send a Response message
       with an Error TLV containing a Dictionary Conflict indicator,
       abort any in-progress Initiator or Listener process, and
       terminate the connection to the peer.  Note that in some
       circumstances no dictionary updates are needed, and the first
       message received in this state will carry a Bundle Offer TLV.
  • If a message with a Bundle Offer TLV is received, restart the

Timer(info) if the "More Offer/Response TLVs Following" flag is

       set in the TLV; otherwise, stop the Timer(info).  Then process
       any PRoPHET ACKs in the TLV by informing the bundle protocol
       agent, and add the bundles offered in the TLV to the set of
       bundles offered.  If the "More Offer/Response TLVs Following"
       flag is set in the TLV, wait for further Bundle Offer TLVs.  If
       a Bundle Offer TLV is received with a String ID that is not in

Lindgren, et al. Experimental [Page 69] RFC 6693 PRoPHET August 2012

       the dictionary, send a message with an Error TLV containing a
       Bad String ID indicator, abort any in-progress Initiator or
       Listener process, and terminate the connection to the peer.
  • If the "More Offer/Response TLVs Following" flag is clear in

the last Bundle Offer TLV received, inspect the set of bundles

       offered to determine the set of bundles that are to be accepted
       using the configured queueing policy.  Record the set of
       bundles accepted so that reception can be checked in the Bundle
       Passing Sub-Phase.  Format one or more Bundle Response TLVs
       flagging the accepted offers and send them to the peer.  If
       more than one Bundle Response TLV is sent, all but the last one
       should have the "More Offer/Response TLVs Following" flag set
       to 1.  At least one Bundle Response TLV MUST be sent even if
       the node does not wish to accept any of the offers.  In this
       case, the Bundle Response TLV contains an empty set of
       acceptances.
  • If an Error TLV indicating a Bad String ID is received during

or after sending the Bundle Response TLVs, abort any in-

       progress Initiator or Listener process, re-initialize the local
       dictionary, and terminate the connection to the peer.
  • Restart the Timer(info) timer in case the peer does not start

sending the requested bundles.

  • Transition to state REQUEST.
 REQUEST
    In this state, the Initiator node expects to be receiving the
    bundles accepted in the Bundle Response TLV(s):
  • Keep track of the bundles received and delete them from the set

of bundles accepted.

  • If the Timer(info) expires while waiting for bundles, format

and send one or more Bundle Response TLVs listing the bundles

       previously accepted but not yet received.  If more than one
       Bundle Response TLV is sent, all but the last one should have
       the "More Offer/Response TLVs Following" flag set to 1.
  • If an Error TLV indicating a Bad String ID is received during

or after sending the Bundle Response TLVs, abort any in-

       progress Initiator or Listener process, re-initialize the local
       dictionary, and terminate the connection to the peer.
  • Restart the Timer(info) timer after each bundle is received in

case the peer does not continue sending the requested bundles.

Lindgren, et al. Experimental [Page 70] RFC 6693 PRoPHET August 2012

  • When all the requested bundles have been received, format a

Bundle Response TLV with the Bundle Offer Count set to zero and

       with the "More Offer/Response TLVs Following" flag cleared to 0
       to signal completion to the peer node.  Also, signal the
       Listener in this node that the Initiator has completed.  If the
       peer node is using a sequential policy, the Listener may still
       be in the initial state, in which case, it needs to start a
       timer to ensure that it detects if the peer fails to start the
       Initiator state machine.  Thereafter, coordinate with the
       Listener state machine in the same node: when the Listener has
       received the completion notification from the peer node and
       this Initiator has sent its completion notification, start
       Timer(next_exchange).
  • If the Timer(next_exchange) expires, transition to state

CREATE_DR to restart the Information Exchange Phase.

    Note that if Timer(info) timeout occurs a number of times
    (configurable, typically 3) without any bundles being received,
    then this SHOULD generally be interpreted as the problem that the
    link to the peer is no longer functional and the session should be
    terminated.  However, some bundles may be very large and take a
    long time to transmit.  Before terminating the session, this state
    machine needs to check if a large bundle is actually being
    received although no new completed bundles have been received
    since the last expiry of the timer.  In this case the timer should
    be restarted without sending the Bundle Response TLV.  Also, if
    the bundles are being exchanged over a transport protocol that can
    detect link failure, then the session MUST be terminated if the
    bundle exchange link is shut down because it has failed.

5.3.2. State Definitions for the Listener Role

 The state machine component with the Listener role in each node
 initially waits to receive a RIB Dictionary update followed by a set
 of RIB delivery predictabilities during the Information Exchange
 Phase.  The process from the point of view of the Listener does the
 following:
 o  Receive RIB Dictionary updates and RIB values from the peer.  Note
    that in some circumstances no dictionary updates are needed, and
    the RIBD TLV will contain no entries or may be omitted completely.
 o  When all RIB messages have been received, the delivery
    predictability update algorithms are run (see Section 2.1.2) using
    the values received from the Initiator node and applying any of
    the optional optimizations configured for this node (see
    Section 2.1.3).

Lindgren, et al. Experimental [Page 71] RFC 6693 PRoPHET August 2012

 o  Using the updated delivery predictabilities and the queueing
    policy and forwarding strategy configured for this node (see
    Section 2.1.4) examine the set of bundles currently stored in the
    Listener node to determine the set of bundles to be offered to the
    Initiator and order the list according to the forwarding strategy
    in use.  The Bundle Offer TLVs are also used to notify the peer of
    any PRoPHET ACKs that have been received by the Listener role
    node.
 o  Send the list of bundles in one or more bundle offers, preceded if
    necessary by one or more RIB dictionary updates to add any EIDs
    required for the source or destination EIDs of the offered
    bundles.  These updates MUST be marked as being sent by the
    Listener role so that they will be processed by the Initiator role
    in the peer.
 o  Wait for the Initiator to send bundle responses indicating which
    bundles should be sent and possibly a modified order for the
    sending.  Send the accepted bundles in the specified order.  The
    bundle sending will normally be carried out over a separate
    connection using a suitable DTN convergence layer.
 o  On completion of the sending, wait for a message with an empty
    Bundle Response TLV indicating correct completion of the process.
 o  The Listener process will be notified if any new bundles or
    PRoPHET ACKs are received by the node after the completion of the
    bundle sending that results from this information exchange.  The
    forwarding policy and the current delivery predictabilities will
    then be applied to determine if this information should be sent to
    the peer.  If it is determined that one or more bundles and/or
    ACKs ought to be forwarded, a new set of bundle offers are sent to
    the peer.  If the peer accepts them by sending bundle responses,
    the bundles and/or ACKS are transferred as previously.
 o  Periodically, the Initiator in the peer will restart the complete
    information exchange by sending a RIB TLV that may be, optionally,
    preceded by RIB Dictionary entries if they are required for the
    updated RIB.
 Timers are used to ensure that the Listener does not lock up if
 messages are not received from the Initiator in a timely fashion.
 The Listener is restarted if the RIB is not received, and a Hello ACK
 message is sent to force the Initiator to restart.  If bundle
 response messages are not received in a timely fashion, the Listener
 re-sends the bundle offers and associated dictionary updates.  The
 following states are used:

Lindgren, et al. Experimental [Page 72] RFC 6693 PRoPHET August 2012

 WAIT_DICT
    The Listener subsidiary state machine transitions to this state
    automatically and immediately from the state ESTAB in both peers.
    This state will be entered in the same way if the
    Timer(next_exchange) expires in the peer, signaling the start of a
    new round of information exchange and bundle passing.  This will
    result in one or more RIB TLVs being sent to the Listener by the
    peer node's Initiator.
  • When a RIB Dictionary TLV is received, use the TLV to update

the local dictionary, start or (if it is running) restart the

       Timer(peer) and transition to state WAIT_RIB.  If any of the
       entries in the RIB Dictionary TLV conflict with existing
       entries (i.e., an entry is received that uses the same String
       ID as some previously received entry, but the EID in the entry
       is different), send a Response message with an Error TLV
       containing a Dictionary Conflict indicator, abort any in-
       progress Initiator or Listener process, and terminate the
       connection to the peer.
  • If a Hello ACK message is received from the peer node,

transition to state WAIT_DICT and restart the process.

    If multiple timeouts occur (configurable, typically 3), assume
    that the link is broken and terminate the session.  Note that the
    RIB Dictionary and RIB TLVs may be combined into a single message.
    The RIB TLV should be passed on to be processed in the WAIT_RIB
    state.
 WAIT_RIB
    In this state, the Listener expects to be receiving one or more
    RIB TLVs and possibly additional RIB Dictionary TLVs.
  • On entry to this state, clear the set of received delivery

predictabilities.

  • Whenever a new message is received, restart the Timer(peer)

timer.

  • If a RIB dictionary TLV is received, use it to update the local

dictionary and remain in this state. If any of the entries in

       the RIB Dictionary TLV conflict with existing entries (i.e., an
       entry is received that uses the same String ID as some
       previously received entry, but the EID in the entry is
       different), send a message with an Error TLV containing a
       Dictionary Conflict indicator, abort any in-progress Initiator
       or Listener process, and terminate the connection to the peer.

Lindgren, et al. Experimental [Page 73] RFC 6693 PRoPHET August 2012

  • If a RIB TLV is received, record the received delivery

predictabilities for use in recalculating the local delivery

       predictabilities.  If a delivery predictability value is
       received for an EID that is already in the set of received
       delivery predictabilities, overwrite the previously received
       value with the latest value.  If a delivery predictability
       value is received with a String ID that is not in the
       dictionary, send a message with an Error TLV containing a
       Bad String ID indicator, abort any in-progress Initiator or
       Listener process, and terminate the connection to the peer.
  • When a RIB TLV is received with the "More RIB TLVs" flag

cleared, initiate the recalculation of delivery

       predictabilities and stop the Timer(peer).  Use the revised
       delivery predictabilities and the configured queueing and
       forwarding strategies to create a list of bundles to be offered
       to the peer node.
  • Record the state of the local dictionary in case the offer

procedure has to be restarted. Determine if any new dictionary

       entries are required for use in the Bundle Offer TLV(s).  If
       so, record them in the local dictionary, then format and send
       RIB Dictionary entries in zero or more RIB Dictionary TLV
       messages to update the dictionary in the peer if necessary.
  • Format and send Bundle Offer TLV(s) carrying the identifiers of

the bundles to be offered together with any PRoPHET ACKs

       received or generated by this node.  If more than one Bundle
       Offer TLV is sent, all but the last Bundle Offer TLV sent MUST
       have the "More Offer/Response TLVs Following" flag set to 1.
  • When all Bundle Offer TLVs have been sent, start the

Timer(info) and transition to state OFFER.

  • If the Timer(peer) expires, send a Hello ACK TLV to the peer,

restart the timer, and transition to state WAIT_DICT.

  • If an Error TLV indicating a Dictionary Conflict or

Bad String ID is received during or after sending the RIB

       Dictionary TLVs and/or the Bundle Offer TLVs, abort any in-
       progress Initiator or Listener process, and terminate the
       connection to the peer.
  • If a Hello ACK message is received from the peer node,

transition to state WAIT_DICT and restart the process.

Lindgren, et al. Experimental [Page 74] RFC 6693 PRoPHET August 2012

 OFFER
    In this state, the Listener expects to be receiving one or more
    Bundle Response TLVs detailing the bundles accepted by the
    Initiator node.  The ordered list of accepted bundles is
    communicated to the bundle protocol agent, which controls sending
    them to the peer node over a separate connection.
  • When a Bundle Response TLV is received with a non-zero count of

Bundle Offers, extract the list of accepted bundles and send

       the list to the bundle protocol agent so that it can start
       transmission to the peer node.  Ensure that the order of offers
       from the TLV is maintained.  Restart the Timer(info) unless the
       last Bundle Response TLV received has the "More Offer/
       Response TLVs Following" flag set to 0.  If a Bundle Response
       TLV is received with a String ID that is not in the dictionary,
       send a message with an Error TLV containing a Bad String ID
       indicator, abort any in-progress Initiator or Listener process,
       and terminate the connection to the peer.
  • After receiving a Bundle Response TLV with the "More Offer/

Response TLVs Following" flag set to 0 stop the Timer(info) and

       transition to state SND_BUNDLE.
  • If the Timer(info) expires, send a Hello ACK TLV to the peer,

restart the timer and transition to state WAIT_DICT.

  • If a Hello ACK message is received from the peer node,

transition to state WAIT_DICT and restart the process.

 SND_BUNDLE
    In this state the Listener monitors the sending of bundles to the
    Initiator peer node.  In the event of disruption in transmission,
    the Initiator node will, if possible, re-send the list of bundles
    that were accepted but have not yet been received.  The bundle
    protocol agent has to be informed of any updates to the list of
    bundles to send (this is likely to involve re-sending one or more
    bundles).  Otherwise, the Listener is quiescent in this state.
  • When a Bundle Response TLV is received with a non-zero count of

Bundle Offers, extract the list of accepted bundles and update

       the list previously passed to the bundle protocol agent so that
       it can (re)start transmission to the peer node.  Ensure that
       the order of offers from the TLV is maintained so far as is
       possible.  Restart the Timer(info) unless the last Bundle
       Response TLV received has the "More Offer/Response TLVs
       Following" flag set to 0.  If a Bundle Response TLV is received
       with a String ID that is not in the dictionary, send a message
       with an Error TLV containing a Bad String ID indicator, abort

Lindgren, et al. Experimental [Page 75] RFC 6693 PRoPHET August 2012

       any in-progress Initiator or Listener process, re-initialize
       the local dictionary, and restart the Information Exchange
       Phase as if the ESTAB state had just been reached.
  • After receiving a Bundle Response TLV with the "More Offer/

Response TLVs Following" flag set to 0, stop the Timer(info)

       and wait for completion of bundle sending.
  • If the Timer(info) expires, send a Hello ACK TLV to the peer,

restart the timer, and transition to state WAIT_DICT.

  • If a Hello ACK message is received from the peer node,

transition to state WAIT_DICT and restart the process.

  • When a Bundle Response TLV is received with a zero count of

Bundle Offers, the Bundle Passing Sub-Phase is complete.

       Notify the Initiator that the Listener process is complete and
       transition to state WAIT_MORE.
    As explained in the Initiator state REQUEST description, depending
    on the transport protocol (convergence layer) used to send the
    bundles to the peer node, it may be necessary during the bundle
    sending process to monitor the liveness of the connection to the
    peer node in the Initiator process using a timer.
 WAIT_MORE
    In this state, the Listener monitors the reception of new bundles
    that might be received from a number of sources, including
  • local applications on the node,
  • other mobile nodes that connect to the node while this

connection is open, and

  • permanent connections such as might occur at an Internet

gateway.

    When the Listener is notified of received bundles, it determines
    if they should be offered to the peer.  The peer may also re-
    initiate the Information Exchange Phase periodically.
  • When the bundle protocol agent notifies the Listener that new

bundles and/or new PRoPHET ACKs have been received, the

       Listener applies the selected forwarding policy and the current
       delivery predictabilities to determine if any of the items
       ought to be offered to the connected peer.  If so, it carries

Lindgren, et al. Experimental [Page 76] RFC 6693 PRoPHET August 2012

       out the same operations as are described in the WAIT_RIB state
       to build and send any necessary RIB Dictionary TLVs and RIB
       TLVs to the Initiator in the peer.
  • When all Bundle Offer TLVs have been sent, start the

Timer(info) and transition to state OFFER.

  • If a RIB dictionary TLV is received, use it to update the local

dictionary and transition to state WAIT_RIB. If any of the

       entries in the RIB Dictionary TLV conflict with existing
       entries (i.e., an entry is received that uses the same String
       ID as some previously received entry, but the EID in the entry
       is different), send a message with an Error TLV containing a
       Dictionary Conflict indicator, abort any in-progress Initiator
       or Listener process, and terminate the connection to the peer.
    Note that the RIB Dictionary and RIB TLVs may be combined into a
    single message.  The RIB TLV should be passed on to be processed
    in the WAIT_RIB state.

5.3.3. Recommendations for Information Exchange Timer Periods

 The Information Exchange Phase (IEP) state definitions include a
 number of timers.  This section provides advice and recommendations
 for the periods that are appropriate for these timers.
 Both Timer(info) and Timer(peer) are used to ensure that the state
 machines do not become locked into inappropriate states if the peer
 node does not apparently respond to messages sent in a timely fashion
 either because of message loss in the network or unresponsiveness
 from the peer.  The appropriate values are to some extent dependent
 on the speed of the network connection between the nodes and the
 capabilities of the nodes executing the PRoPHET implementations.
 Values in the range 1 to 10 seconds SHOULD be used, with a value of 5
 seconds RECOMMENDED as default.  The period should not be set to too
 low a value, as this might lead to inappropriate restarts if the
 hardware is relatively slow or there are large numbers of pieces of
 information to process before responding.  When using a reliable
 transport protocol such as TCP, these timers effectively provide a
 keep-alive mechanism and ensure that a failed connection is detected
 as rapidly as possible so that remedial action can be taken (if
 possible) or the connection shut down tidily if the peer node has
 moved out of range.
 Timer(next_exchange) is used to determine the maximum frequency of
 (i.e., minimum period between) successive re-executions of the
 information exchange state machines during a single session between a
 pair of nodes.  Selection of the timer period SHOULD reflect the

Lindgren, et al. Experimental [Page 77] RFC 6693 PRoPHET August 2012

 trade-off between load on the node processor and desire for timely
 forwarding of bundles received from other nodes.  It is RECOMMENDED
 that the timer periods used should be randomized over a range from
 50% to 150% of the base value in order to avoid synchronization
 between multiple nodes.  Consideration SHOULD be given to the
 expected length of typical encounters and the likelihood of
 encounters between groups of nodes when setting this period.  Base
 values in the range of 20 to 60 seconds are RECOMMENDED.

5.3.4. State Tables for Information Exchange

 This section shows the state transitions that nodes go through during
 the Information Exchange Phase.  State tables are given for the
 Initiator role and for the Listener role of the subsidiary state
 machines.  Both nodes will be running machines in each role during
 the Information Exchange Phase, and this can be done either
 concurrently or sequentially, depending on the implementation, as
 explained in Section 5.3.  The state tables in this section should be
 read in conjunction with the state descriptions in Sections 5.3.1 and
 5.3.2.

5.3.4.1. Common Notation, Operations and Events

 The following notation is used:
 nS            Node that sent the Hello SYN message.
 nA            Node that sent the Hello SYNACK message.
 The following events are common to the Initiator and Listener state
 tables:
 ErrDC         Dictionary Conflict Error TLV received.
 ErrBadSI      Bad String ID Error TLV received.
 HelloAck      Hello ACK TLV received.  This message is delivered to
               both Initiator and Listener roles in order to cause a
               restart of the Information Exchange Phase in the event
               of message loss or protocol problems.

Lindgren, et al. Experimental [Page 78] RFC 6693 PRoPHET August 2012

 InitStart     Sent by Listener role to Initiator role to signal the
               Initiator role to commence sending messages to peer.
               If the Listener instance is running in the node that
               sent the Hello SYN (nS), then InitStart is signaled
               immediately when the state is entered.  For the node
               that sent the Hello SYNACK (nA), InitStart may be
               signaled immediately if the operational policy requires
               concurrent operation of the Initiator and Listener
               roles or postponed until the Listener role state
               machine has reached a state defined by the configured
               policy.
 RIBnotlast    RIB TLV received with "More RIB TLVs" flag set to 1.
 RIBlast       RIB TLV received with "More RIB TLVs" flag set to 0.
 REQnotlast    Bundle Response TLV received with More Offer/Response
               TLVs Following flag set to 1.
 REQlast       Bundle Response TLV received with More Offer/Response
               TLVs Following flag set to 0.
 RIBDi         RIBD TLV received with Sent by Listener flag set to 0
               (i.e., it was sent by Initiator role).
 RIBDl         RIBD TLV received with Sent by Listener flag set to 1
               (i.e., it was sent by Listener role).
 Timeout(info) The Timer(info) has expired.
 Timeout(peer) The Timer(peer) has expired.
 Both the Initiator and Listener state tables use the following common
 operations:
 o  The "Initialize Dictionary" operation is defined as emptying any
    existing local dictionary and inserting the two initial entries:
    the EID of the node that sent the Hello SYN (String ID 0) and the
    EID of the node that sent the Hello SYNACK (String ID 1).
 o  The "Send RIB Dictionary Updates" operation is defined as:
    1.  Determining what dictionary updates will be needed for any
        extra EIDs in the previously selected RIB entries set that are
        not already in the dictionary and updating the local
        dictionary with these EIDs.  The set of dictionary updates may
        be empty if no extra EIDs are needed.  The set may be empty
        even on the first execution if sequential operation has been

Lindgren, et al. Experimental [Page 79] RFC 6693 PRoPHET August 2012

        selected, this is the second node to start and the necessary
        EIDs were in the set previously sent by the first node to
        start.
    2.  Formatting zero or more RIBD TLVs for the set of dictionary
        updates identified in the "Build RIB Entries" operation and
        sends them to the peer.  The RIBD TLVs MUST have the "Sent by
        Listener" flag set to 0 if the updates are sent by the
        Initiator role and to 1 if sent by the Listener role.  In the
        case of the Initiator role, an empty RIBD TLV MUST be sent
        even if the set of updates is empty in order to trigger the
        Listener state machine.
 o  The "Update Dictionary" operation uses received RIBD TLV entries
    to update the local dictionary.  The received entries are checked
    against the existing dictionary.  If the String ID in the entry is
    already in use, the entry is accepted if the EID in the received
    entry is identical to that stored in the dictionary previously.
    If it is identical, the entry is unchanged, but if it is not a
    Response message with an Error TLV indicating Dictionary Conflict
    is sent to the peer in an Error Response message, the whole
    received RIBD TLV is ignored, and the Initiator and Listener
    processes are restarted as if the ESTAB state has just been
    reached.
 o  The "Abort Exchange" operation is defined as aborting any in-
    progress information exchange state machines and terminating the
    connection to the peer.
 o  The "Start TI" operation is defined as (re)starting the
    Timer(info) timer.
 o  The "Start TP" operation is defined as (re)starting the
    Timer(peer) timer.
 o  The "Cancel TI" operation is defined as canceling the Timer(info)
    timer.
 o  The "Cancel TP" operation is defined as canceling the Timer(info)
    timer.

Lindgren, et al. Experimental [Page 80] RFC 6693 PRoPHET August 2012

5.3.4.2. State Tables for the Initiator Role

 The rules and state tables for the Initiator role use the following
 operations:
 o  The "Build RIB Entries" operation is defined as:
    1.  Recording the state of the local dictionary.
    2.  Determining the set of EIDs for which RIB entries should be
        sent during this execution of the Initiator role state machine
        component.  If this is a second or subsequent run of the state
        machine in this node during the current session with the
        connected peer, then the set of EIDs may be empty if no
        changes have occurred since the previous run of the state
        machine.
    3.  Determining and extracting the current delivery predictability
        information for the set of EIDs selected.
 o  The "Send RIB Entries" operation formats one or more RIB TLVs with
    the set of RIB entries identified in the "Build RIB Entries"
    operation and sends them to the peer.  If the set is empty, a
    single RIB TLV with zero entries is sent.  If more than one RIB
    TLV is sent, all but the last one MUST have the "More RIB TLVs"
    flag set to 1; the last or only one MUST have the flag set to 0.
 o  The "Clear Bundle Lists" operation is defined as emptying the
    lists of bundles offered by the peer and bundles requested from
    the peer.
 o  The "Notify ACKs" operation is defined as informing the bundle
    protocol agent that PRoPHET ACKs has been received for one or more
    bundles in a Bundle Offer TLV using the Bundle Delivered interface
    (see Section 2.2).
 o  The "Record Offers" operation is defined as recording all the
    bundles offered in a Bundle Offer TLV in the list of bundles
    offers.
 o  The "Select for Request" operation prunes and sorts the list of
    offered bundles held into the list of requested bundles according
    to policy and the available resources ready for sending to the
    offering node.

Lindgren, et al. Experimental [Page 81] RFC 6693 PRoPHET August 2012

 o  The "Send Requests" operation is defined as formatting one or more
    non-empty Bundle Response TLVs and sending them to the offering
    node.  If more than one Bundle Offer TLV is sent, all but the last
    one MUST have the "More Offer/Response TLVs Following" flag set to
    1; the last or only one MUST have the flag set to 0.
 o  The "Record Bundle Received" operation deletes a successfully
    received bundle from the list of requests.
 o  The "All Requests Done" operation is defined as formatting and
    sending an empty Bundle Offer TLV, with the "More Offer/Response
    TLVs Following" flag set to 0, to the offering node.
 o  The "Check Receiving" operation is defined as checking with the
    node bundle protocol agent if bundle reception from the peer node
    is currently in progress.  This is needed in case a timeout occurs
    while waiting for bundle reception and a very large bundle is
    being processed.
 o  The "Start NE" operation is defined as (re)starting the
    Timer(next_exchange).
 The following events are specific to the Initiator role state
 machine:
 LastBndlRcvd  Bundle received from peer that is the only remaining
               bundle in Bundle Requests List.
 NotLastBndlRcvd  Bundle received from peer that is not the only
               remaining bundle in Bundle Requests List.
 OFRnotlast    Bundle Offer TLV received with "More Offer/Response
               TLVs Following" flag set to 1.
 OFRlast       Bundle Offer TLV received with "More Offer/Response
               TLVs Following" flag set to 0
 Timeout(next_exch)  The Timer(next_exchange) has expired

Lindgren, et al. Experimental [Page 82] RFC 6693 PRoPHET August 2012

  State: CREATE_DR
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |     On Entry     |    If previous state was ESTAB:   |           |
  |                  |         Initialize Dictionary     |           |
  |                  |    Always:                        |           |
  |                  |         Build RIB Entries         |           |
  |                  |         Wait for Init Start       | CREATE_DR |
  +------------------+-----------------------------------+-----------+
  |    InitStart     |    Send RIB Dictionary Updates    |           |
  |                  |    Send RIB Entries               |           |
  |                  |    Start TI                       |  SEND_DR  |
  +------------------+-----------------------------------+-----------+
  |      ErrDC       |           Abort Exchange          |(finished) |
  +------------------+-----------------------------------+-----------+
  |     ErrBadSI     |           Abort Exchange          |(finished) |
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |           Abort Exchange          | CREATE_DR |
  +==================================================================+

Lindgren, et al. Experimental [Page 83] RFC 6693 PRoPHET August 2012

  State: SEND_DR
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |     On Entry     |         Clear Bundle Lists        |  SEND_DR  |
  +------------------+-----------------------------------+-----------+
  |  Timeout(info)   |   Send RIB Dictionary Updates     |           |
  |                  |   Send RIB Entries (note 1)       |  SEND_DR  |
  +------------------+-----------------------------------+-----------+
  |  RIBDl received  |   Update Dictionary (note 2)      |           |
  |                  |   If Dictionary Conflict found:   |           |
  |                  |           Abort Exchange          | CREATE_DR |
  |                  |   Else:                           |           |
  |                  |           Start TI                |  SEND_DR  |
  +------------------+-----------------------------------+-----------+
  |    OFRnotlast    |           Notify ACKs             |           |
  |                  |           Record Offers           |           |
  |                  |           Start TI                |  SEND_DR  |
  +------------------+-----------------------------------+-----------+
  |     OFRlast      |           Cancel TI               |           |
  |                  |           Notify ACKs             |           |
  |                  |           Record Offers           |           |
  |                  |           Select for Request      |           |
  |                  |           Send Requests           |           |
  |                  |           Start TI                |  REQUEST  |
  +------------------+-----------------------------------+-----------+
  |      ErrDC       |           Abort Exchange          |(finished) |
  +------------------+-----------------------------------+-----------+
  |     ErrBadSI     |           Abort Exchange          |(finished) |
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |           Abort Exchange          | CREATE_DR |
  +==================================================================+

Lindgren, et al. Experimental [Page 84] RFC 6693 PRoPHET August 2012

  State: REQUEST
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |  Timeout(info)   |  Check Receiving                  |           |
  |                  |  If bundle reception in progress: |           |
  |                  |         Start TI                  |  REQUEST  |
  |                  |  Otherwise:                       |           |
  |                  |         Send Requests             |           |
  |                  |         Start TI (note 3)         |  REQUEST  |
  +------------------+-----------------------------------+-----------+
  | NotLastBndlRcvd  |     Record Bundle Received        |           |
  |                  |     Start TI                      |  REQUEST  |
  +------------------+-----------------------------------+-----------+
  |   LastBndlRcvd   |     Cancel TI                     |           |
  |                  |     All Requests Done             |           |
  |                  |     Start NE                      |  REQUEST  |
  +------------------+-----------------------------------+-----------+
  |Timeout(next_exch)|                                   | CREATE_DR |
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |     Abort Exchange                | CREATE_DR |
  +==================================================================+
 Note 1:
    No response to the RIB has been received before the timer expired,
    so we re-send the dictionary and RIB TLVs.  If the timeout occurs
    repeatedly, it is likely that communication has failed and the
    connection MUST be terminated.
 Note 2:
    If a Dictionary Conflict error has to be sent, the state machine
    will be aborted.  If this event occurs repeatedly, it is likely
    that there is either a serious software problem or a security
    issue.  The connection MUST be terminated.
 Note 3:
    Remaining requested bundles have not arrived before the timer
    expired, so we re-send the list of outstanding requests.  If the
    timeout occurs repeatedly, it is likely that communication has
    failed and the connection MUST be terminated.

Lindgren, et al. Experimental [Page 85] RFC 6693 PRoPHET August 2012

5.3.4.3. State Tables for the Listener Role

 The rules and state tables for the Listener role use the following
 operations:
 o  The "Clear Supplied RIBs" operation is defined as setting up an
    empty container to hold the set of RIBs supplied by the peer node.
 o  The "Record RIBs Supplied" operation is defined as:
    1.  Taking the RIB entries from a received RIB TLV.
    2.  Verifying that the String ID used in each entry is present in
        the dictionary.  If not, an Error TLV containing the offending
        String ID is sent to the peer, and the Initiator and Listener
        processes are aborted and restarted as if the ESTAB state had
        just been reached.
    3.  If all the String IDs are present in the dictionary, record
        the delivery predictabilities for each EID in the entries.
 o  The "Recalc Dlvy Predictabilities" operation uses the algorithms
    defined in Section 2.1.2 to update the local set of delivery
    predictabilities using the using the set of delivery
    predictabilities supplied by the peer in RIB TLVs.
 o  The "Determine Offers" operation determines the set of bundles to
    be offered to the peer.  The local delivery predictabilities and
    the delivery predictabilities supplied by the peer are compared,
    and a prioritized choice of the bundles stored in this node to be
    offered to the peer is made according to the configured queueing
    policy and forwarding strategy.
 o  The "Determine ACKs" operation is defined as obtaining the set of
    PRoPHET ACKs recorded by the bundle protocol agent that need to be
    forwarded to the peer.  The list of PRoPHET ACKs is maintained
    internally by the PRoPHET protocol implementation rather than the
    main bundle protocol agent (see Section 3.5).
 o  The "Determine Offer Dict Updates" operation is defined as
    determining any extra EIDs that are not already in the dictionary,
    recording the previous state of the local dictionary, and then
    adding the required extra entries to the dictionary.

Lindgren, et al. Experimental [Page 86] RFC 6693 PRoPHET August 2012

 o  The "Send Offers" operation is defined as formatting one or more
    non-empty Bundle Offer TLVs, incorporating the sets of Offers and
    PRoPHET ACKs previously determined, and sending them to the peer
    node.  If more than one Bundle Offer TLV is sent, all but the last
    one MUST have the "More Offer/Response TLVs Following" flag set to
    1; the last or only one MUST have the flag set to 0.
 o  The "Record Requests" operation is defined as recording all the
    bundles offered in a Bundle Offer TLV in the list of bundles
    offers.  Duplicates MUST be ignored.  The order of requests in the
    TLVs MUST be maintained so far as is possible (it is possible that
    a bundle has to be re-sent, and this may result in out-of-order
    delivery).
 o  The "Send Bundles" operation is defined as sending, in the order
    requested, the bundles in the requested list.  This requires the
    list to be communicated to the bundle protocol agent (see
    Section 2.2).
 o  The "Check Initiator Start Point" operation is defined as checking
    the configured sequential operation policy to determine if the
    Listener role has reached the point where the Initiator role
    should be started.  If so, the InitStart notification is sent to
    the Initiator role in the same node.
 The following events are specific to the Listener role state machine:
 RIBnotlast    RIB TLV received with "More RIB TLVs" flag set to 1.
 RIBlast       RIB TLV received with "More RIB TLVs" flag set to 0 and
               a non-zero count of RIB Entries.
 REQnotlast    Bundle Response TLV received with More Offer/Response
               TLVs Following flag set to 1.
 REQlast       Bundle Response TLV received with More Offer/Response
               TLVs Following flag set to 0 and a non-zero count of
               bundle offers.
 REQempty      Bundle Response TLV received with More Offer/Response
               TLVs Following flag set to 0 and a zero count of bundle
               offers.

Lindgren, et al. Experimental [Page 87] RFC 6693 PRoPHET August 2012

  State: WAIT_DICT
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |     On Entry     |     Check Initiator Start Point   | WAIT_DICT |
  +------------------+-----------------------------------+-----------+
  |       RIBDi      |     Update Dictionary (note 1)    |           |
  |                  |     If Dictionary Conflict found: |           |
  |                  |           Abort Exchange          |(finished) |
  |                  |     Else:                         |           |
  |                  |           Start TP                | WAIT_RIB  |
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |     Abort Exchange                | WAIT_DICT |
  +==================================================================+

Lindgren, et al. Experimental [Page 88] RFC 6693 PRoPHET August 2012

  State: WAIT_RIB
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |     On Entry     |   Clear Supplied RIBS             | WAIT_RIB  |
  +------------------+-----------------------------------+-----------+
  |       RIBDi      |   Update Dictionary (note 1)      |           |
  |                  |   If Dictionary Conflict found:   |           |
  |                  |         Abort Exchange            |(finished) |
  |                  |   Else:                           |           |
  |                  |         Start TP                  | WAIT_RIB  |
  +------------------+-----------------------------------+-----------+
  |    RIBnotlast    |   Record RIBS Supplied (note 2)   |           |
  |                  |   If EID missing in dictionary:   |           |
  |                  |         Abort Exchange            |(finished) |
  |                  |   Else:                           |           |
  |                  |         Start TP                  | WAIT_RIB  |
  +------------------+-----------------------------------+-----------
  |     RIBlast      |   Check Initiator Start Point     |           |
  |                  |   Record RIBS Supplied (note 2)   |           |
  |                  |   If EID missing in dictionary:   |           |
  |                  |         Abort Exchange            |(finished) |
  |                  |   Otherwise                       |           |
  |                  |         Recalc Dlvy               |           |
  |                  |               Predictabilities    |           |
  |                  |         Cancel TP                 |           |
  |                  |         Determine Offers          |           |
  |                  |         Determine ACKs            |           |
  |                  |         Determine Offer           |           |
  |                  |               Dict Updates        |           |
  |                  |         Send RIB Dictionary       |           |
  |                  |               Updates             |           |
  |                  |         Send Offers               |           |
  |                  |         Start TI                  |   OFFER   |
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |     Abort Exchange                | WAIT_DICT |
  +------------------+-----------------------------------+-----------+
  |Any Other TLV rcvd|     Abort Exchange                |(finished) |
  +------------------+-----------------------------------+-----------+
  |  Timeout(peer)   |     Send RIB Dictionary Updates   |           |
  |                  |     Send Offers                   |           |
  |                  |     Start TI (note 3)             |   OFFER   |
  +==================================================================+

Lindgren, et al. Experimental [Page 89] RFC 6693 PRoPHET August 2012

  State: OFFER
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |    REQnotlast    |      Send Bundles                 |           |
  |                  |      Start TI                     |   OFFER   |
  +------------------+-----------------------------------+-----------+
  |     REQlast      |      Cancel TI                    |           |
  |                  |      Check Initiator Start Point  |           |
  |                  |      Send Bundles                 | SND_BUNDLE|
  +------------------+-----------------------------------+-----------+
  |     REQempty     |      Cancel TI                    |           |
  |                  |      Check Initiator Start Point  | WAIT_MORE|
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |      Abort Exchange               | WAIT_DICT |
  +------------------+-----------------------------------+-----------+
  |  Timeout(info)   |      Send RIB Dictionary Updates  |           |
  |                  |      Send Offers                  |           |
  |                  |      Start TI (note 3)            |   OFFER   |
  +==================================================================+
  State: SND_BUNDLE
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  |    REQnotlast    |      Send Bundles                 |           |
  |                  |      Start TI                     | SND_BUNDLE|
  +------------------+-----------------------------------+-----------+
  |     REQlast      |      Cancel TI                    |           |
  |                  |      Send Bundles                 | SND_BUNDLE|
  +------------------+-----------------------------------+-----------+
  |     REQempty     |      Cancel TI                    |           |
  |                  |      Check Initiator Start Point  | WAIT_MORE|
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |      Abort Exchange               | WAIT_DICT |
  +------------------+-----------------------------------+-----------+
  |  Timeout(info)   |      Send RIB Dictionary Updates  |           |
  |                  |      Send Offers                  |           |
  |                  |      Start TI (note 3)            |   OFFER   |
  +==================================================================+

Lindgren, et al. Experimental [Page 90] RFC 6693 PRoPHET August 2012

  State: WAIT_MORE
  +==================================================================+
  |     Condition    |               Action              | New State |
  +==================+===================================+===========+
  | More Bundles     |         Determine Offers          |           |
  |                  |         Determine ACKs            |           |
  |                  |         Determine Offer           |           |
  |                  |               Dict Updates        |           |
  |                  |         Send RIB Dictionary       |           |
  |                  |               Updates             |           |
  |                  |         Send Offers               |           |
  |                  |         Start TI                  |   OFFER   |
  +------------------+-----------------------------------+-----------+
  |       RIBDi      |   Update Dictionary (note 1)      |           |
  |                  |   If Dictionary Conflict found:   |           |
  |                  |         Abort Exchange            |(finished) |
  |                  |   Else:                           |           |
  |                  |         Start TP                  | WAIT_RIB  |
  +------------------+-----------------------------------+-----------+
  |    REQnotlast    |      Send Bundles                 |           |
  |                  |      Start TI                     | SND_BUNDLE|
  +------------------+-----------------------------------+-----------+
  |     REQlast      |      Cancel TI                    |           |
  |                  |      Send Bundles                 | SND_BUNDLE|
  +------------------+-----------------------------------+-----------+
  |     REQempty     |      Cancel TI                    |           |
  |                  |      Check Initiator Start Point  | SND_BUNDLE|
  +------------------+-----------------------------------+-----------+
  |     HelloAck     |      Abort Exchange               | WAIT_DICT |
  +------------------+-----------------------------------+-----------+
  |  Timeout(info)   |      Send RIB Dictionary Updates  |           |
  |                  |      Send Offers                  |           |
  |                  |      Start TI (note 3)            |   OFFER   |
  +==================================================================+
 Note 1:
    Both the dictionary and the RIB TLVs may come in the same PRoPHET
    message.  In that case, the state will change to WAIT_RIB, and the
    RIB will then immediately be processed.
 Note 2:
    Send an ACK if the timer for the peering node expires.  Either the
    link has been broken, and then the link setup will restart, or it
    will trigger the Information Exchange Phase to restart.

Lindgren, et al. Experimental [Page 91] RFC 6693 PRoPHET August 2012

 Note 3:
    When the RIB is received, it is possible for the PRoPHET agent to
    update its delivery predictabilities according to Section 2.1.2.
    The delivery predictabilities and the RIB is then used together
    with the forwarding strategy in use to create a bundle offer TLV.
    This is sent to the peering node.
 Note 4:
    No more bundles are requested by the other node; transfer is
    complete.
 Note 5:
    No response to the bundle offer has been received before the timer
    expired, so we re-send the bundle offer.

5.4. Interaction with Nodes Using Version 1 of PRoPHET

 There are existing implementations of PRoPHET based on draft versions
 of this specification that use version 1 of the protocol.  There are
 a number of significant areas of difference between version 1 and
 version 2 as described in this document:
 o  In version 1, the delivery predictability update equations were
    significantly different, and in the case of the transitivity
    equation (Equation 3) could lead to degraded performance or non-
    delivery of bundles in some circumstances.
 o  In the current version , constraints were placed on the String IDs
    generated by each node to ensure that it was not possible for
    there to be a conflict if the IDs were generated concurrently and
    independently in the two nodes.
 o  In the current version, a flag has been added to the Routing
    Information Base Dictionary TLV to distinguish dictionary updates
    sent by the Initiator role and by the Listener role.
 o  In the current version, the Bundle Offer and Response TLVs have
    been significantly revised.  The version 2 TLVs have been
    allocated new TLV Type numbers, and the version 1 TLVs (types 0xA2
    and 0xA3) are now deprecated.  For each bundle specifier, the
    source EID is transmitted in addition to the creation timestamp by
    version 2 to ensure that the bundle is uniquely identified.
    Version 2 also transmits the fragment payload offset and length
    when the offered bundle is a bundle fragment.  The payload length
    can optionally be transmitted for each bundle (whether or not it
    is a fragment) to give the receiver additional information that
    can be useful when determining which bundle offers to accept.

Lindgren, et al. Experimental [Page 92] RFC 6693 PRoPHET August 2012

 o  The behavior of the system after the first Information Exchange
    Phase has been better defined.  The state machine has been altered
    to better describe how the ongoing operations work.  This has
    involved the removal of the high-level state WAIT_INFO and the
    addition of two states in the Listener role subsidiary state
    machine (SND_BUNDLE and WAIT_MORE).  The protocol on the wire has
    not been altered by this change to the description of the state
    machine.  However, the specification of the later stages of
    operation was slightly vague and might have been interpreted
    differently by various implementers.
 A node implementing version 2 of the PRoPHET protocol as defined in
 this document MAY ignore a communication opportunity with a node that
 sends a HELLO message indicating that it uses version 1, or it MAY
 partially downgrade and respond to messages as if it were a version 1
 node.  This means that the version field in all message headers MUST
 contain 1.
 It is RECOMMENDED that the version 2 node use the metric update
 equations defined in this document even when communicating with a
 version 1 node as this will partially inhibit the problems with the
 transitivity equation in version 1, and that the version 2 node
 modify any received metrics that are greater than (1 - delta) to be
 (1 - delta) to avoid becoming a "sink" for bundles that are not
 destined for this node.  Also version 1 nodes cannot be explicitly
 offered bundle fragments, and an exchange with a node supporting
 version 1 MUST use the, now deprecated, previous versions of the
 Bundle Offer and Response TLVs.
 Generally, nodes using version 1 should be upgraded if at all
 possible because of problems that have been identified.

6. Security Considerations

 Currently, PRoPHET does not specify any special security measures.
 As a routing protocol for intermittently connected networks, PRoPHET
 is a target for various attacks.  The various known possible
 vulnerabilities are discussed in this section.
 The attacks described here are not problematic if all nodes in the
 network can be trusted and are working towards a common goal.  If
 there exist such a set of nodes, but there also exist malicious
 nodes, these security problems can be solved by introducing an
 authentication mechanism when two nodes meet, for example, using a
 public key system.  Thus, only nodes that are known to be members of
 the trusted group of nodes are allowed to participate in the routing.
 This of course introduces the additional problem of key distribution,
 but that is not addressed here.

Lindgren, et al. Experimental [Page 93] RFC 6693 PRoPHET August 2012

 Where suitable, the mechanisms (such as key management and bundle
 authentication or integrity checks) and terminology specified by the
 Bundle Security Protocol [RFC6257] are to be used.

6.1. Attacks on the Operation of the Protocol

 There are a number of kinds of attacks on the operation of the
 protocol that it would be possible to stage on a PRoPHET network.
 The attacks and possible remedies are listed here.

6.1.1. Black-Hole Attack

 A malicious node sets its delivery predictabilities for all
 destinations to a value close to or exactly equal to 1 and/or
 requests all bundles from nodes it meets, and does not forward any
 bundles.  This has two effects, both causing messages to be drawn
 towards the black hole instead of to their correct destinations.
 1.  A node encountering a malicious node will try to forward all its
     bundles to the malicious node, creating the belief that the
     bundle has been very favorably forwarded.  Depending on the
     forwarding strategy and queueing policy in use, this might hamper
     future forwarding of the bundle and/or lead to premature dropping
     of the bundle.
 2.  Due to the transitivity, the delivery predictabilities reported
     by the malicious node will affect the delivery predictabilities
     of other nodes.  This will create a gradient for all destinations
     with the black hole as the "center of gravity" towards which all
     bundles traverse.  This should be particularly severe in
     connected parts of the network.

6.1.1.1. Attack Detection

 A node receiving a set of delivery predictabilities that are all at
 or close to 1 should be suspicious.  Similarly, a node that accepts
 all bundles and offers none might be considered suspicious.  However,
 these conditions are not impossible in normal operation.

6.1.1.2. Attack Prevention/Solution

 To prevent this attack, authentication between nodes that meet needs
 to be present.  Nodes can also inspect the received metrics and
 bundle acceptances/offers for suspicious patterns and terminate
 communications with nodes that appear suspicious.  The natural
 evolution of delivery predictabilities should mean that a genuine
 node would not be permanently ostracized even if the values lead to

Lindgren, et al. Experimental [Page 94] RFC 6693 PRoPHET August 2012

 termination of a communication opportunity on one occasion.  The
 epidemic nature of PRoPHET would mean that such a termination rarely
 leads to non-delivery of bundles.

6.1.2. Limited Black-Hole Attack / Identity Spoofing

 A malicious node misrepresents itself by claiming to be someone else.
 The effects of this attack are:
 1.  The effects of the black-hole attack listed above hold for this
     attack as well, with the exception that only the delivery
     predictabilities and bundles for one particular destination are
     affected.  This could be used to "steal" the data that should be
     going to a particular node.
 2.  In addition to the above problems, PRoPHET ACKs will be issued
     for the bundles that are delivered to the malicious node.  This
     will cause these bundles to be removed from the network, reducing
     the chance that they will reach their real destination.

6.1.2.1. Attack Detection

 The destination can detect that this kind of attack has occurred (but
 it cannot prevent the attack) when it receives a PRoPHET ACK for a
 bundle destined to itself but for which it did not receive the
 corresponding bundle.

6.1.2.2. Attack Prevention/Solution

 To prevent this attack, authentication between nodes that meet needs
 to be present.

6.1.3. Fake PRoPHET ACKs

 A malicious node may issue fake PRoPHET ACKs for all bundles (or only
 bundles for a certain destination if the attack is targeted at a
 single node) carried by nodes it met.  The affected bundles will be
 deleted from the network, greatly reducing their probability of being
 delivered to the destination.

6.1.3.1. Attack Prevention/Solution

 If a public key cryptography system is in place, this attack can be
 prevented by mandating that all PRoPHET ACKs be signed by the
 destination.  Similarly to other solutions using public key
 cryptography, this introduces the problem of key distribution.

Lindgren, et al. Experimental [Page 95] RFC 6693 PRoPHET August 2012

6.1.4. Bundle Store Overflow

 After encountering and receiving the delivery predictability
 information from the victim, a malicious node may generate a large
 number of fake bundles for the destination for which the victim has
 the highest delivery predictability.  This will cause the victim to
 most likely accept these bundles, filling up its bundle storage,
 possibly at the expense of other, legitimate, bundles.  This problem
 is transient as the messages will be removed when the victim meets
 the destination and delivers the messages.

6.1.4.1. Attack Detection

 If it is possible for the destination to figure out that the bundles
 it is receiving are fake, it could report that malicious actions are
 underway.

6.1.4.2. Attack Prevention/Solution

 This attack could be prevented by requiring sending nodes to sign all
 bundles they send.  By doing this, intermediate nodes could verify
 the integrity of the messages before accepting them for forwarding.

6.1.5. Bundle Store Overflow with Delivery Predictability Manipulation

 A more sophisticated version of the attack in the previous section
 can be attempted.  The effect of the previous attack was lessened
 since the destination node of the fake bundles existed.  This caused
 fake bundles to be purged from the network when the destination was
 encountered.  The malicious node may now use the transitive property
 of the protocol to boost the victim's delivery predictabilities for a
 non-existent destination.  After this, it creates a large number of
 fake bundles for this non-existent destination and offers them to the
 victim.  As before, these bundles will fill up the bundle storage of
 the victim.  The impact of this attack will be greater as there is no
 probability of the destination being encountered and the bundles
 being acknowledged.  Thus, they will remain in the bundle storage
 until they time out (the malicious node may set the timeout to a
 large value) or until they are evicted by the queueing policy.
 The delivery predictability for the fake destination may spread in
 the network due to the transitivity, but this is not a problem, as it
 will eventually age and fade away.
 The impact of this attack could be increased if multiple malicious
 nodes collude, as network resources can be consumed at a greater
 speed and at many different places in the network simultaneously.

Lindgren, et al. Experimental [Page 96] RFC 6693 PRoPHET August 2012

6.2. Interactions with External Routing Domains

 Users may opt to connect two regions of sparsely connected nodes
 through a connected network such as the Internet where another
 routing protocol is running.  To this network, PRoPHET traffic would
 look like any other application-layer data.  Extra care must be taken
 in setting up these gateway nodes and their interconnections to make
 sure that malicious nodes cannot use them to launch attacks on the
 infrastructure of the connected network.  In particular, the traffic
 generated should not be significantly more than what a single regular
 user end host could create on the network.

7. IANA Considerations

 Following the policies outlined in "Guidelines for Writing an IANA
 Considerations Section in RFCs" (RFC 5226 [RFC5226]), the following
 name spaces are defined in PRoPHET.
 o  For fields in the PRoPHET message header (Section 4.1):
  • DTN Routing Protocol Number
  • PRoPHET Protocol Version
  • PRoPHET Header Flags
  • PRoPHET Result Field
  • PRoPHET Codes for Success and Codes for Failure
 o  Identifiers for TLVs carried in PRoPHET messages:
  • PRoPHET TLV Type (Section 4.2)
 o  Definitions of TLV Flags and other flag fields in TLVs:
  • Hello TLV Flags (Section 4.3.1)
  • Error TLV Flags (Section 4.3.2)
  • Routing Information Base (RIB) Dictionary TLV Flags

(Section 4.3.3)

  • Routing Information Base (RIB) TLV Flags (Section 4.3.4)
  • Routing Information Base (RIB) Flags per entry (Section 4.3.4)
  • Bundle Offer and Response TLV Flags (Section 4.3.5)

Lindgren, et al. Experimental [Page 97] RFC 6693 PRoPHET August 2012

  • Bundle Offer and Response B Flags per offer or response

(Section 4.3.5)

 The following subsections list the registries that have been created.
 Initial values for the registries are given below; future assignments
 for unassigned values are to be made through the Specification
 Required policy.  Where specific values are defined in the IANA
 registries according to the specifications in the subsections below,
 the registry refers to this document as defining the allocation.

7.1. DTN Routing Protocol Number

 The encoding of the Protocol Number field in the PRoPHET header
 (Section 4.1) is:
       +--------------------------+-----------+---------------+
       |         Protocol         |   Value   |   Reference   |
       +--------------------------+-----------+---------------+
       |     PRoPHET Protocol     |    0x00   | This document |
       |        Unassigned        | 0x01-0xEF |               |
       | Private/Experimental Use | 0xF0-0xFF | This document |
       +--------------------------+-----------+---------------+

7.2. PRoPHET Protocol Version

 The encoding of the PRoPHET Version field in the PRoPHET header
 (Section 4.1) is:
      +----------------------------+-----------+---------------+
      |           Version          |   Value   |   Reference   |
      +----------------------------+-----------+---------------+
      | Reserved (do not allocate) |    0x00   | This document |
      |         PRoPHET v1         |    0x01   | This document |
      |         PRoPHET v2         |    0x02   | This document |
      |         Unassigned         | 0x03-0xEF |               |
      |  Private/Experimental Use  | 0xF0-0xFE | This document |
      |          Reserved          |    0xFF   |               |
      +----------------------------+-----------+---------------+

Lindgren, et al. Experimental [Page 98] RFC 6693 PRoPHET August 2012

7.3. PRoPHET Header Flags

 The following Flags are defined for the PRoPHET Header (Section 4.1):
               +------------+--------------+-----------+
               |   Meaning  | Bit Position | Reference |
               +------------+--------------+-----------+
               | Unassigned |     Bit 0    |           |
               | Unassigned |     Bit 1    |           |
               | Unassigned |     Bit 2    |           |
               | Unassigned |     Bit 3    |           |
               +------------+--------------+-----------+

7.4. PRoPHET Result Field

 The encoding of the Result field in the PRoPHET header (Section 4.1)
 is:
      +--------------------------+-------------+---------------+
      |       Result Value       |    Value    |   Reference   |
      +--------------------------+-------------+---------------+
      |         Reserved         |     0x00    | This document |
      |       NoSuccessAck       |     0x01    | This document |
      |          AckAll          |     0x02    | This document |
      |          Success         |     0x03    | This document |
      |          Failure         |     0x04    | This document |
      |       ReturnReceipt      |     0x05    | This document |
      |        Unassigned        | 0x06 - 0x7F |               |
      | Private/Experimental Use | 0x80 - 0xFF | This document |
      +--------------------------+-------------+---------------+

7.5. PRoPHET Codes for Success and Codes for Failure

 The encoding for Code field in the PRoPHET header (Section 4.1) for
 "Success" messages is:
      +--------------------------+-------------+---------------+
      |         Code Name        |    Values   |   Reference   |
      +--------------------------+-------------+---------------+
      |      Generic Success     |     0x00    | This document |
      |    Submessage Received   |     0x01    | This document |
      |        Unassigned        | 0x02 - 0x7F |               |
      | Private/Experimental Use | 0x80 - 0xFF | This document |
      +--------------------------+-------------+---------------+

Lindgren, et al. Experimental [Page 99] RFC 6693 PRoPHET August 2012

 The encoding for Code in the PRoPHET header (Section 4.1) for
 "Failure" messages is:
     +----------------------------+-------------+---------------+
     |          Code Name         |    Values   |   Reference   |
     +----------------------------+-------------+---------------+
     | Reserved (do not allocate) | 0x00 - 0x01 | This document |
     |     Unspecified Failure    |     0x02    | This document |
     |         Unassigned         | 0x03 - 0x7F |               |
     |  Private/Experimental Use  | 0x80 - 0xFE | This document |
     |    Error TLV in Message    |     0xFF    | This document |
     +----------------------------+-------------+---------------+

7.6. PRoPHET TLV Type

 The TLV Types defined for PRoPHET (Section 4.2) are:
    +------------------------------+-------------+---------------+
    |             Type             |    Value    |   Reference   |
    +------------------------------+-------------+---------------+
    |  Reserved (do not allocate)  |     0x00    | This document |
    |           Hello TLV          |     0x01    | This document |
    |           Error TLV          |     0x02    | This document |
    |          Unsassigned         | 0x03 - 0x9F |               |
    |      RIB dictionary TLV      |     0xA0    | This document |
    |            RIB TLV           |     0xA1    | This document |
    |   Bundle Offer (deprecated)  |     0xA2    | This document |
    | Bundle Response (deprecated) |     0xA3    | This document |
    |       Bundle Offer (v2)      |     0xA4    | This document |
    |     Bundle Response (v2)     |     0xA5    | This document |
    |          Unassigned          | 0xA6 - 0xCF |               |
    |   Private/Experimental Use   | 0xD0 - 0xFF | This document |
    +------------------------------+-------------+---------------+

Lindgren, et al. Experimental [Page 100] RFC 6693 PRoPHET August 2012

7.7. Hello TLV Flags

 The following TLV Flags are defined for the Hello TLV
 (Section 4.3.1).  Flag numbers 0, 1, and 2 are treated as a 3-bit
 unsigned integer with 5 of the 8 possible values allocated, and the
 other 3 reserved.  The remaining bits are treated individually:
 +----------------------------+---------------------+---------------+
 |           Meaning          |        Value        |   Reference   |
 +----------------------------+---------------------+---------------+
 |                            | (Flags 0, 1, and 2) |               |
 | Reserved (do not allocate) |        0b000        | This document |
 |             SYN            |        0b001        | This document |
 |           SYNACK           |        0b010        | This document |
 |             ACK            |        0b011        | This document |
 |           RSTACK           |        0b100        | This document |
 |         Unassigned         |    0b101 - 0b111    |               |
 |                            |    (Flags 3 - 7)    |               |
 |         Unassigned         |        Flag 3       |               |
 |         Unassigned         |        Flag 4       |               |
 |         Unassigned         |        Flag 5       |               |
 |         Unassigned         |        Flag 6       |               |
 |           L Flag           |        Flag 7       | This document |
 +----------------------------+---------------------+---------------+

7.8. Error TLV Flags

 The TLV Flags field in the Error TLV (Section 4.3.2) is treated as an
 unsigned 8-bit integer encoding the Error TLV number.  The following
 values are defined:
    +--------------------------+------------------+---------------+
    |      Error TLV Name      | Error TLV Number |   Reference   |
    +--------------------------+------------------+---------------+
    |    Dictionary Conflict   |       0x00       | This document |
    |       Bad String ID      |       0x01       | This document |
    |        Unassigned        |    0x02 - 0x7F   |               |
    | Private/Experimental Use |    0x80 - 0xFF   | This document |
    +--------------------------+------------------+---------------+

Lindgren, et al. Experimental [Page 101] RFC 6693 PRoPHET August 2012

7.9. RIB Dictionary TLV Flags

 The following TLV Flags are defined for the RIB Base Dictionary TLV
 (Section 4.3.3):
     +----------------------------+--------------+---------------+
     |           Meaning          | Bit Position |   Reference   |
     +----------------------------+--------------+---------------+
     |      Sent by Listener      |    Flag 0    | This document |
     | Reserved (do not allocate) |    Flag 1    | This document |
     | Reserved (do not allocate) |    Flag 2    | This document |
     |         Unassigned         |    Flag 3    |               |
     |         Unassigned         |    Flag 4    |               |
     |         Unassigned         |    Flag 5    |               |
     |         Unassigned         |    Flag 6    |               |
     |         Unassigned         |    Flag 7    |               |
     +----------------------------+--------------+---------------+

7.10. RIB TLV Flags

 The following TLV Flags are defined for the RIB TLV (Section 4.3.4):
     +----------------------------+--------------+---------------+
     |           Meaning          | Bit Position |   Reference   |
     +----------------------------+--------------+---------------+
     |        More RIB TLVs       |    Flag 0    | This document |
     | Reserved (do not allocate) |    Flag 1    | This document |
     | Reserved (do not allocate) |    Flag 2    | This document |
     |         Unassigned         |    Flag 3    |               |
     |         Unassigned         |    Flag 4    |               |
     |         Unassigned         |    Flag 5    |               |
     |         Unassigned         |    Flag 6    |               |
     |         Unassigned         |    Flag 7    |               |
     +----------------------------+--------------+---------------+

Lindgren, et al. Experimental [Page 102] RFC 6693 PRoPHET August 2012

7.11. RIB Flags

 The following RIB Flags are defined for the individual entries in the
 RIB TLV (Section 4.3.4):
               +------------+--------------+-----------+
               |   Meaning  | Bit Position | Reference |
               +------------+--------------+-----------+
               | Unassigned |    Flag 0    |           |
               | Unassigned |    Flag 1    |           |
               | Unassigned |    Flag 2    |           |
               | Unassigned |    Flag 3    |           |
               | Unassigned |    Flag 4    |           |
               | Unassigned |    Flag 5    |           |
               | Unassigned |    Flag 6    |           |
               | Unassigned |    Flag 7    |           |
               +------------+--------------+-----------+

7.12. Bundle Offer and Response TLV Flags

 The following TLV Flags are defined for the Bundle Offer and Response
 TLV (Section 4.3.5):
 +------------------------------------+--------------+---------------+
 |               Meaning              | Bit Position |   Reference   |
 +------------------------------------+--------------+---------------+
 | More Offer/Response TLVs Following |    Flag 0    | This document |
 |             Unassigned             |    Flag 1    |               |
 |             Unassigned             |    Flag 2    |               |
 |             Unassigned             |    Flag 3    |               |
 |             Unassigned             |    Flag 4    |               |
 |             Unassigned             |    Flag 5    |               |
 |             Unassigned             |    Flag 6    |               |
 |             Unassigned             |    Flag 7    |               |
 +------------------------------------+--------------+---------------+

Lindgren, et al. Experimental [Page 103] RFC 6693 PRoPHET August 2012

7.13. Bundle Offer and Response B Flags

 The following B Flags are defined for each Bundle Offer in the Bundle
 Offer and Response TLV (Section 4.3.5):
 +------------------------------------+--------------+---------------+
 |               Meaning              | Bit Position |   Reference   |
 +------------------------------------+--------------+---------------+
 |           Bundle Accepted          |    Flag 0    | This document |
 |        Bundle is a Fragment        |    Flag 1    | This document |
 |  Bundle Payload Length Included in |    Flag 2    | This document |
 |                 TLV                |              |               |
 |             Unassigned             |    Flag 3    |               |
 |             Unassigned             |    Flag 4    |               |
 |             Unassigned             |    Flag 5    |               |
 |             Unassigned             |    Flag 6    |               |
 |             PRoPHET ACK            |    Flag 7    | This document |
 +------------------------------------+--------------+---------------+

8. Implementation Experience

 Multiple independent implementations of the PRoPHET protocol exist.
 The first implementation is written in Java, and has been optimized
 to run on the Lego MindStorms platform that has very limited
 resources.  Due to the resource constraints, some parts of the
 protocol have been simplified or omitted, but the implementation
 contains all the important mechanisms to ensure proper protocol
 operation.  The implementation is also highly modular and can be run
 on another system with only minor modifications (it has currently
 been shown to run on the Lego MindStorms platform and on regular
 laptops).
 Another implementation is written in C++ and runs in the OmNet++
 simulator to enable testing and evaluation of the protocol and new
 features.  Experience and feedback from the implementers on early
 versions of the protocol have been incorporated into the current
 version.
 An implementation compliant to an Internet-Draft (which was posted in
 2006 and eventually evolved into this RFC) has been written at Baylor
 University.  This implementation has been integrated into the DTN2
 reference implementation.
 An implementation of the protocol in C++ was developed by one of the
 authors (Samo Grasic) at Lulea University of Technology (LTU) as part
 of the Saami Networking Connectivity project (see Section 9) and
 continues to track the development of the protocol.  This work is now

Lindgren, et al. Experimental [Page 104] RFC 6693 PRoPHET August 2012

 part of the Networking for Communications Challenged Communities
 (N4C) project and is used in N4C testbeds.

9. Deployment Experience

 During a week in August 2006, a proof-of-concept deployment of a DTN
 system, using the LTU PRoPHET implementation for routing was made in
 the Swedish mountains -- the target area for the Saami Network
 Connectivity project [ccnc07] [doria_02].  Four fixed camps with
 application gateways, one Internet gateway, and seven mobile relays
 were deployed.  The deployment showed PRoPHET to be able to route
 bundles generated by different applications such as email and web
 caching.
 Within the realms of the SNC and N4C projects, multiple other
 deployments, both during summer and winter conditions, have been done
 at various scales during 2007-2010 [winsdr08].
 An implementation has been made for Android-based mobile telephones
 in the Bytewalla project [bytewalla].

10. Acknowledgements

 The authors would like to thank Olov Schelen and Kaustubh S. Phanse
 for contributing valuable feedback regarding various aspects of the
 protocol.  We would also like to thank all other reviewers and the
 DTNRG chairs for the feedback in the process of developing the
 protocol.  The Hello TLV mechanism is loosely based on the Adjacency
 message developed for RFC 3292.  Luka Birsa and Jeff Wilson have
 provided us with feedback from doing implementations of the protocol
 based on various preliminary versions of the document.  Their
 feedback has helped us make the document easier to read for an
 implementer and has improved the protocol.

11. References

11.1. Normative References

 [RFC2119]      Bradner, S., "Key words for use in RFCs to Indicate
                Requirement Levels", BCP 14, RFC 2119, March 1997.
 [RFC5050]      Scott, K. and S. Burleigh, "Bundle Protocol
                Specification", RFC 5050, November 2007.

Lindgren, et al. Experimental [Page 105] RFC 6693 PRoPHET August 2012

11.2. Informative References

 [CLAYER]       Demmer, M., Ott, J., and S. Perreault, "Delay Tolerant
                Networking TCP Convergence Layer Protocol", Work
                in Progress, August 2012.
 [RFC1058]      Hedrick, C., "Routing Information Protocol", RFC 1058,
                June 1988.
 [RFC4838]      Cerf, V., Burleigh, S., Hooke, A., Torgerson, L.,
                Durst, R., Scott, K., Fall, K., and H. Weiss, "Delay-
                Tolerant Networking Architecture", RFC 4838,
                April 2007.
 [RFC5226]      Narten, T. and H. Alvestrand, "Guidelines for Writing
                an IANA Considerations Section in RFCs", BCP 26,
                RFC 5226, May 2008.
 [RFC6257]      Symington, S., Farrell, S., Weiss, H., and P. Lovell,
                "Bundle Security Protocol Specification", RFC 6257,
                May 2011.
 [bytewalla]    Prasad, M., "Bytewalla 3: Network architecture and
                PRoPHET implementation", Bytewalla Project, KTH Royal
                Institute of Technology, Stockholm, Sweden, October
                 2010,
                <http://www.bytewalla.org/sites/bytewalla.org/files/
                Bytewalla3_Network_architecture_and_PRoPHET_v1.0.pdf>.
 [ccnc07]       Lindgren, A. and A. Doria, "Experiences from Deploying
                a Real-life DTN System", Proceedings of the 4th Annual
                IEEE Consumer Communications and Networking Conference
                (CCNC 2007), Las Vegas, Nevada, USA, January 2007.
 [doria_02]     Doria, A., Uden, M., and D. Pandey, "Providing
                connectivity to the Saami nomadic community",
                Proceedings of the 2nd International Conference on
                Open Collaborative Design for Sustainable Innovation
                (dyd 02), Bangalore, India, December 2002.
 [lindgren_06]  Lindgren, A. and K. Phanse, "Evaluation of Queueing
                Policies and Forwarding Strategies for Routing in
                Intermittently Connected Networks", Proceedings of
                COMSWARE 2006, January 2006.
 [vahdat_00]    Vahdat, A. and D. Becker, "Epidemic Routing for
                Partially Connected Ad Hoc Networks", Duke University
                Technical Report CS-200006, April 2000.

Lindgren, et al. Experimental [Page 106] RFC 6693 PRoPHET August 2012

 [winsdr08]     Lindgren, A., Doria, A., Lindblom, J., and M. Ek,
                "Networking in the Land of Northern Lights - Two Years
                of Experiences from DTN System Deployments",
                Proceedings of the ACM Wireless Networks and Systems
                for Developing Regions Workshop (WiNS-DR), San
                Francisco, California, USA, September 2008.

Lindgren, et al. Experimental [Page 107] RFC 6693 PRoPHET August 2012

Appendix A. PRoPHET Example

 To help grasp the concepts of PRoPHET, an example is provided to give
 an understanding of the transitive property of the delivery
 predictability and the basic operation of PRoPHET.  In Figure 13, we
 revisit the scenario where node A has a message it wants to send to
 node D.  In the bottom right corner of subfigures a-c, the delivery
 predictability tables for the nodes are shown.  Assume that nodes C
 and D encounter each other frequently (Figure 13a), making the
 delivery predictability values they have for each other high.  Now
 assume that node C also frequently encounters node B (Figure 13b).
 Nodes B and C will get high delivery predictability values for each
 other, and the transitive property will also increase the value B has
 for D to a medium level.  Finally, node B meets node A (Figure 13c),
 which has a message for node D.  Figure 13d shows the message
 exchange between node A and node B.  Summary vectors and delivery
 predictability information is exchanged, delivery predictabilities
 are updated, and node A then realizes that P_(b,d) > P_(a,d), and
 thus forwards the message for node D to node B.

Lindgren, et al. Experimental [Page 108] RFC 6693 PRoPHET August 2012

 +----------------------------+   +----------------------------+
 |                            |   |                            |
 |                  C         |   |                       D    |
 |                   D        |   |                            |
 |       B                    |   |       B C                  |
 |                            |   |                            |
 |                            |   |                            |
 |                            |   |                            |
 |                            |   |                            |
 | A*                         |   | A*                         |
 +-------------+--------------+   +-------------+--------------+
 |   A  |   B  |   C   |  D   |   |   A  |   B  |   C   |  D   |
 |B:low |A:low |A:low  |A:low |   |B:low |A:low |A:low  |A:low |
 |C:low |C:low |B:low  |B:low |   |C:low |C:high|B:high |B:low |
 |D:low |D:low |D:high |C:high|   |D:low |D:med |D:high |C:high|
 +-------------+--------------+   +-------------+--------------+
              (a)                              (b)
 +----------------------------+   A                            B
 |                            |   |                            |
 |                       D    |   |Summary vector&delivery pred|
 |                            |   |--------------------------->|
 |         C                  |   |Summary vector&delivery pred|
 |                            |   |<---------------------------|
 |                            |   |                            |
 |   B*                       |  Update delivery predictabilities
 |  A                         |   |                            |
 |                            |  Packet for D not in SV        |
 +-------------+--------------+  P(b,d)>P(a,d)                 |
 |   A  |   B  |   C   |  D   |  Thus, send                    |
 |B:low |A:low |A:low  |A:low |   |                            |
 |C:med |C:high|B:high |B:low |   |      Packet for D          |
 |D:low+|D:med |D:high |C:high|   |--------------------------->|
 +-------------+--------------+   |                            |
              (c)                              (d)
                      Figure 13: PRoPHET example

Lindgren, et al. Experimental [Page 109] RFC 6693 PRoPHET August 2012

Appendix B. Neighbor Discovery Example

 This section outlines an example of a simple neighbor discovery
 protocol that can be run in-between PRoPHET and the underlying layer
 in case lower layers do not provide methods for neighbor discovery.
 It assumes that the underlying layer supports broadcast messages as
 would be the case if a wireless infrastructure was involved.
 Each node needs to maintain a list of its active neighbors.  The
 operation of the protocol is as follows:
 1.  Every BEACON_INTERVAL milliseconds, the node does a local
     broadcast of a beacon that contains its identity and address, as
     well as the BEACON_INTERVAL value used by the node.
 2.  Upon reception of a beacon, the following can happen:
     A.  The sending node is already in the list of active neighbors.
         Update its entry in the list with the current time, and
         update the node's BEACON_INTERVAL if it has changed.
     B.  The sending node is not in the list of active neighbors.  Add
         the node to the list of active neighbors and record the
         current time and the node's BEACON_INTERVAL.  Notify the
         PRoPHET agent that a new neighbor is available ("New
         Neighbor", as described in Section 2.4).
 3.  If a beacon has not been received from a node in the list of
     active neighbors within a time period of NUM_ACCEPTED_LOSSES *
     BEACON_INTERVAL (for the BEACON_INTERVAL used by that node), it
     should be assumed that this node is no longer a neighbor.  The
     entry for this node should be removed from the list of active
     neighbors, and the PRoPHET agent should be notified that a
     neighbor has left ("Neighbor Gone", as described in Section 2.4).

Appendix C. PRoPHET Parameter Calculation Example

 The evolution of the delivery predictabilities in a PRoPHET node is
 controlled by three main equations defined in Section 2.1.2.  These
 equations use a number of parameters that need to be appropriately
 configured to ensure that the delivery predictabilities evolve in a
 way that mirrors the mobility model that applies in the PRoPHET zone
 where the node is operating.
 When trying to describe the mobility model, it is more likely that
 the model will be couched in terms of statistical distribution of
 times between encounters and times to deliver a bundle in the zone.
 In this section, one possible way of deriving the PRoPHET parameters

Lindgren, et al. Experimental [Page 110] RFC 6693 PRoPHET August 2012

 from a more usual description of the model is presented.  It should
 be remembered that this may not be the only solution, and its
 appropriateness will depend both on the overall mobility model and
 the distribution of the times involved.  There is an implicit
 assumption in this work that these distributions can be characterized
 by a normal-type distribution with a well-defined first moment
 (mean).  The exact form of the distribution is not considered here,
 but more detailed models may wish to use more specific knowledge
 about the distributions to refine the derivation of the parameters.
 To characterize the model, we consider the following parameters:
 P1  The time resolution of the model.
 P2  The average time between encounters between nodes, I_typ, where
     the identity of the nodes is not taken into account.
 P3  The average number of encounters that a node has between meeting
     a particular node and meeting the same node again.
 P4  The average number of encounters needed to deliver a bundle in
     this zone.
 P5  The multiple of the average number of encounters needed to
     deliver a bundle (P4) after which it can be assumed that a node
     is not going to encounter a particular node again in the
     foreseeable future so that the delivery predictability ought to
     be decayed below P_first_threshold.
 P6  The number of encounters between a particular pair of nodes that
     should result in the delivery predictability of the encountered
     node getting close to the maximum possible delivery
     predictability (1 - delta).
 We can use these parameters to derive appropriate values for gamma
 and P_encounter_max, which are the key parameters in the evolution of
 the delivery predictabilities.  The values of the other parameters
 P_encounter_first (0.5), P_first_threshold (0.1), and delta (0.01),
 with the default values suggested in Figure 3, generally are not
 specific to the mobility model, although in special cases
 P_encounter_first may be different if extra information is available.
 To select a value for gamma:
 After a single, unrepeated encounter, the delivery predictability of
 the encountered node should decay from P_encounter_first to
 P_first_threshold in the expected time for P4 * P5 encounters.  Thus:

Lindgren, et al. Experimental [Page 111] RFC 6693 PRoPHET August 2012

 P_first_threshold = P_encounter_first * gamma ^ ((P2 * P4 * P5)/P1)
 which can be rearranged as
 gamma =
 exp(ln(P_first_threshold/P_encounter_first) * P1 / (P2* P4 * P5)).
 Typical values of gamma will be less than 1, but very close to 1
 (usually greater than 0.99).  The value has to be stored to several
 decimal places of accuracy, but implementations can create a table of
 values for specific intervals to reduce the amount of on-the-fly
 calculation required.
 Selecting a value for P_encounter_max:
 Once gamma has been determined, the decay factor for the average time
 between encounters between a specific pair of nodes can be
 calculated:
 Decay_typ = gamma ^ ((P2 * P3)/P1)
 Starting with P_encounter_first, using Decay_typ and applying
 Equation 1 from Section 2.1.2 (P6 - 1) times, we can calculate the
 typical delivery predictability for the encountered node after P6
 encounters.  The nature of Equation 1 is such that it is not easy to
 produce a closed form that generates a value of P_encounter_max from
 the parameter values, but using a spreadsheet to apply the equation
 repeatedly and tabulate the results will allow a suitable value of
 P_encounter_max to be chosen very simply.  The evolution is not very
 sensitive to the value of P_encounter_max, and values in the range
 0.4 to 0.8 will generally be appropriate.  A value of 0.7 is
 recommended as a default.
 Once a PRoPHET zone has been in operation for some time, the logs of
 the actual encounters can and should be used to check that the
 selected parameters were appropriate and to tune them as necessary.
 In the longer term, it may prove possible to install a learning mode
 in nodes so that the parameters can be adjusted dynamically to
 maintain best congruence with the mobility model that may itself
 change over time.

Lindgren, et al. Experimental [Page 112] RFC 6693 PRoPHET August 2012

Authors' Addresses

 Anders F. Lindgren
 Swedish Institute of Computer Science
 Box 1263
 Kista  SE-164 29
 SE
 Phone: +46707177269
 EMail: andersl@sics.se
 URI:   http://www.sics.se/~andersl
 Avri Doria
 Technicalities
 Providence  RI
 US
 EMail: avri@acm.org
 URI:   http://psg.com/~avri
 Elwyn Davies
 Folly Consulting
 Soham
 UK
 EMail: elwynd@folly.org.uk
 Samo Grasic
 Lulea University of Technology
 Lulea  SE-971 87
 SE
 EMail: samo.grasic@ltu.se

Lindgren, et al. Experimental [Page 113]

/data/webs/external/dokuwiki/data/pages/rfc/rfc6693.txt · Last modified: 2012/08/31 23:13 by 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki