• ProphetRouter

Prophet Router

Background

Prophet is an acronym for "probabilistic routing protocol using history of encounters and transitivity." The protocol operates on the assumption that human mobility is non-random, and that a knowledge of the history of previous encounters is a good indicator of future encounters. By leveraging transitive relays in combination with this history of encounters, Prophet exponentially increases its chances of successfully delivering messages.

The protocol has an initialization phase (HELLO), which in turn is dependent on dynamic NeighborDiscovery. After establishing a peering session across the newly-formed dynamic link, the peers alternate as listener and initiator in the Information Exchange phase. The initiator begins by sending a dictionary (RIBD) and a routing information base (RIB) to the listening peer. The listener responds by sending a list of bundles (possibly 0 entries) destined for nodes listed in the initiator's RIB, according to its forwarding strategy. The initiator requests bundles from the bundle offer, and concludes the protocol by sending an empty request after it has received all the requested bundles. The nodes switch roles to complete the other half of the protocol, then idle for 1/2 of HELLO_DEAD intervals before repeating the Information Exchange.

Design

See the PRoPHET website.

The DTN2 Prophet router is based on the March 2006 Prophet internet draft (Prophet I-D, hereafter). The ProphetRouter class extends BundleRouter and serves as the Prophet interface to the DTN bundling system. prophet::Controller is a member of ProphetRouter

Implementation

prophet::Node represents an individual route. prophet::Table is a collection of these routes. prophet::Encounter implements the protocol between Prophet peers. prophet::ProphetTLV manages the serialization and deserialization of protocol messages. prophet::Dictionary manages the indexing of the routes in prophet::Table into a RIBD for the protocol exchange. prophet::FwdStrategy is the base comparator for the various strategies. prophet::Repository is a priority queue that enforces the queuing policy, using the runtime selected comparator inherited from prophet::QueueComp. prophet::BundleOffer creates a sorted index of bundles to be sent as a Bundle offer, based on the forwarding strategy's comparator and its prophet::Decider.

Configuration

prophet set

The Prophet I-D mentions several parameters for tuning the router's performance. Below is a list of those implemented in the DTN Prophet router.

• age_period

  • The timeout, in seconds, of the timer that calculates Prophet nodes' aging. The same value is used by the timer that expires Prophet ACKs.

• beta

  • The scaling factor for the transivity of predictability; the Prophet I-D recommends a default value of 0.25.

• encounter

  • The initialization value for the direct-contact predictability calculation, defaults to 0.75.

• epsilon

  • The minimum predictability value before the route is discarded. The granularity of an eight-bit value limits this to 0.0039 (1/255).

• gamma

  • The aging constant used to diminish the predictability value of a route over time, defaults to 0.99.

• hello_dead

  • The maximum number of HELLO_INTERVALs before a remote session with a Prophet peer is considered unreachable.

• internet_gw

  • The flag that describes whether the Prophet router bridges to the Internet DTN region. Currently not used.

• kappa

  • The number of milliseconds in a given time unit, referenced by Equation 2 (predictability aging), p. 9, section 2.1.1 of the Prophet I-D.

• max_forward

  • The maximum number of times a bundle may be forwarded by the GTMX forwarding strategy.

• min_forward

  • The minimum number of times a bundle may be forwarded before eviction by the LEPR queuing policy.

• relay_node

  • The flag that describes whether this Prophet node will relay bundles to other nodes.

To tune the above parameters from the DTN CLI or bootstrap config file, call the prophet command, followed by set, followed by the parameter name listed above, followed by an appropriate value. For example:

• prophet set encounter 0.75

prophet queue_policy

To set the queue policy to one of the following, invoke prophet queue_policy=<policyname> Queue policies are discussed in detail in the Prophet I-D on p. 18, section 3.7.

• queue_policy

  • fifo

    • First In First Out: evict oldest first

  • mofo

    • Evict most forwarded first

  • mopr

    • Evict most favorably forwarded first

  • lmopr

    • Evict most favorably forwarded first (linear increase)

  • shli

    • Evict shortest lifetime first (the bundle that will expire soonest)

  • lepr

    • Evict least probable first (lowest predictability)

prophet fwd_strategy

To set the forwarding strategy to one of the following, invoke prophet fwd_strategy=<strategy> Forwarding strategies are discussed in detail in the Prophet I-D on p. 16, section 3.6.

• fwd_strategy

  • grtr

    • Forward if remote's predictability is greater than local's

  • gtmx

    • Forward if grtr and the bundle has been forwarded less than max_forward

  • grtr_plus

    • Forward if grtr and remote's predictability is greater than max predictability seen so far

  • gtmx_plus

    • Forward if grtr_plus and the bundle has been forwarded less than max_forward

  • grtr_sort

    • Forward if grtr and sort descending by P_remote - P_local (subtract local predictability from remote's predictability)

  • grtr_max

    • Forward if grtr and sort descending by remote's predictability

prophet hello_interval

To set the longest acceptable delay between protocol messages, invoke prophet hello_interval=<interval> where <interval> is a number of the range 1 through 255 inclusive, representing time units of 100ms. Set the interval to 255 for a maximum acceptable delay of 25.5 seconds.