|
1 <html> |
|
2 <head> |
|
3 <title> DTN2 Manual: Prophet Router </title> |
|
4 <link rel="stylesheet" type="text/css" href="manual.css" /> |
|
5 </head> |
|
6 <body> |
|
7 <h1>Prophet Router |
|
8 </h1> |
|
9 |
|
10 <p> |
|
11 This is the implementation of a Prophet router. 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. |
|
12 |
|
13 <p>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. For more information please see the <a href="configuration.html#prophet">prophet</a> command. |
|
14 |
|
15 <h2>Design</h2> |
|
16 |
|
17 <p>See the PRoPHET website. |
|
18 |
|
19 <p>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 |
|
20 |
|
21 <h2>Implementation</h2> |
|
22 |
|
23 <p>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. |
|
24 |
|
25 <a name="prophet_cmd"/> |
|
26 <h2> prophet </h2> |
|
27 |
|
28 <h4> prophet set </h4> |
|
29 <p> |
|
30 Syntax: <tt>prophet <i>cmd</i> <i>arg</i> <i>val</i></tt> |
|
31 <br> |
|
32 Example: <tt>prophet set hello_dead 100</tt> |
|
33 |
|
34 You may set the |
|
35 following variables: |
|
36 |
|
37 <p> |
|
38 <table> |
|
39 <tr> |
|
40 <th>Variable |
|
41 <th>Possible settings |
|
42 <th>Default |
|
43 <th>Comments |
|
44 |
|
45 <tr> |
|
46 <td><tt>age_period</tt> |
|
47 <td>seconds |
|
48 <td>TBC |
|
49 <td>The timeout, in seconds, of the timer that calculates Prophet nodes' aging. The same value is used by the timer that expires Prophet ACKs. |
|
50 |
|
51 <tr> |
|
52 <td><tt>beta</tt> |
|
53 <td>number (scale factor) |
|
54 <td>0.25 |
|
55 <td>The scaling factor for the transivity of predictability; the Prophet I-D recommends a default value of 0.25. |
|
56 |
|
57 <tr> |
|
58 <td><tt>encounter</tt> |
|
59 <td>number (initialization value) |
|
60 <td>0.75 |
|
61 <td>The initialization value for the direct-contact predictability calculation. |
|
62 |
|
63 <tr> |
|
64 <td><tt>epsilon</tt> |
|
65 <td>number (predictability value) |
|
66 <td>TBC |
|
67 <td>The minimum predictability value before the route is discarded. The granularity of an eight-bit value limits this to 0.0039 (1/255). |
|
68 |
|
69 <tr> |
|
70 <td><tt>gamma</tt> |
|
71 <td>number (initialization value) |
|
72 <td>0.99 |
|
73 <td>The aging constant used to diminish the predictability value of a route over time. |
|
74 |
|
75 |
|
76 <tr> |
|
77 <td><tt>hello_dead</tt> |
|
78 <td>number |
|
79 <td>TBC |
|
80 <td>The maximum number of HELLO_INTERVALs before a remote session with a Prophet peer is considered unreachable. |
|
81 |
|
82 <tr> |
|
83 <td><tt>internet_gw</tt> |
|
84 <td>flag |
|
85 <td>TBC |
|
86 <td>The flag that describes whether the Prophet router bridges to the Internet DTN region. Currently not used. |
|
87 |
|
88 <tr> |
|
89 <td><tt>kappa</tt> |
|
90 <td>number(ms) |
|
91 <td>TBC |
|
92 <td>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. |
|
93 |
|
94 <tr> |
|
95 <td><tt>max_forward</tt> |
|
96 <td>number |
|
97 <td>TBC |
|
98 <td>The maximum number of times a bundle may be forwarded by the GTMX forwarding strategy. |
|
99 |
|
100 <tr> |
|
101 <td><tt>min_forward</tt> |
|
102 <td>number |
|
103 <td>TBC |
|
104 <td>The minimum number of times a bundle may be forwarded before eviction by the LEPR queuing policy. |
|
105 |
|
106 <tr> |
|
107 <td><tt>relay_node</tt> |
|
108 <td>flag |
|
109 <td>TBC |
|
110 <td>The flag that describes whether this Prophet node will relay bundles to other nodes. |
|
111 </table> |
|
112 |
|
113 |
|
114 <h4><prophet queue_policy</h4> |
|
115 |
|
116 <p>To set the queue policy to one of the following, invoke <tt>prophet queue_policy=<i>policyname</i></tt>. Queue policies are discussed in detail in the Prophet I-D on p. 18, section 3.7. |
|
117 |
|
118 <p> |
|
119 <table> |
|
120 <tr> |
|
121 <th>policyname |
|
122 <th>Comments |
|
123 |
|
124 <tr> |
|
125 <td><tt>fifo</tt> |
|
126 <td>First In First Out: evict oldest first |
|
127 |
|
128 <tr> |
|
129 <td><tt>mofo</tt> |
|
130 <td>Evict most forwarded first |
|
131 |
|
132 <tr> |
|
133 <td><tt>mopr</tt> |
|
134 <td>Evict most favorably forwarded first |
|
135 |
|
136 <tr> |
|
137 <td><tt>lmopr</tt> |
|
138 <td>Evict most favorably forwarded first (linear increase) |
|
139 |
|
140 <tr> |
|
141 <td><tt>shli</tt> |
|
142 <td>Evict shortest lifetime first (the bundle that will expire soonest) |
|
143 |
|
144 <tr> |
|
145 <td><tt>lepr</tt> |
|
146 <td>Evict least probable first (lowest predictability) |
|
147 |
|
148 </table> |
|
149 |
|
150 |
|
151 <h4>prophet fwd_strategy</h4> |
|
152 |
|
153 <p>To set the forwarding strategy to one of the following, invoke <tt>prophet fwd_strategy=<i>strategy</i></tt>. Forwarding strategies are discussed in detail in the Prophet I-D on p. 16, section 3.6. |
|
154 |
|
155 <p> |
|
156 <table> |
|
157 <tr> |
|
158 <th>strategy |
|
159 <th>Comments |
|
160 |
|
161 <tr> |
|
162 <td><tt>grtr</tt> |
|
163 <td>Forward if remote's predictability is greater than local's |
|
164 |
|
165 <tr> |
|
166 <td><tt>gtmx</tt> |
|
167 <td>Forward if grtr and the bundle has been forwarded less than max_forward |
|
168 |
|
169 <tr> |
|
170 <td><tt>grtr_plus</tt> |
|
171 <td>Forward if grtr and remote's predictability is greater than max predictability seen so far |
|
172 |
|
173 <tr> |
|
174 <td><tt>gtmx_plus</tt> |
|
175 <td>Forward if grtr_plus and the bundle has been forwarded less than max_forward |
|
176 |
|
177 <tr> |
|
178 <td><tt>grtr_sort</tt> |
|
179 <td>Forward if grtr and sort descending by P_remote - P_local (subtract local predictability from remote's predictability) |
|
180 |
|
181 <tr> |
|
182 <td><tt>grtr_max</tt> |
|
183 <td>Forward if grtr and sort descending by remote's predictability |
|
184 </table> |
|
185 <h4>prophet hello_interval</h4> |
|
186 |
|
187 <p>To set the longest acceptable delay between protocol messages, invoke <tt>prophet hello_interval<i>interval</i></tt> where <i>interval</i> is a number of the range 1 through 255 inclusive, representin |
|
188 g time units of 100ms. Set the interval to 255 for a maximum acceptable delay of 25.5 seconds. |
|
189 |
|
190 <p> |
|
191 </body> |
|
192 </html> |
|
193 |