|
1 Routing in Delay Tolerant Networks |
|
2 |
|
3 Revision History |
|
4 04.28.04 Initial Revision, mh |
|
5 |
|
6 I. Introduction |
|
7 |
|
8 This document covers the routing requirements for Delay Tolerant Networking. |
|
9 Our objective is to minimize the delay of bundles, and in doing so maximize the |
|
10 probability of delivery, and reduce resource (buffer and network) contention. |
|
11 |
|
12 II. Scenarios |
|
13 |
|
14 A. Scheduled: Interplanetary Internet |
|
15 |
|
16 Nodes in this network are characterized by high latency links that |
|
17 attenuate with distance, leading to variable bandwidth. In addition, |
|
18 they experience frequent scheduled disconnection due to orbital visibility |
|
19 constraints. |
|
20 |
|
21 Regional boundaries may be established along geographical lines, or the |
|
22 entire Interplanetary Internet can be considered to be a region unto itself. |
|
23 If the latter, then all routing within the region is intra-regional, and |
|
24 any identifiers for particular nodes in the internet are in the admin id. |
|
25 If the former, then the routing layer will determine the best next hop |
|
26 necessary to reach the destination region using parameters in its inter- |
|
27 regional routing table. |
|
28 |
|
29 B. Internetworking: Sensor Networks->Gateway->Internet |
|
30 |
|
31 There are several approaches to enabling sensor networks to communicate |
|
32 reliably with the internet. In one scenario, each sensor is a DTN node, |
|
33 and uses custody transfer to ensure delivery to a DTN gateway at the |
|
34 edge of the sensor net. In another scenario, a DTN mule walks among the |
|
35 sensors on a scheduled route, collects the data, and transports it |
|
36 to a DTN gateway, which serves as an interface between the sensor region |
|
37 and the internet region. |
|
38 |
|
39 C. Unreliable: Wireless Radio |
|
40 |
|
41 Wireless radio links are characterized by frequent and unpredictable |
|
42 disconnection, due to interference, power management or other issues. |
|
43 Using DTN, a node can choose to transfer bundles to another node that |
|
44 is "closer" to the destination, or to store the bundle until it sees |
|
45 the destination node. In most cases this will entail intra-regional routing |
|
46 and the routing mechanism will be entirely up to the region administrator. |
|
47 For other regions to communicate with a wireless ad hoc region, however, |
|
48 they will need to know the predicted/probabilistic delay between the |
|
49 gateways in the region, as well as the frequency of contacts. (Delay is |
|
50 the latency once a bundle has been sent through the convergence layer, |
|
51 which includes in-network delay if buffering is required at intermediary |
|
52 nodes. The frequency of contacts determines the additional predicted delay |
|
53 due to initial disconnection. |
|
54 |
|
55 D. Opportunistic: Military Ad Hoc |
|
56 |
|
57 Some connections are opportunistic, meaning that they are not necessarily |
|
58 predictable, but are still useful when available. In some cases, the |
|
59 appearance of an opportunistic connection will allow earlier transmission |
|
60 than expected (which would require the ability to rechedule bundles already |
|
61 designated for a particular contact). In other cases, one could depend |
|
62 entirely on opportunistic connection for intercommunication between |
|
63 regions (or within). Thus a bundle could be scheduled for the "next |
|
64 available" contact for a particular next hop, or it could be placed on an |
|
65 unscheduled list, for review next time a contact is available. Like |
|
66 scenario C, particular nodes may have an expected probability of next |
|
67 contact. A region might correspond to the nodes that are expected to |
|
68 be together at all times (such as a particular unit), or it may correspond |
|
69 to the set of nodes that may be in contact over time. In the latter case, |
|
70 routing between nodes is delegated to the region and not governed by |
|
71 the dtn specification. |
|
72 |
|
73 E. Contact Discovery: Datamule Bus(es) passing a PDA |
|
74 |
|
75 Given a small DTN node that knows very little about the current routing |
|
76 topology, it should be able to make use of opportunistic contacts as |
|
77 they become available. A new contact might advertise the length of time the |
|
78 contact will be available, the bandwidth, the buffer capacity, and what |
|
79 regions it knows. Some of these calculations can be done in the convergence |
|
80 layer, and other Most likely, though, the contact |
|
81 duration will not be advertised, and both sides will employ reactive |
|
82 fragmentation to make maximum use of the connection. Potential issues are |
|
83 link congestion (what happens if everyone attacks the link at once) and |
|
84 reliability. |
|
85 |
|
86 * How does the PDA know that this contact will relay the bundle |
|
87 successfully? |
|
88 * How can custody acknowledgements or application data be sent to the PDA? |
|
89 * Would it make sense to employ gps-based geographic routing and |
|
90 attempt to send the data to the general physical area where the pda was |
|
91 last found? |
|
92 * How would that impact the inter-regional routing? |
|
93 * Where are the region boundaries in this case? |
|
94 |
|
95 F. Multi-protocol: Personal regions |
|
96 |
|
97 Here I describe the scenario in which one region supports multiple |
|
98 protocols. The classic example is the "Internet region" which will support |
|
99 requests from a number of protocols, including gprs, tcp, and udp. Another |
|
100 conceivable application is the concept of the "personal" region. Since |
|
101 region identifiers are used to aid routing between regions, one could |
|
102 conceive of a region mapping to your set of personal DTN nodes, including |
|
103 a laptop, your phone, and a number of bluetooth devices. The laptop and |
|
104 phone can serve as gateways, and intra-regional routing can direct bundles |
|
105 to the interface/convergence layer corresponding to the other devices. |
|
106 Each gateway has convergence layers for the interfaces it supports. |
|
107 |
|
108 G. Internetworking: Village Scenario (from Sushant's paper) |
|
109 |
|
110 A village kiosk is connected to a nearby town via a digital courier (man on |
|
111 motorbike), a wired dialup Internet connection, and a LEO. Actually, I'll |
|
112 take the paragraph straight out of the paper: |
|
113 |
|
114 "We begin with a hypoteical village equipped with a digital courier, a wired |
|
115 dialup Internet connection, and a LEO (e.g. PACSAT) satellite store-and- |
|
116 forward connection. These satellites have low to moderate bandwidth (around |
|
117 10kbps) and are visible for 4-5 short periods of time ('passes') per day |
|
118 (lasting arund 10 minutes per pass, depending on orbit inclination and |
|
119 location on Earth). We call the opportunity to communicate a contact, which |
|
120 is characterized by a duration of time, a capacity, ad a latency (assumed to |
|
121 remain constant during the contact duration). In addition, depending on the |
|
122 type of connection used, finite buffering constraints related to the contact |
|
123 may need to be considered. The digital courier service thus represents a |
|
124 high-bandwidth, high-latency contact, the dialup represents a low-bandwidth, |
|
125 low-latency contact, and the LEO satellite represents a moderate-bandwidth, |
|
126 low-latency contact. The problem of selecting which contacts to carry |
|
127 traffic (and consequently what time to send traffic) represents an instance |
|
128 of the DTN routing problem..." |
|
129 |
|
130 III. Definitions |
|
131 |
|
132 A. Tuple: A pair of identifiers <region id, administrative id> is used in |
|
133 routing a message to its final destination. The region id is used |
|
134 throughout the DTN to get the bundle to its destination region, and the |
|
135 admin id is used within the region. |
|
136 |
|
137 B. Inter-regional Routing: Bundles destined for other regions are routed |
|
138 using a well-known routing standard. This may entail, but is not limited |
|
139 to, hand configured tables, machine-learned, or dynamic routing updates. |
|
140 |
|
141 C. Intra-regional Routing: This is region-specific routing for bundles that |
|
142 are already within their target region. This allows each node in a region |
|
143 to decide whether to try and deliver the bundle directly to the app, or |
|
144 to another DTN node within the same region. The exact implementation and |
|
145 mechanism may differ from region to region. |
|
146 |
|
147 D. Contact: A period of time when data can be transmitted over a particular |
|
148 interface. |
|
149 |
|
150 E. Custody Overlay: There is a question of whether special routing should |
|
151 be done to send |
|
152 |
|
153 IV. Bundle Layer Interface |
|
154 |
|
155 A. Inter-regional Routing - non-matching region identifier |
|
156 |
|
157 Given a bundle, the routing layer will determine which next hops are |
|
158 best, given the destination region, bandwidth and storage requirements, |
|
159 and whether custodial transfer has been requested. Specific bundle |
|
160 parameters that affect this decision are priority, custody transfer,, |
|
161 bundle size, and destination region id. The destination admin id does |
|
162 NOT affect this decision. Given a particular next hop, the convergence |
|
163 layer is responsible for getting the bundle to that particular node, and |
|
164 may employ intermediary hosts not within the DTN overlay. |
|
165 |
|
166 The routing layer should return a set of next hop identifiers, together |
|
167 with the corresponding fragment offsets and lengths. The routing layer |
|
168 may choose to replicate some or all of the bundle across different |
|
169 contacts. In addition, the routing layer may choose to delegate scheduling |
|
170 until later, if no known path is yet available. |
|
171 |
|
172 B. Intra-regional Routing - matching region identifier |
|
173 |
|
174 Once a bundle has reached its destination region, the bundle daemon can |
|
175 use the admin id to determine the next end point. Design and implementation |
|
176 of this mechanism is left up to the region administrator, but may use a |
|
177 similar mechanism as inter-regional routing. |
|
178 |
|
179 C. Non-DTN Routing - between DTN hops |
|
180 |
|
181 Between DTN hops, it is up to the underlying technology to determine which |
|
182 path is the most appropriate for delivering bundles between DTN nodes. |
|
183 For ad hoc regions, this may entail AODV, DSDV, or even epidemic routing. |
|
184 |
|
185 V. Routing Considerations |
|
186 |
|
187 The following is the data we can take into account in determining the best |
|
188 set of routes for a given bundle. We have the option of choosing one or more |
|
189 routes |
|
190 |
|
191 A. Contacts Schedule |
|
192 |
|
193 This includes pre-arranged, recurring, and probabilistic contacts. The |
|
194 probabilistic contacts may involve some level of machine learning, but |
|
195 if all of your contacts are recurring, then this can be set by hand and |
|
196 ignored thereafter. This schedule should be modifiable by a management |
|
197 interface. Information in this table includes latency and bandwidth for |
|
198 each contact. Information may also include buffer availability. |
|
199 |
|
200 Note: Buffer availability may also be used as a form of hop-by-hop |
|
201 congestion control. |
|
202 |
|
203 B. Contact->Region Map |
|
204 |
|
205 Particular contacts can reach specific regions. If this is an oracle, it |
|
206 would include the number of DTN hops to, the effective throughput of, and |
|
207 the frequency of contact with each region. |
|
208 |
|
209 C. Region->Region Map |
|
210 |
|
211 Some regions may be named hierarchically, in which case regions can be |
|
212 matched by longest match. In other cases, we know that we can reach |
|
213 certain regions through other regions. For example, the sensor network |
|
214 gateway may not recognize the interplanetary region, but has an entry for |
|
215 "*" to some Internet gateway that might know. Eventually, bundles |
|
216 routed to "*" entries will reach a gateway that can identify the region. |
|
217 |
|
218 D. Traffic Demand Schedule |
|
219 |
|
220 In anticipation of higher traffic demand, a routing algorithm may be able |
|
221 to optimize by distributing load, either by proactively fragmenting the |
|
222 bundle or by sending bundles on different routes via some form of round |
|
223 robin routing. |
|
224 |
|
225 Note: This will probably not be a factor in routing. |
|
226 |
|
227 E. Queueing Considerations |
|
228 |
|
229 The contacts schedule should track immediate Queue state. However, if |
|
230 it is known that a downsteam queue will not have sufficient capacity, the |
|
231 routing layer may decide to use a different path, to prevent future loss or |
|
232 delays. |
|
233 |
|
234 F. Custodial Nodes |
|
235 |
|
236 If we are using custody transfer for the bundle, we may choose a route |
|
237 that has more custodians, rather than a route without custodians. |
|
238 |
|
239 VI. Cost Factors (from Sushant's paper) |
|
240 |
|
241 Delay Components: |
|
242 * queuing time: time until a contact becomes available |
|
243 * transmission delay: time to inject a message into an edge |
|
244 * propagation delay: time for a message to arrive at next hop |
|
245 |
|
246 Route Stability: |
|
247 * how often do topology changes occur? Is source routing viable? |
|
248 * proactive vs reactive routing |
|
249 * scheduled routes: for recurring contacts, we can set up known scheduled |
|
250 routes, allowing for pre-planning of buffer space and load |
|
251 * with delay tolerant networking, there is no way to propagate route changes |
|
252 instantaneously |
|
253 * source routing vs per hop routing: |
|
254 - network queuing time may be large compared to forwarding delay |
|
255 - topological changes will probably occur while a message is in transit |
|
256 - potential loops |
|
257 |
|
258 Resource Consumption: |
|
259 * a routing protocol will consume some amount of overhead |
|
260 * the decision to replicate must be weigh the increased reliability against |
|
261 overhead of additional traffic |
|
262 |
|
263 Fragmentation |
|
264 * routing layer may choose to split a bundle across multiple subsequent |
|
265 contacts, if the throughput of a given contact is insufficient to transport |
|
266 the whole thing |
|
267 * routing layer may choose to splite a bundle across differnt paths entirely |
|
268 to improve load balancing and reduce delay |
|
269 (e.g. you have 14 phone lines and the node two hops down as a T1 to the |
|
270 destination, so you use all 14 at once to send the message) |