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