DTN Research Group A. Lindgren
Internet-Draft SICS
Intended status: Experimental A. Doria
Expires: April 26, 2011 Lulea University of Technology
E. Davies
Folly Consulting
S. Grasic
Lulea University of Technology
October 23, 2010
Probabilistic Routing Protocol for Intermittently Connected Networks
draft-irtf-dtnrg-prophet-08
Abstract
This document is a product of the Delay Tolerant Networking Research
Group and has been reviewed by that group. No objections to its
publication as an RFC were raised.
This document defines PRoPHET, a Probabilistic Routing Protocol using
History of Encounters and Transitivity. PRoPHET is a variant of the
epidemic routing protocol for intermittently connected networks that
operates by pruning the epidemic distribution tree to minimize
resource usage while still attempting to achieve the best case
routing capabilities of epidemic routing. It is intended for use in
sparse mesh networks where there is no guarantee that a fully
connected path between source and destination exists at any time,
rendering traditional routing protocols unable to deliver messages
between hosts. These networks are examples of networks where there
is a disparity between the latency requirements of applications and
the capabilities of the underlying network (networks often referred
to as Delay and Disruption Tolerant). The document presents an
architectural overview followed by the protocol specification.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
Lindgren, et al. Expires April 26, 2011 [Page 1]
Internet-Draft PRoPHET October 2010
material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 26, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Lindgren, et al. Expires April 26, 2011 [Page 2]
Internet-Draft PRoPHET October 2010
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1. Relation to the Delay Tolerant Networking architecture . . 7
1.2. Applicability of the protocol . . . . . . . . . . . . . . 8
1.3. PRoPHET as Compared to Regular Routing Protocols . . . . . 9
1.4. Requirements notation . . . . . . . . . . . . . . . . . . 10
2. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1. PRoPHET . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1. Delivery Predictability Calculation . . . . . . . . . 11
2.1.2. Optional Delivery Predictability Optimizations . . . . 14
2.1.3. Forwarding Strategies and Queueing Policies . . . . . 15
2.2. Bundle Agent to Routing Agent Interface . . . . . . . . . 16
2.3. PRoPHET Zone Gateways . . . . . . . . . . . . . . . . . . 17
2.4. Lower Layer Requirements and Interface . . . . . . . . . . 18
3. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . 19
3.1. Neighbor Awareness . . . . . . . . . . . . . . . . . . . . 19
3.2. Information Exchange Phase . . . . . . . . . . . . . . . . 19
3.2.1. Routing Information Base Dictionary . . . . . . . . . 20
3.3. Routing Algorithm . . . . . . . . . . . . . . . . . . . . 20
3.4. Bundle Passing . . . . . . . . . . . . . . . . . . . . . . 23
3.4.1. Custody . . . . . . . . . . . . . . . . . . . . . . . 23
3.5. When a Bundle Reaches its Destination . . . . . . . . . . 23
3.6. Forwarding Strategies . . . . . . . . . . . . . . . . . . 24
3.7. Queueing Policies . . . . . . . . . . . . . . . . . . . . 26
4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . 29
4.1. Header . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2. TLV Structure . . . . . . . . . . . . . . . . . . . . . . 34
4.3. TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3.1. Hello TLV . . . . . . . . . . . . . . . . . . . . . . 34
4.3.2. Error TLV . . . . . . . . . . . . . . . . . . . . . . 36
4.3.3. Routing Information Base Dictionary TLV . . . . . . . 37
4.3.4. Routing Information Base TLV . . . . . . . . . . . . . 38
4.3.5. Bundle Offer and Response TLV . . . . . . . . . . . . 39
5. Detailed Operation . . . . . . . . . . . . . . . . . . . . . . 42
5.1. High Level State Tables . . . . . . . . . . . . . . . . . 42
5.2. Hello Procedure . . . . . . . . . . . . . . . . . . . . . 44
5.2.1. State Tables . . . . . . . . . . . . . . . . . . . . . 46
5.2.2. Interaction with Nodes Using Version 1 of PRoPHET . . 48
5.3. Information Exchange and Bundle Passing Phase . . . . . . 49
5.3.1. State Tables . . . . . . . . . . . . . . . . . . . . . 49
6. Security Considerations . . . . . . . . . . . . . . . . . . . 54
6.1. Attacks on the Operation of the Protocol . . . . . . . . . 54
6.1.1. Black Hole Attack . . . . . . . . . . . . . . . . . . 54
6.1.2. Limited Black Hole Attack/Identity Spoofing . . . . . 55
6.1.3. Fake PRoPHET ACKs . . . . . . . . . . . . . . . . . . 56
6.1.4. Bundle Store Overflow . . . . . . . . . . . . . . . . 56
6.1.5. Bundle Store Overflow with Delivery Predictability
Lindgren, et al. Expires April 26, 2011 [Page 3]
Internet-Draft PRoPHET October 2010
Manipulation . . . . . . . . . . . . . . . . . . . . . 56
6.2. Interactions with External Routing Domains . . . . . . . . 57
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 58
7.1. DTN Routing Protocol Number . . . . . . . . . . . . . . . 59
7.2. PRoPHET Version . . . . . . . . . . . . . . . . . . . . . 59
7.3. Header Flags . . . . . . . . . . . . . . . . . . . . . . . 60
7.4. Result . . . . . . . . . . . . . . . . . . . . . . . . . . 60
7.5. Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.6. Error and Log Messages . . . . . . . . . . . . . . . . . . 61
7.7. TLV Type . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.8. Hello TLV Flags . . . . . . . . . . . . . . . . . . . . . 62
7.9. Error TLV Flags . . . . . . . . . . . . . . . . . . . . . 63
7.10. RIB Base Dictionary TLV Flags . . . . . . . . . . . . . . 63
7.11. RIB TLV Flags . . . . . . . . . . . . . . . . . . . . . . 63
7.12. RIB Flags . . . . . . . . . . . . . . . . . . . . . . . . 64
7.13. Bundle Flags . . . . . . . . . . . . . . . . . . . . . . . 64
8. Implementation Experience . . . . . . . . . . . . . . . . . . 65
9. Deployment Experience . . . . . . . . . . . . . . . . . . . . 66
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 67
11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 68
11.1. Normative References . . . . . . . . . . . . . . . . . . . 68
11.2. Informative References . . . . . . . . . . . . . . . . . . 68
Appendix A. PRoPHET Example . . . . . . . . . . . . . . . . . . . 70
Appendix B. Neighbor Discovery Example . . . . . . . . . . . . . 72
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 73
Lindgren, et al. Expires April 26, 2011 [Page 4]
Internet-Draft PRoPHET October 2010
1. Introduction
The Probabilistic Routing Protocol using History of Encounters and
Transitivity (PRoPHET) algorithm enables communication between
participating nodes wishing to communicate in an intermittently
connected network where at least some of the nodes are mobile. One
of the most basic requirements for 'traditional' (IP) networking is
that there must exist a fully connected path between communication
endpoints for the duration of a communication session in order for
communication to be possible. There are, however, a number of
scenarios where connectivity is intermittent so that this is not the
case (thus rendering the end-to-end use of traditional networking
protocols impossible), but where it still is desirable to allow
communication between nodes.
Consider a network of mobile nodes using wireless communication with
a limited range which is less than the typical excursion distances
over which the nodes travel. Communication between a pair of nodes
at a particular instant is only possible when the distance between
the nodes is less than the range of the wireless communication. This
means that, even if messages are forwarded through other nodes acting
as intermediate routes, there is no guarantee of finding a viable
continuous path when it is needed to transmit a message.
One way to enable communication in such scenarios, is by allowing
messages to be buffered at intermediate nodes for a longer time than
normally occurs in the queues of conventional routers (c.f. Delay
and Disruption Tolerant Networking [RFC4838]). It would then be
possible to exploit the mobility of a subset of the nodes to bring
messages closer to their destination by transferring them to other
nodes as they meet. Figure 1 shows how the mobility of nodes in such
a scenario can be used to eventually deliver a message to its
destination. In this figure, the four sub-figures (a) - (d)
represent the physical positions of four nodes (A, B, C, and D) at
four time instants, increasing from (a) to (d) and associated radio
ranges. At the start time node A has a message (indicated by a *
next to that node) to be delivered to node D, but there does not
exist a path between nodes A and D because of the limited range of
available wireless connections. As shown in sub-figures (a) - (d),
the mobility of the nodes allows the message to first be transferred
to node B, then to node C, and when finally node C moves within range
of node D, it can deliver the message to its final destination. This
technique is known as 'transitive networking'.
Mobility and contact patterns in real application scenarios are
likely to be non-random, but rather be predictable, based on the
underlying activities of the higher level application (this could for
example stem from human mobility having regular traffic patterns
Lindgren, et al. Expires April 26, 2011 [Page 5]
Internet-Draft PRoPHET October 2010
based on repeating behavioral patterns (e.g., going to work or the
market and returning home) and social interactions, or from any
number of other node mobility situations where a proportion of nodes
are mobile and move in ways that are not completely random over time
but have a degree of predictability over time). This means that if a
node has visited a location or been in contact with a certain node
several times before, it is likely that it will visit that location
or meet that node again.
PRoPHET can also be used in some networks where such mobility as
described above does not take place. Predictable patterns in node
contacts can also occur among static nodes where varying radio
conditions or power-saving sleeping schedules cause connection
between nodes to be intermittent.
In previously discussed mechanisms to enable communication in
intermittently connected networks, such as Epidemic Routing
[vahdat_00], very general approaches have been taken to the problem
at hand. In an environment where buffer space and bandwidth are
infinite, Epidemic Routing will give an optimal solution to the
problem of routing in an intermittently connected network with regard
to message delivery ratio and latency. However, in most cases
neither bandwidth nor buffer space is infinite, but instead they are
rather scarce resources, especially in the case of sensor networks.
PRoPHET is fundamentally an epidemic protocol with strict pruning.
An epidemic protocol works by transferring its data to each and every
node it meets. As data is passed from node to node, it is eventually
passed to all nodes, including the target node. One of the
advantages of an epidemic protocol is that by trying every path, it
is guaranteed to try the best path. One of the disadvantages of an
epidemic protocol is the extensive use of resources with every node
needing to carry every packet and the associated transmission costs.
PRoPHET's goal is to gain the advantages of an epidemic protocol
without paying the price in storage and communication resources
incurred by the basic epidemic protocol. That is, PRoPHET offers an
alternative to basic Epidemic Routing, with lower demands on buffer
space and bandwidth, and with equal or better performance in cases
where those resources are limited, and without loss of generality in
scenarios where it is suitable to use PRoPHET.
Lindgren, et al. Expires April 26, 2011 [Page 6]
Internet-Draft PRoPHET October 2010
+----------------------------+ +----------------------------+
| ___ | | ___ |
| ___ / \ | | / \ |
| / \ ( D ) | | ( D ) |
| ( B ) \___/ | | ___ \___/ |
| \___/ ___ | | /___\ ___ |
|___ / \ | | (/ B*\) / \ |
| \ ( C ) | | (\_A_/) ( C ) |
| A* ) \___/ | | \___/ \___/ |
|___/ | | |
+----------------------------+ +----------------------------+
(a) Time t (b) Time (t + dt)
+----------------------------+ +----------------------------+
| _____ ___ | | ___ ___ |
| / / \ \ / \ | | / \ /___\ |
| ( (B C* ) ( D ) | | ( B ) (/ D*\) |
| \_\_/_/ \___/ | | \___/ (\_C_/) |
| ___ | | ___ \___/ |
| / \ | | / \ |
| ( A ) | | ( A ) |
| \___/ | | \___/ |
| | | |
+----------------------------+ +----------------------------+
(c) Time (t + 2*dt) (d) Time (t + 3*dt)
Figure 1: Example of transitive communication
This document presents a framework for probabilistic routing in
intermittently connected networks, using an assumption of non-random
mobility of nodes to improve the delivery rate of messages while
keeping buffer usage and communication overhead at a low level.
First, a probabilistic metric called delivery predictability is
defined. The document then goes on to define a probabilistic routing
protocol using this metric.
1.1. Relation to the Delay Tolerant Networking architecture
The Delay Tolerant Networking (DTN) architecture[RFC4838] defines an
architecture for communication in environments where traditional
communication protocols can not be used due to excessive delays, link
outages and other extreme conditions. The intermittently connected
networks considered here are a subset of those covered by the DTN
architecture. The DTN architecture defines routes to be computed
based on a collection of 'contacts' indicating the start time,
duration, endpoints, forwarding capacity and latency of a link in the
topology graph. These contacts may be deterministic, or may be
derived from estimates. The architecture defines some different
Lindgren, et al. Expires April 26, 2011 [Page 7]
Internet-Draft PRoPHET October 2010
types of intermittent contacts. The ones called opportunistic and
predicted are the ones addressed by this protocol.
Opportunistic contacts are those that are not scheduled, but rather
present themselves unexpectedly and frequently arise due to node
mobility. Predicted contacts are like opportunistic contacts, but
based on some information, it might be possible to draw some
statistical conclusion as to whether or not a contact will be present
soon.
The DTN architecture also introduces the bundle protocol [RFC5050],
which provides a way for applications to 'bundle' an entire session,
including both data and meta-data, into a single message, or bundle,
that can be sent as a unit. The bundle protocol also provides end-
to-end addressing and acknowledgments. PRoPHET is specifically
intended to provide routing services in a network environment that
uses bundles as its data transfer mechanism, but could be also be
used in other intermittent environments.
1.2. Applicability of the protocol
The PRoPHET routing protocol is mainly targeted at situations where
at least some of the nodes are mobile with mobility that creates
connectivity patterns that are not completely random over time but
have a degree of predictability. Such connectivity patterns can also
occur in networks where nodes switch off radios to preserve power.
Human mobility patterns (often containing daily or weekly periodic
activities) provide one such example where PRoPHET is expected to be
applicable, but the applicability is not limited to scenarios
including humans.
In order for PRoPHET to benefit from such predictability in the
contact patterns between nodes, it is expected the network exist
under similar circumstances over a longer time-scale (in terms of
node encounters) so that the predictability can be accurately
estimated.
The PRoPHET protocol expects nodes to be able to establish a local
TCP link in order to exchange the information needed by the PRoPHET
protocol. Protocol signaling is done out-of-band over this TCP link,
without involving the Bundle Protocol agent [RFC5050]. The PRoPHET
protocol is however expected to interact with the Bundle Protocol
agent to retrieve information about available bundles as well as
requesting that a bundle is sent to another node (it is expected that
the associated bundle agents are then able to establish a link
(probably over the TCP convergence layer) to perform this transfer).
While PRoPHET is currently defined to run over TCP, in future
Lindgren, et al. Expires April 26, 2011 [Page 8]
Internet-Draft PRoPHET October 2010
versions the information exchange may take place over other transport
protocols as well and these may not provide message segmentation.
Hence the capability is provided to segment protocol messages
directly in the PRoPHET layer.
In a large Delay and Disruption Tolerant Network (DTN), network
conditions may vary widely, and in different parts of the network,
different routing protocols may be appropriate. In this
specification, we consider routing within a single 'PRoPHET zone',
which is a set of nodes among which messages are routed using
PRoPHET. In many cases, a PRoPHET zone will not span the entire DTN,
but there will be other parts of the network with other
characteristics that run other routing protocols. To handle this,
there may be nodes within the zone that act as gateways to other
nodes that are the destinations for bundles generated within the zone
or that insert bundles into the zone. Thus, PRoPHET is not
necessarily used end-to-end, but only within regions of the network
where its use is appropriate.
1.3. PRoPHET as Compared to Regular Routing Protocols
While PRoPHET uses a mechanism for pruning the epidemic forwarding
tree that is similar to the mechanism used in Metric-based Vector
Routing protocols (where the metric might be distance or cost), it
should not be confused with a metric vector protocol.
In a traditional metric-based vector routing protocol, the
information passed from node to node is used to create a single non-
looping path from source to destination that is optimal given the
metric used. The path consists of a set of directed edges selected
from the complete graph of communications links between the network
nodes.
In PRoPHET, that information is used to prune the epidemic tree of
paths by removing paths that look less likely to provide an effective
route for delivery of data to its intended destination. One of the
effects of this difference is that the regular notions of split
horizon do not apply to PRoPHET. The purpose of split horizon is to
prevent a distance vector protocol from ever passing a packet back to
the node that sent it the packet because it is well known that the
source does not lie in that direction as determined when the directed
path was computed.
In an epidemic protocol, where that previous system already has the
data, the notion of passing the data back to the node is redundant:
the protocol can readily determine that such a transfer is not
required. Further, given the mobility and constant churn of
encounters possible in a DTN that is dominated by opportunistic
Lindgren, et al. Expires April 26, 2011 [Page 9]
Internet-Draft PRoPHET October 2010
encounters, it is quite possible that on a future encounter, that
node might have become a better option for reaching the destination.
Such a later encounter may require a re-transfer of the data if
resource constraints have resulted in the data being deleted from the
original carrier between the encounters.
The logic of metric routing protocols does not map directly onto the
family of epidemic protocols. In particular it is inappropriate to
try to assess such protocols against the criteria used to assess
conventional routing protocols such as the metric vector protocols;
this is not to say that the family of epidemic protocols do not have
weaknesses but they have to be considered independently of
traditional protocols.
1.4. Requirements notation
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119.
Lindgren, et al. Expires April 26, 2011 [Page 10]
Internet-Draft PRoPHET October 2010
2. Architecture
2.1. PRoPHET
This section presents an overview of the main architecture of
PRoPHET, a Probabilistic Routing Protocol using History of Encounters
and Transitivity. The protocol leverages the observations made on
the non-randomness of mobility patterns present in many application
scenarios to improve routing performance. Instead of doing blind
epidemic replication of bundles through the network as previous
protocols have done, it applies 'probabilistic routing'.
To accomplish this, a metric called 'delivery predictability',
0 <= P_(A,B) <= 1, is established at every node A for each known
destination B. This metric is calculated so that a node with a higher
value for a certain destination is estimated to be a better candidate
for delivering a bundle to that destination (i.e., if
P_(A,B)>P_(C,B), bundles for destination B are preferable to forward
to A rather than C). It is later used when making forwarding
decisions. As routes in a DTN are likely to be asymmetric, the
calculation of the delivery predictability reflects this, and P_(A,B)
may be different from P_(B,A).
The delivery predictability values in each node evolve over time both
as a result of decay of the metrics between encounters between nodes
and due to changes resulting from encounters when metric information
for the encountered node is updated to reflect the encounter and
metric information about other nodes is exchanged.
When two PRoPHET nodes have a communication opportunity, they first
exchange the delivery predictabilities for all destinations known by
the nodes. This information is used by the nodes to update the
internal delivery predictability vector as described below. After
that, the nodes exchange information (including destination and size)
about the bundles each node carries and the information is used in
conjunction with the updated delivery predictabilities to decide
which bundles to request to be forwarded from the other node based on
the forwarding strategy used (as discussed in Section 2.1.3).
2.1.1. Delivery Predictability Calculation
As stated above, PRoPHET relies on calculating a metric based on the
probability of encountering a certain node, and using that to support
the decision of whether or not to forward a bundle to a certain node.
This section describes the operations performed on the metrics stored
in a node when it encounters another node and a communications
opportunity arises. In the operations described by the equations
that follow, the updates are being performed by node A, P_(A,B) is
Lindgren, et al. Expires April 26, 2011 [Page 11]
Internet-Draft PRoPHET October 2010
the delivery predictability value that node A will have stored for
the destination B after the encounter and P_(A,B)_old is the
corresponding value that was stored before the encounter. If no
delivery predictability value is stored for a particular destination
B, P_(A,B) is considered to be zero.
As a special case, the metric value for a node itself is always
defined to be 1 (i.e., P_(A,A)=1).
The equations use a number of parameters that can be selected to
match the characteristics of the mobility pattern in the PRoPHET zone
where the node is located. Recommended settings for the various
parameters are given in Section 3.3. The impact on the evolution of
delivery predictabilities if encountering nodes have different
parameter setting is discussed in Section 2.1.1.1.
The calculation of the updates to the delivery predictabilities
during an encounter has three parts.
When two nodes meet, the first thing they do is to update the
delivery predictability for each other, so that nodes that are often
encountered have a high delivery predictability. If node B has not
met node A for a long time or has never met node B, such that
P_(A,B) < P_first_threshold, then P_(A,B) should be set to
P_encounter_first. Because PRoPHET generally has no prior knowledge
about whether this is an encounter that will be repeated relatively
frequently or one that will be a rare event, P_encounter_first SHOULD
be set to 0.5 unless the node has extra information obtained other
than through the PRoPHET protocol about the likelihood of future
encounters. Otherwise, P_(A,B) should be calculated as shown in
Equation 1, where 0 <= P_encounter <= 1 is a scaling constant setting
the rate at which the predictability increases on encounters after
the first and delta is a small positive number that effectively sets
an upper bound for P_(A,B). The limit is set so that
predictabilities between different nodes stay strictly less than 1.
The value of delta should normally be very small (e.g., 0.01) so as
not to significantly restrict the range of available
predictabilities, but can be chosen to make calculations efficient
where this is important.
P_(A,B) = P_(A,B)_old + ( 1 - delta - P_(A,B)_old ) * P_encounter (1)
If a pair of nodes do not encounter each other during an interval,
they are less likely to be good forwarders of bundles to each other,
thus the delivery predictability values must age, being reduced in
the process. The second part of the updates of the metric values is
application of the aging equation shown in Equation 2, where
0 <= gamma <= 1 is the aging constant, and K is the number of time
Lindgren, et al. Expires April 26, 2011 [Page 12]
Internet-Draft PRoPHET October 2010
units that have elapsed since the last time the metric was aged. The
time unit used can differ, and should be defined based on the
application and the expected delays in the targeted network.
P_(A,B) = P_(A,B)_old * gamma^K (2)
The delivery predictabilities are aged according to Equation 2 before
being passed to an encountered node so that they reflect the time
that has passed since the node had its last encounter with any other
node.
The delivery predictability also has a transitive property, that is
based on the observation that if node A frequently encounters node B,
and node B frequently encounters node C, then node C probably is a
good node to forward bundles destined for node A to. Equation 3
shows how this transitivity affects the delivery predictability,
where 0 <= beta <= 1 is a scaling constant that controls how large an
impact the transitivity should have on the delivery predictability.
P_(A,C) = MAX( P_(A,C)_old, P_(A,B) * P_(B,C)_recv * beta ) (3)
Node A uses Equation 3 and the metric values received from the
encountered node B (e.g., P_(B,C)_recv) in the third part of updating
the metric values stored in node A.
2.1.1.1. Impact of Encounters Between Nodes with Different Parameter
Settings
The various parameters used in the three equations described in
Section 2.1.1 are set independently in each node and it is therefore
possible that encounters may take place between nodes that have been
configured with different values of the parameters. This section
considers whether this could be problematic for the operation of
PRoPHET in that zone.
It is desirable that all the nodes operating in a PRoPHET zone should
use closely matched values of the parameters and that the parameters
should be set to values that are appropriate for the operating zone.
More details of how to select appropriate values are given in
Section 3.3. Using closely matched values means that delivery
predictabilities will evolve in the same way in each node leading to
consistent decision making about the bundles that should be exchanged
during encounters.
Before going on to consider the impact of reasonable but different
settings, it should be noted that malicious nodes can use
inappropriate settings of the parameters to disrupt delivery of
bundles in a PRoPHET zone as described in Section 6.
Lindgren, et al. Expires April 26, 2011 [Page 13]
Internet-Draft PRoPHET October 2010
Firstly and importantly, use of different, but legitimate, settings
in encountering nodes will not cause problems in the protocol itself.
Apart from P_encounter_first, the other parameters control the rate
of change of the the metric values or limit the range of valid values
that will be stored in a node. None of the calculations in a node
will be invalidated or result in illegal values if the metric values
received from another node had been calculated using different
parameters.
Simulation work indicates that the update calculations are quite
stable in the face of changes to the rate parameters, so that minor
discrepancies will not have a major impact on the performance of the
protocol. The protocol is explicitly designed to deal with
situations where there are random factors in the opportunistic nature
of node encounters and this randomness dominates over the
discrepancies in the parameters.
More major discrepancies may lead to sub-optimal behavior of the
protocol as certain paths might be more preferred or more deprecated
inappropriately. However, since the protocol overall is epidemic in
nature, this would not generally lead to non-delivery of bundles as
they would also be passed to other nodes and would still be delivered
though possibly not on the optimal path.
2.1.2. Optional Delivery Predictability Optimizations
2.1.2.1. Smoothing
To give the delivery predictability a smoother rate of change, a node
MAY apply one of the following methods to smooth the metric:
1. Keep a list of NUM_P (the recommended value is 4, which has been
shown in simulations to give a good trade off between smoothness
and rate of response to changes) values for each destination
instead of only a single value. The list is held in order of
acquisition. When a delivery predictability is updated, the
value at the 'newest' position in the list is used as input to
the equations in Section 2.1.1. The oldest value in the list is
then discarded and the new value is written in the 'newest'
position of the list. When a delivery predictability value is
needed (either for sending to a peering PRoPHET node, or for
making a forwarding decision), the average of the values in the
list is calculated, and that value is then used. If less than
NUM_P values have been entered into the list, only the positions
that have been filled should be used for the averaging.
2. In addition to keeping the delivery predictability as described
in Section 2.1.1, a node MAY also keep an exponential weighted
Lindgren, et al. Expires April 26, 2011 [Page 14]
Internet-Draft PRoPHET October 2010
moving average (EWMA) of the delivery predictability. The EWMA
is then used for making forwarding decisions and to report to
peering nodes, but the value calculated according to
Section 2.1.1 is still used as input to the calculations of new
delivery predictabilities. The EWMA is calculated according to
Equation 4, where 0 <= alpha <= 1 is the weight of the most
current value.
P_ewma = P_ewma_old * (1 - alpha) + P * alpha (4)
The appropriate choice of alpha may vary depending on application
scenario circumstances. Unless prior knowledge of the scenario is
available, it is suggested that alpha is set to 0.5.
2.1.2.2. Removal of Low Delivery Predictabilities
To reduce the data to be transferred between two nodes, a node MAY
treat delivery predictabilities smaller than epsilon, where epsilon
is a small number, as if they were zero, and thus they do not need to
be included in the list sent during the information exchange phase.
If this optimization is used, care must be taken to select epsilon to
be smaller than delivery predictability values normally present in
the network for destinations for which this node is a forwarder. It
is possible that epsilon could be calculated based on delivery
predictability ranges and the amount they change historically, but
this has not been investigated yet.
2.1.3. Forwarding Strategies and Queueing Policies
In traditional routing protocols, choosing where to forward a message
is usually a simple task; the message is sent to the neighbor that
has the path to the destination with the lowest cost (often the
shortest path). Normally the message is also only sent to a single
node since the reliability of paths is relatively high. However, in
the settings we envision here, things are radically different. The
first possibility that must be considered when a bundle arrives at a
node is that there might not be a path to the destination available,
so the node has to buffer the bundle and upon each encounter with
another node, the decision must be made whether or not to transfer a
particular bundle. Furthermore, having duplicates of messages (on
different nodes, as the bundle offer/request mechanism described in
Section 4.3.5 ensures that a node does not receive a bundle it
already carries) may also be sensible, as forwarding a bundle to
multiple nodes can increase the delivery probability of that bundle.
Unfortunately, these decisions are not trivial to make. In some
cases it might be sensible to select a fixed threshold and only give
Lindgren, et al. Expires April 26, 2011 [Page 15]
Internet-Draft PRoPHET October 2010
a bundle to nodes that have a delivery predictability over that
threshold for the destination of the bundle. On the other hand, when
encountering a node with a low delivery predictability, it is not
certain that a node with a higher metric will be encountered within
reasonable time. Thus, there can also be situations where we might
want to be less strict in deciding who to give bundles to.
Furthermore, there is the problem of deciding how many nodes to give
a certain bundle to. Distributing a bundle to a large number of
nodes will of course increase the probability of delivering that
particular bundle to its destination, but this comes at the cost of
consuming more system resources for bundle storage and possibly
reducing the probability of other bundles being delivered. On the
other hand, giving a bundle to only a few nodes (maybe even just a
single node) will use less system resources, but the probability of
delivering a bundle is lower, and the delay incurred high.
When resources are constrained, nodes may suffer from storage
shortage, and may have to drop bundles before they have been
delivered to their destinations. Similarly to when deciding whether
or not to forward a bundle, deciding which bundle to drop to still
maintain good performance might require different policies in
different scenarios.
Nodes MAY define their own forwarding strategies and queueing
policies that take into account the special conditions applicable to
the nodes, and local resource constraints. Some default strategies
and policies that should be suitable for most normal operation are
defined in Section 3.6 and Section 3.7.
2.2. Bundle Agent to Routing Agent Interface
The bundle protocol [RFC5050] introduces the concept of a 'bundle
agent' that manages the interface between applications and the
'convergence layers' that provide the transport of bundles between
nodes during communication opportunities. This specification extends
the bundle agent with a routing agent that controls the actions of
the bundle agent during an (opportunistic) communications
opportunity.
This specification defines the details of the PRoPHET routing agent,
but the interface defines a more general interface that is also
applicable to alternative routing protocols.
To enable the PRoPHET routing agent to operate properly, it must be
aware of the bundles stored at the node, and it must also be able to
tell the bundle agent of that node to send a bundle to a peering
node. Therefore, the bundle agent needs to provide the following
interface/functionality to the routing agent:
Lindgren, et al. Expires April 26, 2011 [Page 16]
Internet-Draft PRoPHET October 2010
Get Bundle List
Returns a list of the stored bundles and their attributes to the
routing agent.
Send Bundle
Makes the bundle agent send a specified bundle.
Accept Bundle
Gives the bundle agent a new bundle to store.
Bundle Delivered
Tells the bundle agent that a bundle was delivered to its
destination.
Drop Bundle Advice
Advises the bundle agent that a specified bundle should not be
offered for forwarding in future and may be dropped by the
bundle agent if appropriate.
Route Import
Can be used by a gateway node in a PRoPHET zone to import
reachability information about EIDs that are external to the
PRoPHET zone. Translation functions dependent on the external
routing protocol will be used to set the appropriate delivery
predictabilities for imported destinations as described in
Section 2.3.
Route Export
Can be used by a gateway node in a PRoPHET zone to export
reachability information (destination EIDs and corresponding
delivery predictabilities) for use by routing protocols in other
parts of the DTN.
2.3. PRoPHET Zone Gateways
PRoPHET is designed to handle routing primarily within a "PRoPHET
zone," i.e. a set of nodes that all implement the PRoPHET routing
scheme. However, since we recognise that a PRoPHET routing zone is
unlikely to encompass an entire DTN, there may be nodes within the
zone that act as gateways to other nodes that are the destinations
for bundles generated within the zone or that insert bundles into the
zone.
PRoPHET MAY elect to export and import routes across a bundle agent
interface. The delivery predictability to use for routes that are
imported depends on the routing protocol used to manage those routes.
If a translation function between the external routing protocol and
PRoPHET exists, it SHOULD be used to set the delivery predictability.
Lindgren, et al. Expires April 26, 2011 [Page 17]
Internet-Draft PRoPHET October 2010
If no such translation function exists, the delivery predictability
SHOULD be set to 1. For those routes that are exported, the current
delivery predictability will be exported with the route.
2.4. Lower Layer Requirements and Interface
PRoPHET can be run on a large number of underlying networking
technologies. To accommodate its operation on all kinds of lower
layers, it requires the lower layers to provide the following
functionality and interfaces.
Neighbor discovery and maintenance
A PRoPHET node needs to know the identity of its neighbors and
when new neighbors appear and old neighbors disappear. Some
wireless networking technologies might already contain
mechanisms for detecting neighbors and maintaining this state.
To avoid redundancies and inefficiencies, neighbor discovery is
thus not included as a part of PRoPHET, but PRoPHET relies on
such mechanism in lower layers. The lower layers MUST provide
the two functions listed below. If the underlying networking
technology does not support such services, a simple neighbor
discovery scheme using local broadcasts of beacon messages could
be run in-between PRoPHET and the underlying layer. An example
of a simple neighbor discovery mechanism that could be used is
shown in Appendix B.
New Neighbor
Signals to the PRoPHET agent that a new node has become a
neighbor. A neighbor is here defined as another node that
is currently within communication range of the wireless
networking technology in use. The PRoPHET agent should now
start the Hello procedure as described in Section 5.2.
Neighbor Gone
Signals to the PRoPHET agent that one of its neighbors have
left.
Local Address
An address used by the underlying communication layer (e.g. an
IP or MAC address) that identifies the sender address of the
current message. This address must be unique among the nodes
that can currently communicate, and is only used in conjunction
with the Instance numbers to identify a communicating pair of
nodes as described in Section 4.1. This address and its format
is dependent on the convergence layer that is being used by the
bundle layer.
Lindgren, et al. Expires April 26, 2011 [Page 18]
Internet-Draft PRoPHET October 2010
3. Protocol Overview
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. 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 Section 2.1.1 and Section 2.1.2.
If the nodes have already done this exchange within a time interval
shorter than, say, 5% of the characteristic intercontact time
expected, the nodes MAY omit this recalculation phase depending on
the characteristics of the communications mechanism and expected node
behavior in the PRoPHET zone. For example mobile nodes communicating
with each other using Wi-Fi ad hoc mode may produce apparent multiple
encounters with a short interval between them but these are
frequently due to artifacts of the underlying physical network when
using wireless connections, where transmission problems or small
changes in location may result in repeated reconnections. Treating
such multiple reconnections as new encounters can give an
inappropriate view of the real probability that the two nodes will
encounter each other in the future and updating the predictabilities
repeatedly will mirror this inappropriate view in the predictability
values, which should be avoided. On the other hand there may be some
networks where it is desirable to update predictabilities after every
encounter. Also if one or other of the nodes has encountered a third
node in the meantime it MAY be appropriate to carry out the exchange
even though there has only been a short interval between encounters.
Nodes can agree to suppress the recalculation phase but it MUST be
carried out if one or other node does not request suppression.
3.2. Information Exchange Phase
The first step in the Information Exchange Phase is for the protocol
to send a Routing Information Base Dictionary TLV to the node it is
peering with. This is a dictionary of the Endpoint Identifiers
Lindgren, et al. Expires April 26, 2011 [Page 19]
Internet-Draft PRoPHET October 2010
(EIDs) of the nodes that will be listed in the Routing Information
Base. After this, a Routing Information Base TLV is sent. This TLV
contains a list of the EIDs that the node has knowledge of, and the
corresponding delivery predictabilities for those nodes, and flags
describing the capabilities of the sending node. Upon reception of
this TLV, the node updates its delivery predictability table
according to the equations in Section 2.1.1, and using its forwarding
strategy (see Section 2.1.3) determines which of its stored bundles
it wishes to offer the peering node. After making this decision, a
Bundle Offer TLV is prepared, listing the bundle identifiers and
their destinations for all bundles it wishes to offer the other node.
If the Bundle Offer TLV lists a bundle for which the destination was
not included in the first Routing Information Base Dictionary TLV
sent, a new such TLV is sent first with an incremental update of the
dictionary. When the peering node has a dictionary with all
necessary EIDs, the Bundle Offer TLV is sent to it. The Bundle Offer
TLV also contains a list of PRoPHET ACKs (see Section 3.5). This
phase of the protocol is described in more detail in Section 5.3.
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 when the WAIT_INFO
timer expires to allow new delivery predictability information to be
spread through the network and new bundle exchanges to take place.
3.2.1. Routing Information Base Dictionary
To reduce the overhead of the protocol, the Routing Information Base
and Bundle Offer/Request TLVs utilize an EID dictionary. This
dictionary maps long variable length EIDs as defined in [RFC4838] to
shorter SDNV (see Section 4.1. of RFC 5050 [RFC5050]) identifiers
that are used in place of the EIDs in subsequent TLVs. The
dictionary established only persist through a single encounter with a
node (while the same link set up by the Hello procedure, with the
same instance numbers, remains).
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 2
provides some recommended default values. A brief explanation of the
parameters is given below.
Lindgren, et al. Expires April 26, 2011 [Page 20]
Internet-Draft PRoPHET October 2010
P_encounter
P_encounter is used to increase the delivery predictability for
a destination when the destination node is encountered. A
larger value of P_encounter 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.
In order to reduce the effect of spurious encounters, a lower
value, P_encounter_first, is used when a node is encountered for
the first time, or when the last encounter was sufficiently long
ago so that the delivery predictability for that node has
decayed to a value below the threshold P_first_threshold. We
have found the values given in the table below to be suitable.
alpha
The alpha parameter is used in the optional smoothing of the
delivery predictabilities described in Section 2.1.2.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.
To set an appropriate gamma value, one should consider the 'average
expected delivery' time T_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 T_aed time interval
can be estimated according to the average number of hops that bundles
have to pass and average encounter frequency. Clearly if bundles
Lindgren, et al. Expires April 26, 2011 [Page 21]
Internet-Draft PRoPHET October 2010
have a Time To Live (TTL) that is less than T_aed they are unlikely
to survive in the network to be delivered to a node in this PRoPHET
zone, but 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 T_aed and selecting how much we want the delivery
predictability to age in one T_aed time period (call this A), we can
calculate the number of time unit in one T_aed as K=T_aed/timeunit.
This can then be used to calculate gamma as gamma=Kth-root(A). These
instructions on how to set gamma are only given as a possible method
for selecting an appropriate value, but network operators are free to
set gamma as they choose.
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.1.1.
+========================================+
| Parameter | Recommended value |
+========================================+
| P_encounter | 0.5 |
+----------------------------------------+
| P_encounter_first | 0.5 |
+----------------------------------------+
| P_first_threshold | 0.1 |
+----------------------------------------+
| alpha | 0.5 |
+----------------------------------------+
| beta | 0.9 |
+----------------------------------------+
| gamma | 0.999 |
+----------------------------------------+
| delta | 0.01 |
+========================================+
Figure 2: Default parameter settings
Lindgren, et al. Expires April 26, 2011 [Page 22]
Internet-Draft PRoPHET October 2010
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 destination. This
decision has to be made using local policies and considering
parameters such as available buffer space. For each such acceptable
bundle, the node sends a Bundle Request TLV to its peering node,
which in response to that sends 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
When a bundle reaches its destination within the PRoPHET zone (i.e.,
within the part of the network where PRoPHET is used for routing; not
necessarily the final destination of the bundle), a PRoPHET ACK for
that bundle is issued. A PRoPHET ACK is a confirmation that a bundle
has been delivered to its destination in the PRoPHET zone (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
Lindgren, et al. Expires April 26, 2011 [Page 23]
Internet-Draft PRoPHET October 2010
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 keep track of which nodes they have sent PRoPHET ACKs for
certain bundles to, 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 network.
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 uses 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 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 A has given the bundle
to some other node.
Lindgren, et al. Expires April 26, 2011 [Page 24]
Internet-Draft PRoPHET October 2010
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 apart from 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 (5)
This strategy is like GRTR, but nodes keep track of the largest
delivery predictability of any node it has forwarded this bundle
to, and only forward 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 (6)
Lindgren, et al. Expires April 26, 2011 [Page 25]
Internet-Draft PRoPHET October 2010
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 also
has 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 as specific acronyms for any set of words in
the specification.
Lindgren, et al. Expires April 26, 2011 [Page 26]
Internet-Draft PRoPHET October 2010
FIFO
Handle the queue in a First In First Out (FIFO) order.
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 keeps 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 the node the
bundle is forwarded to has for its destination.
FAV_new = FAV_old + ( 1 - FAV_old ) * P (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 the node the
bundle is forwarded to has for its destination.
FAV_new = FAV_old + P (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 life will soon be dropped anyway, this policy decides to drop
the bundle with the shortest remaining life time 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. This is however not
specific to this routing protocol, but a more general DTN
problem.
Lindgren, et al. Expires April 26, 2011 [Page 27]
Internet-Draft PRoPHET October 2010
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, which 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 life
time 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 obviously nodes MUST NOT drop bundles for
which it has custody unless the lifetime expires.
Lindgren, et al. Expires April 26, 2011 [Page 28]
Internet-Draft PRoPHET October 2010
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].
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 3: Basic message format
Lindgren, et al. Expires April 26, 2011 [Page 29]
Internet-Draft PRoPHET October 2010
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 4: 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 middle boxes 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. Also in 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 four bit
unsigned integer in network bit order. This document defines
version 2.
Lindgren, et al. Expires April 26, 2011 [Page 30]
Internet-Draft PRoPHET October 2010
Flags
Reserved
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.
In a response message, the result field can have two values:
"Success," and "Failure". The "Success" results 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 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
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 the first TLV after the header.
Lindgren, et al. Expires April 26, 2011 [Page 31]
Internet-Draft PRoPHET October 2010
The Code field is encoded as an 8 bit unsigned integer in
network bit order. The following value ranges are defined:
PRoPHET Error Messages 0x00 - 0x99
Reserved 0xA0 - 0xFE
Error TLV in message 0xFF
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 an unsigned integer in network bit
order.
Receiver Instance
For messages during the Hello phase with the Hello SYN, Hello
SYNACK, and Hello ACK functions, 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 SHOULD 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 they are responding
to. The Transaction Identifier is a 32-bit bit pattern.
Lindgren, et al. Expires April 26, 2011 [Page 32]
Internet-Draft PRoPHET October 2010
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 sub-message of a sequence.
SubMessage Number
When a message is segmented because it exceeds the MTU of the
link layer, each segment will include a SubMessage Number to
indicate its position. Alternatively, if it is the first sub-
message in a sequence of sub-messages, 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 byte order
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.
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 used by the underlying communication layer as
described in Section 2.4 that identifies the sender address of
the current message. This address must be unique among the
nodes that can currently communicate, and is only used in
conjunction with the Receiver Local Address and the Receiver
Instance and Sender Instance to identify a communicating pair of
nodes.
Receiver Local Address
An address used by the underlying communication layer as
described in Section 2.4 that 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 and the Receiver
Instance and Sender Instance to identify a communicating pair of
nodes.
When PRoPHET is run over TCP, the IP addresses of the communicating
Lindgren, et al. Expires April 26, 2011 [Page 33]
Internet-Draft PRoPHET October 2010
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 5: 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.
TLV Length
Length of the TLV in octets, including the TLV header and any
nested TLVs. Encoded as an SDNV.
4.3. TLVs
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. 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 an ESTAB connection (as
defined in the state machine in Section 5.2), the connection SHOULD
Lindgren, et al. Expires April 26, 2011 [Page 34]
Internet-Draft PRoPHET October 2010
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 | Hello Function| TLV Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Timer (SDNV) |EID Length,SDNV| Sender EID (variable length) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6: Hello TLV Format
Hello Function
Specifies the function of the Hello TLV. Four main functions
are specified for the Hello TLV, as well as one flag to indicate
that the information exchange phase can be suppressed (to be
used together with either the SYNACK or ACK flag). The
functions are encoded as an 8 bit unsigned integer.
The encoding of the Hello Function is:
SYN: Hello Function = 1
SYNACK:
Requesting execution of recalculation phase:
Hello Function = 2
Requesting suppression of recalculation phase:
Hello Function = 130
ACK:
Requesting execution of recalculation phase:
Hello Function = 3
Requesting suppression of recalculation phase:
Hello Function = 131
RSTACK: Hello Function = 4
If the SYNACK message requests suppression of recalculation
(function 130) and the ACK message requests suppression of
recalculation (function 131) then recalculation MUST be
suppressed. In all other cases recalculation must be done.
TLV Data
Lindgren, et al. Expires April 26, 2011 [Page 35]
Internet-Draft PRoPHET October 2010
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 100ms 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 | Flags | TLV Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Data ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7: Error TLV Format
TLV Flags
Reserved
TLV Data
Reserved
Lindgren, et al. Expires April 26, 2011 [Page 36]
Internet-Draft PRoPHET October 2010
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 messages.
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 | Flags | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIBD Entry Count (SDNV) | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ ~
~ Variable Length Routing Address Strings ~
~ ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Routing Address String
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID 1 (SDNV) | Length (SDNV) | Resv |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ Endpoint Identifier 1 (variable) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| . |
~ . ~
| . |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| String ID n (SDNV) | Length (SDNV) | Resv |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Endpoint Identifier n (variable) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 8: Routing Information Base Dictionary
TLV Flags
Reserved
Lindgren, et al. Expires April 26, 2011 [Page 37]
Internet-Draft PRoPHET October 2010
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 initiating the session
through sending the Hello SYN message, and String ID one is
predefined as the node responding with the Hello SYNACK message.
Length
Length of Address String. Encoded as SDNV.
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 | Flags | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIB String Count (SDNV) | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIBD String ID 1 (SDNV) | P-Value |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIB Flags 1 | . ~
+-+-+-+-+-+-+-+-+ . ~
~ . ~
~ . ~
~ . ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIBD String ID n (SDNV) | P-Value |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RIB Flags n |
+-+-+-+-+-+-+-+-+
Figure 9: Routing Information Base Header
Flags
The encoding of the Header flag field relates to the
capabilities of the Source node sending the RIB:
Lindgren, et al. Expires April 26, 2011 [Page 38]
Internet-Draft PRoPHET October 2010
Flag 0: More RIB TLVs 0b1
Flag 1: Reserved 0b1
Flag 2: Reserved 0b1
Flag 3: Reserved 0b1
Flag 4: Reserved 0b1
Flag 5: Reserved 0b1
Flag 6: Reserved 0b1
Flag 7: Reserved 0b1
The "More RIB TLVs" flag is set to 1 if the RIB requires more
TLVs to be fully transferred. This flag is set to 0 if this is
the final TLV of this RIB.
RIB String Count
Number of routing entries in the TLV. Encoded as SDNV.
RIBD String ID
ID string as predefined in the dictionary TLV. Encoded as SDNV.
P-value
Delivery predictability for the destination of this entry as
calculated according to the equations in Section 2.1.1, 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 RIB flag field is:
Flag 0: Reserved 0b1
Flag 1: Reserved 0b1
Flag 2: Reserved 0b1
Flag 3: Reserved 0b1
Flag 4: Reserved 0b1
Flag 5: Reserved 0b1
Flag 6: Reserved 0b1
Flag 7: Reserved 0b1
4.3.5. Bundle Offer and Response TLV
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. The Bundle Offer TLV also lists the bundles that a
PRoPHET acknowledgement has been issued for. Those bundles have the
Lindgren, et al. Expires April 26, 2011 [Page 39]
Internet-Draft PRoPHET October 2010
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 agent that this bundle is no longer required for
transmission by PRoPHET. Despite no longer transmitting the bundle,
it SHOULD keep an entry of the acknowledged bundle to be able to
further propagate the PRoPHET ACK.
The Response message is identical to the request message with the
exception of the TLV Type field.
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 | Flags | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle Offer Count | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle Dest String Id 1 (SDNV)| B_flags | resv |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle 1 Creation Timestamp time |
| (variable length SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle 1 Creation Timestamp sequence number |
| (variable length SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~ . ~
~ . ~
~ . ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle Dest String Id n (SDNV)| B_flags | resv |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle n Creation Timestamp time |
| (variable length SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Bundle n Creation Timestamp sequence number |
| (variable length SDNV) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 10: Bundle Offer and Response
TLV Type
The TLV Type for a Bundle Offer is 0xA2. The TLV Type for a
Bundle Response is 0xA3.
Lindgren, et al. Expires April 26, 2011 [Page 40]
Internet-Draft PRoPHET October 2010
TLV Flags
Reserved
Bundle Offer Count
Number of bundle offer/response entries.
Bundle Dest String Id
ID string of the destination of the bundle as predefined in the
dictionary TLV. Encoded as SDNV.
B-Flags
The encoding of the B_Flags are:
Flag 0: Bundle Accepted 0b1
Flag 1: Reserved 0b1
Flag 2: Reserved 0b1
Flag 3: Reserved 0b1
Flag 4: Reserved 0b1
Flag 5: Reserved 0b1
Flag 6: Reserved 0b1
Flag 7: PRoPHET ACK 0b1
Lindgren, et al. Expires April 26, 2011 [Page 41]
Internet-Draft PRoPHET October 2010
5. Detailed Operation
In this section, some more details on the operation of PRoPHET is
given along with state tables to help in implementing the protocol.
5.1. High Level State Tables
This section gives high level state tables for the operation of
PRoPHET. The following sections will describe each part of the
operation in more detail (including state tables for the internal
states of those procedures).
The following states are used in the state tables:
WAIT_NB This is the state all nodes start in. Nodes remain in this
state until they are notified that a new neighbor is available.
At that point, the Hello procedure should be started with the
new neighbor, and the node move into the HELLO state. It does
also needs to remain in the WAIT_NB state to ensure that it can
detect new neighbors. This can be handled by creating a new
thread or process that enters the HELLO state and takes care of
the communication with the new neighbor while the parent
remains in WAIT_NB.
HELLO Nodes are in the HELLO state from when a new neighbor is
detected until the Hello procedure is completed and a link is
established (which happens when the Hello procedure enters the
ESTAB state as described in Section 5.2 - during this
procedure, the states ESTAB, SYNSENT, and SYNRCVD will be used,
but those are internal to the Hello procedure and are not
listed here). If the node is notified that the neighbor is no
longer in range before a link has been established, it returns
to the WAIT_NB state.
INFO_EXCH After a link has been set up by the Hello procedure, a
node enters the INFO_EXCH state where the information exchange
and bundle passing is done. The node remains in this state as
long as Information Exchange Phase TLVs (Routing RIB, Routing
RIB Dictionary) and bundle passing TLVs (Bundle Offer, Bundle
Request) are being received. When an empty Bundle Request TLV
(i.e., no more bundles to send) is received, the node starts a
timer and enters the WAIT_INFO state. If the node is notified
that the neighbor is no longer in range before all information
and bundles have been exchanged, it returns to the WAIT_NB
state.
Lindgren, et al. Expires April 26, 2011 [Page 42]
Internet-Draft PRoPHET October 2010
WAIT_INFO Nodes enter the WAIT_INFO state after a completed
Information Exchange Phase and bundle passing phase. Nodes
remain in this state until a timer expires that means that the
Information Exchange Phase should be re-initiated. If the node
is notified that the neighbor is no longer in range before the
timer has expired, it returns to the WAIT_NB state.
State: WAIT_NB
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| New Neighbor | Start Hello procedure for neighbor| HELLO |
| | Keep waiting for more neighbors | WAIT_NB |
+==================================================================+
State: HELLO
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Hello TLV rcvd | | HELLO |
+------------------+-----------------------------------+-----------+
| Enter ESTAB state| Start Information Exchange Phase | INFO_EXCH |
+------------------+-----------------------------------+-----------+
| Neighbor Gone | | WAIT_NB |
+==================================================================+
State: INFO_EXCH
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
|Info Exch TLV rcvd| | INFO_EXCH |
+------------------+-----------------------------------+-----------+
| No more bundles | Start WAIT_INFO timer | WAIT_INFO |
+------------------+-----------------------------------+-----------+
Lindgren, et al. Expires April 26, 2011 [Page 43]
Internet-Draft PRoPHET October 2010
| Neighbor Gone | | WAIT_NB |
+==================================================================+
State: WAIT_INFO
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Timer expires | Restart Information Exchange Phase| INFO_EXCH |
+------------------+-----------------------------------+-----------+
| Neighbor Gone | | WAIT_NB |
+==================================================================+
5.2. Hello Procedure
The Hello TLV procedure is described by the following rules and state
tables.
The rules and state tables use the following operations:
o The "Update Peer Verifier" operation is defined as storing the
values of the Sender Instance and Sender Local Address fields from
a Hello SYN or Hello SYNACK function received from the entity at
the far end of the link.
o The procedure "Reset the link" is defined as:
1. Generate a new instance number for the link.
2. Delete the peer verifier (set to zero the values of Sender
Instance and Sender Local Address previously stored by the
Update Peer Verifier operation).
3. Send a SYN message.
4. Enter the SYNSENT state.
o The state tables use the following Boolean terms and operators:
A The Sender Instance in the incoming message matches the
value stored from a previous message by the "Update Peer
Verifier" operation.
Lindgren, et al. Expires April 26, 2011 [Page 44]
Internet-Draft PRoPHET October 2010
B The Sender Instance and Sender Local Address fields in the
incoming message match the values stored from a previous
message by the "Update Peer Verifier" operation.
C The Receiver Instance and Receiver Local Address fields in
the incoming message match the values of the Sender Instance
and Sender Local Address used in outgoing Hello SYN, Hello
SYNACK, and Hello ACK messages.
SYN A Hello SYN TLV has been received.
SYNACK A Hello SYNACK TLV has been received.
ACK A Hello ACK TLV has been received.
"&&" Represents the logical AND operation
"||" Represents the logical OR operation
"!" Represents the logical negation (NOT) operation.
o A timer is required for the periodic generation of Hello SYN,
Hello SYNACK, and Hello ACK messages. The value of the timer is
announced in the Timer field. To avoid synchronization effects,
uniformly distributed random jitter of +/-5% of the Timer field
SHOULD be added to the actual interval used for the timer.
There are two independent events: the timer expires, and a packet
arrives. The processing rules for these events are:
Timer Expires: Reset Timer
If state = SYNSENT Send SYN
If state = SYNRCVD Send SYNACK
If state = ESTAB Send ACK
Lindgren, et al. Expires April 26, 2011 [Page 45]
Internet-Draft PRoPHET October 2010
Packet Arrives:
If incoming message is an RSTACK:
If (A && C && !SYNSENT) Reset the link
Else discard the message.
If incoming message is a SYN, SYNACK, or ACK:
Response defined by the following State Tables.
If incoming message is any other PRoPHET TLV and
state != ESTAB:
Discard incoming message.
If state = SYNSENT Send SYN (Note 1)
If state = SYNRCVD Send SYNACK (Note 1)
Note 1: No more than two SYN or SYNACK messages should be
sent within any time period of length defined by the timer.
o A connection across a link is considered to be achieved when the
protocol reaches the ESTAB state. All TLVs, other than Hello
TLVs, that are received before synchronisation is achieved, will
be discarded.
5.2.1. State Tables
State: SYNSENT
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| SYNACK && C | Update Peer Verifier; Send ACK | ESTAB |
+------------------+-----------------------------------+-----------+
| SYNACK && !C | Send RSTACK | SYNSENT |
+------------------+-----------------------------------+-----------+
| SYN | Update Peer Verifier; Send SYNACK | SYNRCVD |
+------------------+-----------------------------------+-----------+
| ACK | Send RSTACK | SYNSENT |
+==================================================================+
Note: When sending SYNACK determine if recalculation of
predictabilities should be executed or suppressed and send
appropriate flag accompanying SYNACK. See Figure 6.
Note: When sending ACK, if received SYNACK requested suppression of
predictability recalculation, determine if recalculation of
predictabilities should be executed or suppressed and send
appropriate flag accompanying ACK; otherwise send ACK indicating
Lindgren, et al. Expires April 26, 2011 [Page 46]
Internet-Draft PRoPHET October 2010
recalculation should be executed.
State: SYNRCVD
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| SYNACK && C | Update Peer Verifier; Send ACK | ESTAB |
+------------------+-----------------------------------+-----------+
| SYNACK && !C | Send RSTACK | SYNRCVD |
+------------------+-----------------------------------+-----------+
| SYN | Update Peer Verifier; Send SYNACK | SYNRCVD |
+------------------+-----------------------------------+-----------+
| ACK && B && C | Send ACK | ESTAB |
+------------------+-----------------------------------+-----------+
| ACK && !(B && C) | Send RSTACK | SYNRCVD |
+==================================================================+
Note: When sending SYNACK determine if recalculation of
predictabilities should be executed or suppressed and send
appropriate flag accompanying SYNACK. See Figure 6.
Note: When sending ACK, if received SYNACK requested suppression of
predictability recalculation, determine if recalculation of
predictabilities should be executed or be suppressed and send
appropriate flag accompanying ACK; otherwise send ACK indicating
recalculation should be executed.
State: ESTAB
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| SYN || SYNACK | Send ACK (notes 2, 4, and 5) | ESTAB |
+------------------+-----------------------------------+-----------+
| ACK && B && C | Send ACK (notes 3, 4, and 5) | ESTAB |
+------------------+-----------------------------------+-----------+
| ACK && !(B && C) | Send RSTACK | ESTAB |
+==================================================================+
Lindgren, et al. Expires April 26, 2011 [Page 47]
Internet-Draft PRoPHET October 2010
Note 2: No more than two ACKs should be sent within any time
period of length defined by the timer. Thus, one ACK MUST be sent
every time the timer expires. In addition, one further ACK may be
sent between timer expirations if the incoming message is a SYN or
SYNACK. This additional ACK allows the Hello functions to reach
synchronisation more quickly.
Note 3: No more than one ACK should be sent within any time period
of length defined by the timer.
Note 4: No more than one ACK should be sent within any time period
of length defined by the timer.
Note 5: When sending ACK, if received SYNACK requested suppression
of predictability recalculation, determine if recalculation of
predictabilities should be executed or be suppressed and send
appropriate flag accompanying ACK; otherwise send ACK indicating
recalculation should be executed.
5.2.2. Interaction with Nodes Using Version 1 of PRoPHET
There are existing implementations of PRoPHET based on drafts of this
specification prior to version 06 that use version 1 of the protocol.
There are two significant areas of difference between version 1 and
version 2 as described in this document:
o the delivery predictability update equations were significantly
different, and in the case of the transitivity equation (Equation
3) could lead to incorrect behavior in some circumstances in
version 1, and
o the versions of the SYNACK and ACK messages requesting suppression
of the recalculation phase were not present in version 1.
A node implementing version 2 of the PRoPHET protocol as defined in
this document MAY choose either to ignore a communication opportunity
with a node that sends a HELLO message indicating that it uses
version 1 or it may partially downgrade and respond to messages as if
it were a version 1 node. This means that the version field in all
message headers MUST contain 1, and the SYNACK and ACK messages
indicating use of recalculation phase suppression MUST not be used
(i.e., recalculation will always be done). It is RECOMMENDED that
the version 2 node use the metric update equations defined in this
document even when communicating with a version 1 node as this will
Lindgren, et al. Expires April 26, 2011 [Page 48]
Internet-Draft PRoPHET October 2010
partially inhibit the problems with the transitivity equation in
version 1, and that the version 2 node should modify any received
metrics that are greater than (1 - delta) to be (1 - delta) to avoid
becoming a 'sink' for bundles that are not destined for this node.
Generally, nodes using version 1 should be upgraded if at all
possible because of problems that have been identified.
5.3. Information Exchange and Bundle Passing Phase
After the Hello messages have been exchanged, and the nodes are in
the ESTAB state, the information exchange and bundle passing phase is
initiated. This section describes the procedure and shows the state
transitions necessary in this phase, and the following sections
describe the various TLVs passed in this phase in detail.
5.3.1. State Tables
This section shows the state transitions that nodes goes through
during the information exchange and bundle passing phase. State
tables are given for a "Listener" and for a "Initiator". Both nodes
should assume both roles during this phase, and this can be done
either concurrently or sequentially, depending on the implementation.
Listener:
---------
State: WAIT_DICT
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Dictionary rcvd | Update local dictionary (note 1) | WAIT_RIB |
+------------------+-----------------------------------+-----------+
| ACK received | | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| Timeout(peer) | Send ACK (note 2) | WAIT_DICT |
+==================================================================+
Lindgren, et al. Expires April 26, 2011 [Page 49]
Internet-Draft PRoPHET October 2010
State: WAIT_RIB
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| RIB TLV received | Save RIB information. | WAIT_RIB |
| More RIB TLVs=1 | Wait for more RIB TLVs. | |
+------------------+-----------------------------------+-----------+
| RIB TLV received | Update P ; Send offer (note 3) | OFFER |
| More RIB TLVs=0 | | |
+------------------+-----------------------------------+-----------+
| ACK received | | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| Dictionary rcvd | Update local dictionary | WAIT_RIB |
+------------------+-----------------------------------+-----------+
| Bundle req rcd | Send ACK | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| Timeout(peer) | Send ACK | WAIT_DICT |
+==================================================================+
State: OFFER
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Bundle req rcvd | Send requested bundle(s) | OFFER |
| #req bundles!=0 | | |
+------------------+-----------------------------------+-----------+
| Bundle req rcvd | (note 4) | WAIT_DICT |
| #req bundles==0 | | |
+------------------+-----------------------------------+-----------+
| ACK received | | WAIT_DICT |
+------------------+-----------------------------------+-----------+
| Timeout(info) | Resend bundle offer (note 5) | OFFER |
+------------------+-----------------------------------+-----------+
| Dictionary or ACK| Resend bundle offer | OFFER |
| received | | |
+==================================================================+
Lindgren, et al. Expires April 26, 2011 [Page 50]
Internet-Draft PRoPHET October 2010
Note 1: Both the dictionary and the RIB TLVs may come in the same
PRoPHET message. In that case, the state will change to WAIT_RIB
and the RIB will then immediately be processed.
Note 2: Send an ACK if the timer for the peering node expires.
Either the link has been broken, and then the link setup will
restart, or it will trigger the information exchange phase to
restart.
Note 3: When the RIB is received it is possible for the PRoPHET
agent to update its delivery predictabilities according to
Section 2.1.1. If the SYNACK message requests suppression of
recalculation (function 130) and the ACK message requests
suppression of recalculation (function 131) then recalculation
MUST be suppressed. In all other cases recalculation must be
done. The delivery predictabilities and the RIB is then used
together with the forwarding strategy in use to create a bundle
offer TLV. This is sent to the peering node.
Note 4: No more bundles are requested by the other node, transfer
is complete.
Note 5: No response to the bundle offer has been received before
the timer expired, so we resend the bundle offer.
Initiator:
----------
State: CREATE_DR
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Always | Create & send dict & RIB (note 1) | SEND_DR |
+==================================================================+
Lindgren, et al. Expires April 26, 2011 [Page 51]
Internet-Draft PRoPHET October 2010
State: SEND_DR
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Timeout(info) | Resend dictionary & RIB (note 2) | SEND_DR |
+------------------+-----------------------------------+-----------+
| Bundle offer rcvd| Send bundle request | REQUEST |
+==================================================================+
State: REQUEST
+==================================================================+
| Condition | Action | New State |
+==================+===================================+===========+
| Timeout(info) | Send bundle request for | REQUEST |
| | missing bundles (note 3) | |
+------------------+-----------------------------------+-----------+
| Bundle rcvd && | Wait for more bundles | REQUEST |
| REQ not fulfilled| (note 4) | |
+------------------+-----------------------------------+-----------+
| Bundle rcvd && | Send empty bundle request | REQUEST |
| REQ fulfilled | (note 4) | |
+------------------+-----------------------------------+-----------+
| ACK received | | CREATE_DR |
+==================================================================+
Note 1: The Initiator always starts by creating dictionary and RIB
TLVs, and send them to its peering node.
Note 2: No response to the RIB has been received before the timer
expired, so we resend the dictionary and RIB TLVs.
Note 3: If the timer expires, and not all requested bundles have
been received, send a new bundle request for the missing bundles.
Lindgren, et al. Expires April 26, 2011 [Page 52]
Internet-Draft PRoPHET October 2010
Note 4: While bundles are received, but there still are requested
bundles that have not been received, continue waiting for more
bundles. If all desired bundles have been received, send an empty
bundles request message to the peering node to signal that no more
bundles should be passed.
Lindgren, et al. Expires April 26, 2011 [Page 53]
Internet-Draft PRoPHET October 2010
6. Security Considerations
Currently, PRoPHET does not specify any special security measures.
As a routing protocol for intermittently connected networks, PRoPHET
is a target for various attacks. The various known possible
vulnerabilities are discussed in this section.
The attacks described here are not problematic if all nodes in the
network can be trusted and are working towards a common goal. If
there exist such a set of nodes, but there also exist malicious
nodes, these security problems can be solved by introducing an
authentication mechanism when two nodes meet, for example using a
public key system. Thus, only nodes that are known to be members of
the trusted group of nodes are allowed to participate in the routing.
This of course introduces the additional problem of key distribution,
but that is not addressed here.
Where suitable, the mechanisms (such as key management and bundle
authentication or integrity checks) and terminology specified by the
Bundle Security Protocol[symington_09] is to be used.
6.1. Attacks on the Operation of the Protocol
There are a number of kinds of attacks on the operation of the
protocol that it would be possible to stage on a PRoPHET network.
The attacks and possible remedies are listed here.
6.1.1. Black Hole Attack
A malicious node sets its delivery predictabilities for all
destinations to a value close to or exactly equal to 1 and/or
requests all bundles from nodes it meets, and does not forward any
bundles. This has two effects, both causing messages to be drawn
towards the black hole, instead of to its correct destination.
1. A node encountering a malicious node will try to forward all its
bundles to the malicious node, creating the belief that the
bundle has been very favorably forwarded. Depending on the
forwarding strategy and queueing policy in use, this might hamper
future forwarding of the bundle and/or lead to premature dropping
of the bundle.
2. Due to the transitivity, the delivery predictabilities reported
by the malicious node will affect the delivery predictabilities
of other nodes. This will create a gradient for all destinations
with the black hole as the "center of gravity" towards which all
bundles traverse. This should be particularly severe in
connected parts of the network.
Lindgren, et al. Expires April 26, 2011 [Page 54]
Internet-Draft PRoPHET October 2010
6.1.1.1. Attack detection
A node receiving a set of delivery predictabilities that are all at
or close to 1 should be suspicious. Similarly, a node which accepts
all bundles and offers none might be considered suspicious. However
these conditions are not impossible in normal operation.
6.1.1.2. Attack prevention/solution
To prevent this attack, authentication between nodes that meet needs
to be present. Nodes can also inspect the received metrics and
bundle acceptances/offers for suspicious patterns and terminate
communications with nodes that appear suspicious. The natural
evolution of delivery predictabilities should mean that a genuine
node would not be permanently ostracised even if the values lead to
termination of a communication opportunity on one occasion. The
epidemic nature of PRoPHET would mean that such a termination would
not generally lead to non-delivery of bundles.
6.1.2. Limited Black Hole Attack/Identity Spoofing
A malicious node misrepresents itself by claiming to be someone else.
The effects of this attack are:
1. The effects of the black hole attack listed above hold for this
attack as well, with the exception that only the delivery
predictabilities and bundles for one particular destination are
affected. This could be used to "steal" the data that should be
going to a particular node.
2. In addition to the above problems, PRoPHET ACKs will be issued
for the bundles that are delivered to the malicious node. This
will cause these bundles to be removed from the network, reducing
the chance that they will reach their real destination.
6.1.2.1. Attack Detection
It is possible for the destination to detect that this kind of attack
has occurred (but it will not be able to prevent it) if it receives a
PRoPHET ACK for a bundle destined to itself but for which it did not
receive the corresponding bundle.
6.1.2.2. Attack Prevention/Solution
To prevent this attack, authentication between nodes that meet needs
to be present.
Lindgren, et al. Expires April 26, 2011 [Page 55]
Internet-Draft PRoPHET October 2010
6.1.3. Fake PRoPHET ACKs
A malicious node may issue fake PRoPHET ACKs for all bundles (or only
bundles for a certain destination if the attack is targeted at a
single node) carried by nodes it meet. The affected bundles will be
deleted from the network, greatly reducing their probability of being
delivered to the destination.
6.1.3.1. Attack Prevention/Solution
If a public key cryptography system is in place, this attack can be
prevented by mandating that all PRoPHET ACKs be signed by the
destination. Similarly to other solutions using public key
cryptography, this introduces the problem of key distribution.
6.1.4. Bundle Store Overflow
After encountering and receiving the delivery predictability
information from the victim, a malicious node may generate a large
number of fake bundles for the destination for which the victim has
the highest delivery predictability. This will cause the victim to
most likely accept these bundles, filling up its bundle storage,
possibly at the expense of other, legitimate, bundles. This problem
is transient as the messages will be removed when the victim meets
the destination and delivers the messages.
6.1.4.1. Attack Detection
If it is possible for the destination to figure out that the bundles
it is receiving are fake, it could report that malicious actions are
underway.
6.1.4.2. Attack Prevention/Solution
This attack could be prevented by requiring sending nodes to sign all
bundles they send. By doing this, intermediate nodes could verify
the integrity of the messages before accepting them for forwarding.
6.1.5. Bundle Store Overflow with Delivery Predictability Manipulation
A more sophisticated version of the attack in the previous section
can be attempted. The effect of the previous attack was lessened
since the destination node of the fake bundles existed. This caused
fake bundles to be purged from the network when the destination was
encountered. The malicious node may now use the transitive property
of the protocol to boost the victim's delivery predictabilities for a
non-existent destination. After this, it creates a large number of
fake bundles for this non-existent destination and offers them to the
Lindgren, et al. Expires April 26, 2011 [Page 56]
Internet-Draft PRoPHET October 2010
victim. As before, these bundles will fill up the bundle storage of
the victim. The impact of this attack will be greater as there is no
probability of the destination being encountered and the bundles
being acknowledged. Thus, they will remain in the bundle storage
until they time out (the malicious node may set the timeout to a
large value) or until they are evicted by the queueing policy.
The delivery predictability for the fake destination may spread in
the network due to the transitivity, but this is not a problem, as it
will eventually age and fade away.
The impact of this attack could be increased if multiple malicious
nodes collude, as network resources can be consumed at a greater
speed and at many different places in the network simultaneously.
6.2. Interactions with External Routing Domains
Users may opt to connect two regions of sparsely connected nodes
through a connected network such as the Internet where another
routing protocol is running. To this network, PRoPHET traffic would
look like any other application layer data. Extra care must be taken
in setting up these gateway nodes and their interconnections to make
sure that malicious nodes cannot use them to launch attacks on the
infrastructure of the connected network. In particular, the traffic
generated should not be significantly more than what a single regular
user end host could create on the network.
Lindgren, et al. Expires April 26, 2011 [Page 57]
Internet-Draft PRoPHET October 2010
7. IANA Considerations
Following the policies outlined in "Guidelines for Writing an IANA
Considerations Section in RFCs" (RFC 5226 [RFC5226]), the following
name spaces are defined in PRoPHET:
o DTN Routing Protocol Number Section 4.1
o PRoPHET Version Section 4.1
o Header FlagsSection 4.1
o Result Section 4.1
o Code Section 4.1
o Error and Log Messages
o TLV Type Section 4.2
o Hello TLV Flags
o Error TLV Flags
o Routing Information Base Dictionary TLV Flags Section 4.3.3
o Routing Information Base TLV Flags Section 4.3.3
o RIB entry Flag Section 4.3.4
o Bundle Offer/Response TLV FlagsSection 4.3.5
The following subsections lists the registries that are requested to
be created. Initial values for the registries are given below;
future assignments are to be made through the Specification Required
policy. Where specific values are defined in the IANA registries to
be setup according to the specifications in the sub-sections below,
the registry should refer to this document as defining the
allocation.
Lindgren, et al. Expires April 26, 2011 [Page 58]
Internet-Draft PRoPHET October 2010
7.1. DTN Routing Protocol Number
The encoding of the Protocol Number field is:
+------------------+-----------+------------------------+
| Protocol | Value | Allocation Control |
+------------------+-----------+------------------------+
| PRoPHET Protocol | 0x00 | |
| | | |
| Reserved | 0x01-0xEF | Specification required |
| | | |
| Private | 0xF0-0xFE | Experimental |
+------------------+-----------+------------------------+
7.2. PRoPHET Version
The encoding of the PRoPHET Version field is:
+------------------------------+-----------+------------------------+
| Version | Value | Allocation Control |
+------------------------------+-----------+------------------------+
| Reserved | 0x00 | |
| | | |
| Earlier Drafts | 0x01 | |
| | | |
| This protocol | 0x02 | |
| | | |
| Reserved | 0x03-0xEF | Specification required |
| | | |
| Private | 0xF0-0xFE | Experimental |
| | | |
| Reserved for future | 0xFF | Specification required |
| expansion | | |
+------------------------------+-----------+------------------------+
Lindgren, et al. Expires April 26, 2011 [Page 59]
Internet-Draft PRoPHET October 2010
7.3. Header Flags
The flags for the Header are:
+--------------+----------+------------------------+
| Bit Position | Meaning | Explanation |
+--------------+----------+------------------------+
| Bit 0 | Reserved | Specification required |
| | | |
| Bit 1 | Reserved | Specification required |
| | | |
| Bit 2 | Reserved | Specification required |
| | | |
| Bit 3 | Reserved | Specification required |
+--------------+----------+------------------------+
7.4. Result
The encoding of the result field is:
+---------------+-------------+------------------------+
| Result Value | Value | Allocation Control |
+---------------+-------------+------------------------+
| NoSuccessAck | 0x01 | |
| | | |
| AckAll | 0x02 | |
| | | |
| Success | 0x03 | |
| | | |
| Failure | 0x04 | |
| | | |
| ReturnReceipt | 0x05 | |
| | | |
| Reserved | 0x06 - 0x7F | Specification required |
| | | |
| Private | 0x80 - 0xFF | Experimental |
+---------------+-------------+------------------------+
Lindgren, et al. Expires April 26, 2011 [Page 60]
Internet-Draft PRoPHET October 2010
7.5. Code
The encoding for Code is:
+----------------------+-------------+------------------------+
| Message Type | Range | Allocation Control |
+----------------------+-------------+------------------------+
| Error Responses | 0x00 - 0x33 | Specification required |
| | | |
| Success Responses | 0x34 - 0x66 | Specification required |
| | | |
| Event Codes | 0x67 - 0x99 | Specification required |
| | | |
| Private | 0xA0 - 0xFE | Experimental |
| | | |
| Error TLV in message | 0xFF | |
+----------------------+-------------+------------------------+
7.6. Error and Log Messages
Messages defined in range 0x00 - 0x33 of Code defined in Section 7.5
+-----------------+-------+--------------------+
| Error Message | Value | Allocation Control |
+-----------------+-------+--------------------+
| Undefined Error | 1 | |
+-----------------+-------+--------------------+
Lindgren, et al. Expires April 26, 2011 [Page 61]
Internet-Draft PRoPHET October 2010
7.7. TLV Type
The list of TLVs Defined for PRoPHET are:
+--------------------+-------------+------------------------+
| Type | Value | Allocation Control |
+--------------------+-------------+------------------------+
| Hello TLV | 0x01 | |
| | | |
| Error TLV | 0x02 | |
| | | |
| Reserved | 0x03 - 0x9F | Specification required |
| | | |
| RIB dictionary TLV | 0xA0 | |
| | | |
| RIB TLV | 0xA1 | |
| | | |
| Bundle Offer | 0xA2 | |
| | | |
| Bundle Response | 0xA3 | |
| | | |
| Reserved | 0xA4 - 0xCF | Specification required |
| | | |
| Private | 0xD0 - 0xFF | Experimental |
+--------------------+-------------+------------------------+
7.8. Hello TLV Flags
The following flags are defined for the Hello TLV:
+----------+-------------+------------------------+
| Type | Value | Allocation Control |
+----------+-------------+------------------------+
| SYN | 0x01 | |
| | | |
| SYNACK | 0x02 | |
| | | |
| ACK | 0x03 | |
| | | |
| RSTACK | 0x04 | |
| | | |
| Reserved | 0x05 - 0x0F | Specification required |
| | | |
| Private | 0x10 - 0xFF | Experimental |
+----------+-------------+------------------------+
Lindgren, et al. Expires April 26, 2011 [Page 62]
Internet-Draft PRoPHET October 2010
7.9. Error TLV Flags
The following flags are defined for the Error TLV:
+----------+-------------+------------------------+
| Type | Value | Allocation Control |
+----------+-------------+------------------------+
| Reserved | 0x00 - 0x7F | Specification required |
| | | |
| Private | 0x80 - 0xFF | Experimental |
+----------+-------------+------------------------+
7.10. RIB Base Dictionary TLV Flags
The following flags are defined for the RIB Base Dictionary TLV:
+----------+-------------+------------------------+
| Type | Value | Allocation Control |
+----------+-------------+------------------------+
| Reserved | 0x00 - 0x7F | Specification required |
| | | |
| Private | 0x80 - 0xFF | Experimental |
+----------+-------------+------------------------+
7.11. RIB TLV Flags
The following flags are defined for the Error TLV:
+----------+-------------+------------------------+
| Type | Value | Allocation Control |
+----------+-------------+------------------------+
| Reserved | 0x00 - 0x7F | Specification required |
| | | |
| Private | 0x80 - 0xFF | Experimental |
+----------+-------------+------------------------+
Lindgren, et al. Expires April 26, 2011 [Page 63]
Internet-Draft PRoPHET October 2010
7.12. RIB Flags
The following flags are defined for the Error TLV:
+----------+-------------+------------------------+
| Type | Value | Allocation Control |
+----------+-------------+------------------------+
| Reserved | 0x00 - 0x7F | Specification required |
| | | |
| Private | 0x80 - 0xFF | Experimental |
+----------+-------------+------------------------+
7.13. Bundle Flags
The flags for the Bundle Offer and Response TLV are:
+--------------+-----------------+------------------------+
| Bit Position | Meaning | Allocation Control |
+--------------+-----------------+------------------------+
| Bit 0 | Bundle Accepted | |
| | | |
| Bit 1 | Reserved | Specification required |
| | | |
| Bit 2 | Reserved | Specification required |
| | | |
| Bit 3 | Reserved | Specification required |
| | | |
| Bit 4 | Reserved | Specification required |
| | | |
| Bit 5 | Reserved | Specification required |
| | | |
| Bit 6 | Reserved | Specification required |
| | | |
| Bit 7 | PRoPHET ACK | |
+--------------+-----------------+------------------------+
Lindgren, et al. Expires April 26, 2011 [Page 64]
Internet-Draft PRoPHET October 2010
8. Implementation Experience
Multiple independent implementations of the PRoPHET protocol exist.
The first implementation is written in Java, and has been optimized
to run on the Lego MindStorms platform that has very limited
resources. Due to the resource constraints, some parts of the
protocol have been simplified or omitted, but the implementation
contains all the important mechanisms to ensure proper protocol
operation. The implementation is also highly modular and can be run
on another system with only minor modifications (it has currently
been shown to run on the Lego MindStorms platform and on regular
laptops).
Another implementation is written in C++ and runs in the OmNet++
simulator to enable testing and evaluation of the protocol and new
features. Experience and feedback from the implementors on early
versions of the protocol have been incorporated into the current
version.
An implementation compliant to version 2 of the predecessor draft
(draft-lindgren-prophet-02.txt) has been written at Baylor
University. This implementation has been integrated into the DTN2
reference implementation.
An implementation of the protocol in C++ was developed by one of the
authors (Samo Grasic) at Lulea University of Technology (LTU) as part
of the Saami Networking Connectivity project (see Section 9) and
continues to track the development of the protocol. This work is now
part of the Networking for Communications Challenged Communities
(N4C) project and is used in N4C testbeds.
Lindgren, et al. Expires April 26, 2011 [Page 65]
Internet-Draft PRoPHET October 2010
9. Deployment Experience
During a week in August 2006, a proof-of-concept deployment of a DTN
system, using the LTU PRoPHET implementation for routing was made in
the Swedish mountains - the target area for the Saami Network
Connectivity project [ccnc07][doria_02]. Four fixed camps with
application gateways, one Internet gateway, and seven mobile relays
were deployed. The deployment showed PRoPHET to be able to route
bundles generated by different applications such as e-mail and web
caching.
Within the realms of the SNC and N4C projects, multiple other
deployments, both during summer and winter conditions have been done
in various scale during 2007-2009. [winsdr08]
Lindgren, et al. Expires April 26, 2011 [Page 66]
Internet-Draft PRoPHET October 2010
10. Acknowledgements
The authors would like to thank Olov Schelen and Kaustubh S. Phanse
for contributing with valuable feedback regarding various aspects of
the protocol. We would also like to thank all other reviewers and
the DTNRG chairs for the feedback in the process of developing the
protocol. The Hello TLV mechanism is loosely based on Adjacency
message developed for RFC3292. Luka Birsa and Jeff Wilson have
provided us with feedback from doing implementations of the protocol
based on various preliminary versions of the draft. Their feedback
has helped us make the draft easier to read for an implementor and
has improved the protocol.
Lindgren, et al. Expires April 26, 2011 [Page 67]
Internet-Draft PRoPHET October 2010
11. References
11.1. Normative References
[RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol
Specification", RFC 5050, November 2007.
11.2. Informative References
[RFC4838] Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst,
R., Scott, K., Fall, K., and H. Weiss, "Delay-Tolerant
Network Architecture", RFC 4838, April 2007.
[RFC5226] Narten, T. and H. Tveit Alvestrand, "Guidelines for
Writing an IANA Considerations Section in RFCs", RFC 5226,
May 2008.
[ccnc07] Lindgren, A. and A. Doria, "Experiences from Deploying a
Real-life DTN System", Proceedings of the 4th Annual IEEE
CONSUMER COMMUNICATIONS and NETWORKING CONFERENCE (CCNC
2007), Las Vegas, Nevada, USA , January 2007.
[doria_02]
Doria, A., Uden, M., and D. Pandey, "Providing
connectivity to the Saami nomadic community", Proceedings
of the 2nd International Conference on Open Collaborative
Design for Sustainable Innovation (dyd 02), Bangalore,
India , December 2002.
[lindgren_06]
Lindgren, A. and K. Phanse, "Evaluation of Queueing
Policies and Forwarding Strategies for Routing in
Intermittently Connected Networks", Proceedings of
COMSWARE 2006 , January 2006.
[symington_09]
Symington, S., Farrell, S., Weiss, H., and P. Lovell,
"Bundle Security Protocol Specification", Internet Draft
draft-irtf-dtnrg-bundle-security-11.txt , November 2009.
[vahdat_00]
Vahdat, A. and D. Becker, "Epidemic Routing for Partially
Connected Ad Hoc Networks", Duke University Technical
Report CS-200006, April 2000.
[winsdr08]
Lindgren, A., Doria, A., Lindblom, J., and M. Ek,
"Networking in the Land of Northern Lights - Two Years of
Lindgren, et al. Expires April 26, 2011 [Page 68]
Internet-Draft PRoPHET October 2010
Experiences from DTN System Deployments", Proceedings of
the ACM Wireless Networks and Systems for Developing
Regions Workshop(WiNS-DR), San Francisco, California,
USA , September 2008.
Lindgren, et al. Expires April 26, 2011 [Page 69]
Internet-Draft PRoPHET October 2010
Appendix A. PRoPHET Example
To help grasp the concepts of PRoPHET, an example is provided to give
a understanding of the transitive property of the delivery
predictability, and the basic operation of PRoPHET. In Figure 11, we
revisit the scenario where node A has a message it wants to send to
node D. In the bottom right corner of subfigures a)-c), the delivery
predictability tables for the nodes are shown. Assume that nodes C
and D encounter each other frequently (Figure 11a) ), making the
delivery predictability values they have for each other high. Now
assume that node C also frequently encounters node B (Figure 11b) ).
B and C will get high delivery predictability values for each other,
and the transitive property will also increase the value B has for D
to a medium level. Finally, node B meets node A (Figure 11c) ) that
has a message for node D. Figure 11d) shows the message exchange
between node A and node B. Summary vectors and delivery
predictability information is exchanged, delivery predictabilities
are updated, and node A then realized that P_(b,d) > P_(a,d), and
thus forwards the message for D to node B.
Lindgren, et al. Expires April 26, 2011 [Page 70]
Internet-Draft PRoPHET October 2010
+----------------------------+ +----------------------------+
| | | |
| C | | D |
| D | | |
| B | | B C |
| | | |
| | | |
| | | |
| | | |
| A* | | A* |
+-------------+--------------+ +-------------+--------------+
| A | B | C | D | | A | B | C | D |
|B:low |A:low |A:low |A:low | |B:low |A:low |A:low |A:low |
|C:low |C:low |B:low |B:low | |C:low |C:high|B:high |B:low |
|D:low |D:low |D:high |C:high| |D:low |D:med |D:high |C:high|
+-------------+--------------+ +-------------+--------------+
a) b)
+----------------------------+ A B
| | | |
| D | |Summary vector&delivery pred|
| | |--------------------------->|
| C | |Summary vector&delivery pred|
| | |<---------------------------|
| | | |
| B* | Update delivery predictabilities
| A | | |
| | Packet for D not in SV |
+-------------+--------------+ P(b,d)>P(a,d) |
| A | B | C | D | Thus, send |
|B:low |A:low |A:low |A:low | | |
|C:med |C:high|B:high |B:low | | Packet for D |
|D:low+|D:med |D:high |C:high| |--------------------------->|
+-------------+--------------+ | |
c) d)
Figure 11: PRoPHET example
Lindgren, et al. Expires April 26, 2011 [Page 71]
Internet-Draft PRoPHET October 2010
Appendix B. Neighbor Discovery Example
This section outlines an example of a simple neighbor discovery
protocol that can be run in-between PRoPHET and underlying layer in
case lower layers do not provide methods for neighbor discovery. It
assumes that the underlying layer supports broadcast messages as
would be the case if a wireless infrastructure was involved.
Each node needs to maintain a list of its active neighbors. The
operation of the protocol is as follows:
1. Every BEACON_INTERVAL milliseconds, the node does a local
broadcast of a beacon that contains its identity and address, as
well as the BEACON_INTERVAL value used by the node.
2. Upon reception of a beacon, the following can happen:
1. The sending node is already in the list of active neighbors.
Update its entry in the list with the current time, and the
node's BEACON_INTERVAL if it has changed.
2. The sending node is not in the list of active neighbors. Add
the node to the list of active neighbors and record the
current time and the node's BEACON_INTERVAL. Notify the
PRoPHET agent that a new neighbor is available ("New
Neighbor", as described in Section 2.4).
3. If a beacon has not been received from a node in the list of
active neighbors within a time period of NUM_ACCEPTED_LOSSES *
BEACON_INTERVAL (for the BEACON_INTERVAL used by that node), it
should be assumed that this node is no longer a neighbor. The
entry for this node should be removed from the list of active
neighbors, and the PRoPHET agent should be notified that a
neighbor has left ("Neighbor Gone", as described in Section 2.4).
Lindgren, et al. Expires April 26, 2011 [Page 72]
Internet-Draft PRoPHET October 2010
Authors' Addresses
Anders F. Lindgren
Swedish Institute of Computer Science
Box 1263
Kista SE-164 29
SE
Phone: +46707177269
Email: andersl@sics.se
URI: http://www.sics.se/~andersl
Avri Doria
Lulea University of Technology
Lulea SE-971 87
SE
Phone:
Email: avri@acm.org
URI: http://psg.com/~avri
Elwyn Davies
Folly Consulting
Soham
UK
Phone:
Email: elwynd@folly.org.uk
URI:
Samo Grasic
Lulea University of Technology
Lulea SE-971 87
SE
Phone:
Email: samo.grasic@ltu.se
URI:
Lindgren, et al. Expires April 26, 2011 [Page 73]