RFC 6693
Probabilistic Routing Protocol for Intermittently Connected Networks
Pages: 113
Experimental
Experimental
Part 4 of 4 – Pages 93 to 113
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 [RFC6257] are to be used.6.1. Attacks on the Operation of the Protocol
There are a number of kinds of attacks on the operation of the protocol that it would be possible to stage on a PRoPHET network. The attacks and possible remedies are listed here.6.1.1. Black-Hole Attack
A malicious node sets its delivery predictabilities for all destinations to a value close to or exactly equal to 1 and/or requests all bundles from nodes it meets, and does not forward any bundles. This has two effects, both causing messages to be drawn towards the black hole instead of to their correct destinations. 1. A node encountering a malicious node will try to forward all its bundles to the malicious node, creating the belief that the bundle has been very favorably forwarded. Depending on the forwarding strategy and queueing policy in use, this might hamper future forwarding of the bundle and/or lead to premature dropping of the bundle. 2. Due to the transitivity, the delivery predictabilities reported by the malicious node will affect the delivery predictabilities of other nodes. This will create a gradient for all destinations with the black hole as the "center of gravity" towards which all bundles traverse. This should be particularly severe in connected parts of the network.6.1.1.1. Attack Detection
A node receiving a set of delivery predictabilities that are all at or close to 1 should be suspicious. Similarly, a node that accepts all bundles and offers none might be considered suspicious. However, these conditions are not impossible in normal operation.6.1.1.2. Attack Prevention/Solution
To prevent this attack, authentication between nodes that meet needs to be present. Nodes can also inspect the received metrics and bundle acceptances/offers for suspicious patterns and terminate communications with nodes that appear suspicious. The natural evolution of delivery predictabilities should mean that a genuine node would not be permanently ostracized even if the values lead to
termination of a communication opportunity on one occasion. The epidemic nature of PRoPHET would mean that such a termination rarely leads to non-delivery of bundles.6.1.2. Limited Black-Hole Attack / Identity Spoofing
A malicious node misrepresents itself by claiming to be someone else. The effects of this attack are: 1. The effects of the black-hole attack listed above hold for this attack as well, with the exception that only the delivery predictabilities and bundles for one particular destination are affected. This could be used to "steal" the data that should be going to a particular node. 2. In addition to the above problems, PRoPHET ACKs will be issued for the bundles that are delivered to the malicious node. This will cause these bundles to be removed from the network, reducing the chance that they will reach their real destination.6.1.2.1. Attack Detection
The destination can detect that this kind of attack has occurred (but it cannot prevent the attack) when it receives a PRoPHET ACK for a bundle destined to itself but for which it did not receive the corresponding bundle.6.1.2.2. Attack Prevention/Solution
To prevent this attack, authentication between nodes that meet needs to be present.6.1.3. Fake PRoPHET ACKs
A malicious node may issue fake PRoPHET ACKs for all bundles (or only bundles for a certain destination if the attack is targeted at a single node) carried by nodes it met. The affected bundles will be deleted from the network, greatly reducing their probability of being delivered to the destination.6.1.3.1. Attack Prevention/Solution
If a public key cryptography system is in place, this attack can be prevented by mandating that all PRoPHET ACKs be signed by the destination. Similarly to other solutions using public key cryptography, this introduces the problem of key distribution.
6.1.4. Bundle Store Overflow
After encountering and receiving the delivery predictability information from the victim, a malicious node may generate a large number of fake bundles for the destination for which the victim has the highest delivery predictability. This will cause the victim to most likely accept these bundles, filling up its bundle storage, possibly at the expense of other, legitimate, bundles. This problem is transient as the messages will be removed when the victim meets the destination and delivers the messages.6.1.4.1. Attack Detection
If it is possible for the destination to figure out that the bundles it is receiving are fake, it could report that malicious actions are underway.6.1.4.2. Attack Prevention/Solution
This attack could be prevented by requiring sending nodes to sign all bundles they send. By doing this, intermediate nodes could verify the integrity of the messages before accepting them for forwarding.6.1.5. Bundle Store Overflow with Delivery Predictability Manipulation
A more sophisticated version of the attack in the previous section can be attempted. The effect of the previous attack was lessened since the destination node of the fake bundles existed. This caused fake bundles to be purged from the network when the destination was encountered. The malicious node may now use the transitive property of the protocol to boost the victim's delivery predictabilities for a non-existent destination. After this, it creates a large number of fake bundles for this non-existent destination and offers them to the victim. As before, these bundles will fill up the bundle storage of the victim. The impact of this attack will be greater as there is no probability of the destination being encountered and the bundles being acknowledged. Thus, they will remain in the bundle storage until they time out (the malicious node may set the timeout to a large value) or until they are evicted by the queueing policy. The delivery predictability for the fake destination may spread in the network due to the transitivity, but this is not a problem, as it will eventually age and fade away. The impact of this attack could be increased if multiple malicious nodes collude, as network resources can be consumed at a greater speed and at many different places in the network simultaneously.
6.2. Interactions with External Routing Domains
Users may opt to connect two regions of sparsely connected nodes through a connected network such as the Internet where another routing protocol is running. To this network, PRoPHET traffic would look like any other application-layer data. Extra care must be taken in setting up these gateway nodes and their interconnections to make sure that malicious nodes cannot use them to launch attacks on the infrastructure of the connected network. In particular, the traffic generated should not be significantly more than what a single regular user end host could create on the network.7. IANA Considerations
Following the policies outlined in "Guidelines for Writing an IANA Considerations Section in RFCs" (RFC 5226 [RFC5226]), the following name spaces are defined in PRoPHET. o For fields in the PRoPHET message header (Section 4.1): * DTN Routing Protocol Number * PRoPHET Protocol Version * PRoPHET Header Flags * PRoPHET Result Field * PRoPHET Codes for Success and Codes for Failure o Identifiers for TLVs carried in PRoPHET messages: * PRoPHET TLV Type (Section 4.2) o Definitions of TLV Flags and other flag fields in TLVs: * Hello TLV Flags (Section 4.3.1) * Error TLV Flags (Section 4.3.2) * Routing Information Base (RIB) Dictionary TLV Flags (Section 4.3.3) * Routing Information Base (RIB) TLV Flags (Section 4.3.4) * Routing Information Base (RIB) Flags per entry (Section 4.3.4) * Bundle Offer and Response TLV Flags (Section 4.3.5)
* Bundle Offer and Response B Flags per offer or response
(Section 4.3.5)
The following subsections list the registries that have been created.
Initial values for the registries are given below; future assignments
for unassigned values are to be made through the Specification
Required policy. Where specific values are defined in the IANA
registries according to the specifications in the subsections below,
the registry refers to this document as defining the allocation.
7.1. DTN Routing Protocol Number
The encoding of the Protocol Number field in the PRoPHET header
(Section 4.1) is:
+--------------------------+-----------+---------------+
| Protocol | Value | Reference |
+--------------------------+-----------+---------------+
| PRoPHET Protocol | 0x00 | This document |
| Unassigned | 0x01-0xEF | |
| Private/Experimental Use | 0xF0-0xFF | This document |
+--------------------------+-----------+---------------+
7.2. PRoPHET Protocol Version
The encoding of the PRoPHET Version field in the PRoPHET header
(Section 4.1) is:
+----------------------------+-----------+---------------+
| Version | Value | Reference |
+----------------------------+-----------+---------------+
| Reserved (do not allocate) | 0x00 | This document |
| PRoPHET v1 | 0x01 | This document |
| PRoPHET v2 | 0x02 | This document |
| Unassigned | 0x03-0xEF | |
| Private/Experimental Use | 0xF0-0xFE | This document |
| Reserved | 0xFF | |
+----------------------------+-----------+---------------+
7.3. PRoPHET Header Flags
The following Flags are defined for the PRoPHET Header (Section 4.1): +------------+--------------+-----------+ | Meaning | Bit Position | Reference | +------------+--------------+-----------+ | Unassigned | Bit 0 | | | Unassigned | Bit 1 | | | Unassigned | Bit 2 | | | Unassigned | Bit 3 | | +------------+--------------+-----------+7.4. PRoPHET Result Field
The encoding of the Result field in the PRoPHET header (Section 4.1) is: +--------------------------+-------------+---------------+ | Result Value | Value | Reference | +--------------------------+-------------+---------------+ | Reserved | 0x00 | This document | | NoSuccessAck | 0x01 | This document | | AckAll | 0x02 | This document | | Success | 0x03 | This document | | Failure | 0x04 | This document | | ReturnReceipt | 0x05 | This document | | Unassigned | 0x06 - 0x7F | | | Private/Experimental Use | 0x80 - 0xFF | This document | +--------------------------+-------------+---------------+7.5. PRoPHET Codes for Success and Codes for Failure
The encoding for Code field in the PRoPHET header (Section 4.1) for "Success" messages is: +--------------------------+-------------+---------------+ | Code Name | Values | Reference | +--------------------------+-------------+---------------+ | Generic Success | 0x00 | This document | | Submessage Received | 0x01 | This document | | Unassigned | 0x02 - 0x7F | | | Private/Experimental Use | 0x80 - 0xFF | This document | +--------------------------+-------------+---------------+
The encoding for Code in the PRoPHET header (Section 4.1) for "Failure" messages is: +----------------------------+-------------+---------------+ | Code Name | Values | Reference | +----------------------------+-------------+---------------+ | Reserved (do not allocate) | 0x00 - 0x01 | This document | | Unspecified Failure | 0x02 | This document | | Unassigned | 0x03 - 0x7F | | | Private/Experimental Use | 0x80 - 0xFE | This document | | Error TLV in Message | 0xFF | This document | +----------------------------+-------------+---------------+7.6. PRoPHET TLV Type
The TLV Types defined for PRoPHET (Section 4.2) are: +------------------------------+-------------+---------------+ | Type | Value | Reference | +------------------------------+-------------+---------------+ | Reserved (do not allocate) | 0x00 | This document | | Hello TLV | 0x01 | This document | | Error TLV | 0x02 | This document | | Unsassigned | 0x03 - 0x9F | | | RIB dictionary TLV | 0xA0 | This document | | RIB TLV | 0xA1 | This document | | Bundle Offer (deprecated) | 0xA2 | This document | | Bundle Response (deprecated) | 0xA3 | This document | | Bundle Offer (v2) | 0xA4 | This document | | Bundle Response (v2) | 0xA5 | This document | | Unassigned | 0xA6 - 0xCF | | | Private/Experimental Use | 0xD0 - 0xFF | This document | +------------------------------+-------------+---------------+
7.7. Hello TLV Flags
The following TLV Flags are defined for the Hello TLV (Section 4.3.1). Flag numbers 0, 1, and 2 are treated as a 3-bit unsigned integer with 5 of the 8 possible values allocated, and the other 3 reserved. The remaining bits are treated individually: +----------------------------+---------------------+---------------+ | Meaning | Value | Reference | +----------------------------+---------------------+---------------+ | | (Flags 0, 1, and 2) | | | Reserved (do not allocate) | 0b000 | This document | | SYN | 0b001 | This document | | SYNACK | 0b010 | This document | | ACK | 0b011 | This document | | RSTACK | 0b100 | This document | | Unassigned | 0b101 - 0b111 | | | | (Flags 3 - 7) | | | Unassigned | Flag 3 | | | Unassigned | Flag 4 | | | Unassigned | Flag 5 | | | Unassigned | Flag 6 | | | L Flag | Flag 7 | This document | +----------------------------+---------------------+---------------+7.8. Error TLV Flags
The TLV Flags field in the Error TLV (Section 4.3.2) is treated as an unsigned 8-bit integer encoding the Error TLV number. The following values are defined: +--------------------------+------------------+---------------+ | Error TLV Name | Error TLV Number | Reference | +--------------------------+------------------+---------------+ | Dictionary Conflict | 0x00 | This document | | Bad String ID | 0x01 | This document | | Unassigned | 0x02 - 0x7F | | | Private/Experimental Use | 0x80 - 0xFF | This document | +--------------------------+------------------+---------------+
7.9. RIB Dictionary TLV Flags
The following TLV Flags are defined for the RIB Base Dictionary TLV (Section 4.3.3): +----------------------------+--------------+---------------+ | Meaning | Bit Position | Reference | +----------------------------+--------------+---------------+ | Sent by Listener | Flag 0 | This document | | Reserved (do not allocate) | Flag 1 | This document | | Reserved (do not allocate) | Flag 2 | This document | | Unassigned | Flag 3 | | | Unassigned | Flag 4 | | | Unassigned | Flag 5 | | | Unassigned | Flag 6 | | | Unassigned | Flag 7 | | +----------------------------+--------------+---------------+7.10. RIB TLV Flags
The following TLV Flags are defined for the RIB TLV (Section 4.3.4): +----------------------------+--------------+---------------+ | Meaning | Bit Position | Reference | +----------------------------+--------------+---------------+ | More RIB TLVs | Flag 0 | This document | | Reserved (do not allocate) | Flag 1 | This document | | Reserved (do not allocate) | Flag 2 | This document | | Unassigned | Flag 3 | | | Unassigned | Flag 4 | | | Unassigned | Flag 5 | | | Unassigned | Flag 6 | | | Unassigned | Flag 7 | | +----------------------------+--------------+---------------+
7.11. RIB Flags
The following RIB Flags are defined for the individual entries in the RIB TLV (Section 4.3.4): +------------+--------------+-----------+ | Meaning | Bit Position | Reference | +------------+--------------+-----------+ | Unassigned | Flag 0 | | | Unassigned | Flag 1 | | | Unassigned | Flag 2 | | | Unassigned | Flag 3 | | | Unassigned | Flag 4 | | | Unassigned | Flag 5 | | | Unassigned | Flag 6 | | | Unassigned | Flag 7 | | +------------+--------------+-----------+7.12. Bundle Offer and Response TLV Flags
The following TLV Flags are defined for the Bundle Offer and Response TLV (Section 4.3.5): +------------------------------------+--------------+---------------+ | Meaning | Bit Position | Reference | +------------------------------------+--------------+---------------+ | More Offer/Response TLVs Following | Flag 0 | This document | | Unassigned | Flag 1 | | | Unassigned | Flag 2 | | | Unassigned | Flag 3 | | | Unassigned | Flag 4 | | | Unassigned | Flag 5 | | | Unassigned | Flag 6 | | | Unassigned | Flag 7 | | +------------------------------------+--------------+---------------+
7.13. Bundle Offer and Response B Flags
The following B Flags are defined for each Bundle Offer in the Bundle Offer and Response TLV (Section 4.3.5): +------------------------------------+--------------+---------------+ | Meaning | Bit Position | Reference | +------------------------------------+--------------+---------------+ | Bundle Accepted | Flag 0 | This document | | Bundle is a Fragment | Flag 1 | This document | | Bundle Payload Length Included in | Flag 2 | This document | | TLV | | | | Unassigned | Flag 3 | | | Unassigned | Flag 4 | | | Unassigned | Flag 5 | | | Unassigned | Flag 6 | | | PRoPHET ACK | Flag 7 | This document | +------------------------------------+--------------+---------------+8. Implementation Experience
Multiple independent implementations of the PRoPHET protocol exist. The first implementation is written in Java, and has been optimized to run on the Lego MindStorms platform that has very limited resources. Due to the resource constraints, some parts of the protocol have been simplified or omitted, but the implementation contains all the important mechanisms to ensure proper protocol operation. The implementation is also highly modular and can be run on another system with only minor modifications (it has currently been shown to run on the Lego MindStorms platform and on regular laptops). Another implementation is written in C++ and runs in the OmNet++ simulator to enable testing and evaluation of the protocol and new features. Experience and feedback from the implementers on early versions of the protocol have been incorporated into the current version. An implementation compliant to an Internet-Draft (which was posted in 2006 and eventually evolved into this RFC) has been written at Baylor University. This implementation has been integrated into the DTN2 reference implementation. An implementation of the protocol in C++ was developed by one of the authors (Samo Grasic) at Lulea University of Technology (LTU) as part of the Saami Networking Connectivity project (see Section 9) and continues to track the development of the protocol. This work is now
part of the Networking for Communications Challenged Communities (N4C) project and is used in N4C testbeds.9. Deployment Experience
During a week in August 2006, a proof-of-concept deployment of a DTN system, using the LTU PRoPHET implementation for routing was made in the Swedish mountains -- the target area for the Saami Network Connectivity project [ccnc07] [doria_02]. Four fixed camps with application gateways, one Internet gateway, and seven mobile relays were deployed. The deployment showed PRoPHET to be able to route bundles generated by different applications such as email and web caching. Within the realms of the SNC and N4C projects, multiple other deployments, both during summer and winter conditions, have been done at various scales during 2007-2010 [winsdr08]. An implementation has been made for Android-based mobile telephones in the Bytewalla project [bytewalla].10. Acknowledgements
The authors would like to thank Olov Schelen and Kaustubh S. Phanse for contributing valuable feedback regarding various aspects of the protocol. We would also like to thank all other reviewers and the DTNRG chairs for the feedback in the process of developing the protocol. The Hello TLV mechanism is loosely based on the Adjacency message developed for RFC 3292. Luka Birsa and Jeff Wilson have provided us with feedback from doing implementations of the protocol based on various preliminary versions of the document. Their feedback has helped us make the document easier to read for an implementer and has improved the protocol.11. References
11.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC5050] Scott, K. and S. Burleigh, "Bundle Protocol Specification", RFC 5050, November 2007.
11.2. Informative References
[CLAYER] Demmer, M., Ott, J., and S. Perreault, "Delay Tolerant Networking TCP Convergence Layer Protocol", Work in Progress, August 2012. [RFC1058] Hedrick, C., "Routing Information Protocol", RFC 1058, June 1988. [RFC4838] Cerf, V., Burleigh, S., Hooke, A., Torgerson, L., Durst, R., Scott, K., Fall, K., and H. Weiss, "Delay- Tolerant Networking Architecture", RFC 4838, April 2007. [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 5226, May 2008. [RFC6257] Symington, S., Farrell, S., Weiss, H., and P. Lovell, "Bundle Security Protocol Specification", RFC 6257, May 2011. [bytewalla] Prasad, M., "Bytewalla 3: Network architecture and PRoPHET implementation", Bytewalla Project, KTH Royal Institute of Technology, Stockholm, Sweden, October 2010, <http://www.bytewalla.org/sites/bytewalla.org/files/ Bytewalla3_Network_architecture_and_PRoPHET_v1.0.pdf>. [ccnc07] Lindgren, A. and A. Doria, "Experiences from Deploying a Real-life DTN System", Proceedings of the 4th Annual IEEE Consumer Communications and Networking Conference (CCNC 2007), Las Vegas, Nevada, USA, January 2007. [doria_02] Doria, A., Uden, M., and D. Pandey, "Providing connectivity to the Saami nomadic community", Proceedings of the 2nd International Conference on Open Collaborative Design for Sustainable Innovation (dyd 02), Bangalore, India, December 2002. [lindgren_06] Lindgren, A. and K. Phanse, "Evaluation of Queueing Policies and Forwarding Strategies for Routing in Intermittently Connected Networks", Proceedings of COMSWARE 2006, January 2006. [vahdat_00] Vahdat, A. and D. Becker, "Epidemic Routing for Partially Connected Ad Hoc Networks", Duke University Technical Report CS-200006, April 2000.
[winsdr08] Lindgren, A., Doria, A., Lindblom, J., and M. Ek, "Networking in the Land of Northern Lights - Two Years of Experiences from DTN System Deployments", Proceedings of the ACM Wireless Networks and Systems for Developing Regions Workshop (WiNS-DR), San Francisco, California, USA, September 2008.
Appendix A. PRoPHET Example
To help grasp the concepts of PRoPHET, an example is provided to give an understanding of the transitive property of the delivery predictability and the basic operation of PRoPHET. In Figure 13, we revisit the scenario where node A has a message it wants to send to node D. In the bottom right corner of subfigures a-c, the delivery predictability tables for the nodes are shown. Assume that nodes C and D encounter each other frequently (Figure 13a), making the delivery predictability values they have for each other high. Now assume that node C also frequently encounters node B (Figure 13b). Nodes B and C will get high delivery predictability values for each other, and the transitive property will also increase the value B has for D to a medium level. Finally, node B meets node A (Figure 13c), which has a message for node D. Figure 13d shows the message exchange between node A and node B. Summary vectors and delivery predictability information is exchanged, delivery predictabilities are updated, and node A then realizes that P_(b,d) > P_(a,d), and thus forwards the message for node D to node B.
+----------------------------+ +----------------------------+ | | | | | C | | D | | D | | | | B | | B C | | | | | | | | | | | | | | | | | | A* | | A* | +-------------+--------------+ +-------------+--------------+ | A | B | C | D | | A | B | C | D | |B:low |A:low |A:low |A:low | |B:low |A:low |A:low |A:low | |C:low |C:low |B:low |B:low | |C:low |C:high|B:high |B:low | |D:low |D:low |D:high |C:high| |D:low |D:med |D:high |C:high| +-------------+--------------+ +-------------+--------------+ (a) (b) +----------------------------+ A B | | | | | D | |Summary vector&delivery pred| | | |--------------------------->| | C | |Summary vector&delivery pred| | | |<---------------------------| | | | | | B* | Update delivery predictabilities | A | | | | | Packet for D not in SV | +-------------+--------------+ P(b,d)>P(a,d) | | A | B | C | D | Thus, send | |B:low |A:low |A:low |A:low | | | |C:med |C:high|B:high |B:low | | Packet for D | |D:low+|D:med |D:high |C:high| |--------------------------->| +-------------+--------------+ | | (c) (d) Figure 13: PRoPHET example
Appendix B. Neighbor Discovery Example
This section outlines an example of a simple neighbor discovery protocol that can be run in-between PRoPHET and the underlying layer in case lower layers do not provide methods for neighbor discovery. It assumes that the underlying layer supports broadcast messages as would be the case if a wireless infrastructure was involved. Each node needs to maintain a list of its active neighbors. The operation of the protocol is as follows: 1. Every BEACON_INTERVAL milliseconds, the node does a local broadcast of a beacon that contains its identity and address, as well as the BEACON_INTERVAL value used by the node. 2. Upon reception of a beacon, the following can happen: A. The sending node is already in the list of active neighbors. Update its entry in the list with the current time, and update the node's BEACON_INTERVAL if it has changed. B. The sending node is not in the list of active neighbors. Add the node to the list of active neighbors and record the current time and the node's BEACON_INTERVAL. Notify the PRoPHET agent that a new neighbor is available ("New Neighbor", as described in Section 2.4). 3. If a beacon has not been received from a node in the list of active neighbors within a time period of NUM_ACCEPTED_LOSSES * BEACON_INTERVAL (for the BEACON_INTERVAL used by that node), it should be assumed that this node is no longer a neighbor. The entry for this node should be removed from the list of active neighbors, and the PRoPHET agent should be notified that a neighbor has left ("Neighbor Gone", as described in Section 2.4).Appendix C. PRoPHET Parameter Calculation Example
The evolution of the delivery predictabilities in a PRoPHET node is controlled by three main equations defined in Section 2.1.2. These equations use a number of parameters that need to be appropriately configured to ensure that the delivery predictabilities evolve in a way that mirrors the mobility model that applies in the PRoPHET zone where the node is operating. When trying to describe the mobility model, it is more likely that the model will be couched in terms of statistical distribution of times between encounters and times to deliver a bundle in the zone. In this section, one possible way of deriving the PRoPHET parameters
from a more usual description of the model is presented. It should
be remembered that this may not be the only solution, and its
appropriateness will depend both on the overall mobility model and
the distribution of the times involved. There is an implicit
assumption in this work that these distributions can be characterized
by a normal-type distribution with a well-defined first moment
(mean). The exact form of the distribution is not considered here,
but more detailed models may wish to use more specific knowledge
about the distributions to refine the derivation of the parameters.
To characterize the model, we consider the following parameters:
P1 The time resolution of the model.
P2 The average time between encounters between nodes, I_typ, where
the identity of the nodes is not taken into account.
P3 The average number of encounters that a node has between meeting
a particular node and meeting the same node again.
P4 The average number of encounters needed to deliver a bundle in
this zone.
P5 The multiple of the average number of encounters needed to
deliver a bundle (P4) after which it can be assumed that a node
is not going to encounter a particular node again in the
foreseeable future so that the delivery predictability ought to
be decayed below P_first_threshold.
P6 The number of encounters between a particular pair of nodes that
should result in the delivery predictability of the encountered
node getting close to the maximum possible delivery
predictability (1 - delta).
We can use these parameters to derive appropriate values for gamma
and P_encounter_max, which are the key parameters in the evolution of
the delivery predictabilities. The values of the other parameters
P_encounter_first (0.5), P_first_threshold (0.1), and delta (0.01),
with the default values suggested in Figure 3, generally are not
specific to the mobility model, although in special cases
P_encounter_first may be different if extra information is available.
To select a value for gamma:
After a single, unrepeated encounter, the delivery predictability of
the encountered node should decay from P_encounter_first to
P_first_threshold in the expected time for P4 * P5 encounters. Thus:
P_first_threshold = P_encounter_first * gamma ^ ((P2 * P4 * P5)/P1) which can be rearranged as gamma = exp(ln(P_first_threshold/P_encounter_first) * P1 / (P2* P4 * P5)). Typical values of gamma will be less than 1, but very close to 1 (usually greater than 0.99). The value has to be stored to several decimal places of accuracy, but implementations can create a table of values for specific intervals to reduce the amount of on-the-fly calculation required. Selecting a value for P_encounter_max: Once gamma has been determined, the decay factor for the average time between encounters between a specific pair of nodes can be calculated: Decay_typ = gamma ^ ((P2 * P3)/P1) Starting with P_encounter_first, using Decay_typ and applying Equation 1 from Section 2.1.2 (P6 - 1) times, we can calculate the typical delivery predictability for the encountered node after P6 encounters. The nature of Equation 1 is such that it is not easy to produce a closed form that generates a value of P_encounter_max from the parameter values, but using a spreadsheet to apply the equation repeatedly and tabulate the results will allow a suitable value of P_encounter_max to be chosen very simply. The evolution is not very sensitive to the value of P_encounter_max, and values in the range 0.4 to 0.8 will generally be appropriate. A value of 0.7 is recommended as a default. Once a PRoPHET zone has been in operation for some time, the logs of the actual encounters can and should be used to check that the selected parameters were appropriate and to tune them as necessary. In the longer term, it may prove possible to install a learning mode in nodes so that the parameters can be adjusted dynamically to maintain best congruence with the mobility model that may itself change over time.
Authors' Addresses
Anders F. Lindgren Swedish Institute of Computer Science Box 1263 Kista SE-164 29 SE Phone: +46707177269 EMail: andersl@sics.se URI: http://www.sics.se/~andersl Avri Doria Technicalities Providence RI US EMail: avri@acm.org URI: http://psg.com/~avri Elwyn Davies Folly Consulting Soham UK EMail: elwynd@folly.org.uk Samo Grasic Lulea University of Technology Lulea SE-971 87 SE EMail: samo.grasic@ltu.se