|
1 <title>Fragmentation: Delay Tolerant Networks</title> |
|
2 |
|
3 <pre> |
|
4 <u><b>Fragmentation in Delay Tolerant Networks</b></u> |
|
5 |
|
6 <small> |
|
7 Revision History |
|
8 02.19.04 Initial Revision, mh |
|
9 02.23.04 Rewrote requirements, added header spec. mh |
|
10 02.24.04 Edits, Added Non-functional requirements, mh |
|
11 02.25.04 Edits, Added some definitions, extended intro, mh |
|
12 03.26.04 Added design section, updated header specifications, mh |
|
13 </small> |
|
14 |
|
15 <b>I. Introduction</b> |
|
16 |
|
17 This document covers the requirements for the fragmentation interface, as |
|
18 integrated with the bundle processing. |
|
19 |
|
20 Our main goals are to be able to (i) fork a bundle across multiple links and |
|
21 (ii) send a bundle over the same link using multiple contacts (assuming the |
|
22 contact disconnects and reconnects later). A secondary goal is to integrate |
|
23 digital fountain so we can have a sort of hop-by-hop error control. |
|
24 |
|
25 There is a main assumption that the routing layer will contain and control all |
|
26 knowledge about the fragmentation capabilities of other dtn gateways and |
|
27 routers, so it can make essential fragmentation decisions. |
|
28 |
|
29 <b>II. Design Overview</b> |
|
30 |
|
31 In terms of basic mechanics, the Fragmentation Manager knows how to create |
|
32 fragments from an original bundle, as well as how to create a bundle from |
|
33 its constituent fragments. When the bundle to be fragmented is ready to be |
|
34 scheduled for delivery, the Routing Layer will make a decision as to |
|
35 how the bundle should be fragmented, and on which channel(s) the fragments |
|
36 should be sent. Once the fragment it on a particular channel, it is treated |
|
37 exactly like any other bundle. Upon receipt of a bundle fragment, it is |
|
38 funnelled into the Fragment Manager, until we know that a bundle can be |
|
39 reconstructed. At this point, the bundleDaemon will reconstruct the bundle |
|
40 and treat it as if had just been received from the convergence layer. |
|
41 |
|
42 We would also like the Fragmentation Manager to be stateless, so information |
|
43 about the fragments should be stored in its own persistent database table. |
|
44 |
|
45 <b>III. Functional Requirements</b> |
|
46 |
|
47 M - Must Have |
|
48 S - Should Have |
|
49 C - Could Have |
|
50 W - Want to Have |
|
51 |
|
52 DF: related to digital fountain feature (raptor codes) |
|
53 FRAG: fragmentation without digital fountain |
|
54 CUST: related to custody transfer |
|
55 REAC: related to reactive/dynamic fragmentation |
|
56 |
|
57 <u>A. Routing Layer Changes</u> |
|
58 |
|
59 RA1 S) For a particular route and convergence layer, |
|
60 a S) determine necessary level of redundancy needed to increase |
|
61 probability of end-to-end delivery (or just next hop), which may |
|
62 depend on characteristics of underlying protocol |
|
63 b M) Decide what type and level of fragmentation is feasible |
|
64 - Could choose none, if underlying layer takes care of it properly |
|
65 - DF vs FRAG, or combination of two (DF some fragments) |
|
66 - could choose to FRAG, then DF portions if especially large file |
|
67 - could choose to DF, and then FRAG code blocks, if downstream |
|
68 links need fragments smaller than ~16 bytes |
|
69 - could choose only one or another |
|
70 - based on endpoint capability - does it support DF? |
|
71 - oracle: list of known df-capable routers |
|
72 - possibly based on entity part of tuple |
|
73 - choose maximum fragment size (MFS) |
|
74 - default to what is reasonable for the next hop |
|
75 - decide what is the largest block size that can be sent over |
|
76 all of the known expected hops in the route, based on |
|
77 the medium and protocols that will be used |
|
78 - only need to fragment up to next "layover", can reassemble and |
|
79 fragment downstream when it is being buffered. (e.g. fragment |
|
80 during the DakNet bus ride) |
|
81 - DF: Choose how many coding blocks we need (what factor) |
|
82 - estimate downstream loss rate, and produce |
|
83 (s*1.05 + 800)/mfs x (1 + loss rate) fragments, where |
|
84 s is the number of bytes in the file, and mfs is the size of |
|
85 the coding block. |
|
86 - based on past history from custody transfers? |
|
87 - pre-determined fixed value based on prior monitoring (more |
|
88 for scheduled contacts, but also for on-average homogeneous |
|
89 performance) |
|
90 - this is basically error control! |
|
91 RA2 M) Given a bundle and a particular route, do the following: |
|
92 a M) Decide if fragmentation is necessary (or error coding) |
|
93 b M) Choose appropriate fragmentation, based on bundle size, MFS |
|
94 c M) if bundle is too big, fragment according to specification |
|
95 RA3 W) Given a bundle, send fragments along different routes/channels |
|
96 RA4 M) CUST: Upon custody ACK, stop sending fragments, and clear rtx buffers |
|
97 RA5 M) CUST: Upon retransmission timeout, send fragments out again |
|
98 a S) CUST/DF: If custody transfer timeout occurs, retransmit bundle using |
|
99 a new set of pseodorandom keys. (Rather than duplicating data) |
|
100 b S) FRAG: same fragments |
|
101 c W) FRAG: guess which fragments haven't been recieved |
|
102 d C) Optionally choose a new route (or set of routes) |
|
103 RA6 S) REAC: Upon unexpected termination of contact |
|
104 a W) recalculate route for remaining packets, and shift to new |
|
105 contact queue. This entails shifting bundles back out of the |
|
106 convergence layer and into the bundle layer again. |
|
107 b S) DF: upon reconnect, just continue sending messages from new q |
|
108 c S) FRAG: upon reconnect send rest of fragments, then maybe fragments |
|
109 that have we guess may have dropped because connection terminated just |
|
110 prior to their sending. (pseudo-FEC) |
|
111 Note: This implies that the queues are managed on in the routing layer |
|
112 rather than the convergence layer, or that we implement |
|
113 revocation - allowing the routing layer to tell the convergence layer |
|
114 that it no longer needs to send specific pending bundles or bundle |
|
115 fragments. |
|
116 RA7 M) Identify bundles as fragments, and decide where it should go: |
|
117 a M) Fragmentation Manager if we need to reassemble, may choose to do this |
|
118 always if all contacts are idle or busy. |
|
119 b S) Immediate relay if contact is open, and fragment size is okay |
|
120 c M) Buffer fragments until sufficient to assume custody |
|
121 - DF: original_size * 1.05 + 800 bytes, rounded up to nearest |
|
122 encoding unit size multiple |
|
123 - FRAG: reassemble packet to verify all bytes |
|
124 d M) Fragment if packet too large for downstream route |
|
125 e M) If bundle fragment has arrived at last hop, wait for rest of bundle |
|
126 so it can be reassembled prior to delivery. (i.e. Applications do |
|
127 not get fragments.) |
|
128 RA8 S) Recall fragments from Fragmentation Manager if a new contact has |
|
129 arrived and we can relay immediately. |
|
130 ?) Are bundle fragments copied to manager from routing layer? |
|
131 ?) Does routing layer track which fragments are in fragmentation manager? |
|
132 ?) Should requests for fragments be non-blocking? Should routing layer |
|
133 request to send fragments, or should fragmentation manager ask routing |
|
134 layer to send fragments as they are ready? |
|
135 RA9 S) Identify and process partial custody ACKs |
|
136 a S) upon custody transfer timeout, only retransmit portions that are not |
|
137 ACKed |
|
138 b S) if entire bundle has been ACKed by same custodian, then allow |
|
139 custody transfer |
|
140 RA10 M) Generate bundle status report for bundle, if requested. |
|
141 S) Generate report of which fragments received |
|
142 C) Set timer, so receipt of multiple fragments can be placed in |
|
143 single report |
|
144 RA11 M) Track which bundles are being reassembled, and assembly status |
|
145 a M) DF: decoding is optional, can just gather fragments and count |
|
146 b M) FRAG: produce partial ACK report |
|
147 RA12 M) Request fragments for a particular bundle, specifying maximum fragment |
|
148 size, fragmentation type, number of fragments needed (if DF), seed for |
|
149 pseudo random generator (if DF), offset start/end (if FRAG) |
|
150 - callback, routing layer registers request, and frag mgr delivers |
|
151 bundle fragments as they are ready |
|
152 - if relaying DF fragments, MFS and seed are not necessary |
|
153 RA13 M) Tell Fragmentation Manager when it can clean up fragments for a |
|
154 given bundle. |
|
155 RA14 W) Replicate or Split fragments for a given bundle across multiple |
|
156 channels to increase probability or speed of delivery. |
|
157 |
|
158 <u>B. Fragmentation Manager</u> |
|
159 |
|
160 RB1 M) Accept New Bundle and Fragmentation request. |
|
161 RB2 M) Accept requests for fragments for bundles that arrived as fragments |
|
162 RB3 M) Generate Bundle Fragments using Raptor Codes (DF) |
|
163 - optional initial seed parameter for key generator |
|
164 - code block size specified by routing layer |
|
165 - fragments include key, source size, and data (as payload) |
|
166 - if code blocks are not subdivisible, then code block size is 40 bytes |
|
167 and bundle fragments may carry multiple code blocks |
|
168 RB4 M) Generate Bundle Fragments using Basic Fragmentation (FRAG) |
|
169 - fragment segment size specified by routing layer |
|
170 - fragments include source size, fragment offset, and data (as payload) |
|
171 - allow fragmentation to begin from a specific offset |
|
172 RB5 S) FRAG: Generate Bundle Fragments from partial assembly |
|
173 - in case not all fragments have been received, allow fragment creation |
|
174 RB7 M) Accept and Track Fragments from routing layer |
|
175 a M) DF: Maintain fragment count, keep fragments generated using |
|
176 different encoding unit sizes separated |
|
177 b M) DF: Remove duplicate fragments |
|
178 c M) CUST: Notify Routing layer if sufficient fragments have been |
|
179 recieved to accept custody (based on parameters provided by routing |
|
180 layer, and if custody has been requested) |
|
181 d M) CUST: Update custody id of each fragment once custody is accepted |
|
182 e M) FRAG: Order fragments, and track which bytes have arrived |
|
183 RB8 M) Reassemble Bundle from received fragments (DF/FRAG) |
|
184 RB9 M) Allow relay of existing fragments (no assembly/refragmenting) |
|
185 RB10 W) REAC: Reactive Fragmentation - buffer fragments or partial payload |
|
186 until contact resumes. |
|
187 RB11 M) Garbage collection |
|
188 - remove fragments for bundles that have already been sent |
|
189 - remove fragments for expired bundles |
|
190 |
|
191 <u>Remaining Questions</u> |
|
192 |
|
193 * Can we fragment pre-encoded blocks further by splitting the information |
|
194 in such a way that the <i>code block fragments</i> are still useful to the |
|
195 decoder? |
|
196 - retain key, source size, and original encoding block size |
|
197 - include offset of this code block fragment |
|
198 * If not, is there a value add to fragmenting as small as possible and |
|
199 including multiple code blocks in a given bundle fragment? |
|
200 - suggested "quantum" code block size is 40 bytes |
|
201 * If we split a bundle across multiple channels, how does custody transfer |
|
202 work? |
|
203 * Should we allow partial ACKs for custody transfer? |
|
204 * Where/how should fragment queueing occur? - currently managed by routing |
|
205 layer, with the fragmentation functionality being stateless |
|
206 * Could we reduce fragment overhead by only sending the duplicate headers |
|
207 with some subset of the fragments? Thus, fragments 0, 5, and 10 will carry |
|
208 the original headers, and the rest will carry some matching hash identifier. |
|
209 This reduces the duplicate information being sent out.... |
|
210 |
|
211 <b>III. Non-Functional Requirements</b> |
|
212 |
|
213 NF1 ?) The Fragmentation Manager should be stateless |
|
214 - client handles filesystem and memory allocation |
|
215 NF2 M) Maximize the utility of contacts by sending fragments of packets |
|
216 and reassembling them later. (see RA14) |
|
217 NF3 S) Consider resource limitations. |
|
218 NF4 M) Digital Fountain encode/decode functionality must be optional |
|
219 - we may require routers to be df-aware? |
|
220 |
|
221 <b>IV. Header Specification</b> |
|
222 |
|
223 There will be two headers for fragments, one for traditional fragmentation |
|
224 and another for Digital Fountain Bundle Fragments. |
|
225 |
|
226 <u>Standard Bundle Fragment Header</u> |
|
227 |
|
228 +----------------+----------------+----------------+----------------+ |
|
229 | Next Header | Length of original bundle payload (4 bytes) |
|
230 +----------------+----------------+----------------+----------------+ |
|
231 | Offset of this bundle fragment (4 bytes) |
|
232 +----------------+--------------------------------------------------+ |
|
233 | |
|
234 -----------------+ |
|
235 |
|
236 Bundle fragment headers are present in all bundle fragments whose |
|
237 offsets from the beginning of the original bundle are non-zero. |
|
238 Bundle fragment headers MAY also appear in bundles whose offsets from |
|
239 the beginning of the original bundle are zero. |
|
240 |
|
241 The fields of the Bundle Fragment Header are: |
|
242 |
|
243 Next Header Type. The Next Header Type field is a 1-byte field that |
|
244 indicates the type of the header that immediately follows this |
|
245 one. Header types are listed in Table 1 above. |
|
246 |
|
247 Length of Original Bundle Payload. This is the total length of the |
|
248 original bundle's payload before any fragmentation. |
|
249 |
|
250 Fragment Offset. The byte offset of the beginning of this fragment |
|
251 within the original bundle. |
|
252 |
|
253 Note: The length of the fragment itself is included in the Bundle |
|
254 Payload Header. |
|
255 |
|
256 <u>Digital Fountain Bundle Fragment Header (Proposed Version A)</u> |
|
257 |
|
258 +----------------+----------------+----------------+----------------+ |
|
259 | Next Header | Length of original bundle payload (4 bytes) |
|
260 +----------------+----------------+----------------+----------------+ |
|
261 | Code Block Size (4 bytes) |
|
262 +----------------+--------------------------------------------------+ |
|
263 | Number of Code Blocks (4 bytes) |
|
264 +----------------+--------------------------------------------------+ |
|
265 | |
|
266 -----------------+ |
|
267 |
|
268 Digital Fountain Bundle Fragment Headers appear in all bundles where |
|
269 the payload consists of one or more raptor-encoded coded blocks. |
|
270 |
|
271 The fields of the Bundle Fragment Header are: |
|
272 |
|
273 Next Header Type. The Next Header Type field is a 1-byte field that |
|
274 indicates the type of the header that immediately follows this |
|
275 one. Header types are listed in Table 1 above. |
|
276 |
|
277 Length of Original Bundle Payload. This is the total length of the |
|
278 original bundle's payload before any fragmentation. |
|
279 |
|
280 Code Block Size. This is the size of the encoding unit. |
|
281 |
|
282 Number of Code Blocks. This is the number of code blocks included in |
|
283 the payload. |
|
284 |
|
285 |
|
286 Note: The bundle payload in this case MUST consist of a series of code |
|
287 blocks, each preceded by a 4 byte key corresponding to the key used |
|
288 to generate the code block. This key determines the graph used to encode |
|
289 the data in the code block. The size of the payload will be a multiple of |
|
290 4 bytes + the code block size. |
|
291 |
|
292 <u>Digital Fountain Bundle Fragment Header (Proposed Version B)</u> |
|
293 |
|
294 +----------------+----------------+----------------+----------------+ |
|
295 | Next Header | Length of original bundle payload (4 bytes) |
|
296 +----------------+----------------+----------------+----------------+ |
|
297 | Code Block Size (4 bytes) |
|
298 +----------------+--------------------------------------------------+ |
|
299 | Code Block Key (4 bytes) |
|
300 +----------------+--------------------------------------------------+ |
|
301 | |
|
302 -----------------+ |
|
303 |
|
304 Digital Fountain Bundle Fragment Headers appear in all bundles where |
|
305 the payload consists of one or more raptor-encoded coded blocks. |
|
306 |
|
307 The fields of the Bundle Fragment Header are: |
|
308 |
|
309 Next Header Type. The Next Header Type field is a 1-byte field that |
|
310 indicates the type of the header that immediately follows this |
|
311 one. Header types are listed in Table 1 above. |
|
312 |
|
313 Length of Original Bundle Payload. This is the total length of the |
|
314 original bundle's payload before any fragmentation. |
|
315 |
|
316 Code Block Size. This is the size of the encoding unit. |
|
317 |
|
318 Code Block Key. This key uniquely identifies the code block and is used |
|
319 as the key for determining the graph used to generate this code |
|
320 block. |
|
321 |
|
322 Note: The bundle payload in this case MUST be a digital-fountain encoded |
|
323 code block of the size specified as the code block size. |
|
324 |
|
325 Thoughts: We could eliminate the Code Block Size field and make that |
|
326 implicit in the bundle payload length specified in that header. This |
|
327 version differs from (A) in that there is only one code block per |
|
328 bundle fragment. |
|
329 |
|
330 <b>Glossary</b> |
|
331 |
|
332 <u>code block</u> - a set of bits generated using digital fountain's raptor |
|
333 codes that can be used with other blocks to decode an encoded payload. |
|
334 |
|
335 <u>key</u> - the number used to pseudo-randomly generate the degree and |
|
336 connections for a given block. Also can be used as a unique identifier |
|
337 |
|
338 <u>custody id</u> - the tuple of the current custodian of the bundle |
|
339 or bundle fragment |
|
340 |
|
341 <u>custody timeout</u> - if the current custodian has not received a custody |
|
342 ack within this time, the custodian must retransmit the bundle |
|
343 |
|
344 <u>custody ack</u> - when a downstream custodian decides to accept custody |
|
345 of a particular bundle, it sends an ack to the current custodian, so it can |
|
346 release custody |
|
347 |
|
348 <u>partial custody ack</u> - if a downstream custodian only has a fragment |
|
349 of the original bundle (or some percentage of the DF fragments) then it can |
|
350 send a partial custody ack, telling the current custodian that it accepts the |
|
351 custody of those fragments |
|
352 |
|
353 <u>fragmentation manager</u> - encapsulation of the code that knows how to |
|
354 break bundles into bundle fragments, and how to reassemble them |
|
355 |
|
356 </pre> |