RFC 2041
Mobile Network Tracing
Mobile Network Tracing 🎀
Okay bestie, this is the RFC, and it's giving research diary meets wishlist. 🦋 It's RFC 2041, titled "Mobile Network Tracing," from the Network Working Group in October 1996. The authors are B. Noble (Carnegie Mellon University), G. Nguyen (University of California, Berkeley), M. Satyanarayanan (Carnegie Mellon University), and R. Katz (University of California, Berkeley). It's Informational, so it's sharing knowledge, not setting a standard. 💅 Its title block doesn't list anything it obsoletes or updates, so it's standing on its own. ✨
Status of this Memo
Quick legal bit, but it matters 🙈: this memo provides information for the Internet community, and it does not specify an Internet standard of any kind. Distribution is unlimited. Basically, it's a sharing-is-caring doc. 🌸
Abstract
Mobile networks are both poorly understood and difficult to experiment with, and honestly, same. 😭 This RFC argues that mobile network tracing gives us two things: tools to better understand wireless channels, and a way to build realistic, repeatable testbeds for mobile software and systems. 🧚
It's a status report on the authors' own work tracing mobile networks. The big goal is to kick off discussion about a standard format for mobile network tracing, plus a testbed for mobile systems research. They share their format for collecting mobile network traces, plus tools that turn those traces into analytical models of mobile network behavior. 💜
They also describe tools for network modulation based on collected traces. Modulation lets you emulate wireless channel latency, bandwidth, loss, and error rates on private, wired networks. Designers can test systems in a realistic yet repeatable way, which is iconic. 🔥
1. Introduction ✨
How does one accurately capture and reproduce the behavior of a network? 🤔 This is an especially hard problem in mobile computing, because the network quality a mobile host experiences can change dramatically over time and space. Long-term averages can't capture it, and neither can simple analytical models. The variations in bandwidth, latency, and signal degradation a host sees are just too wild. 🌈 The solution here is network tracing, and it has two phases: trace recording and trace modulation.
In the trace recording phase, an experimenter with an instrumented mobile host physically travels a path they care about. 🚶♀️ While they're moving, packets from a known workload are generated by a static host. The mobile host records what it observes: the packets it receives from that workload, plus the device characteristics during the workload. When the traversal ends, the list of observations is an accurate trace of the network behavior for that trip. Do multiple traversals of the same path, using different workloads, and you get a trace family that collectively describes network quality on that path. Main character energy. 👑
In the trace modulation phase, mobile system and application software gets subjected to the network behavior recorded in a trace. 🎭 The mobile software runs on a LAN-attached host whose kernel has been modified to read a file containing the trace (possibly postprocessed for efficiency). That kernel then delays, drops, or otherwise degrades packets to match the behavior in the trace. So the mobile software experiences network quality that's indistinguishable from what was recorded. Also, trace modulation is fully transparent to mobile software. No source or binary changes needed. Iconic, no cap. 💖
Trace-based approaches have already proven super valuable in areas like file system design [2, 10, 11] and computer architecture. [1, 5, 13] So the authors expect network tracing to be just as useful for mobile system design and implementation. 🌸 A few examples they give:
- Detailed trace analyses can reveal how mobile networks behave and can validate predictive models. 🔍
- Traces can help with stress testing and debugging, since you can reproduce the network conditions where a bug first showed up. 🐛
- A system under development can be subjected to network conditions from distant real-life environments. 🌍
- A set of traces can work as a benchmark family for evaluating and comparing the adaptive capabilities of different mobile system designs. 🏆
The goal of this RFC is to encourage a widely-accepted standard format for network traces. Standardizing would make traces easy to share and would help trace-based benchmarks spread. 🫶 Wireless mobile networks are the main motivation, but the authors made a real effort to keep the work useful for other network types too. For example, the trace format and some of the tools may be valuable for analyzing and modeling ATM networks. 🦋
Here's how the rest of the RFC is laid out. First, it looks at the properties of wireless networks and backs up the claim that these networks are hard to model. ✨ Next, Section 3 covers the factors that should be taken into account when designing a trace format. Section 4 presents the details of the proposed trace format standard. Section 5 introduces a set of tools the authors built for collecting, analyzing, and replaying traces. Last, there's a discussion of related and future work. 🌈
2. Modeling Wireless Networks 📡
Wireless channels are seriously complex to model, and it's giving physics homework. 🧠 Their behavior depends on the physical properties of radio waves, like reflections off "hard" surfaces, diffraction around corners, and scattering caused by small objects. Site-specific geometries matter too. Channels are usually modeled as a signal strength that varies over time and distance, capturing the statistical nature of how reflected radio waves interact. The signal strength can swing by several orders of magnitude (+ or - 20-30 dB) within a short distance. 😭 Lots of people have tried to build general models of radio propagation inside buildings and over wide areas, but those models end up being inherently inaccurate. They can differ from actual measurements by an order of magnitude or more. Yikes. 💀
Signal-to-noise ratio, or SNR, measures how good the received signal is. If the SNR is too low, the receiver won't detect the signal, which causes bit errors and packet losses. But SNR isn't the only thing that causes losses. There's also inter-symbol interference caused by delay spread. That means an earlier transmitted symbol arrives late, after taking a circuitous path, and partially cancels out the current symbol. 🙃 Then there's Doppler shift, which shifts the frequency of the arriving signal because the transmitter and receiver are moving relative to each other. That makes reception harder. And if coherent reception is being used, receiver synchronization can get lost. 🌀
More empirically, wireless channels have been observed to follow a two-state error model. Channels are usually well behaved, but they occasionally slip into a bad state where many burst errors happen in a short time interval. 🌩️
Developers of network protocols and mobility algorithms must be able to test with realistic channel parameters... wait, not capitalized in the original, so the vibe is: they need to experiment with realistic channel parameters. 🧪 It's highly desirable for the wireless network to be modeled in a thoroughly reproducible way, so an algorithm and its variations can be evaluated in a controlled, repeatable manner. But this discussion makes it clear that whether you use analytical models or actually experiment with the network, the results will be either inaccurate or unlikely to reproduce. A trace-based approach fixes these problems. 💖
3. Desirable Trace Format Properties 🍓
When designing the trace format, the authors followed three principles. One, the format should be extensible. Two, it should be self-describing. Three, traces should be easy to manage. This section explains how each principle shaped the design. 🧚
Even though network traces already have several interesting uses, more will definitely show up over time. 🔮 As traces get used in new ways, it may become necessary to add new data to the format. Instead of redesigning the whole format each time, the authors made it extensible. There's a built-in mechanism for adding new kinds of data that can be recorded in network traces. ✨
Extensibility doesn't help much if the tool set has to change every time the format grows. 🙄 So the format, especially its extensible parts, is self-describing. That means older versions of tools can keep working with extended traces, maybe not as well as they could, but they still work. 🫶
Managing trace files is often rough, honestly. 😩 Common headaches include having to manage multiple trace files as a single unit, not being able to easily pull out the important features of large trace files, and needing dedicated trace management tools for even the simplest tasks. To help with file management, the traces are designed to be split or merged easily. To cut down on dependence on specialized tools, some descriptive information is stored as ASCII strings, so you can get by with the standard UNIX tool suite. 🐧💅
4. Trace Format 🎀
This section describes the format for network traces. 📝 It starts with the basic abstractions that the trace format is built on: the record, and the track, which is a collection of related records. Then it covers the records at the beginning and end of a trace, the header and footer. The bulk of the section describes the three kinds of record tracks: packet, device, and general. Those tracks make up most of the actual trace too. The section wraps up with two special-purpose records: the annotation and the trace data loss records. 🌸
4.1. Basic Abstractions 🧩
4.1.1. Records ✨
okay so a record is the tiniest unit of trace data, the building block of everything 🧱 There are several different kinds of records, and we're going through each one in Sections 4.2 through 4.7. they all share some features though, so we're covering those here 💅
records are made of fields, stored in network order 🌐 Most fields are word-sized. ngl that might be a little wasteful on space, but we wanted room to grow and trace management to stay simple 🫶
the first field in every record is a magic word: a random 32 bit pattern that tells you what type of record it is AND gives you some confidence the record is well formed 🔮 A lot of record types have both required and optional fields, so they can be different sizes. that's why we put the record's size in the second field 📏 By checking that size against what's known for that record type, we get even more confidence the record is well-formed. this basic layout is shown in Figure 1 👑
+------------------+
| Magic Number |
| Size of Record |
+------------------+
| Required Fields |
| ... |
+------------------+
| Optional Fields |
| ... |
+------------------+Figure 1: Record format
every record also has a two-word timestamp ⏰ This timestamp can be one of two formats: timeval or timespec. only one of them gets used in any given trace, and the format is set at the start of the trace file 📂 The first word in either format is the number of seconds since midnight, January 1, 1970. the second word holds the extra fractions of a second. in timeval, those fractions are in microseconds, which is how a lot of current operating systems do it 🖥️ in timespec, they're in nanoseconds, the POSIX time standard 🧚 We picked these two because they're convenient, they cover most current and expected systems' idea of time, and they give good granularity for measuring network events. literally perfect 💖
4.1.2. Tracks
okay this part is so good 🦋 Lots of record types have fixed, required fields AND a set of optional fields. those options are what make the trace format extensible ✨ But to make the trace self-describing, we need a compact way to figure out which optional fields are present in a given record. so we group related sets of packets into tracks 🎀 For example, a set of records that captured packet activity for one protocol between two machines could be put together into a track. a track is a header followed by some number of related records, and the header completely describes the format of those individual records 📜 Records from separate tracks can be interleaved with each other, as long as each track's header shows up before any of that track's records. Figure 2 shows an example of how records from different tracks might be interleaved 🌈
Track headers describe their records' content through property lists 📋 Each entry in a property list is a two-element tuple made of a name and a value. The name is a word that identifies the property defined by that entry. some properties only get measured once per track, like the address of a one-hop router in a track recording packets from that router 🧭 Others get measured once per record in the track, like the signal strength of a device that changes over time 📶 The first kind, which we call header-only properties, have their most significant name bit set 🔒 The value field of a header-only property holds the measured value of that property. For everything else, the value field holds the number of words used in each of the track's records 🔢
+----------++----------++----------++----------++----------+
| Track #1 || Track #1 || Track #2 || Track #1 || Track #2 |
| Header || Entry || Header || Entry || Entry |
+----------++----------++----------++----------++----------+Figure 2: Interleaved track records
the properties measured in each record are grouped together in a value list at the end of each record 🧃 They show up in the same order that was specified in the track header's property list, so tools can correctly attribute the data 🎯 That means even if a tool doesn't know what a particular property name stands for, it can still figure out which parts of a trace record are measuring that property, and just ignore them. iconic behaviour, honestly 💅
4.2. Trace Headers and Footers
trace files start with a trace header and end with a trace footer 🎬 The formats for both are in Figure 3. The header says whether the trace was collected on a single machine or merged from several other traces 🗂️ If it's a single machine, the IP address and host name of that machine get recorded. If it's a merged trace, the IP address is taken from the family of Class E addresses, which are invalid 🙈 We use a family of invalid addresses so that, even if we can't identify how many hosts took part in the trace, we can still tell apart the records from different hosts. big brain move, tbh 🧠
#define TR_DATESZ 32
#define TR_NAMESZ 64
struct tr_header_t {
u_int32_t h_magic;
u_int32_t h_size;
u_int32_t h_time_fmt; /* usec or nsec */
struct tr_time_t h_ts; /* starting time */
char h_date[TR_DATESZ]; /* Date collected */
char h_agent[TR_NAMESZ]; /* DNS name */
u_int32_t h_agent_ip;
char h_desc[0]; /* variable size */
};
struct tr_end_t {
u_int32_t e_magic;
u_int32_t e_size;
struct tr_time_t e_ts; /* end time */
char e_date[32]; /* Date end written */
};Figure 3: Trace header and footer records
the trace header also says which timestamp format is used in the trace, plus the time the trace begins ⏳ There's a variable-length description too, which is a string giving details about how the trace was collected 📝 The trace footer only contains the time the trace ended. it mainly acts as a marker to show the trace is complete ✅
unlike other record types in the trace format, the header and footer have several ASCII fields 🔤 This is so standard utilities can peek at the contents of the trace without needing specialized tools. slay for accessibility 👑
4.3. Packet Tracks
measuring packet activity is the main focus of the network tracing project 🔍 Packet activity gets recorded in tracks, each with a packet header and a set of packet entries. A single track is meant to capture the activity of one protocol, traffic from one router, or some other subset of the total traffic a machine sees 🛰️ The required parts of packet headers and entries are shown in Figure 4 💖
packet track headers identify which host generated the trace records for that track, plus the time the track began ⏰ They also record the device the packets were received or sent on, and the protocol used to ship the packet. those let you interpret device-specific or protocol-specific options 🔧 The header ends with the property list for the track 📋
struct tr_pkt_hdr_t {
u_int32_t ph_magic;
u_int32_t ph_size;
u_int32_t ph_defines; /* magic number defined */
struct tr_time_t ph_ts;
u_int32_t ph_ip; /* host generating stream */
u_int32_t ph_dev_type; /* device collected from */
u_int32_t ph_protocol; /* protocol */
struct tr_prop_lst_t ph_plist[0]; /* variable size */
};
struct tr_pkt_ent_t {
u_int32_t pe_magic;
u_int32_t pe_size;
struct tr_time_t pe_ts;
u_int32_t pe_psize; /* packet size */
u_int32_t pe_vlist[0]; /* variable size */
};Figure 4: Packet header and entry records
a packet entry gets generated for every traced packet 📦 It holds the size of the traced packet, the time it was sent or received, and the list of property measurements specified in the track header 📊
the options we've defined so far are in Table 1 🎀 A few of them played a big role in our early experiments. ADDR_PEER identifies the senders of traffic during the experiment 🙋 We can measure network performance using either PKT_SENTTIME for one-way traffic between two hosts with closely synchronized clocks, or round trip ICMP ECHO traffic with the ICMP_PINGTIME option ⚡ Tracking PKT_SEQUENCE numbers shows us both loss rates and patterns 👀 Section 5 discusses how these measurements are used. 💜
4.4. Device Tracks ✨
okay so bestie, device tracks are how this format keeps a record of the devices that carry network traffic 🛜 and we figured out pretty fast that this is the MOST useful bit for matching up lost packets with the signal numbers wireless gear hands back 🔥. The required parts of the device header and entry records are in Figure 5 and honestly they're super simple 💅. A device track header tells you which host made the track's records 🎀, when the observation kicks off ⏰, and what kind of device is getting traced 🧚. Each entry carries the time of its observation plus a list of optional characteristics 🍓.
Table 1 below is the list of optional fields for packet entries 💖
+---------------+-----------------------------------------------+
| ADDR_PEER | Address of peer host |
| ADDR_LINK | Address of one-hop router |
| BS_LOC_X | One-hop router's X coordinate (header only) |
| BS_LOC_Y | One-hop router's Y coordinate (header only) |
| PKT_SEQUENCE | Sequence number of packet |
| PKT_SENTTIME | Time packet was sent |
| PKT_HOPS | Number of hops packet took |
| SOCK_PORTS | Sending and receiving ports |
| IP_PROTO | Protocol number of an IP packet |
| ICMP_PINGTIME | Roundtrip time of an ICMP ECHO/REPLY pair |
| ICMP_KIND | Type and code of an ICMP packet |
| ICMP_ID | The id field of an ICMP packet |
| PROTO_FLAGS | Protocol-specific flags |
| PROTO_ERRLIST | Protocol-specific status/error words |
+---------------+-----------------------------------------------+
Table 1: Current optional fields for packet entriesstruct tr_dev_hdr_t {
u_int32_t dh_magic;
u_int32_t dh_size;
u_int32_t dh_defines; /* Magic number defined */
struct tr_time_t dh_ts;
u_int32_t dh_ip; /* host generating stream */
u_int32_t dh_dev_type; /* device described */
struct tr_prop_lst_t dh_plist[0]; /* Variable size */
};
struct tr_dev_ent_t {
u_int32_t de_magic;
u_int32_t de_size;
struct tr_time_t de_ts;
u_int32_t de_vlist[0]; /* Variable size */
}; Figure 5: Device header and entry recordsThese optional characteristics, which you'll see in Table 2, are mostly about the signal parameters of the wireless interfaces we have on hand 📡. Reading those parameters is super device-dependent, so fair warning, it's not one-size-fits-all 🙈. We show examples of how we've used device observations in Section 5 🌈.
+-----------------+--------------------------------------------------+
| DEV_ID | Major and minor number of device (header only) |
| DEV_STATUS | Device specific status registers |
| WVLN_SIGTONOISE | Signal to noise ratio reported by WaveLAN |
| WVLN_SIGQUALITY | Signal quality reported by WaveLAN |
| WVLN_SILENCELVL | WaveLAN silence level |
+-----------------+--------------------------------------------------+
Table 2: Current optional fields for packet entries4.5. Miscellaneous Tracks 🦋
okay so miscellaneous (or "general") tracks are the catch-all for stuff that doesn't fit neatly into the packet or device buckets 🧺. Right now, the only thing tracked in general records is the physical location of a mobile host 📍. The required part of the general header and entry records is in Figure 6, and the two optional properties are in Table 3 💜. Besides the property list, general headers only hold the IP address of the host that made the record and the time the observations started ⏰. General entries just have a timestamp and the optional fields 💅.
4.6. Annotations 🎀
sometimes an experimenter wants to shove some arbitrary descriptive text into a trace, and that's what annotation records are for 📝. They're not part of a track, they just stand alone 🦋. Figure 7 shows the structure. An annotation includes the time it was inserted into the trace ⏰, the host that inserted it 🫶, and the variable-sized text itself 🌸.
struct tr_gen_hdr_t {
u_int32_t gh_magic;
u_int32_t gh_size;
u_int32_t gh_defines;
struct tr_time_t gh_ts;
u_int32_t gh_ip;
struct tr_prop_lst_t gh_plist[0]; /* Variable size */
};
struct tr_gen_ent_t {
u_int32_t ge_magic;
u_int32_t ge_size;
struct tr_time_t ge_ts;
u_int32_t ge_vlist[0]; /* Variable size */
}; Figure 6: General header and entry records+------------+--------------------------------------------+
| MH_LOC_X | Mobile host's X coordinate (map-relative) |
| MH_LOC_Y | Mobile host's Y coordinate (map-relative) |
| MH_LOC_LAT | Mobile host's GPS latitude |
| MH_LOC_LON | Mobile host's GPS longitude |
+------------+--------------------------------------------+
Table 3: Current optional fields for general entriesstruct tr_annote_t {
u_int32_t a_magic;
u_int32_t a_size;
struct tr_time_t a_ts;
u_int32_t a_ip;
char a_text[0]; /* variable size */
}; Figure 7: Annotation records4.7. Lost Trace Data 💀
so, during collection, some trace records can get lost 😭 because the trace buffer overflowed or for other reasons. Instead of tossing those traces or, worse, just ignoring the missing data 🙈, we added a loss record that counts the other record types that got lost during collection 🔢. Loss records are in Figure 8 ✨.
struct tr_loss_t {
u_int32_t l_magic;
u_int32_t l_size;
struct tr_time_t l_ts;
u_int32_t l_ip;
u_int32_t l_pkthdr;
u_int32_t l_pktent;
u_int32_t l_devhdr;
u_int32_t l_devent;
u_int32_t l_annote;
}; Figure 8: Loss records- Software Components 👑
in this section we walk through the tools that have been built so far for mobile network tracing 🛠️. A lot of them are broadly useful for network tracing, but some are especially good for mobile stuff 📱. We start with an overview of the tools, what they're for, and which platforms they run on (plus the ones being ported to) 🗺️. All of that is summed up in Table 4 💖.
We went all in on keeping our software's dependencies down to protocol and device specs and nothing else 🫶. Because of that, we expect ports to other BSD-derived systems to be straightforward ✨. Ports to other UNIX systems might be trickier, but they're doable 💪.
There are three categories for our tracing tools: trace collection, trace modulation, and trace analysis 🎯. Trace collection tools generate new traces 📼. They record general networking info plus mobile-specific stuff like mobile host location, base station location, and wireless device characteristics 📡. These run on BSDI right now, and NetBSD is getting them soon 💅. We cover them in Section 5.1 🦋.
Trace modulation tools copy how a traced wireless network performs on a private wired network 🔁. They're covered in Section 5.2 and currently run on NetBSD 💜. They're built for replaying slow or flaky networks on faster, more reliable ones, so they're the best fit for reproducing mobile environments 🌸.
Last up, Section 5.3 has a set of trace processing and analysis tools that run on both NetBSD and BSDI 🧚. Our analyses so far focus on wireless network properties, so they fit mobile traces best, though the processing tools are useful for lots of stuff 🌈.
+--------------+--------------+--------------+
| Collection | Modulation | Analysis |
+-----------+--------------+--------------+--------------+
| NetBSD | In Progress | Supported | Supported |
| BSDI | Supported | Planned | Supported |
+-----------+--------------+--------------+--------------+This table sums up which platforms are currently supported for the tracing tool suites, and which platforms have ports underway 🗂️.
Table 4: Tool Availability5.1. Trace Collection Tools 🔥
the network trace collection facility has two key pieces: the trace agent and the trace collector 🤝. They're shown in Figure 9 ✨.
The trace agent lives in the kernel, where it can grab data that's either expensive to get or can't be reached from user level 🧠. It collects and buffers data in kernel memory 📦. The user-level trace collector periodically pulls data out of that kernel buffer and writes it to disk 💾. The buffer spreads the fixed cost of data transfer across lots of records, so the transfer doesn't hit system performance too hard 🙌. The trace collector gets data through a pseudo-device, which makes sure only a single (and therefore complete) trace file gets generated from one experiment 🎀. To keep things simple and fast, the collector doesn't interpret the data it extracts 🧃. Instead, the post-processing and analysis tools described in Sections 5.2 and 5.3 handle it off-line 🌙.
There are three kinds of data collected by the tracing tools: network traffic, network device characteristics, and mobile host location 🗺️. The first two get collected in pretty much the same way, and we describe that methodology in Section 5.1.1 💅. Mobile host location is collected in two novel ways 🤯, which are covered in Section 5.1.2 🦋.
+-----------+ write to disk
| Trace | ==============>
| Collector |
+-----------+
A
========================================|===== kernel boundary
+-----------------+ |
| Transport Layer | |
|-----------------| +------------------+
| Network Layer |------------>| Trace +------+ |
|-----------------| | Agent |buffer| |
| NI | NI | NI |------------>| +------+ |
+-----------------+ +------------------+
This figure illustrates the components of trace collection. The NI's
are network interfaces. Figure 9: Components of trace collection5.1.1. Traffic and Device Collection ✨
okay bestie, so the trace agent exports a set of function calls for collecting traffic and device data 💖. traffic data gets collected per packet 🎀. a function gets called from the device drivers with the packet and a device identifier as arguments. for each packet, the trace record holds the source and destination address options. our trace format groups related packets into tracks, so stuff like the destination address gets stored once in the track header. that keeps each packet entry small 🦋. we also record the size of each packet.
beyond size and address info, the rest is protocol-dependent 👑. for transport protocols like UDP and TCP, we record the source and destination port numbers, and TCP packet records also have the sequence number. for ICMP packets we record their type, code, and extra type-dependent data. as explained in Section 5.2.3, we record the identifier, sequence number, and time stamp for ICMP ECHOREPLY packets 💅.
before appending a record to the trace buffer, we check whether it's the first record in a track. if it is, we make a new packet track header and write it to the buffer right before the packet entry 🧚.
our trace collection facility also has similar mechanisms for recording device-specific data like signal quality, signal level, and noise level 🌈. hooks can be easily added to the device drivers to call these tracing mechanisms. the extensible, self-describing features of our trace format let us capture a whole bunch of data specific to particular network interfaces ✨.
for wireless devices, we record several signal quality measurements that the interfaces provide 🫶. some interfaces, like NCR's WaveLAN, can supply this info for every packet received. most devices average their measurements over a longer period, though, so we only trace these measurements periodically. it's up to the device drivers to decide how often data gets reported to the trace agent.
when devices support it, we also trace status and error events 😭. the types of errors, like CRC or buffer overflow, help us figure out causes for some observed packet losses. for example, we can attribute loss to either the wireless channel or the network interface 💀.
5.1.2. Location Tracing
at first thought, recording the position of a mobile host seems straightforward 🌸. it can be approximated by recording the base station (BS) the mobile host is communicating with. however, because most radio interfaces cover a large area, this info is a loose approximation at best 🙈. in commercial deployments, we may not be able to reliably record the base station a mobile host talks to. this section lays out our collection strategy for location info in both outdoor and indoor environments 🗺️.
for wide-area, outdoor environments, the solution we've considered uses the Global Positioning System (GPS) 🛰️. the longitude and latitude info from the GPS device gets recorded in a general track.
indoor environments need a different approach, since satellite signals can't reach a GPS device inside a building 🏢. we considered deploying an infrared network like the Active Badge [14] or the ParcTab [12]. however, that's a significant addition to the wireless infrastructure, and it's not an option for most research groups 😩.
so instead we built a graphical tool that displays an image of a building map and expects the user to "click" their location as they move 🖱️. the coordinates on the map get recorded in one or more general tracks. the header of such tracks can also record the coordinates of the base stations, if they're known 📍.
this tool is easy to extend to support multiple maps 🗂️. when the user asks the graphical tracing tool to load a new map, a new location track gets created, along with an annotation record that captures the file name of that image. locations of new base stations can be recorded in this new track header. each location track should represent a different physical and wireless environment 🌍.
5.2. Trace Modulation Tools
a key tool we built around our trace format is PaM, the Packet Modulator 🔥. the idea behind PaM is to take traces collected by a mobile host and distill them into modulation traces. these modulation traces capture the networking environment seen by the traced host. a PaM kernel uses them to delay, drop, or corrupt incoming and outgoing packets. with PaM, we've built a testbed that can repeatably and reliably mimic live systems under certain mobile scenarios 👑.
there are three main components to PaM 💅. first, we've built a kernel that can delay, drop, and corrupt packets to match the characteristics of some observed network. second, we've defined a modulation trace format that describes how such a kernel should modulate packets. third, we've built a tool that generates modulation traces from certain classes of raw traces collected by mobile hosts.
5.2.1. Packet Modulation
the PaM modulation tool sits in the kernel between the IP layer and the underlying interfaces 🧚. it intercepts incoming and outgoing packets, and it may choose to drop, corrupt, or delay them. dropping an incoming or outgoing packet is easy: you just don't forward it along 🙃. similarly, we can corrupt a packet by flipping some bits before forwarding it.
delaying a packet is slightly more complicated 🫠. we model the delay a packet experiences as the time it takes the sender to put the packet onto the network interface, plus the time it takes for the last byte to propagate to the receiver. the first part, the transmission time, is the size of the packet divided by the available bandwidth. the second part is latency 🦋.
our approach to delay modulation is simple -- we assume the actual network the packets travel over is much faster and of better quality than the one we're trying to emulate, so we can ignore it 🌈. we delay the packet according to our latency and bandwidth targets, and then decide whether to drop or corrupt it. we take care that packet modulation doesn't unduly penalize other system activity, and we use the internal system clock to schedule packets 🫶. since this clock has a large granularity compared to delay resolution, we try to keep the average scheduling error to a minimum, rather than scheduling each packet at exactly the right time ⭐.
5.2.2. Modulation Traces
to tell the PaM kernel how the modulation parameters change over time, we give it a series of modulation-trace entries 📜. each entry sets loss and corruption percentages, as well as network latency and inter-byte time, which is 1/bandwidth. these entries are stored in a trace file. its format is much simpler than record-format traces, and it's designed for efficient playback 💜. the format of modulation traces is shown in Figure 10.
struct tr_rep_hdr_t {
u_int32_t rh_magic;
u_int32_t rh_size;
u_int32_t rh_time_fmt; /* nsec or used */
struct tr_time_t rh_ts;
char rh_date[TR_DATESZ];
char rh_agent[TR_NAMESZ];
u_int32_t rh_ip;
u_int32_t rh_ibt_ticks; /* units/sec, ibt */
u_int32_t rh_lat_ticks; /* units/sec, lat */
u_int32_t rh_loss_max; /* max loss rate */
u_int32_t rh_crpt_max; /* max corrupt rate */
char rh_desc[0]; /* variable size */
};
struct tr_rep_ent_t {
u_int32_t re_magic;
struct tr_time_t re_dur; /* duration of entry */
u_int32_t re_lat; /* latency */
u_int32_t re_ibt; /* inter-byte time */
u_int32_t re_loss; /* loss rate */
u_int32_t re_crpt; /* corrupt rate */
};
Figure 10: Modulation trace formatmodulation traces begin with a header that's pretty similar to the one found in record-format trace headers 🎀. modulation headers also carry the units in which latency and inter-byte time are expressed, plus the maximum values for loss and corruption rates 🍓. each individual entry contains how long the entry applies, along with its latency, inter-byte time, loss rate, and corruption rate ✨.
5.2.3. Trace Transformation ✨
Okay so the big question is how we turn those recorded observational traces from Section 4 into these descriptive modulation traces 🤔 To keep things high-quality, we only use a really narrow set of source traces 💅 Our experience with modulation traces is still pretty limited, so we use a simple but tunable algorithm to generate them 🎀
Our basic strategy for latency and bandwidth is tied to how we model packet delays: delay is transmission time plus latency 🦋 We also assume packets that traversed the network close together in time experienced the same latency and bandwidth in transit. So we look for two packets of different sizes sent close to each other along the same path. From their transit times and sizes, we can figure out the near-instantaneous bandwidth and latency of the end-to-end path those packets covered 🔥 If the traced packet traffic has sequence numbers, loss rates are fairly easy to calculate 📊 And if the protocol can mark corrupt packets, that corruption info can be stored and pulled back out of the recorded traces 🫶
Now the timing is the tricky part 😭 Deriving network latency and bandwidth from timestamped packet observations requires very accurate timing, and the laptops we had on hand have clocks that drift non-negligibly. We chose not to use protocols like NTP [9] for two reasons. First, they produce network traffic above and beyond the known traced workload. Second (and perhaps more importantly), they can make the clock speed up or slow down during adjustment. Those clock movements can play havoc with careful measurement 💀
So we can only depend on the timestamps of a single machine to determine packet transit times 🧚 To provide workloads on the traced machines, we use the ICMP ECHO service. The ECHO request is timestamped on its way out, and the corresponding ECHOREPLY is traced. We modified the ping program to alternate between small and large packets 🌸 Traces that capture this altered ping traffic can then go through our transformation tool.
The tool itself uses a simple sliding window scheme to generate modulation entries. For each window position in the recorded trace, it determines the loss rate, plus the average latency and bandwidth experienced by pairs of ICMP ECHO packets 🌈 The size and granularity of the sliding window are parameters of the transformation. As we gain experience in both analysis and modulation of wireless traces, we expect to be able to recommend good window sizes 🍓
Unfortunately, our wireless devices do not report corrupt packets 😤 They get dropped by the hardware without any operating system notification. Still, our modulation system will coerce any such corruptions into an increased loss rate, duplicating the behavior of the original network 💜
5.3. Trace Analysis Tools 🧠
A trace is only as useful as its processing tools 🛠️ The requirements for those tools include robustness, flexibility, and portability. Having an extensible trace format adds extra emphasis on being able to work with future versions. So we provide a general processing library as a framework where users can easily build customized processing tools 🎀 It's designed for both high portability and good performance ✨
In this section, we first present the trace library. Then we describe a set of tools for simple post-processing and for preparing the trace for further analyses. We wrap up with a brief description of our analysis tools, which are applied to this minimally processed data 💅
5.3.1. Trace Library 📚
The trace library gives applications an interface to simplify working with network traces 🦋 That includes functions to read, write, and print trace records. The reading and writing functions manage byte swapping, plus optional integrity checking of the trace as it's read or written. The library uses a buffering strategy that is optimized for trace I/O 🔥 Trace printing facilities are provided for both debugging and parsing purposes 🫶
5.3.2. Processing Tools 🛠️
The processing tools are generally the simplest set we've built around the trace format 😌 By far the most complicated one is the modulation-trace transformation tool from Section 5.2.3, and the rest are quite simple in comparison. The first is a parser that prints the content of an entire trace. With the trace library, it's less than a single page of C code 🙈 For each record, it prints the known data fields along with their textual names, followed by all the optional properties and values.
Since lots of analysis tasks work with records of the same type, an enhanced version of the parser can split the trace data by tracks into many files, one per track 📂 Each line of the output text files holds a time stamp followed by the integer values of all the optional data in a track entry. In this form, traces are easy to analyze further with scripts written in an interpreted language such as perl 🧚
We also have a small suite of tools for simple jobs, like listing all the track headers or changing the trace description when we need to. With the trace library, each one is trivial to construct 💖
5.3.3. Analysis Tools 📈
Analysis tools depend a lot on what kind of information an experimenter wants to pull out of the trace, and honestly, ours show our own biases in experimentation 👀 Most analyses derive common statistical descriptions of traces or establish some correlation between the trace data sets.
As early users of the trace format and collection tools, we built a few analysis tools to study the behavior of the wireless networks we had access to 📡 We've been especially interested in the loss characteristics of wireless channels and how they relate to signal quality and the position of the mobile host. In this section, we briefly present some of these tools to hint at the kind of experimentation the trace format makes possible 🦋
Loss characteristics are among the most interesting aspects of wireless networks, and certainly among the least well understood 😭 To shed light on this, we created tools that extract loss information from collected traces. On top of standard parameters like the packet loss rate, the tool also derives transition probabilities for a two-state error model 🧠 This has proven to be a simple yet powerful model for capturing the burstiness seen in wireless loss rates caused by fading signals. To help visualize channel behavior while the host is moving, our tool can replay the mobile host's movement while plotting the loss rate as it changes over time 🎬 It also lets us zoom in on locations along the path and get detailed statistics over arbitrary time intervals 🔍
Our traces can also be analyzed to understand the relationship between channel behavior and signal quality 💜 For wireless devices like the NCR WaveLAN, we can easily get measurements of signal quality, signal strength, and noise level 📶 We built a simple statistical tool to test the correlation between measured signal and loss characteristics. Variations of this test are also possible using different combinations of those three signal measurements along with the movement of the host 🌸
The question of just how mobile these mobile hosts really are can be investigated through our traces too 🏃 Position data comes from traces that involved either GPS or user-supplied positions with our trace collection tools 🗺️ This data is valuable for comparing and validating various mobility prediction algorithms. Given adequate network infrastructure and good signal measurements, we can pin down the mobile location within a region significantly smaller than the cell size 🎯 We're also developing a tool to combine position information and signal measurements from many traces to identify the "signal quality" signature for different regions inside a building 🏢 Once that signature database is completed and validated, it can generate position information for other traces that contain only signal quality information 🌈
6. Related Work ✨
Okay bestie, let's talk about who came before us 💅. The earlier work that's most relevant to mobile network tracing sorts into two camps 🦋. The first camp collects network traffic data, and the big names there are tcpdump [7] and the BSD Packet Filter, or BPF [8] 📦. The second camp does network modulation, which is basically the same kind of thing PaM does. Its members are Delayline [6], the Probe/Fault Injection Tool [4], and the University of Lancaster's network emulator [3] 🌸.
Let's start with the first camp. There are tons of systems that record network packet traffic, but the de facto standard is tcpdump, and it works together with a packet filter like BPF 🧚. The packet filter gets a small piece of code that describes which packets are interesting. Then the first several bytes of each interesting packet get copied into a buffer for tcpdump to consume. This setup is efficient, flexible, and has rightly won the networking community over 💖.
BUT (sorry, I'm yelling 😭), tcpdump only captures traffic data. It doesn't record anything about mobile networking devices or where a mobile host is located 🙈. Instead of bolting separate software components onto a host that's already running tcpdump to grab that extra stuff, we went with an integrative approach so trace file administration stays easy 🎀. We kept the lessons of tcpdump and BPF close to our hearts too: copy only the information that's necessary, and move data up to user level in batches ✨. Here's a lowkey plot twist 👀: it may well pay off to look into either putting device and location information straight into BPF, or taking BPF's flexible filtering mechanism and building it into our trace collection software. For now we don't know exactly what data we'll need to explore the properties of mobile networks, so we aren't excluding any data yet 🫶.
Now the second camp. There are three notable systems that do packet modulation similar to PaM 💜. The earliest is Delayline, which was designed to emulate wide-area networks on top of local-area ones. That's a goal really similar to PaM's 🌈. The biggest difference is that Delayline's emulation happens entirely at user level. Applications have to be recompiled against a library that emulates the BSD socket system and its library calls. This is a portable approach that works well when kernel-level source access isn't available, but it has a catch: not all network traffic goes through the emulation layer, and that traffic may have a serious impact on how the final system performs 💀. Delayline also works differently from PaM because its emulated network uses one set of parameters for each emulated connection. Performance stays fairly constant and can't change much over time 😴.
The Lancaster network emulator was designed specifically to model mobile networks 📡. Instead of giving each host its own modulation, it uses one central server that all network traffic from instrumented applications passes through. This system also doesn't capture all the traffic going into and out of a particular host. But it does let modulation depend on multiple hosts that share one emulated medium, which is a great look 👑. Changing the emulation parameters between hosts is possible, but it's pretty cumbersome 🙃. The system reads a configuration file, and that file can be changed and re-read while the system is running ⭐.
The system closest in spirit to PaM is the Probe/Fault Injection Tool, or PFI 💅. Its design philosophy lets an arbitrary protocol layer, including device drivers, be wrapped by a layer below to modulate existing traffic. A layer above it generates test traffic. The modulation parameters come from a script written in an interpreted language, which is currently Tcl, so there's a lot of flexibility 🍓. The downside is that there's no mechanism for synthesizing those scripts, so they all have to be explicitly designed by hand 😩. Also, using an interpreted language like Tcl limits PFI to user-level implementations of network drivers, and that can have performance implications too 🥺.
7. Future Work 🔮
Real talk, this work is still super young 🍼. We've only just started exploring what mobile network traces can be used for, and we've spotted several areas for future work 🌟.
First up, the trace format as it stands is very IP-centric 🌐. You could imagine using unknown IP addresses for non-IP hosts, and encoding other addressing schemes in header-only properties. But that's cumbersome at best 😵💫. We're looking into more convenient ways to encode other addressing schemes, but for now we're happy to focus on IP networks 💖.
Next, there are two big questions about wireless media that are literally begging to be answered 🙋♀️. How does a group of machines perform when they all share the same bandwidth? And how asymmetric is the performance of real-world wireless channels? We do have tools for merging traces taken from multiple hosts into one trace file, but we haven't really dug into those multiple-host scenarios yet. We're also looking into instrumenting wireless base stations as well as end-point hosts 📶.
A lot of our planned work involves the PaM testbed 🧪. The top priority is that many wireless channels are known to be asymmetric. So splitting the replay trace into incoming and outgoing modulation entries is of paramount importance 🔥. We'd also love to extend PaM to handle multiple emulated interfaces, and to apply different modulation parameters to packets going to or coming from different destinations 🦋. You could also picture tracing performance across several different networking environments, then switching between them under application control ✈️. For example, imagine a set of traces showing radio performance at various altitudes. An airplane simulator in a dive would switch from high-altitude modulation traces to low-altitude ones. Iconic, right? 😭
Finally, we are so excited to start exploring the properties of real-world mobile networks, and to put our own mobile system designs through PaM to see how they perform 🚀. We really hope others can use our tools to do the same 🫶✨.
Acknowledgements 🎀
The authors wish to thank Dave Johnson, who gave early pointers to related work and helped us immeasurably with RFC formatting 🙌. We also wish to thank the people who commented on early drafts of the document: Mike Davis, Barbara Denny, Mark Lewis, and Hui Zhang 💜. And finally, we'd like to thank Bruce Maggs and Chris Hobbs, our first customers! 🥹
This research was supported by the Air Force Materiel Command (AFMC) and ARPA under contract numbers F196828-93-C-0193 and DAAB07-95-C-D154, and by the State of California MICRO Program 🌸. Additional support was provided by AT&T, Hughes Aircraft, IBM Corp., Intel Corp., and Metricom ✨. The views and conclusions contained here are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either express or implied, of AFMC, ARPA, AT&T, Hughes, IBM, Intel, Metricom, Carnegie Mellon University, the University of California, the State of California, or the U.S. Government 🫶.
Security Considerations 🔐
This RFC raises no security considerations 🙌. Honestly, that's a whole vibe 💅.
Authors' Addresses 📮
Questions about this document can be directed to the authors 💌:
Brian D. Noble
Computer Science Department
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213-3891
Phone: +1-412-268-7399
Fax: +1-412-268-5576
EMail: bnoble@cs.cmu.eduGiao T. Nguyen
Room 473 Soda Hall #1776 (Research Office)
University of California, Berkeley
Berkeley, CA 94720-1776
Phone: +1-510-642-8919
Fax: +1-510-642-5775
EMail: gnguyen@cs.berkeley.eduMahadev Satyanarayanan
Computer Science Department
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213-3891
Phone: +1-412-268-3743
Fax: +1-412-268-5576
EMail: satya@cs.cmu.eduRandy H. Katz
Room 231 Soda Hall #1770 (Administrative Office)
University of California, Berkeley
Berkeley, CA 94720-1770
Phone: +1-510-642-0253
Fax: +1-510-642-2845
EMail: randy@cs.berkeley.eduReferences 📚
[1] Chen, J. B., and Bershad, B. N. The Impact of Operating System Structure on Memory System Performance. In Proceedings of the 14th ACM Symposium on Operating System Principles (Asheville, NC, December 1993).
[2] Dahlin, M., Mather, C., Wang, R., Anderson, T., and Patterson, D. A Quantitative Analysis of Cache Policies for Scalable Network File Systems. In Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems (Nashville, TN, May 1994).
[3] Davies, N., Blair, G. S., Cheverst, K., and Friday, A. A Network Emulator to Support the Development of Adaptive Applications. In Proceedings of the 2nd USENIX Symposium on Mobile and Location Independent Computing (April 10-11 1995).
[4] Dawson, S., and Jahanian, F. Probing and Fault Injection of Dependable Distributed Protocols. The Computer Jouranl 38, 4 (1995).
[5] Gloy, N., Young, C., Chen, J. B., and Smith, M. D. An Analysis of Dynamic Branch Prediction Schemes on System Workloads. In The Proceedings of the 23rd Annual International Symposium on Computer Architecture (May 1996).
[6] Ingham, D. B., and Parrington, G. D. Delayline: A Wide-Area Network Emulation Tool. Computing Systems 7, 3 (1994).
[7] Jacobson, V., Leres, C., and McCanne, S. The Tcpdump Manual Page. Lawrence Berkeley Laboratory, Berkeley, CA.
[8] McCanne, S., and Jacobson, V. The BSD Packet Filter: A New Architecture for User-level Packet Capture. In Proceedings of the 1993 Winter USENIX Technical Conference (San Deigo, CA, January 1993).
[9] Mills, D. L. Improved Algorithms for Synchronizing Computer Network Clocks. IEEE/ACM Transactions on Networking 3, 3 (June 1995).
[10] Mummert, L. B., Ebling, M. R., and Satyanarayanan, M. Exploiting Weak Connectivity for Mobile File Access. In Proceedings of the 15th Symposium on Operating System Prinicples (Copper Mountain, CO, December 1995).
[11] Nelson, M. N., Welch, B. B., and Ousterhout, J. K. Caching in the Sprite Network File System. ACM Transactions on Computer Systems 6, 1 (February 1988).
[12] Schilit, B., Adams, N., Gold, R., Tso, M., and Want, R. The PARCTAB Mobile Computing System. In Proceedings of the 4th IEEE Workshop on Workstation Operating Systems (Napa, CA, October 1993), pp. 34--39.
[13] Uhlig, R., Nagle, D., Stanley, T., Mudge, T., Sechrest, S., and Brown, R. Design Tradeoffs for Software-Managed TLBs. ACM Transactions on Computer Systems 12, 3 (August 1994).
[14] Want, R., Hopper, A., Falcao, V., and Gibbons, J. The Active Badge Location System. ACM Transactions on Information Systems 10, 1 (January 1992), 91--102.
📦 where this page comes from
- ietf: rfc2041 1996-10
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms