tech-invite   World Map     

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

RFC 6693

 
 
 

Probabilistic Routing Protocol for Intermittently Connected Networks

Part 2 of 4, p. 22 to 55
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 22 
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

Top      Up      ToC       Page 23 
   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

Top      Up      ToC       Page 24 
   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

Top      Up      ToC       Page 25 
   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

Top      Up      ToC       Page 26 
   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:

Top      Up      ToC       Page 27 
   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.

Top      Up      ToC       Page 28 
   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

Top      Up      ToC       Page 29 
        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

Top      Up      ToC       Page 30 
        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.

Top      Up      ToC       Page 31 
   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,

Top      Up      ToC       Page 32 
   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

Top      Up      ToC       Page 33 
   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.

Top      Up      ToC       Page 34 
   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.

Top      Up      ToC       Page 35 
   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+.

Top      Up      ToC       Page 36 
   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.

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

Top      Up      ToC       Page 38 
   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.

Top      Up      ToC       Page 39 
       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.

Top      Up      ToC       Page 40 
        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.

Top      Up      ToC       Page 41 
        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.

Top      Up      ToC       Page 42 
        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.

Top      Up      ToC       Page 43 
   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:

Top      Up      ToC       Page 44 
   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.

Top      Up      ToC       Page 45 
   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:

Top      Up      ToC       Page 46 
        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.

Top      Up      ToC       Page 47 
        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.

Top      Up      ToC       Page 48 
        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

Top      Up      ToC       Page 49 
   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.

Top      Up      ToC       Page 50 
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.

Top      Up      ToC       Page 51 
   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

Top      Up      ToC       Page 52 
   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.

Top      Up      ToC       Page 53 
       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

Top      Up      ToC       Page 54 
   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.

Top      Up      ToC       Page 55 
        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.



(page 55 continued on part 3)

Next RFC Part