tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 6693

 
 
 

Probabilistic Routing Protocol for Intermittently Connected Networks

Part 4 of 4, p. 93 to 113
Prev RFC Part

 


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

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

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

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

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

Top      Up      ToC       Page 98 
      *  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   |               |
        +----------------------------+-----------+---------------+

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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