Debian Codegraph @

rfc2041.html

raw
1 <pre>Network Working Group B. Noble
2 Request for Comments: 2041 Carnegie Mellon University
3 Category: Informational G. Nguyen
4 University of California, Berkeley
5 M. Satyanarayanan
6 Carnegie Mellon University
7 R. Katz
8 University of California, Berkeley
9 October 1996
10
11
12 <span class="h1">Mobile Network Tracing</span>
13
14 Status of this Memo
15
16 This memo provides information for the Internet community. This memo
17 does not specify an Internet standard of any kind. Distribution of
18 this memo is unlimited.
19
20 Abstract
21
22 Mobile networks are both poorly understood and difficult to
23 experiment with. This RFC argues that mobile network tracing
24 provides both tools to improve our understanding of wireless
25 channels, as well as to build realistic, repeatable testbeds for
26 mobile software and systems. The RFC is a status report on our work
27 tracing mobile networks. Our goal is to begin discussion on a
28 standard format for mobile network tracing as well as a testbed for
29 mobile systems research. We present our format for collecting mobile
30 network traces, and tools to produce from such traces analytical
31 models of mobile network behavior.
32
33 We also describe a set of tools to provide network modulation based
34 on collected traces. Modulation allows the emulation of wireless
35 channel latency, bandwidth, loss, and error rates on private, wired
36 networks. This allows system designers to test systems in a
37 realistic yet repeatable manner.
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 <span class="grey">Noble, et. al. Informational [Page 1]</span></pre>
53 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
54 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
55
56
57 <span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
58
59 How does one accurately capture and reproduce the observed behavior
60 of a network? This is an especially challenging problem in mobile
61 computing because the network quality experienced by a mobile host
62 can vary dramatically over time and space. Neither long-term average
63 measures nor simple analytical models can capture the variations in
64 bandwidth, latency, and signal degradation observed by such a host.
65 In this RFC, we describe a solution based on network tracing. Our
66 solution consists of two phases: trace recording and trace
67 modulation.
68
69 In the trace recording phase, an experimenter with an instrumented
70 mobile host physically traverses a path of interest to him. During
71 the traversal, packets from a known workload are generated from a
72 static host. The mobile host records observations of both packets
73 received from the known workload as well as the device
74 characteristics during the workload. At the end of the traversal,
75 the list of observations represents an accurate trace of the observed
76 network behavior for this traversal. By performing multiple
77 traversals of the same path, and by using different workloads, one
78 can obtain a trace family that collectively characterizes network
79 quality on that path.
80
81 In the trace modulation phase, mobile system and application software
82 is subjected to the network behavior observed in a recorded trace.
83 The mobile software is run on a LAN-attached host whose kernel is
84 modified to read a file containing the trace (possibly postprocessed
85 for efficiency,) and to delay, drop or otherwise degrade packets in
86 accordance with the behavior described by the trace. The mobile
87 software thus experiences network quality indistinguishable from that
88 recorded in the trace. It is important to note that trace modulation
89 is fully transparent to mobile software --- no source or binary
90 changes have to be made.
91
92 Trace-based approaches have proved to be of great value in areas such
93 as file system design [<a href="#ref-2" title="and Patterson">2</a>, <a href="#ref-10" title="and Satyanarayanan">10</a>, <a href="#ref-11" title="and Ousterhout">11</a>] and computer architecture. [1, 5,
94 13] Similarly, we anticipate that network tracing will prove valuable
95 in many aspects of mobile system design and implementation. For
96 example, detailed analyses of traces can provide insights into the
97 behavior of mobile networks and validate predictive models. As
98 another example, it can play an important role in stress testing and
99 debugging by providing the opportunity to reproduce the network
100 conditions under which a bug was originally uncovered. As a third
101 example, it enables a system under development to be subjected to
102 network conditions observed in distant real-life environments. As a
103 final example, a set of traces can be used as a benchmark family for
104 evaluating and comparing the adaptive capabilities of alternative
105
106
107
108 <span class="grey">Noble, et. al. Informational [Page 2]</span></pre>
109 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
110 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
111
112
113 mobile system designs.
114
115 Our goal in writing this RFC is to encourage the development of a
116 widely-accepted standard format for network traces. Such
117 standardization will allow traces to be easily shared. It will also
118 foster the development and widespread use of trace-based benchmarks.
119 While wireless mobile networks are the primary motivation for this
120 work, we have made every effort to ensure that our work is applicable
121 to other types of networks. For example, the trace format and some
122 of the tools may be valuable in analyzing and modeling ATM networks.
123
124 The rest of this RFC is organized as follows. We begin by examining
125 the properties of wireless networks and substantiating the claim that
126 it is difficult to model such networks. Next, in <a href="#section-3">Section 3</a>, we
127 describe the factors that should be taken into account in designing a
128 trace format. We present the details of a proposed trace format
129 standard in <a href="#section-4">Section 4</a>. <a href="#section-5">Section 5</a> presents a set of tools that we
130 have built for the collection, analysis and replay of traces.
131 Finally, we conclude with a discussion of related and future work.
132
133 <span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Modeling Wireless Networks</span>
134
135 Wireless channels are particularly complex to model, because of their
136 inherent dependence on the physical properties of radio waves (such
137 as reflections from "hard" surfaces, diffraction around corners, and
138 scattering caused by small objects) and the site specific geometries
139 in which the channel is formed. They are usually modeled as a time-
140 and distance-varying signal strength, capturing the statistical
141 nature of the interaction among reflected radio waves. The signal
142 strength can vary by several orders of magnitude (+ or - 20-30 dB)
143 within a short distance. While there have been many efforts to
144 obtain general models of radio propagation inside buildings and over
145 the wide area, these efforts have yielded inherently inaccurate
146 models that can vary from actual measurements by an order of
147 magnitude or more.
148
149 Signal-to-noise ratio, or SNR, is a measure of the received signal
150 quality. If the SNR is too low, the received signal will not be
151 detected at the receiver, yielding bit errors and packet losses. But
152 SNR is not the only effect that can lead to losses. Another is
153 inter-symbol interference caused by delay spread, that is, the
154 delayed arrival of an earlier transmitted symbol that took a
155 circuitous propagation path to arrive at the receiver, thereby
156 (partially) canceling out the current symbol. Yet another problem is
157 doppler shift, which causes frequency shifts in the arrived signal
158 due to relative velocities of the transmitter and the receiver,
159 thereby complicating the successful reception of the signal. If
160 coherent reception is being used, receiver synchronization can be
161
162
163
164 <span class="grey">Noble, et. al. Informational [Page 3]</span></pre>
165 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
166 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
167
168
169 lost.
170
171 More empirically, it has been observed that wireless channels adhere
172 to a two state error model. In other words, channels are usually
173 well behaved but occasionally go into a bad state in which many burst
174 errors occur within a small time interval.
175
176 Developers of network protocols and mobility algorithms must
177 experiment with realistic channel parameters. It is highly desirable
178 that the wireless network be modeled in a thoroughly reproducible
179 fashion. This would allow an algorithm and its variations to be
180 evaluated in a controlled and repeatable way. Yet the above
181 discussion makes it clear that whether analytical models are used or
182 even actual experimentation with the network itself, the results will
183 be either inaccurate or unlikely to be reproducible. A trace-based
184 approach alleviates these problems.
185
186 <span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Desirable Trace Format Properties</span>
187
188 In designing our trace format, we have been guided by three
189 principles. First, the format should be extensible. Second, it
190 should be self-describing. Third, traces should be easy to manage.
191 This section describes how each of these principles has affected our
192 design.
193
194 Although we have found several interesting uses for network traces,
195 it is certain that more will evolve over time. As the traces are
196 used in new ways, it may be necessary to add new data to the trace
197 format. Rather than force the trace format to be redesigned, we have
198 structured the format to be extensible. There is a built-in
199 mechanism to add to the kinds of data that can be recorded in network
200 traces.
201
202 This extensibility is of little use if the tool set needs to change
203 as the trace format is extended. Recognizing this, we have made the
204 format -- particularly the extensible portions -- self-describing.
205 Thus, old versions of tools can continue to work with extended
206 traces, if perhaps in a less than optimal way.
207
208 In our experience with other tracing systems, management of trace
209 files is often difficult at best. Common problems include the need
210 to manage multiple trace files as a unit, not easily being able to
211 extract the salient features of large trace files, and having to use
212 dedicated trace management tools to perform even the simplest tasks.
213 To help cope with file management, we have designed the the traces to
214 be split or merged easily. To reduce dependence on specialized
215 tools, we've chosen to store some descriptive information as ASCII
216 strings, allowing minimal access to the standard UNIX tool suite.
217
218
219
220 <span class="grey">Noble, et. al. Informational [Page 4]</span></pre>
221 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
222 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
223
224
225 <span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Trace Format</span>
226
227 This section describes the format for network traces. We begin by
228 presenting the basic abstractions that are key to the trace format:
229 the record, and the track, a collection of related records. We then
230 describe the records at the beginning and end of a trace, the header
231 and footer. The bulk of the section describes the three kinds of
232 record tracks: packet, device, and general. These also make up the
233 bulk of the actual trace. We conclude the section with a discussion
234 of two special purpose records: the annotation and the trace data
235 loss records.
236
237 <span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a>. Basic Abstractions</span>
238
239 <span class="h4"><a class="selflink" id="section-4.1.1" href="#section-4.1.1">4.1.1</a>. Records</span>
240
241 A record is the smallest unit of trace data. There are several
242 different types of records, each of which is discussed in Sections
243 4.2 through 4.7. All of the records share several features in
244 common; these features are described here.
245
246 Records are composed of fields, which are stored in network order.
247 Most of the fields in our records are word-sized. Although this may
248 be wasteful in space, we chose to leave room to grow and keep trace
249 management simple.
250
251 The first field in each record is a magic word, a random 32 bit
252 pattern that both identifies the record's type and lends some
253 confidence that the record is well formed. Many record types have
254 both required and optional fields; thus they can be of variable size.
255 We place every record's size in its second field. By comparing the
256 size of a record to the known constraints for the record's type, we
257 can gain further confidence that a record is well-formed. This basic
258 record structure is illustrated in Figure 1.
259
260 All records also contain a two-word timestamp. This timestamp can
261 take one of two formats: timeval or timespec. Only one of the two
262 formats is used in any given trace, and the format is specified at
263 the start of a trace file. The first word in either format is the
264 number of seconds that have elapsed since midnight, January 1, 1970.
265 The second word is the additional fractions of a second. In the
266 timeval format, these fractions are expressed in microseconds, in the
267 same way that many current operating systems express time. In the
268 timespec format, these fractions are expressed in nanoseconds, the
269 POSIX time standard. We've chosen these two values since they are
270 convenient, cover most current and anticipated systems' notions of
271 time, and offer appropriate granularity for measuring network events.
272
273
274
275
276 <span class="grey">Noble, et. al. Informational [Page 5]</span></pre>
277 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
278 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
279
280
281 +------------------+
282 | Magic Number |
283 | Size of Record |
284 +------------------+
285 | Required Fields |
286 | ... |
287 +------------------+
288 | Optional Fields |
289 | ... |
290 +------------------+
291
292 Figure 1: Record format
293
294 <span class="h4"><a class="selflink" id="section-4.1.2" href="#section-4.1.2">4.1.2</a>. Tracks</span>
295
296 Many of the record types have both fixed, required fields, as well as
297 a set of optional fields. It is these options that provide
298 extensibility to our trace format. However, to provide a self-
299 describing trace, we need some compact way of determining which
300 optional fields are present in a given record. To do this, we group
301 related sets of packets into tracks. For example, a set of records
302 that captured packet activity for a single protocol between two
303 machines might be put together into a track. A track is a header
304 followed by some number of related records; the header completely
305 describes the format of the individual records. Records from
306 separate tracks can be interleaved with one another, so long as the
307 header for each individual track appears before any of the track's
308 records. Figure 2 shows an example of how records from different
309 tracks might be interleaved.
310
311 Track headers describe their records' content through property lists.
312 An entry in a property list is a two-element tuple consisting of a
313 name and a value. The name is a word which identifies the property
314 defined by this entry. Some of these properties are measured only
315 once for a track, for example, the address of a one-hop router in a
316 track recording packets from that router. Others are measured once
317 per record in that track, such as the signal strength of a device
318 which changes over time. The former, which we call header-only
319 properties, have their most significant name bit set. The value
320 field of a header-only property holds the measured value of the
321 property. Otherwise, the value field holds the number of words used
322 in each of the track's records.
323
324
325
326
327
328
329
330
331
332 <span class="grey">Noble, et. al. Informational [Page 6]</span></pre>
333 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
334 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
335
336
337 +----------++----------++----------++----------++----------+
338 | Track #1 || Track #1 || Track #2 || Track #1 || Track #2 |
339 | Header || Entry || Header || Entry || Entry |
340 +----------++----------++----------++----------++----------+
341
342 Figure 2: Interleaved track records
343
344 Those properties measured in each record in the track are grouped
345 together in a value list at the end of each such record. They appear
346 in the same order that was specified in the track header's property
347 list so that tools can properly attribute data. Thus, even if a tool
348 doesn't know what property a particular name represents, it can
349 identify which parts of a trace record are measuring that property,
350 and ignore them.
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388 <span class="grey">Noble, et. al. Informational [Page 7]</span></pre>
389 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
390 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
391
392
393 <span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a>. Trace Headers and Footers</span>
394
395 Trace files begin with a trace header, and end with a trace footer.
396 The formats of these appear in Figure 3. The header specifies
397 whether this trace was collected on a single machine, or was merged
398 from several other traces. In the former case, the IP address and
399 host name of the machine are recorded. In the latter, the IP address
400 is taken from the family of Class E address, which are invalid. We
401 use a family of invalid addresses so that even if we cannot identify
402 a number of hosts participating in the trace we can still distinguish
403 records from distinct hosts.
404
405 #define TR_DATESZ 32
406 #define TR_NAMESZ 64
407
408 struct tr_header_t {
409 u_int32_t h_magic;
410 u_int32_t h_size;
411 u_int32_t h_time_fmt; /* usec or nsec */
412 struct tr_time_t h_ts; /* starting time */
413 char h_date[TR_DATESZ]; /* Date collected */
414 char h_agent[TR_NAMESZ]; /* DNS name */
415 u_int32_t h_agent_ip;
416 char h_desc[0]; /* variable size */
417 };
418
419 struct tr_end_t {
420 u_int32_t e_magic;
421 u_int32_t e_size;
422 struct tr_time_t e_ts; /* end time */
423 char e_date[32]; /* Date end written */
424 };
425
426
427 Figure 3: Trace header and footer records
428
429 The trace header also specifies which time stamp format is used in
430 the trace, and the time at which the trace begins. There is a
431 variable-length description that is a string meant to provide details
432 of how the trace was collected. The trace footer contains only the
433 time at which the trace ended; it serves primarily as a marker to
434 show the trace is complete.
435
436 Unlike other kinds of records in the trace format, the header and
437 footer records have several ASCII fields. This is to allow standard
438 utilities some access to the contents of the trace, without resorting
439 to specialized tools.
440
441
442
443
444 <span class="grey">Noble, et. al. Informational [Page 8]</span></pre>
445 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
446 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
447
448
449 <span class="h3"><a class="selflink" id="section-4.3" href="#section-4.3">4.3</a>. Packet Tracks</span>
450
451 Measuring packet activity is the main focus of the network tracing
452 project. Packet activity is recorded in tracks, with a packet header
453 and a set of packet entries. A single track is meant to capture the
454 activity of a single protocol, traffic from a single router, or some
455 other subset of the total traffic seen by a machine. The required
456 portions of packet headers and entries are presented in Figure 4.
457
458 Packet track headers identify which host generated the trace records
459 for that track, as well as the time at which the track began. It
460 records the device on which these packets are received or sent, and
461 the protocol used to ship the packet; these allow interpretation of
462 device-specific or protocol-specific options. The header concludes
463 with the property list for the track.
464
465 struct tr_pkt_hdr_t {
466 u_int32_t ph_magic;
467 u_int32_t ph_size;
468 u_int32_t ph_defines; /* magic number defined */
469 struct tr_time_t ph_ts;
470 u_int32_t ph_ip; /* host generating stream */
471 u_int32_t ph_dev_type; /* device collected from */
472 u_int32_t ph_protocol; /* protocol */
473 struct tr_prop_lst_t ph_plist[0]; /* variable size */
474 };
475
476 struct tr_pkt_ent_t {
477 u_int32_t pe_magic;
478 u_int32_t pe_size;
479 struct tr_time_t pe_ts;
480 u_int32_t pe_psize; /* packet size */
481 u_int32_t pe_vlist[0]; /* variable size */
482 };
483
484
485 Figure 4: Packet header and entry records
486
487 A packet entry is generated for every traced packet. It contains the
488 size of the traced packet, the time at which the packet was sent or
489 received, and the list of property measurements as specified in the
490 track header.
491
492 The options we have defined to date are in Table 1. Several of these
493 have played an important role in our early experiments. ADDR_PEER
494 identifies the senders of traffic during the experiment. We can
495 determine network performance using either PKT_SENTTIME for one-way
496 traffic between two hosts with closely synchronized clocks, or round
497
498
499
500 <span class="grey">Noble, et. al. Informational [Page 9]</span></pre>
501 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
502 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
503
504
505 trip ICMP ECHO traffic and the ICMP_PINGTIME option. Tracking
506 PKT_SEQUENCE numbers sheds light on both loss rates and patterns.
507 <a href="#section-5">Section 5</a> discusses how these measurements are used.
508
509 <span class="h3"><a class="selflink" id="section-4.4" href="#section-4.4">4.4</a>. Device Tracks</span>
510
511 Our trace format records details of the devices which carry network
512 traffic. To date, we've found this most useful for correlating lost
513 packets with various signal parameters provided by wireless devices.
514 The required portions of device header and entry records appear in
515 Figure 5, and are quite simple. Device track headers identify the
516 host generating the track's records, the time at which the
517 observation starts, and the type of device that is being traced.
518 Each entry contains the time of the observation, and the list of
519 optional characteristics.
520
521 +---------------+-----------------------------------------------+
522 | ADDR_PEER | Address of peer host |
523 | ADDR_LINK | Address of one-hop router |
524 | BS_LOC_X | One-hop router's X coordinate (header only) |
525 | BS_LOC_Y | One-hop router's Y coordinate (header only) |
526 | PKT_SEQUENCE | Sequence number of packet |
527 | PKT_SENTTIME | Time packet was sent |
528 | PKT_HOPS | Number of hops packet took |
529 | SOCK_PORTS | Sending and receiving ports |
530 | IP_PROTO | Protocol number of an IP packet |
531 | ICMP_PINGTIME | Roundtrip time of an ICMP ECHO/REPLY pair |
532 | ICMP_KIND | Type and code of an ICMP packet |
533 | ICMP_ID | The id field of an ICMP packet |
534 | PROTO_FLAGS | Protocol-specific flags |
535 | PROTO_ERRLIST | Protocol-specific status/error words |
536 +---------------+-----------------------------------------------+
537 Table 1: Current optional fields for packet entries
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556 <span class="grey">Noble, et. al. Informational [Page 10]</span></pre>
557 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
558 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
559
560
561 struct tr_dev_hdr_t {
562 u_int32_t dh_magic;
563 u_int32_t dh_size;
564 u_int32_t dh_defines; /* Magic number defined */
565 struct tr_time_t dh_ts;
566 u_int32_t dh_ip; /* host generating stream */
567 u_int32_t dh_dev_type; /* device described */
568 struct tr_prop_lst_t dh_plist[0]; /* Variable size */
569 };
570
571 struct tr_dev_ent_t {
572 u_int32_t de_magic;
573 u_int32_t de_size;
574 struct tr_time_t de_ts;
575 u_int32_t de_vlist[0]; /* Variable size */
576 };
577
578
579 Figure 5: Device header and entry records
580
581 These optional characteristics, listed in Table 2, are mostly
582 concerned with the signal parameters of the wireless interfaces we
583 have available. Interpreting these parameters is heavily device-
584 dependent. We give examples of how we've used device observations in
585 <a href="#section-5">Section 5</a>.
586
587 +-----------------+--------------------------------------------------+
588 | DEV_ID | Major and minor number of device (header only) |
589 | DEV_STATUS | Device specific status registers |
590 | WVLN_SIGTONOISE | Signal to noise ratio reported by WaveLAN |
591 | WVLN_SIGQUALITY | Signal quality reported by WaveLAN |
592 | WVLN_SILENCELVL | WaveLAN silence level |
593 +-----------------+--------------------------------------------------+
594 Table 2: Current optional fields for packet entries
595
596 <span class="h3"><a class="selflink" id="section-4.5" href="#section-4.5">4.5</a>. Miscellaneous Tracks</span>
597
598 We use miscellaneous, or general, tracks to record things that don't
599 fit clearly in either the packet or device model. At the moment,
600 physical location of a mobile host is the only attribute tracked in
601 general trace records. The required portion of the general header
602 and entry records is shown in Figure 6, the two optional properties
603 are in Table 3. In addition to the property list, general headers
604 have only the IP address of the host generating the record and the
605 time at which observations began. General entries have only a
606 timestamp, and the optional fields.
607
608
609
610
611
612 <span class="grey">Noble, et. al. Informational [Page 11]</span></pre>
613 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span>
614 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
615
616
617 <span class="h3"><a class="selflink" id="section-4.6" href="#section-4.6">4.6</a>. Annotations</span>
618
619 An experimenter may occasionally want to embed arbitrary descriptive
620 text into a trace. We include annotation records to provide for
621 this. Such records are not part of a track; they stand alone. The
622 structure of an annotation record is shown in Figure 7. Annotations
623 include the time at which the annotation was inserted in the trace,
624 the host which inserted the annotation, and the variable-sized text
625 of the annotation itself.
626
627 struct tr_gen_hdr_t {
628 u_int32_t gh_magic;
629 u_int32_t gh_size;
630 u_int32_t gh_defines;
631 struct tr_time_t gh_ts;
632 u_int32_t gh_ip;
633 struct tr_prop_lst_t gh_plist[0]; /* Variable size */
634 };
635
636 struct tr_gen_ent_t {
637 u_int32_t ge_magic;
638 u_int32_t ge_size;
639 struct tr_time_t ge_ts;
640 u_int32_t ge_vlist[0]; /* Variable size */
641 };
642
643 Figure 6: General header and entry records
644
645
646 +------------+--------------------------------------------+
647 | MH_LOC_X | Mobile host's X coordinate (map-relative) |
648 | MH_LOC_Y | Mobile host's Y coordinate (map-relative) |
649 | MH_LOC_LAT | Mobile host's GPS latitude |
650 | MH_LOC_LON | Mobile host's GPS longitude |
651 +------------+--------------------------------------------+
652 Table 3: Current optional fields for general entries
653
654
655 struct tr_annote_t {
656 u_int32_t a_magic;
657 u_int32_t a_size;
658 struct tr_time_t a_ts;
659 u_int32_t a_ip;
660 char a_text[0]; /* variable size */
661 };
662
663
664 Figure 7: Annotation records
665
666
667
668 <span class="grey">Noble, et. al. Informational [Page 12]</span></pre>
669 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span>
670 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
671
672
673 <span class="h3"><a class="selflink" id="section-4.7" href="#section-4.7">4.7</a>. Lost Trace Data</span>
674
675 It is possible that, during collection, some trace records may be
676 lost due to trace buffer overflow or other reasons. Rather than
677 throw such traces away, or worse, ignoring the lost data, we've
678 included a loss record to count the types of other records which are
679 lost in the course of trace collection. Loss records are shown in
680 Figure 8.
681
682 struct tr_loss_t {
683 u_int32_t l_magic;
684 u_int32_t l_size;
685 struct tr_time_t l_ts;
686 u_int32_t l_ip;
687 u_int32_t l_pkthdr;
688 u_int32_t l_pktent;
689 u_int32_t l_devhdr;
690 u_int32_t l_devent;
691 u_int32_t l_annote;
692 };
693
694 Figure 8: Loss records
695
696 <span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Software Components</span>
697
698 In this section, we describe the set of tools that have been built to
699 date for mobile network tracing. We believe many of these tools are
700 widely applicable to network tracing tasks, but some have particular
701 application to mobile network tracing. We begin with an overview of
702 the tools, their applicability, and the platforms on which they are
703 currently supported, as well as those they are being ported to. This
704 information is summarized in Table 4.
705
706 We have made every effort to minimize dependencies of our software on
707 anything other than protocol and device specifications. As a result,
708 we expect ports to other BSD-derived systems to be straightforward;
709 ports to other UNIX systems may be more complicated, but feasible.
710
711 There are three categories into which our tracing tools can be
712 placed: trace collection, trace modulation, and trace analysis.
713 Trace collection tools are used for generating new traces. They
714 record information about the general networking facilities, as well
715 as data specific to mobile situations: mobile host location, base
716 station location, and wireless device characteristics. These tools
717 are currently supported on BSDI, and are being ported to NetBSD. We
718 describe these tools in <a href="#section-5.1">Section 5.1</a>.
719
720
721
722
723
724 <span class="grey">Noble, et. al. Informational [Page 13]</span></pre>
725 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span>
726 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
727
728
729 Trace modulation tools emulate the performance of a traced wireless
730 network on a private wired network. The trace modulation tools,
731 discussed in <a href="#section-5.2">Section 5.2</a>, are currently supported on NetBSD
732 platforms. They are geared toward replaying low speed/quality
733 networks on faster and more reliable ones, and are thus most
734 applicable to reproducing mobile environments.
735
736 In <a href="#section-5.3">Section 5.3</a>, we conclude with a set of trace processing and
737 analysis tools, which are currently supported on both NetBSD and BSDI
738 platforms. Our analyses to date have focused on properties of
739 wireless networks, and are most directly applicable to mobile traces.
740 The processing tools, however, are of general utility.
741
742 +--------------+--------------+--------------+
743 | Collection | Modulation | Analysis |
744 +-----------+--------------+--------------+--------------+
745 | NetBSD | In Progress | Supported | Supported |
746 | BSDI | Supported | Planned | Supported |
747 +-----------+--------------+--------------+--------------+
748 This table summarizes the currently supported platforms for the tracing
749 tool suites, and the platforms to which ports are underway.
750
751 Table 4: Tool Availability
752
753 <span class="h3"><a class="selflink" id="section-5.1" href="#section-5.1">5.1</a>. Trace Collection Tools</span>
754
755 The network trace collection facility comprises two key components:
756 the trace agent and the trace collector. They are shown in Figure 9.
757
758 The trace agent resides in the kernel where it can obtain data that
759 is either expensive to obtain or inaccessible from the user level.
760 The agent collects and buffers data in kernel memory; the user-level
761 trace collector periodically extracts data from this kernel buffer
762 and writes it to disk. The buffer amortizes the fixed costs of data
763 transfer across a large number of records, minimizing the impact of
764 data transfer on system performance. The trace collector retrieves
765 data through a pseudo-device, ensuring that only a single -- and
766 therefore complete -- trace file is being generated from a single
767 experiment. To provide simplicity and efficiency, the collector does
768 not interpret extracted data; it is instead processed off-line by the
769 post-processing and analysis tools described in Sections <a href="#section-5.2">5.2</a> and <a href="#section-5.3">5.3</a>.
770
771 There are three sorts of data collected by the tracing tools: network
772 traffic, network device characteristics, and mobile host location.
773 The first two are collected in much the same way; we describe the
774 methodology in <a href="#section-5.1.1">Section 5.1.1</a>. The last is collected in two novel
775 ways. These collection methods are addressed in <a href="#section-5.1.2">Section 5.1.2</a>.
776
777
778
779
780 <span class="grey">Noble, et. al. Informational [Page 14]</span></pre>
781 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span>
782 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
783
784
785 +-----------+ write to disk
786 | Trace | ==============&gt;
787 | Collector |
788 +-----------+
789 A
790 ========================================|===== kernel boundary
791 +-----------------+ |
792 | Transport Layer | |
793 |-----------------| +------------------+
794 | Network Layer |------------&gt;| Trace +------+ |
795 |-----------------| | Agent |buffer| |
796 | NI | NI | NI |------------&gt;| +------+ |
797 +-----------------+ +------------------+
798 This figure illustrates the components of trace collection. The NI's
799 are network interfaces.
800
801 Figure 9: Components of trace collection
802
803 <span class="h4"><a class="selflink" id="section-5.1.1" href="#section-5.1.1">5.1.1</a>. Traffic and Device Collection</span>
804
805 The trace agent exports a set of function calls for traffic and
806 device data collection. Traffic data is collected on a per-packet
807 basis. This is done via a function called from device drivers with
808 the packet and a device identifier as arguments. For each packet,
809 the trace record contains the source and destination address options.
810 Since our trace format assembles related packets into tracks, common
811 information, such as the destination address, is recorded in the
812 track header to reduce the record size for each packet entry. We
813 also record the size of each packet.
814
815 Information beyond packet size and address information is typically
816 protocol-dependent. For transport protocols such as UDP and TCP, for
817 example, we record the source and destination port numbers; TCP
818 packet records also contain the sequence number. For ICMP packets,
819 we record their type, code and additional type-dependent data. As
820 explained in <a href="#section-5.2.3">Section 5.2.3</a>, we record the identifier, sequence number
821 and time stamp for ICMP ECHOREPLY packets.
822
823 Before appending the record to the trace buffer, we check to see if
824 it is the first record in a track. If so, we create a new packet
825 track header, and write it to the buffer prior the packet entry.
826
827 Our trace collection facility provides similar mechanisms to record
828 device-specific data such as signal quality, signal level, and noise
829 level. Hooks to these facilities can be easily added to the device
830 drivers to invoke these tracing mechanisms. The extensible and
831 self-describing features of our trace format allow us to capture a
832 wide variety of data specific to particular network interfaces.
833
834
835
836 <span class="grey">Noble, et. al. Informational [Page 15]</span></pre>
837 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span>
838 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
839
840
841 For wireless network devices, we record several signal quality
842 measurements that the interfaces provide. Although some interfaces,
843 such as NCR's WaveLAN, can supply this of information for every
844 packet received, most devices average their measurements over a
845 longer period of time. As a result, we only trace these measurements
846 periodically. It is up to the device drivers to determine the
847 frequency at which data is reported to the trace agent.
848
849 When devices support it, we also trace status and error events. The
850 types of errors, such as CRC or buffer overflow, allow us to
851 determine causes for some observed packet losses. For example, we
852 can attribute loss to either the wireless channel or the network
853 interface.
854
855 <span class="h4"><a class="selflink" id="section-5.1.2" href="#section-5.1.2">5.1.2</a>. Location Tracing</span>
856
857 At first thought, recording the position of a mobile host seems
858 straightforward. It can be approximated by recording the base
859 station (BS) with which the mobile host is communicating. However,
860 due to the large coverage area provided by most radio interfaces,
861 this information provides a loose approximation at best. In
862 commercial deployments, we may not be able to reliably record the
863 base station with which a mobile host communicates. This section
864 outlines our collection strategy for location information in both
865 outdoor and indoor environments.
866
867 The solution that we have considered for wide-area, outdoor
868 environments makes use of the Global Positioning System (GPS). The
869 longitude and latitude information provided by the GPS device is
870 recorded in a general track.
871
872 Indoor environments require a different approach because the
873 satellite signals cannot reach a GPS device inside a building. We
874 considered deploying an infrared network similar to the Active Badge
875 [<a href="#ref-14" title="and Gibbons">14</a>] or the ParcTab [<a href="#ref-12" title="and Want">12</a>]; however, this significant addition to the
876 wireless infrastructure is not an option for most research groups.
877
878 As an alternative, we have developed a graphical tool that displays
879 the image of a building map and expects the user to "click" their
880 location as they move; the coordinates on the map are recorded in one
881 or more general tracks. The header of such tracks can also record
882 the coordinates of the base stations if they are known.
883
884 An extension can be easily added to this tool to permit multiple
885 maps. As the user requests that a new map be loaded into the
886 graphical tracing tool, a new location track is created along with an
887 annotation record that captures the file name of that image.
888 Locations of new base stations can be recorded in this new track
889
890
891
892 <span class="grey">Noble, et. al. Informational [Page 16]</span></pre>
893 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span>
894 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
895
896
897 header. Each location track should represent a different physical
898 and wireless environment.
899
900 <span class="h3"><a class="selflink" id="section-5.2" href="#section-5.2">5.2</a>. Trace Modulation Tools</span>
901
902 A key tool we have built around our trace format is PaM, the Packet
903 Modulator. The idea behind PaM is to take traces that were collected
904 by a mobile host and distill them into modulation traces. These
905 modulation traces capture the networking environment seen by the
906 traced host, and are used by a PaM kernel to delay, drop, or corrupt
907 incoming and outgoing packets. With PaM, we've built a testbed that
908 can repeatably, reliably mimic live systems under certain mobile
909 scenarios.
910
911 There are three main components to PaM. First, we've built a kernel
912 capable of delaying, dropping, and corrupting packets to match the
913 characteristics of some observed network. Second, we've defined a
914 modulation trace format to describe how such a kernel should modulate
915 packets. Third, we've built a tool to generate modulation traces
916 from certain classes of raw traces collected by mobile hosts.
917
918 <span class="h4"><a class="selflink" id="section-5.2.1" href="#section-5.2.1">5.2.1</a>. Packet Modulation</span>
919
920 The PaM modulation tool has been placed in the kernel between the IP
921 layer and the underlying interfaces. The tool intercepts incoming
922 and outgoing packets, and may choose to drop it, corrupt it, or delay
923 it. Dropping an incoming or outgoing packet is easy, simply don't
924 forward it along. Similarly, we can corrupt a packet by flipping
925 some bits in the packet before forwarding it.
926
927 Correctly delaying a packet is slightly more complicated. We model
928 the delay a packet experiences as the time it takes the sender to put
929 the packet onto the network interface plus the time it takes for the
930 last byte to propagate to the receiver. The former, the transmission
931 time, is the size of the packet divided by the available bandwidth;
932 the latter is latency.
933
934 Our approach at delay modulation is simple -- we assume that the
935 actual network over which packets travel is much faster and of better
936 quality than the one we are trying to emulate, and can thus ignore
937 it. We delay the packet according to our latency and bandwidth
938 targets, and then decide whether to drop or corrupt it. We take care
939 to ensure that packet modulation does not unduly penalize other
940 system activity, using the internal system clock to schedule packets.
941 Since this clock is at a large granularity compared to delay
942 resolution, we try to keep the average error in scheduling to a
943 minimum, rather than scheduling each packet at exactly the right
944 time.
945
946
947
948 <span class="grey">Noble, et. al. Informational [Page 17]</span></pre>
949 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span>
950 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
951
952
953 <span class="h4"><a class="selflink" id="section-5.2.2" href="#section-5.2.2">5.2.2</a>. Modulation Traces</span>
954
955 To tell the PaM kernel how the modulation parameters change over
956 time, we provide it with a series of modulation-trace entries. Each
957 of these entries sets loss and corruption percentages, as well as
958 network latency and inter-byte time, which is 1/bandwidth. These
959 entries are stored in a trace file, the format of which is much
960 simpler than record-format traces, and is designed for efficiency in
961 playback. The format of modulation traces is shown in Figure 10.
962
963 struct tr_rep_hdr_t {
964 u_int32_t rh_magic;
965 u_int32_t rh_size;
966 u_int32_t rh_time_fmt; /* nsec or used */
967 struct tr_time_t rh_ts;
968 char rh_date[TR_DATESZ];
969 char rh_agent[TR_NAMESZ];
970 u_int32_t rh_ip;
971 u_int32_t rh_ibt_ticks; /* units/sec, ibt */
972 u_int32_t rh_lat_ticks; /* units/sec, lat */
973 u_int32_t rh_loss_max; /* max loss rate */
974 u_int32_t rh_crpt_max; /* max corrupt rate */
975 char rh_desc[0]; /* variable size */
976 };
977
978 struct tr_rep_ent_t {
979 u_int32_t re_magic;
980 struct tr_time_t re_dur; /* duration of entry */
981 u_int32_t re_lat; /* latency */
982 u_int32_t re_ibt; /* inter-byte time */
983 u_int32_t re_loss; /* loss rate */
984 u_int32_t re_crpt; /* corrupt rate */
985 };
986
987
988 Figure 10: Modulation trace format
989
990 Modulation traces begin with a header that is much like that found in
991 record-format trace headers. Modulation headers additionally carry
992 the units in which latency and inter-byte time are expressed, and the
993 maximum values for loss and corruption rates. Individual entries
994 contain the length of time for which the entry applies as well as the
995 latency, inter-byte time, loss rate, and corruption rate.
996
997
998
999
1000
1001
1002
1003
1004 <span class="grey">Noble, et. al. Informational [Page 18]</span></pre>
1005 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span>
1006 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1007
1008
1009 <span class="h4"><a class="selflink" id="section-5.2.3" href="#section-5.2.3">5.2.3</a>. Trace Transformation</span>
1010
1011 How can we generate these descriptive modulation traces from the
1012 recorded observational traces described in <a href="#section-4">Section 4</a>? To ensure a
1013 high-quality modulation trace, we limit ourselves to a very narrow
1014 set of source traces. As our experience with modulation traces is
1015 limited, we use a simple but tunable algorithm to generate them.
1016
1017 Our basic strategy for determining latency and bandwidth is tied
1018 closely to our model of packet delays: delay is equal to
1019 transmission time plus latency. We further assume that packets which
1020 traversed the network near one another in time experienced the same
1021 latency and bandwidth during transit. Given this, we look for two
1022 packets of different size that were sent close to one another along
1023 the same path; from the transit times and sizes of these packets, we
1024 can determine the near-instantaneous bandwidth and latency of the
1025 end-to-end path covered by those packets. If traced packet traffic
1026 contains sequence numbers, loss rates are fairly easy to calculate.
1027 Likewise, if the protocol is capable of marking corrupt packets,
1028 corruption information can be stored and then extracted from recorded
1029 traces.
1030
1031 Using timestamped packet observations to derive network latency and
1032 bandwidth requires very accurate timing. Unfortunately, the laptops
1033 we have on hand have clocks that drift non-negligibly. We have
1034 chosen not to use protocols such as NTP [<a href="#ref-9" title="D. L. Improved Algorithms for Synchronizing Computer Network Clocks. IEEE/ACM Transactions on Networking 3">9</a>] for two reasons. First,
1035 they produce network traffic above and beyond that in the known
1036 traced workload. Second, and perhaps more importantly, they can
1037 cause the clock to speed up or slow down during adjustment. Such
1038 clock movements can play havoc with careful measurement.
1039
1040 As a result, we can only depend on the timestamps of a single machine
1041 to determine packet transit times. So, we use the ICMP ECHO service
1042 to provide workloads on traced machines; the ECHO request is
1043 timestamped on it's way out, and the corresponding ECHOREPLY is
1044 traced. We have modified the ping program to alternate between small
1045 and large packets. Traces that capture such altered ping traffic can
1046 then be subject to our transformation tool.
1047
1048 The tool itself uses a simple sliding window scheme to generate
1049 modulation entries. For each window position in the recorded trace,
1050 we determine the loss rate, and the average latency and bandwidth
1051 experienced by pairs of ICMP ECHO packets. The size and granularity
1052 of the sliding window are parameters of the transformation; as we
1053 gain experience both in analysis and modulation of wireless traces,
1054 we expect to be able to recommend good window sizes.
1055
1056
1057
1058
1059
1060 <span class="grey">Noble, et. al. Informational [Page 19]</span></pre>
1061 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span>
1062 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1063
1064
1065 Unfortunately, our wireless devices do not report corrupt packets;
1066 they are dropped by the hardware without operating system
1067 notification. However, our modulation system will also coerce any
1068 such corruptions to an increased loss rate, duplicating the behavior
1069 in the original network.
1070
1071 <span class="h3"><a class="selflink" id="section-5.3" href="#section-5.3">5.3</a>. Trace Analysis Tools</span>
1072
1073 A trace is only as useful as its processing tools. The requirements
1074 for such tools tools include robustness, flexibility, and
1075 portability. Having an extensible trace format places additional
1076 emphasis on the ability to work with future versions. To this end,
1077 we provide a general processing library as a framework for users to
1078 easily develop customized processing tools; this library is designed
1079 to provide both high portability and good performance.
1080
1081 In this section, we first present the trace library. We then
1082 describe a set of tools for simple post-processing and preparing the
1083 trace for further analyses. We conclude with a brief description of
1084 our analysis tools that are applied to this minimally processed data.
1085
1086 <span class="h4"><a class="selflink" id="section-5.3.1" href="#section-5.3.1">5.3.1</a>. Trace Library</span>
1087
1088 The trace library provides an interface that applications can use to
1089 simplify interaction with network traces, including functions to
1090 read, write, and print trace records. The trace reading and writing
1091 functions manage byte swapping as well as optional integrity checking
1092 of the trace as it is read or written. The library employs a
1093 buffering strategy that is optimized to trace I/O. Trace printing
1094 facilities are provided for both debugging and parsing purposes.
1095
1096 <span class="h4"><a class="selflink" id="section-5.3.2" href="#section-5.3.2">5.3.2</a>. Processing Tools</span>
1097
1098 The processing tools are generally the simplest set of tools we have
1099 built around the trace format. By far the most complicated one is
1100 the modulation-trace transformation tool described in <a href="#section-5.2.3">Section 5.2.3</a>;
1101 the remainder are quite simple in comparison. The first such tool is
1102 a parser that prints the content of an entire trace. With the trace
1103 library, it is less than a single page of C code. For each record,
1104 it prints the known data fields along with their textual names,
1105 followed by all the optional properties and values.
1106
1107 Since many analysis tasks tend to work with records of the same type,
1108 an enhanced version of the parser can split the trace data by tracks
1109 into many files, one per track. Each line of the output text files
1110 contains a time stamp followed by the integer values of all the
1111 optional data in a track entry; in this form traces are amenable to
1112 further analysis be scripts written in an interpreted language such
1113
1114
1115
1116 <span class="grey">Noble, et. al. Informational [Page 20]</span></pre>
1117 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span>
1118 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1119
1120
1121 as perl.
1122
1123 We have developed a small suite of tools providing simple functions
1124 such as listing all the track headers and changing the trace
1125 description as they have been needed. With the trace library, each
1126 such tool is trivial to construct.
1127
1128 <span class="h4"><a class="selflink" id="section-5.3.3" href="#section-5.3.3">5.3.3</a>. Analysis Tools</span>
1129
1130 Analysis tools depend greatly on the kind of information an
1131 experimenter wants to extract from the trace; our tools show our own
1132 biases in experimentation. Most analyses derive common statistical
1133 descriptions of traces, or establish some correlation between the
1134 trace data sets.
1135
1136 As early users of the trace format and collection tools, we have
1137 developed a few analysis tools to study the behavior of the wireless
1138 networks at our disposal. We have been particularly interested in
1139 loss characteristics of wireless channels and their relation to
1140 signal quality and the position of the mobile host. In this section,
1141 we briefly present some of these tools to hint at the kind of
1142 experimentation possible with our trace format.
1143
1144 Loss characteristics are among the most interesting aspects of
1145 wireless networks, and certainly among the least well understood. To
1146 shed light on this area, we have created tools to extract the loss
1147 information from collected traces; in addition to calculating the
1148 standard parameters such as the packet loss rate, the tool also
1149 derives transitional probabilities for a two-state error model.
1150
1151 This has proven to be a simple yet powerful model for capturing the
1152 burstiness observed in wireless loss rates due to fading signals. To
1153 help visualize the channel behavior in the presence of mobility, our
1154 tool can replay the movement of the mobile host while plotting the
1155 loss rate as it changes with time. It also allows us to zoom in the
1156 locations along the path and obtain detailed statistics over
1157 arbitrary time intervals.
1158
1159 Our traces can be further analyzed to understand the relationship
1160 between channel behavior and the signal quality. For wireless
1161 devices like the NCR WaveLAN, we can easily obtain measurements of
1162 signal quality, signal strength, and noise level. We have developed
1163 a simple statistical tool to test the correlation between measured
1164 signal and the loss characteristics. Variations of this test are
1165 also possible using different combinations of the three signal
1166 measurements and the movement of the host.
1167
1168
1169
1170
1171
1172 <span class="grey">Noble, et. al. Informational [Page 21]</span></pre>
1173 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span>
1174 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1175
1176
1177 The question of just how mobile such mobile hosts are can also be
1178 investigated through our traces. Position data are provided by
1179 traces that either involved GPS or user-supplied positions with our
1180 trace collection tools. This data is valuable for comparing and
1181 validating various mobility prediction algorithms. Given adequate
1182 network infrastructure and good signal measurements, we can determine
1183 the mobile location within a region that is significantly smaller
1184 than the cell size. We are developing a tool to combine position
1185 information and signal measurement from many traces to identify the
1186 "signal quality" signature for different regions inside a building.
1187 Once this signature database is completed and validated, it can be
1188 used to generate position information for other traces that contain
1189 only the signal quality information.
1190
1191 <span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Related Work</span>
1192
1193 The previous work most relevant to mobile network tracing falls into
1194 two camps. The first, chiefly exemplified by tcpdump [<a href="#ref-7" title="and McCanne">7</a>] and the BSD
1195 Packet Filter, or BPF [<a href="#ref-8" title="and Jacobson">8</a>], collect network traffic data. The second,
1196 notably Delayline [<a href="#ref-6" title="and Parrington">6</a>], and the later Probe/Fault Injection Tool [<a href="#ref-4" title="and Jahanian">4</a>],
1197 and the University of Lancaster's netowrk emulator [<a href="#ref-3" title="and Friday">3</a>], provide
1198 network modulation similar to PaM.
1199
1200 There are many systems that record network packet traffic; the de
1201 facto standard is tcpdump, which works in concert with a packet
1202 filter such as BPF. The packet filter is given a small piece of code
1203 that describes packets of interest, and the first several bytes of
1204 each packet found to be interesting is copied to a buffer for tcpdump
1205 to consume. This architecture is efficient, flexible, and has
1206 rightly found great favor with the networking community.
1207
1208 However, tcpdump cpatures only traffic data. It records neither
1209 information concerning mobile networking devices nor mobile host
1210 location. Rather than adding seperate software components to a host
1211 running tcpdump to capture this additional data, we have chosen to
1212 follow an integrative approach to ease trace file administration. We
1213 have kept the lessons of tcpdump and BPF to heart; namely copying
1214 only the information necessary, and transferring data up to user
1215 level in batches. It may well pay to investigate either
1216 incorporating device and location information directly into BPF, or
1217 taking the flexible filtering mechanism of BPF and including it in
1218 our trace collection software. For the moment, we do not know
1219 exactly what data we will need to explore the properties of mobile
1220 networks, and therefore do not exclude any data.
1221
1222 There are three notable systems that provide packet modulation
1223 similar to PaM. The earliest such work is Delayline, a system
1224 designed to emulate wide-area networks atop local-area ones; a goal
1225
1226
1227
1228 <span class="grey">Noble, et. al. Informational [Page 22]</span></pre>
1229 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span>
1230 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1231
1232
1233 similar to PaM's. The most striking difference between Delayline and
1234 PaM is that Delayline's emulation takes place entirely at the user-
1235 level, and requires applications to be recompiled against a library
1236 emulating the BSD socket system and library calls. While this is a
1237 portable approach that works well in the absence of kernel-level
1238 source access, it has the disadvantage that not all network traffic
1239 passes through the emulation layer; such traffic may have a profound
1240 impact on the performance of the final system. Delayline also
1241 differs from PaM in that the emulated network uses a single set of
1242 parameters for each emulated connection; performance remains fairly
1243 constant, and cannot change much over time.
1244
1245 The Lancaster network emulator was designed explicitly to model
1246 mobile networks. Rather than providing per-host modulation, it uses
1247 a single, central server through which all network traffic from
1248 instrumented applications passes. While this system also does not
1249 capture all traffic into and out of a particular host, it does allow
1250 modulation based on multiple hosts sharing a single emulated medium.
1251 There is a mechanism to change the parameters of emulation between
1252 hosts, though it is fairly cumbersome. The system uses a
1253 configuration file that can be changed and re-read while the system
1254 is running.
1255
1256 The system closest in spirit to PaM is the Probe/Fault Injection
1257 Tool. This system's design philosophy allows an arbitrary protocol
1258 layer -- including device drivers -- to be encapsulated by a layer
1259 below to modulate existing traffic, and a layer above to generate
1260 test traffic. The parameters of modulation are provided by a script
1261 in an interpreted language, presently Tcl, providing considerable
1262 flexibility. However, there is no mechanism to synthesize such
1263 scripts -- they must be explicitly designed. Furthermore, the use of
1264 an interpreted language such as Tcl limits the use of PFI to user-
1265 level implementations of network drivers, and may have performance
1266 implications.
1267
1268 <span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. Future Work</span>
1269
1270 This work is very much in its infancy; we have only begun to explore
1271 the possible uses for mobile network traces. We have uncovered
1272 several areas of further work.
1273
1274 The trace format as it stands is very IP-centric. While one could
1275 imagine using unknown IP addresses for non-IP hosts, while using
1276 header-only properties to encode other addressing schemes, this is
1277 cumbersome at best. We are looking into ways to more conveniently
1278 encode other addressing schemes, but are content to focus on IP
1279 networks for the moment.
1280
1281
1282
1283
1284 <span class="grey">Noble, et. al. Informational [Page 23]</span></pre>
1285 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span>
1286 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1287
1288
1289 Two obvious questions concerning wireless media are the following.
1290 How does a group of machines perform when sharing the same bandwidth?
1291 How asymmetric is the performance of real-world wireless channels?
1292 While we do have tools for merging traces taken from multiple hosts
1293 into a single trace file, we've not yet begun to examine such
1294 multiple-host scenarios in depth. We are also looking into
1295 instrumenting wireless base stations as well as end-point hosts.
1296
1297 Much of our planned work involves the PaM testbed. First and
1298 foremost, many wireless channels are known to be asymmetric;
1299 splitting the replay trace into incoming and outgoing modulation
1300 entries is of paramount importance. We would like to extend PaM to
1301 handle multiple emulated interfaces as well as applying different
1302 modulation parameters to packets from or to different destinations.
1303 One could also imagine tracing performance from several different
1304 networking environments, and switching between such environments
1305 under application control. For example, consider a set of traces
1306 showing radio performance at various altitudes; an airplane simulator
1307 in a dive would switch from high-altitude modulation traces to low-
1308 altitude ones.
1309
1310 Finally, we are anxious to begin exploring the properties of real-
1311 world mobile networks, and subjecting our own mobile system designs
1312 to PaM to see how they perform. We hope others can make use of our
1313 tools to do the same.
1314
1315 Acknowledgements
1316
1317 The authors wish to thank Dave Johnson, who provided early pointers
1318 to related work and helped us immeasurably in RFC formatting. We
1319 also wish to thank those who offered comments on early drafts of the
1320 document: Mike Davis, Barbara Denny, Mark Lewis, and Hui Zhang.
1321 Finally, we would like to thank Bruce Maggs and Chris Hobbs, our
1322 first customers!
1323
1324 This research was supported by the Air Force Materiel Command (AFMC)
1325 and ARPA under contract numbers F196828-93-C-0193 and DAAB07-95-C-
1326 D154, and the State of California MICRO Program. Additional support
1327 was provided by AT&amp;T, Hughes Aircraft, IBM Corp., Intel Corp., and
1328 Metricom. The views and conclusions contained here are those of the
1329 authors and should not be interpreted as necessarily representing the
1330 official policies or endorsements, either express or implied, of
1331 AFMC, ARPA, AT&amp;T, Hughes, IBM, Intel, Metricom, Carnegie Mellon
1332 University, the University of California, the State of California, or
1333 the U.S. Government.
1334
1335
1336
1337
1338
1339
1340 <span class="grey">Noble, et. al. Informational [Page 24]</span></pre>
1341 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-25" ></span>
1342 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1343
1344
1345 Security Considerations
1346
1347 This RFC raises no security considerations.
1348
1349 Authors' Addresses
1350
1351 Questions about this document can be directed to the authors:
1352
1353 Brian D. Noble
1354 Computer Science Department
1355 Carnegie Mellon University
1356 5000 Forbes Avenue
1357 Pittsburgh, PA 15213-3891
1358
1359 Phone: +1-412-268-7399
1360 Fax: +1-412-268-5576
1361 EMail: [email protected]
1362
1363
1364 Giao T. Nguyen
1365 Room 473 Soda Hall #1776 (Research Office)
1366 University of California, Berkeley
1367 Berkeley, CA 94720-1776
1368
1369 Phone: +1-510-642-8919
1370 Fax: +1-510-642-5775
1371 EMail: [email protected]
1372
1373
1374 Mahadev Satyanarayanan
1375 Computer Science Department
1376 Carnegie Mellon University
1377 5000 Forbes Avenue
1378 Pittsburgh, PA 15213-3891
1379
1380 Phone: +1-412-268-3743
1381 Fax: +1-412-268-5576
1382 EMail: [email protected]
1383
1384
1385 Randy H. Katz
1386 Room 231 Soda Hall #1770 (Administrative Office)
1387 University of California, Berkeley
1388 Berkeley, CA 94720-1770
1389
1390 Phone: +1-510-642-0253
1391 Fax: +1-510-642-2845
1392 EMail: [email protected]
1393
1394
1395
1396 <span class="grey">Noble, et. al. Informational [Page 25]</span></pre>
1397 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-26" ></span>
1398 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1399
1400
1401 References
1402
1403 [<a id="ref-1">1</a>] Chen, J. B., and Bershad, B. N. The Impact of Operating System
1404 Structure on Memory System Performance. In Proceedings of the
1405 14th ACM Symposium on Operating System Principles (Asheville,
1406 NC, December 1993).
1407
1408 [<a id="ref-2">2</a>] Dahlin, M., Mather, C., Wang, R., Anderson, T., and Patterson,
1409 D. A Quantitative Analysis of Cache Policies for Scalable
1410 Network File Systems. In Proceedings of the 1994 ACM SIGMETRICS
1411 Conference on Measurement and Modeling of Computer Systems
1412 (Nashville, TN, May 1994).
1413
1414 [<a id="ref-3">3</a>] Davies, N., Blair, G. S., Cheverst, K., and Friday, A. A
1415 Network Emulator to Support the Development of Adaptive
1416 Applications. In Proceedings of the 2nd USENIX Symposium on
1417 Mobile and Location Independent Computing (April 10-11 1995).
1418
1419 [<a id="ref-4">4</a>] Dawson, S., and Jahanian, F. Probing and Fault Injection of
1420 Dependable Distributed Protocols. The Computer Jouranl 38, 4
1421 (1995).
1422
1423 [<a id="ref-5">5</a>] Gloy, N., Young, C., Chen, J. B., and Smith, M. D. An Analysis
1424 of Dynamic Branch Prediction Schemes on System Workloads. In
1425 The Proceedings of the 23rd Annual International Symposium on
1426 Computer Architecture (May 1996).
1427
1428 [<a id="ref-6">6</a>] Ingham, D. B., and Parrington, G. D. Delayline: A Wide-Area
1429 Network Emulation Tool. Computing Systems 7, 3 (1994).
1430
1431 [<a id="ref-7">7</a>] Jacobson, V., Leres, C., and McCanne, S. The Tcpdump Manual
1432 Page. Lawrence Berkeley Laboratory, Berkeley, CA.
1433
1434 [<a id="ref-8">8</a>] McCanne, S., and Jacobson, V. The BSD Packet Filter: A New
1435 Architecture for User-level Packet Capture. In Proceedings of
1436 the 1993 Winter USENIX Technical Conference (San Deigo, CA,
1437 January 1993).
1438
1439 [<a id="ref-9">9</a>] Mills, D. L. Improved Algorithms for Synchronizing Computer
1440 Network Clocks. IEEE/ACM Transactions on Networking 3, 3 (June
1441 1995).
1442
1443 [<a id="ref-10">10</a>] Mummert, L. B., Ebling, M. R., and Satyanarayanan, M.
1444 Exploiting Weak Connectivity for Mobile File Access. In
1445 Proceedings of the 15th Symposium on Operating System Prinicples
1446 (Copper Mountain, CO, December 1995).
1447
1448
1449
1450
1451
1452 <span class="grey">Noble, et. al. Informational [Page 26]</span></pre>
1453 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-27" ></span>
1454 <span class="grey"><a href="./rfc2041">RFC 2041</a> Mobile Network Tracing October 1996</span>
1455
1456
1457 [<a id="ref-11">11</a>] Nelson, M. N., Welch, B. B., and Ousterhout, J. K. Caching in
1458 the Sprite Network File System. ACM Transactions on Computer
1459 Systems 6, 1 (February 1988).
1460
1461 [<a id="ref-12">12</a>] Schilit, B., Adams, N., Gold, R., Tso, M., and Want, R. The
1462 PARCTAB Mobile Computing System. In Proceedings of the 4th IEEE
1463 Workshop on Workstation Operating Systems (Napa, CA, October
1464 1993), pp. 34--39.
1465
1466 [<a id="ref-13">13</a>] Uhlig, R., Nagle, D., Stanley, T., Mudge, T., Sechrest, S., and
1467 Brown, R. Design Tradeoffs for Software-Managed TLBs. ACM
1468 Transactions on Computer Systems 12, 3 (August 1994).
1469
1470 [<a id="ref-14">14</a>] Want, R., Hopper, A., Falcao, V., and Gibbons, J. The Active
1471 Badge Location System. ACM Transactions on Information Systems
1472 10, 1 (January 1992), 91--102.
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508 Noble, et. al. Informational [Page 27]
1509 </pre>