RFC 6693
Probabilistic Routing Protocol for Intermittently Connected Networks
Pages: 113
Experimental
Experimental
Part 2 of 4 – Pages 22 to 55
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
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
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
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
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:
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.
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
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
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.
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,
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 settings3.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
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.
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.
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+.
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.
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).
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.
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 Format4.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.
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.
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.
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.
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:
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.
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:
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.
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.
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
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.
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.
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
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.
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
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.
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)