Network Working Group A. Lindgren Internet-Draft A. Doria Expires: January 18, 2006 Lulea University of Technology July 17, 2005 Probabilistic Routing Protocol for Intermittently Connected Networks draft-lindgren-dtnrg-prophet-01 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. 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 material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on January 18, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This document describes a routing protocol for intermittently connected 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 special cases of networks where the Delay-Tolerant Network architecture[1] is applicable. We define PRoPHET, a Probabilistic Routing Protocol using History of Encounters and Transitivity for intermittently connected networks. The document Lindgren & Doria Expires January 18, 2006 [Page 1] Internet-Draft PRoPHET July 2005 presents an architectural overview followed by the protocol specification. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Relation to the Delay-Tolerant Networking architecture . . 7 2. Architecture . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 PRoPHET . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Delivery predictability calculation . . . . . . . . . 8 2.1.2 Forwarding strategies . . . . . . . . . . . . . . . . 9 2.2 Bundle Agent to Routing Agent Interface . . . . . . . . . 9 3. Operation . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1 Neighbor Awareness . . . . . . . . . . . . . . . . . . . . 10 3.2 Information Exchange Phase . . . . . . . . . . . . . . . . 10 3.2.1 Routing Information Base Dictionary . . . . . . . . . 11 3.3 Routing Algorithm . . . . . . . . . . . . . . . . . . . . 11 3.4 Bundle Passing . . . . . . . . . . . . . . . . . . . . . . 11 3.4.1 Custody . . . . . . . . . . . . . . . . . . . . . . . 12 3.5 When a bundle reaches its destination . . . . . . . . . . 12 3.6 Forwarding strategies . . . . . . . . . . . . . . . . . . 13 3.7 Queueing policies . . . . . . . . . . . . . . . . . . . . 14 3.8 Aging of delivery predictability . . . . . . . . . . . . . 15 4. Protocol Description . . . . . . . . . . . . . . . . . . . . . 16 4.1 Messages . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 Header . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.3 TLV Structure . . . . . . . . . . . . . . . . . . . . . . 20 4.4 TLVs . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.4.1 Hello TLV . . . . . . . . . . . . . . . . . . . . . . 20 4.4.2 Error TLV . . . . . . . . . . . . . . . . . . . . . . 26 4.4.3 Routing Information Base Dictionary TLV . . . . . . . 27 4.4.4 Routing Information Base TLV . . . . . . . . . . . . . 28 4.4.5 Bundle Offer and Response TLV . . . . . . . . . . . . 29 5. Security Considerations . . . . . . . . . . . . . . . . . . . 31 6. Implementation Experience . . . . . . . . . . . . . . . . . . 31 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 31 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 32 A. PRoPHET Example . . . . . . . . . . . . . . . . . . . . . . . 33 Intellectual Property and Copyright Statements . . . . . . . . 35 Lindgren & Doria Expires January 18, 2006 [Page 2] Internet-Draft PRoPHET July 2005 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 (see Section 1.1 for a survey of such scenarios). To introduce the work, 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 Tolerant Networking [1]). It would then be possible to exploit the mobility of a subset of the nodes to bring messages closer to their destination by transferring messages 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 wireless communication. As shown in sub-figures (a) - (d), the mobility of the nodes allow the message to first be transferred to node B, then to node C, and finally node C moves within range of node D and can deliver the message to its final destination. This technique is known as 'transitive networking'. Real users are not likely to move around randomly, but rather move in a predictable fashion based on repeating behavioral patterns (e.g., Lindgren & Doria Expires January 18, 2006 [Page 3] Internet-Draft PRoPHET July 2005 going to work or the market and returning home) such that if a node has visited a location several times before, it is likely that it will visit that location again. In previously discussed mechanisms to enable communication in intermittently connected networks, such as Epidemic Routing[3], very general approaches have been taken to the problem at hand. There have, however, not been any attempts to make use of assumed knowledge of different (mobility) properties of the nodes in the network in a truly distributed way. 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. We define an alternative to 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 applicable. Lindgren & Doria Expires January 18, 2006 [Page 4] Internet-Draft PRoPHET July 2005 +----------------------------+ +----------------------------+ | ___ | | ___ | | ___ / \ | | / \ | | / \ ( 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. A probabilistic metric called delivery predictability is defined in this document. The document then goes on to define a probabilistic routing protocol using this metric. 1.1 Background The kinds of communication networks addressed in this document are only viable for applications that can tolerate long delays and are able to deal with extended periods of being disconnected. In practice there are many different scenarios and situations where communication is inherently intermittent, and in which it is of high value to develop methods of communication despite the limitations on applications. This section presents a selection of situations where it appears that these kinds of communication offer valuable solutions to realistic problems. Lindgren & Doria Expires January 18, 2006 [Page 5] Internet-Draft PRoPHET July 2005 The aboriginal Saami population of reindeer herders in the north of Sweden follow the movement of the reindeer and when in their summer camps, no fixed infrastructure is available. The herders would find it useful to be able to communicate with the rest of the world through, for example, mobile relays attached to snowmobiles and ATVs[5], or carried as small devices in a backpack, to (for example) obtain weather reports, conduct herd business and maintain the supply of educational material for children in the parties. Similar problems exist between rural villages in India and in other regions where the Internet infrastructure is less well developed or is only available at prices which are beyond the means of the local population. The DakNet project[6] has deployed store-and-forward networks connecting a number of villages through relays on buses and motorcycles in India and Cambodia. While satellite networks often rely on very well defined trajectories and predictable encounters, there are cases when connectivity between them can be intermittent and opportunistic. In military war-time scenarios and disaster recovery situations, soldiers, human rights observers, or rescue personnel are often in hostile environments where no infrastructure can be assumed to be present, or if present, cannot be trusted. Furthermore, the units may be sparsely distributed so that connectivity between them is intermittent and infrequent. In sensor networks, a large number of sensors are usually deployed in the area in which measurements are to be performed. To ensure connectivity among the sensors and to get measurements from the entire area, it is common to deploy a very large number of sensors. If sensors can be mobile and transitive communication techniques can be used between them, the number of sensors required can be reduced, and new areas where regular sensor networks have been too expensive or difficult to deploy, can be monitored. Experiments have been done with attaching sensors to seals, vastly increasing the number of oceanic temperature readings compared to using a number of fixed sensors, and in a similar project sensors are attached to whales[4]. To allow scientists to analyze the collected data, it must somehow be transferred to a data sink, even though connectivity among the seals and whales is very sparse and intermittent, so the mobility of the animals (and their occasional encounters with each other and networked buoys at feeding grounds) must be relied upon for successful data delivery. Resembling the vast areas of the oceans are the plains of Africa in that there are many remote areas with almost no fixed infrastructure and where satellite connectivity is prohibitively expensive. In the ZebraNet project, an attempt is made to gain a better understanding of the life and movements of the wildlife in a certain part of Africa by equipping zebras with tracking collars communicating in fashions similar to the ones Lindgren & Doria Expires January 18, 2006 [Page 6] Internet-Draft PRoPHET July 2005 described above. Yet another example concerns weather monitoring of large areas such as a national park, where a number of electronic display boards showing weather reports from other parts of the park have been installed. By equipping hikers with small networked devices, their mobility through the park can be used to spread the weather information throughout the entire park. 1.2 Relation to the Delay-Tolerant Networking architecture The Delay-Tolerant Networking (DTN) architecture[1] 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, such as the case is in this scenario. The architecture defines some different types of intermittent contacts. The ones called opportunistic and predicted are the ones addressed by this proposal. 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 on if a contact will be present soon. The DTN architecture also defines the bundle protocol [2], 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 bundling protocol also provides end- to-end addressing and reliability. We build on the bundling protocol, using bundles as the basic transfer unit. 2. Architecture 2.1 PRoPHET To make use of the observations of the non-randomness of mobility and to improve routing performance we consider doing 'probabilistic routing' and propose PRoPHET, a Probabilistic Routing Protocol using History of Encounters and Transitivity. To accomplish this, we establish a probabilistic metric called 'delivery predictability', 0 <= P_(A,B) <= 1, at every node A for each known destination B. This indicates how likely it is that this Lindgren & Doria Expires January 18, 2006 [Page 7] Internet-Draft PRoPHET July 2005 node will be able to deliver a message to that destination. The operation of PRoPHET is similar to that of the Epidemic Routing protocol presented in [3]. When two nodes meet, they exchange summary vectors which contain the identifiers of the bundles each node carries, and also a delivery predictability vector containing the delivery predictability information for destinations known by the nodes. This additional information is used to update the internal delivery predictability vector as described below. After that, the information in the summary vector is used to decide which messages to request from the other node based on the forwarding strategy used (as discussed in Section 2.1.2). 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 message to a certain node. The calculation of the delivery predictabilities has three parts. The first thing to do is to update the metric whenever a node is encountered, so that nodes that are often encountered have a high delivery predictability. This calculation is shown in Equation 1, where 0 <= P_encounter <= 1 is an initialization constant. P_(A,B) = P_(A,B)_old + ( 1 - 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 messages to each other, thus the delivery predictability values must age, being reduced in the process. The aging equation is shown in Equation 2, where 0 <= gamma <= 1 is the aging constant, and K is the number of time units that have elapsed since the last time the metric was aged. The 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 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 messages 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) = P_(A,C)_old + ( 1 - P_(A,C)_old ) * P_(A,B) * P_(B,C) * beta (3) Lindgren & Doria Expires January 18, 2006 [Page 8] Internet-Draft PRoPHET July 2005 2.1.2 Forwarding strategies 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. For starters, when a message arrives at a node, there might not be a path to the destination available so the node have to buffer the message and upon each encounter with another node, the decision must be made on whether or not to transfer a particular message. Furthermore, it may also be sensible to forward a message to multiple nodes to increase the probability that a message is really delivered to its destination. Unfortunately, these decisions are not trivial to make. In some cases it might be sensible to select a fixed threshold and only give a message to nodes that have a delivery predictability over that threshold for the destination of the message. 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 messages to. Furthermore, there is the problem of deciding how many nodes to give a certain message to. Distributing a message to a large number of nodes will of course increase the probability of delivering a message to its destination, but in return, more system resources will be wasted. On the other hand, giving a message to only a few nodes (maybe even just a single node) will use less system resources, but the probability of delivering a message is lower, and the incurred delay high. Nodes MAY define their own forwarding strategies that take into account the special conditions posed by the nodes, and local resource constraints. Some default strategies that should be suitable for most normal operation are defined in Section 3.6. 2.2 Bundle Agent to Routing Agent Interface 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 & Doria Expires January 18, 2006 [Page 9] Internet-Draft PRoPHET July 2005 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 Makes the bundle agent drop a specified bundle. 3. Operation 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 achieve this, periodic local broadcasts of Hello messages are performed. The details of the Hello message exchange are described in Section 4.4.1. When a new neighbor has been detected, the protocol enters the information exchange phase. 3.2 Information Exchange Phase The first step in the information exchange phase is for the protocol to send a Routing Information Base Dictionary message to the node it is peering with. This is a dictionary of the addresses of the nodes that will be listed in the Routing Information Base. After this, a Routing Information Base message is sent. This message contains a list of the addresses that the node has heard of, and the corresponding P-values for those nodes, and flags describing the capabilities of that node. Upon reception of this message, the node updates its P-values table according to the equations in Section 2.1.1, and using its forwarding strategy (see Section 2.1.2) determines which of its stored bundles it wish to offer the peering node. After making this decision, a Bundle Offer message is prepared, listing the bundle identifiers and their destination for all bundles it wishes to offer the other node. If the Bundle Offer message lists a bundle for which the destination was not included in the first Routing Information Base Dictionary message sent, a new such message is sent with an incremental update of the dictionary. When the peering node has a dictionary with all necessary addresses, the Bundle Offer message is sent to it. The Bundle Offer message Lindgren & Doria Expires January 18, 2006 [Page 10] Internet-Draft PRoPHET July 2005 also contains a list of PRoPHET ACKs (see Section 3.5). If a new bundle arrives at a node after the initial information exchange phase with a neighbor which might be a candidate to forward that bundle to, a new Bundle Offer message MAY be sent to that node. Each node also keeps a PredUpdate timer for each neighbor that is set after each information exchange phase. When this timer expires, a new information exchange phase is initiated to update the P-values of the node. The recommended value for this timer is 10 times the Hello interval. 3.2.1 Routing Information Base Dictionary To reduce the overhead of the protocol, the Routing Information Base and Bundle Offer/Request messages utilize an address dictionary. This dictionary maps long variable length addresses to shorter 16 bit identifiers that are used in place of the addresses in subsequent messages. The dictionary established only persist through a single encounter with a node. 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. Recommended parameter values +==================================+ | Parameter | Recommended value | +==================================+ | P_encounter | 0.75 | +----------------------------------+ | beta | 0.25 | +----------------------------------+ | gamma | 0.98 | +==================================+ Figure 2 3.4 Bundle Passing Upon reception of the Bundle Offer message, the node inspects the Lindgren & Doria Expires January 18, 2006 [Page 11] Internet-Draft PRoPHET July 2005 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 message to its peering node, which in response to that sends the requested bundle. If a node has some bundles it prefers to get over other (e.g. bundles that it can deliver to their final destination), it MAY request the bundles in that priority order as there is no guarantee that the nodes will remain in contact with each other long enough to transfer all the desired 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 (which is found out during the information exchange phase). When a node accepts custody of a bundle, it MUST keep that bundle until it gets an ACK that it has been delivered to its destination, until another node accepts custody of the bundle, or until its time to live has expired. When custody of a bundle has been accepted by another node, the previous custodian MAY delete that bundle if needed to free up local resources. When custody of a bundle is transferred, the new custodian SHOULD inherit any retransmission timers associated with the bundle from the old custodian. The exact policy used to decide when to offer and accept custody is something that each node must decide on, and is not currently defined. It is believed that the custody policy in most cases will be a stricter version of the forwarding strategy. 3.5 When a bundle reaches its destination When a bundle reaches its destination, a PRoPHET ACK for that bundle is issued. A PRoPHET ACK is a confirmation that a bundle has been delivered to its destination within the PRoPHET domain. When nodes exchange Bundle Offer messages, bundles that have been ACKed are also listed, having the "PRoPHET ACK" flag set. The node that receive 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 to grow indefinitely, each PRoPHET ACK should have a timeout that MUST NOT be longer than the timeout of the bundle the ACK corresponds to. Lindgren & Doria Expires January 18, 2006 [Page 12] Internet-Draft PRoPHET July 2005 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 are different things. PRoPHET ACKs are only valid within the PRoPHET domain, while bundle ACKs are end-to-end acknowledgments that may go outside of the PRoPHET domain. Care should be taken to ensure that bundle acknowledgments as well as PRoPHET ACKs are created in an efficient way. 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. We use the following notation in our descriptions below. A and B are the nodes that meet, and the strategies are described as they should be followed by node A. The destination node is D. P_(X,Y) denotes the delivery predictability for node X to destination Y, and NF is the number of times A has given the bundle to someone else. GRTR Forward the message only if P_(B,D) > P_(A,D). When two nodes meet, a message is sent to the other node if the delivery predictability of the destination of the message is higher at the other node. The first node does not delete the message 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 message in the future). GTMX Forward the message only if P_(B,D) > P_(A,D) && NF < NF_max. Lindgren & Doria Expires January 18, 2006 [Page 13] Internet-Draft PRoPHET July 2005 This strategy is like the previous one, but each bundle is given to at most NF_max other nodes. GRTR+ Forward the message only if P_(B,D) > P_(A,D) && P_(B,D) > P_max, where P_max is the largest delivery predictability the bundle has been sent to so far. This strategy is like GRTR, but nodes keep track of the largest P-value of any node it has forwarded this bundle to, and only forward the bundle if the currently encountered node has a greater P-value. GTMX+ Forward the message only if P_(B,D) > P_(A,D) && P_(B,D) > P_max && NF < NF_max. This strategy is like GTMX, but nodes keep track of P_max like in GRTR+. GRTRSort Select messages in descending order of the value of P_{(B,D) - P_(A,D). Forward the message only if P_(B,D) > P_(A,D). This strategy is like GRTR, but instead of just going through the message queue linearly, this strategy looks at the difference in P-values for each message between the two nodes, and forwards the messages with the largest difference first. As bandwidth limitations or disruptive connections may result in not all messages that would be desirable can be exchanged, it could be desirable to first send messages that get a large improvement in delivery predictability. GRTRMax Select messages in descending order of P_(B,D). Forward the message only if P_(B,D) > P_(A,D). This strategy begins by considering the messages 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 messages 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 queuing 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. Lindgren & Doria Expires January 18, 2006 [Page 14] Internet-Draft PRoPHET July 2005 FIFO Handle the queue in a 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 probable first Keep a value FP for each bundle in the queue, initialized to zero. Each time the bundle is forwarded, update FP according to Equation 4, where P is the predictability metric the node the bundle is forwarded to has for its destination. FP_new = FP_old + ( 1 - FP_old ) * P (4) The bundle with the highest FP value is the first to be dropped. SHLI - Evict shortest life time first Each bundle has a timeout value, when it should be deleted. If this policy is used, the bundle with the shortest remaining life time is the first to be dropped. LEPR - Evict least probable first Since the node is least likely to deliver a bundle for which it has a low P-value, drop the bundle for which the node has the lowest P-value, and that has been forwarded at least MF times. More than one queueing policy MAY be combined in a 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. Worth noting is that obviously nodes MUST NOT drop bundles for which it has custody. 3.8 Aging of delivery predictability To ensure proper properties of the delivery predictabilities, the parameters determining the rate of aging used for the metric must be set depending on the scenario the protocol will be operating in. Lindgren & Doria Expires January 18, 2006 [Page 15] Internet-Draft PRoPHET July 2005 4. Protocol Description 4.1 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Header ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ TLV 1 ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . | ~ . ~ | . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ TLV n ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Basic message format Lindgren & Doria Expires January 18, 2006 [Page 16] Internet-Draft PRoPHET July 2005 4.2 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Version | Flags | Result | Code | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Receiver Instance | Sender Instance | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Transaction Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |S| SubMessage Number | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Message Body ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4: Header Version This version of the PRoPHET Protocol = 1. Flags TBD 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. Lindgren & Doria Expires January 18, 2006 [Page 17] Internet-Draft PRoPHET July 2005 The encoding of the result field is: 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. In a Hello message, the Code field is used to determine the function of the message. 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. The encoding is: PRoPHET Error messages 0x000 - 0x0FF Reserved 0x100 - 0x4FE Error TLV in message 0x4FF Sender Instance For messages with the Hello SYN, Hello SYNACK, and Hello ACK functions, 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 18-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, 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. Receiver Instance For messages 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. Lindgren & Doria Expires January 18, 2006 [Page 18] Internet-Draft PRoPHET July 2005 Transaction Identifier Used to associate a message with its response message. S-flag If I is set then the SubMessage Number field indicates the total number of SubMessage segments that compose the entire message. If it is not set then the SubMessage Number field indicates the sequence number of this SubMessage segment within the whole message. the I field will only be set i 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 submessage in a sequence of submessages, the I flag will be set and this field will contain the total count of submessage segments. Length Length in octets of the message including headers and message body. The protocol also uses a pseudo header with information that MUST be provided by the underlying communication layer. The following pseudo header fields are defined: Sender 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 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 (e.g. an IP or MAC address) 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. Lindgren & Doria Expires January 18, 2006 [Page 19] Internet-Draft PRoPHET July 2005 4.3 TLV Structure All TLVs have the following format. 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ TLV Data ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 7: TLV Format TLV Type Specific TLVs are defined in Section 4.4. Each TLV will have specific fields defined specific to the function of that TLV. TLV Flags These are defined per TLV type. TLV Length Length of the TLV in octets, including the TLV header and any nested TLVs. 4.4 TLVs 4.4.1 Hello TLV The Hello TLV is used for neighbor detection between two PRoPHET nodes. Hello messages with the SYN function are broadcasted periodically as beacons. The Hello TLV is the first TLV exchanged between PRoPHET nodes when they encounter each other. Once a communications are established between two PRoPHET nodes, the Hello TLV will be sent once for each interval as defined in the interval timer. If 2 intervals go by without receiving a Hello TLV on an ESTAB connection, the connection will be assumed broken. Lindgren & Doria Expires January 18, 2006 [Page 20] Internet-Draft PRoPHET July 2005 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | type=0x01 | resv | HS | TLV Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Timer | Name Length | Sender Name (variable) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 8: Hello TLV Format HS Specifies the function of the Hello TLV. Four functions are specified for the Hello TLV: SYN: Code = 1 SYNACK: Code = 2 ACK: Code = 3 RSTACK: Code = 4. TLV Data Timer The Timer field is used to inform the receiver of the timer value used in the Hello processing of the sender. The timer specifies the nominal time between periodic Hello messages. It is a constant for the duration of session. The timer field is specified in units of 100ms. Name Length The Name Length field is used to specify the length of the Sender Name field in octets. If the name 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 Name from the Hello TLV. Sender Name The Sender Name field specifies the routable DTN name of the sender that is to be used in updating routing information and making forwarding decisions. 4.4.1.1 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 Lindgren & Doria Expires January 18, 2006 [Page 21] Internet-Draft PRoPHET July 2005 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. 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. "&&" 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. The period of the timer is unspecified but a value of one second is suggested. 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 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 Lindgren & Doria Expires January 18, 2006 [Page 22] Internet-Draft PRoPHET July 2005 sent within any time period of length defined by the timer. o A connections 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. Lindgren & Doria Expires January 18, 2006 [Page 23] Internet-Draft PRoPHET July 2005 4.4.1.1.1 State Tables Lindgren & Doria Expires January 18, 2006 [Page 24] Internet-Draft PRoPHET July 2005 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 | +==================================================================+ 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 | +==================================================================+ State: ESTAB +==================================================================+ | Condition | Action | New State | +==================+===================================+===========+ | SYN || SYNACK | Send ACK (note 2) | ESTAB | +------------------+-----------------------------------+-----------+ | ACK && B && C | Send ACK (note 3) | ESTAB | +------------------+-----------------------------------+-----------+ | ACK && !(B && C) | Send RSTACK | ESTAB | +==================================================================+ 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 Lindgren & Doria Expires January 18, 2006 [Page 25] Internet-Draft PRoPHET July 2005 synchronisation more quickly. Note 3: No more than one ACK should be sent within any time period of length defined by the timer. Figure 12 4.4.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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | type=0x02 | Flags | TLV Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Data ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 13: Error TLV Format TLV Flags TBD TLV Data TBD Lindgren & Doria Expires January 18, 2006 [Page 26] Internet-Draft PRoPHET July 2005 4.4.3 Routing Information Base Dictionary TLV The Routing Information Base Dictionary includes the list of addresses used in making routing decisions. The referents remain constant for the duration of a session and can be used by both the Routing Information Base messages and the bundle offer messages. Header = 0xA0 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | type = 0xA0 | Flags | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RIBD Entry Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ ~ ~ Variable Length Routing Address Strings ~ ~ ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Routing Address String +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | String ID 1 | Length | Resv | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ Routing Address String 1(variable) ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | . | ~ . ~ | . | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | String ID n | Length | Resv | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Routing Address String n ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 14: Routing Information Base dictionary Lindgren & Doria Expires January 18, 2006 [Page 27] Internet-Draft PRoPHET July 2005 TLV Flags TBD RIBD Entry Count Number of entries in the database String ID 16 bit 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. 4.4.4 Routing Information Base TLV The Routing Information Base includes the information needed by the PRoPHET algorithm to make decisions on Routing. Header = 0xA1 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | type = 0xA1 | Flags | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RIB String Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RIB String ID 1 | P-Value | RIB Flag 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ . ~ ~ . ~ ~ . ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RIBD String ID n | P-Value | RIB Flags n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 15: Routing Information Base Header Flags Lindgren & Doria Expires January 18, 2006 [Page 28] Internet-Draft PRoPHET July 2005 The encoding of the Header flag field relates to the capabilities of the Source node sending the RIB: Flag 0: Relay Node 0b1 Flag 1: Custody Node 0b1 Flag 2: Internet GW Node 0b1 Flag 3: Reserved 0b1 Flag 4: Reserved 0b1 Flag 5: Reserved 0b1 Flag 6: Reserved 0b1 Flag 7: Reserved 0b1 RIBD String Count Number of routing entries in the TLV RIB String ID ID string as predefined in the dictionary TLV. PRoPHET routing probability as calculated according to the algorithm in section (add ref.) RIBD Flag The encoding of the RIB flag field is: Flag 0: Relay Node 0b1 Flag 1: Custody Node 0b1 Flag 2: Internet GW Node 0b1 Flag 3: Reserved 0b1 Flag 4: Reserved 0b1 Flag 5: Reserved 0b1 Flag 6: Reserved 0b1 Flag 7: Reserved 0b1 4.4.5 Bundle Offer and Response TLV After the routing information has been passed, a relay node will ask another relay 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 P-values as explained in (add xref to explanation section). The Response message is identical to the request message with the exception that the flag indicate acceptance of the bundle. Lindgren & Doria Expires January 18, 2006 [Page 29] Internet-Draft PRoPHET July 2005 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | type = 0xA2 | Flags | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bundle Offer Count | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bundle String Id 1 | B_flags | resv | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bundle 1 Creation Timestamp | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ~ . ~ ~ . ~ ~ . ~ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bundle String Id n | flags | resv | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Bundle n Creation Timestamp | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 18: Bundle Offer and Response TLV Flags TBD Bundle Offer Count Number of bundle off entries. Bundle String Id ID string as predefined in the dictionary TLV. The encoding of the B_Flags in the request are: Flag 0: Custody Offered 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 Lindgren & Doria Expires January 18, 2006 [Page 30] Internet-Draft PRoPHET July 2005 The encoding B_flag values for the send are: Flag 0: Custody Accepted 0b1 Flag 1: Bundle Accepted 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 5. Security Considerations The security implications have not been addressed yet... 6. Implementation Experience Currently, two independent implementations of the PRoPHET protocol exist. The first implementation is written in Java, and is designed to run on a regular computer system as, for example, a laptop. The other implementation is also implemented in Java, but 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). Experience and feedback from the implementors on early versions of the protocol have been incorporated into the current version. 7. Acknowledgements We would like to thank Olov Schelen, Kaustubh S. Phanse, and Elwyn Davies for valuable discussions regarding various aspects of the protocol. The Hello TLV mechanism is loosely based on Adjacency message developed for RFC3292. Implementation feedback has been received from Christophe Baraer, Luka Birsa, Oskar Burman, Therese Wiklund, Keith Moriarty, and Mikael Kunto. 8. References [1] Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R., Scott, K., Fall, K., and H. Weiss, "Delay-Tolerant Network Architecture", Internet Draft draft-irtf-dtnrg-arch-01.txt, Lindgren & Doria Expires January 18, 2006 [Page 31] Internet-Draft PRoPHET July 2005 October 2003. [2] Scott, K. and S. Burleigh, "Bundle Protocol Specification", Internet Draft draft-irtf-dtnrg-bundle-spec-01.txt, October 2003. [3] Vahdat, A. and D. Becker, "Epidemic Routing for Partially Connected Ad Hoc Networks", Duke University Technical Report CS- 200006, April 2000. [4] Small, T. and Z. Haas, "The Shared Wireless Infostation Model - A New Ad Hoc Networking Paradigm (or Where there is a Whale, there is a Way)", Proceedings of The Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2003) pp 233-244, June 2003. [5] 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. [6] Pentland, A., Fletcher, R., and A. Hasson, "A Road to Universal Broadband Connectivity", Proceedings of the 2nd International Conference on Open Collaborative Design for Sustainable Innovation (dyd 02), Bangalore, India , December 2002. Authors' Addresses Anders F. Lindgren Lulea University of Technology Lulea SE-971 87 Sweden Phone: +46920491489 Email: dugdale@sm.luth.se URI: http://www.sm.luth.se/~dugdale Lindgren & Doria Expires January 18, 2006 [Page 32] Internet-Draft PRoPHET July 2005 Avri Doria Lulea University of Technology Lulea SE-971 87 Sweden Phone: Email: avri@acm.org URI: 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 21, 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 21a) ), making the delivery predictability values they have for each other high. Now assume that node C also frequently encounters node B (Figure 21b) ). 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 21c) ) that has a message for node D. Figure 21d) 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 & Doria Expires January 18, 2006 [Page 33] Internet-Draft PRoPHET July 2005 +----------------------------+ +----------------------------+ | | | | | 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 21: PRoPHET example Lindgren & Doria Expires January 18, 2006 [Page 34] Internet-Draft PRoPHET July 2005 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Lindgren & Doria Expires January 18, 2006 [Page 35]