As per Relevance of the word optional, we have this rfc below:
Network Working Group B.
Request for Comments: 2041 Carnegie Mellon
Category: Informational G.
University of California,
M.
Carnegie Mellon
R.
University of California,
October 1996
Mobile Network
Status of this
This memo provides information for the Internet community. This
does not specify an Internet standard of any kind. Distribution
this memo is unlimited
Mobile networks are both poorly understood and difficult
experiment with. This RFC argues that mobile network
provides both tools to improve our understanding of
channels, as well as to build realistic, repeatable testbeds
mobile software and systems. The RFC is a status report on our
tracing mobile networks. Our goal is to begin discussion on
standard format for mobile network tracing as well as a testbed
mobile systems research. We present our format for collecting
network traces, and tools to produce from such traces
models of mobile network behavior
We also describe a set of tools to provide network modulation
on collected traces. Modulation allows the emulation of
channel latency, bandwidth, loss, and error rates on private,
networks. This allows system designers to test systems in
realistic yet repeatable manner
Noble, et. al. Informational [Page 1]
RFC 2041 Mobile Network Tracing October 1996
1.
How does one accurately capture and reproduce the observed
of a network? This is an especially challenging problem in
computing because the network quality experienced by a mobile
can vary dramatically over time and space. Neither long-term
measures nor simple analytical models can capture the variations
bandwidth, latency, and signal degradation observed by such a host
In this RFC, we describe a solution based on network tracing.
solution consists of two phases: trace recording and
modulation
In the trace recording phase, an experimenter with an
mobile host physically traverses a path of interest to him.
the traversal, packets from a known workload are generated from
static host. The mobile host records observations of both
received from the known workload as well as the
characteristics during the workload. At the end of the traversal
the list of observations represents an accurate trace of the
network behavior for this traversal. By performing
traversals of the same path, and by using different workloads,
can obtain a trace family that collectively characterizes
quality on that path
In the trace modulation phase, mobile system and application
is subjected to the network behavior observed in a recorded trace
The mobile software is run on a LAN-attached host whose kernel
modified to read a file containing the trace (possibly
for efficiency,) and to delay, drop or otherwise degrade packets
accordance with the behavior described by the trace. The
software thus experiences network quality indistinguishable from
recorded in the trace. It is important to note that trace
is fully transparent to mobile software --- no source or
changes have to be made
Trace-based approaches have proved to be of great value in areas
as file system design [2, 10, 11] and computer architecture. [1, 5,
13] Similarly, we anticipate that network tracing will prove
in many aspects of mobile system design and implementation.
example, detailed analyses of traces can provide insights into
behavior of mobile networks and validate predictive models.
another example, it can play an important role in stress testing
debugging by providing the opportunity to reproduce the
conditions under which a bug was originally uncovered. As a
example, it enables a system under development to be subjected
network conditions observed in distant real-life environments. As
final example, a set of traces can be used as a benchmark family
evaluating and comparing the adaptive capabilities of
Noble, et. al. Informational [Page 2]
RFC 2041 Mobile Network Tracing October 1996
mobile system designs
Our goal in writing this RFC is to encourage the development of
widely-accepted standard format for network traces.
standardization will allow traces to be easily shared. It will
foster the development and widespread use of trace-based benchmarks
While wireless mobile networks are the primary motivation for
work, we have made every effort to ensure that our work is
to other types of networks. For example, the trace format and
of the tools may be valuable in analyzing and modeling ATM networks
The rest of this RFC is organized as follows. We begin by
the properties of wireless networks and substantiating the claim
it is difficult to model such networks. Next, in Section 3,
describe the factors that should be taken into account in designing
trace format. We present the details of a proposed trace
standard in Section 4. Section 5 presents a set of tools that
have built for the collection, analysis and replay of traces
Finally, we conclude with a discussion of related and future work
2. Modeling Wireless
Wireless channels are particularly complex to model, because of
inherent dependence on the physical properties of radio waves (
as reflections from "hard" surfaces, diffraction around corners,
scattering caused by small objects) and the site specific
in which the channel is formed. They are usually modeled as a time
and distance-varying signal strength, capturing the
nature of the interaction among reflected radio waves. The
strength can vary by several orders of magnitude (+ or - 20-30 dB
within a short distance. While there have been many efforts
obtain general models of radio propagation inside buildings and
the wide area, these efforts have yielded inherently
models that can vary from actual measurements by an order
magnitude or more
Signal-to-noise ratio, or SNR, is a measure of the received
quality. If the SNR is too low, the received signal will not
detected at the receiver, yielding bit errors and packet losses.
SNR is not the only effect that can lead to losses. Another
inter-symbol interference caused by delay spread, that is,
delayed arrival of an earlier transmitted symbol that took
circuitous propagation path to arrive at the receiver,
(partially) canceling out the current symbol. Yet another problem
doppler shift, which causes frequency shifts in the arrived
due to relative velocities of the transmitter and the receiver
thereby complicating the successful reception of the signal.
coherent reception is being used, receiver synchronization can
Noble, et. al. Informational [Page 3]
RFC 2041 Mobile Network Tracing October 1996
lost
More empirically, it has been observed that wireless channels
to a two state error model. In other words, channels are
well behaved but occasionally go into a bad state in which many
errors occur within a small time interval
Developers of network protocols and mobility algorithms
experiment with realistic channel parameters. It is highly
that the wireless network be modeled in a thoroughly
fashion. This would allow an algorithm and its variations to
evaluated in a controlled and repeatable way. Yet the
discussion makes it clear that whether analytical models are used
even actual experimentation with the network itself, the results
be either inaccurate or unlikely to be reproducible. A trace-
approach alleviates these problems
3. Desirable Trace Format
In designing our trace format, we have been guided by
principles. First, the format should be extensible. Second,
should be self-describing. Third, traces should be easy to manage
This section describes how each of these principles has affected
design
Although we have found several interesting uses for network traces
it is certain that more will evolve over time. As the traces
used in new ways, it may be necessary to add new data to the
format. Rather than force the trace format to be redesigned, we
structured the format to be extensible. There is a built-
mechanism to add to the kinds of data that can be recorded in
traces
This extensibility is of little use if the tool set needs to
as the trace format is extended. Recognizing this, we have made
format -- particularly the extensible portions -- self-describing
Thus, old versions of tools can continue to work with
traces, if perhaps in a less than optimal way
In our experience with other tracing systems, management of
files is often difficult at best. Common problems include the
to manage multiple trace files as a unit, not easily being able
extract the salient features of large trace files, and having to
dedicated trace management tools to perform even the simplest tasks
To help cope with file management, we have designed the the traces
be split or merged easily. To reduce dependence on
tools, we've chosen to store some descriptive information as
strings, allowing minimal access to the standard UNIX tool suite
Noble, et. al. Informational [Page 4]
RFC 2041 Mobile Network Tracing October 1996
4. Trace
This section describes the format for network traces. We begin
presenting the basic abstractions that are key to the trace format
the record, and the track, a collection of related records. We
describe the records at the beginning and end of a trace, the
and footer. The bulk of the section describes the three kinds
record tracks: packet, device, and general. These also make up
bulk of the actual trace. We conclude the section with a
of two special purpose records: the annotation and the trace
loss records
4.1. Basic
4.1.1.
A record is the smallest unit of trace data. There are
different types of records, each of which is discussed in
4.2 through 4.7. All of the records share several features
common; these features are described here
Records are composed of fields, which are stored in network order
Most of the fields in our records are word-sized. Although this
be wasteful in space, we chose to leave room to grow and keep
management simple
The first field in each record is a magic word, a random 32
pattern that both identifies the record's type and lends
confidence that the record is well formed. Many record types
both required and optional fields; thus they can be of variable size
We place every record's size in its second field. By comparing
size of a record to the known constraints for the record's type,
can gain further confidence that a record is well-formed. This
record structure is illustrated in Figure 1.
All records also contain a two-word timestamp. This timestamp
take one of two formats: timeval or timespec. Only one of the
formats is used in any given trace, and the format is specified
the start of a trace file. The first word in either format is
number of seconds that have elapsed since midnight, January 1, 1970.
The second word is the additional fractions of a second. In
timeval format, these fractions are expressed in microseconds, in
same way that many current operating systems express time. In
timespec format, these fractions are expressed in nanoseconds,
POSIX time standard. We've chosen these two values since they
convenient, cover most current and anticipated systems' notions
time, and offer appropriate granularity for measuring network events
Noble, et. al. Informational [Page 5]
RFC 2041 Mobile Network Tracing October 1996
+------------------+
| Magic Number |
| Size of Record |
+------------------+
| Required Fields |
| ... |
+------------------+
| Optional Fields |
| ... |
+------------------+
Figure 1: Record
4.1.2.
Many of the record types have both fixed, required fields, as well
a set of optional fields. It is these options that
extensibility to our trace format. However, to provide a self
describing trace, we need some compact way of determining
optional fields are present in a given record. To do this, we
related sets of packets into tracks. For example, a set of
that captured packet activity for a single protocol between
machines might be put together into a track. A track is a
followed by some number of related records; the header
describes the format of the individual records. Records
separate tracks can be interleaved with one another, so long as
header for each individual track appears before any of the track'
records. Figure 2 shows an example of how records from
tracks might be interleaved
Track headers describe their records' content through property lists
An entry in a property list is a two-element tuple consisting of
name and a value. The name is a word which identifies the
defined by this entry. Some of these properties are measured
once for a track, for example, the address of a one-hop router in
track recording packets from that router. Others are measured
per record in that track, such as the signal strength of a
which changes over time. The former, which we call header-
properties, have their most significant name bit set. The
field of a header-only property holds the measured value of
property. Otherwise, the value field holds the number of words
in each of the track's records
Noble, et. al. Informational [Page 6]
RFC 2041 Mobile Network Tracing October 1996
+----------++----------++----------++----------++----------+
| Track #1 || Track #1 || Track #2 || Track #1 || Track #2 |
| Header || Entry || Header || Entry || Entry |
+----------++----------++----------++----------++----------+
Figure 2: Interleaved track
Those properties measured in each record in the track are
together in a value list at the end of each such record. They
in the same order that was specified in the track header's
list so that tools can properly attribute data. Thus, even if a
doesn't know what property a particular name represents, it
identify which parts of a trace record are measuring that property
and ignore them
Noble, et. al. Informational [Page 7]
RFC 2041 Mobile Network Tracing October 1996
4.2. Trace Headers and
Trace files begin with a trace header, and end with a trace footer
The formats of these appear in Figure 3. The header
whether this trace was collected on a single machine, or was
from several other traces. In the former case, the IP address
host name of the machine are recorded. In the latter, the IP
is taken from the family of Class E address, which are invalid.
use a family of invalid addresses so that even if we cannot
a number of hosts participating in the trace we can still
records from distinct hosts
#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
The trace header also specifies which time stamp format is used
the trace, and the time at which the trace begins. There is
variable-length description that is a string meant to provide
of how the trace was collected. The trace footer contains only
time at which the trace ended; it serves primarily as a marker
show the trace is complete
Unlike other kinds of records in the trace format, the header
footer records have several ASCII fields. This is to allow
utilities some access to the contents of the trace, without
to specialized tools
Noble, et. al. Informational [Page 8]
RFC 2041 Mobile Network Tracing October 1996
4.3. Packet
Measuring packet activity is the main focus of the network
project. Packet activity is recorded in tracks, with a packet
and a set of packet entries. A single track is meant to capture
activity of a single protocol, traffic from a single router, or
other subset of the total traffic seen by a machine. The
portions of packet headers and entries are presented in Figure 4.
Packet track headers identify which host generated the trace
for that track, as well as the time at which the track began.
records the device on which these packets are received or sent,
the protocol used to ship the packet; these allow interpretation
device-specific or protocol-specific options. The header
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
A packet entry is generated for every traced packet. It contains
size of the traced packet, the time at which the packet was sent
received, and the list of property measurements as specified in
track header
The options we have defined to date are in Table 1. Several of
have played an important role in our early experiments. ADDR_
identifies the senders of traffic during the experiment. We
determine network performance using either PKT_SENTTIME for one-
traffic between two hosts with closely synchronized clocks, or
Noble, et. al. Informational [Page 9]
RFC 2041 Mobile Network Tracing October 1996
trip ICMP ECHO traffic and the ICMP_PINGTIME option.
PKT_SEQUENCE numbers sheds light on both loss rates and patterns
Section 5 discusses how these measurements are used
4.4. Device
Our trace format records details of the devices which carry
traffic. To date, we've found this most useful for correlating
packets with various signal parameters provided by wireless devices
The required portions of device header and entry records appear
Figure 5, and are quite simple. Device track headers identify
host generating the track's records, the time at which
observation starts, and the type of device that is being traced
Each entry contains the time of the observation, and the list
optional characteristics
+---------------+-----------------------------------------------+
| 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
Noble, et. al. Informational [Page 10]
RFC 2041 Mobile Network Tracing October 1996
struct 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
These optional characteristics, listed in Table 2, are
concerned with the signal parameters of the wireless interfaces
have available. Interpreting these parameters is heavily device
dependent. We give examples of how we've used device observations
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
4.5. Miscellaneous
We use miscellaneous, or general, tracks to record things that don'
fit clearly in either the packet or device model. At the moment
physical location of a mobile host is the only attribute tracked
general trace records. The required portion of the general
and entry records is shown in Figure 6, the two optional
are in Table 3. In addition to the property list, general
have only the IP address of the host generating the record and
time at which observations began. General entries have only
timestamp, and the optional fields
Noble, et. al. Informational [Page 11]
RFC 2041 Mobile Network Tracing October 1996
4.6.
An experimenter may occasionally want to embed arbitrary
text into a trace. We include annotation records to provide
this. Such records are not part of a track; they stand alone.
structure of an annotation record is shown in Figure 7.
include the time at which the annotation was inserted in the trace
the host which inserted the annotation, and the variable-sized
of the annotation 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
+------------+--------------------------------------------+
| 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
struct 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
Noble, et. al. Informational [Page 12]
RFC 2041 Mobile Network Tracing October 1996
4.7. Lost Trace
It is possible that, during collection, some trace records may
lost due to trace buffer overflow or other reasons. Rather
throw such traces away, or worse, ignoring the lost data, we'
included a loss record to count the types of other records which
lost in the course of trace collection. Loss records are shown
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
5. Software
In this section, we describe the set of tools that have been built
date for mobile network tracing. We believe many of these tools
widely applicable to network tracing tasks, but some have
application to mobile network tracing. We begin with an overview
the tools, their applicability, and the platforms on which they
currently supported, as well as those they are being ported to.
information is summarized in Table 4.
We have made every effort to minimize dependencies of our software
anything other than protocol and device specifications. As a result
we expect ports to other BSD-derived systems to be straightforward
ports to other UNIX systems may be more complicated, but feasible
There are three categories into which our tracing tools can
placed: trace collection, trace modulation, and trace analysis
Trace collection tools are used for generating new traces.
record information about the general networking facilities, as
as data specific to mobile situations: mobile host location,
station location, and wireless device characteristics. These
are currently supported on BSDI, and are being ported to NetBSD.
describe these tools in Section 5.1.
Noble, et. al. Informational [Page 13]
RFC 2041 Mobile Network Tracing October 1996
Trace modulation tools emulate the performance of a traced
network on a private wired network. The trace modulation tools
discussed in Section 5.2, are currently supported on
platforms. They are geared toward replaying low speed/
networks on faster and more reliable ones, and are thus
applicable to reproducing mobile environments
In Section 5.3, we conclude with a set of trace processing
analysis tools, which are currently supported on both NetBSD and
platforms. Our analyses to date have focused on properties
wireless networks, and are most directly applicable to mobile traces
The processing tools, however, are of general utility
+--------------+--------------+--------------+
| Collection | Modulation | Analysis |
+-----------+--------------+--------------+--------------+
| NetBSD | In Progress | Supported | Supported |
| BSDI | Supported | Planned | Supported |
+-----------+--------------+--------------+--------------+
This table summarizes the currently supported platforms for the
tool suites, and the platforms to which ports are underway
Table 4: Tool
5.1. Trace Collection
The network trace collection facility comprises two key components
the trace agent and the trace collector. They are shown in Figure 9.
The trace agent resides in the kernel where it can obtain data
is either expensive to obtain or inaccessible from the user level
The agent collects and buffers data in kernel memory; the user-
trace collector periodically extracts data from this kernel
and writes it to disk. The buffer amortizes the fixed costs of
transfer across a large number of records, minimizing the impact
data transfer on system performance. The trace collector
data through a pseudo-device, ensuring that only a single --
therefore complete -- trace file is being generated from a
experiment. To provide simplicity and efficiency, the collector
not interpret extracted data; it is instead processed off-line by
post-processing and analysis tools described in Sections 5.2 and 5.3.
There are three sorts of data collected by the tracing tools:
traffic, network device characteristics, and mobile host location
The first two are collected in much the same way; we describe
methodology in Section 5.1.1. The last is collected in two
ways. These collection methods are addressed in Section 5.1.2.
Noble, et. al. Informational [Page 14]
RFC 2041 Mobile Network Tracing October 1996
+-----------+ write to
| Trace | ==============>
| Collector |
+-----------+
========================================|===== kernel
+-----------------+ |
| Transport Layer | |
|-----------------| +------------------+
| Network Layer |------------>| Trace +------+ |
|-----------------| | Agent |buffer| |
| NI | NI | NI |------------>| +------+ |
+-----------------+ +------------------+
This figure illustrates the components of trace collection. The NI'
are network interfaces
Figure 9: Components of trace
5.1.1. Traffic and Device
The trace agent exports a set of function calls for traffic
device data collection. Traffic data is collected on a per-
basis. This is done via a function called from device drivers
the packet and a device identifier as arguments. For each packet
the trace record contains the source and destination address options
Since our trace format assembles related packets into tracks,
information, such as the destination address, is recorded in
track header to reduce the record size for each packet entry.
also record the size of each packet
Information beyond packet size and address information is
protocol-dependent. For transport protocols such as UDP and TCP,
example, we record the source and destination port numbers;
packet records also contain the sequence number. For ICMP packets
we record their type, code and additional type-dependent data.
explained in Section 5.2.3, we record the identifier, sequence
and time stamp for ICMP ECHOREPLY packets
Before appending the record to the trace buffer, we check to see
it is the first record in a track. If so, we create a new
track header, and write it to the buffer prior the packet entry
Our trace collection facility provides similar mechanisms to
device-specific data such as signal quality, signal level, and
level. Hooks to these facilities can be easily added to the
drivers to invoke these tracing mechanisms. The extensible
self-describing features of our trace format allow us to capture
wide variety of data specific to particular network interfaces
Noble, et. al. Informational [Page 15]
RFC 2041 Mobile Network Tracing October 1996
For wireless network devices, we record several signal
measurements that the interfaces provide. Although some interfaces
such as NCR's WaveLAN, can supply this of information for
packet received, most devices average their measurements over
longer period of time. As a result, we only trace these
periodically. It is up to the device drivers to determine
frequency at which data is reported to the trace agent
When devices support it, we also trace status and error events.
types of errors, such as CRC or buffer overflow, allow us
determine causes for some observed packet losses. For example,
can attribute loss to either the wireless channel or the
interface
5.1.2. Location
At first thought, recording the position of a mobile host
straightforward. It can be approximated by recording the
station (BS) with which the mobile host is communicating. However
due to the large coverage area provided by most radio interfaces
this information provides a loose approximation at best.
commercial deployments, we may not be able to reliably record
base station with which a mobile host communicates. This
outlines our collection strategy for location information in
outdoor and indoor environments
The solution that we have considered for wide-area,
environments makes use of the Global Positioning System (GPS).
longitude and latitude information provided by the GPS device
recorded in a general track
Indoor environments require a different approach because
satellite signals cannot reach a GPS device inside a building.
considered deploying an infrared network similar to the Active
[14] or the ParcTab [12]; however, this significant addition to
wireless infrastructure is not an option for most research groups
As an alternative, we have developed a graphical tool that
the image of a building map and expects the user to "click"
location as they move; the coordinates on the map are recorded in
or more general tracks. The header of such tracks can also
the coordinates of the base stations if they are known
An extension can be easily added to this tool to permit
maps. As the user requests that a new map be loaded into
graphical tracing tool, a new location track is created along with
annotation record that captures the file name of that image
Locations of new base stations can be recorded in this new
Noble, et. al. Informational [Page 16]
RFC 2041 Mobile Network Tracing October 1996
header. Each location track should represent a different
and wireless environment
5.2. Trace Modulation
A key tool we have built around our trace format is PaM, the
Modulator. The idea behind PaM is to take traces that were
by a mobile host and distill them into modulation traces.
modulation traces capture the networking environment seen by
traced host, and are used by a PaM kernel to delay, drop, or
incoming and outgoing packets. With PaM, we've built a testbed
can repeatably, reliably mimic live systems under certain
scenarios
There are three main components to PaM. First, we've built a
capable of delaying, dropping, and corrupting packets to match
characteristics of some observed network. Second, we've defined
modulation trace format to describe how such a kernel should
packets. Third, we've built a tool to generate modulation
from certain classes of raw traces collected by mobile hosts
5.2.1. Packet
The PaM modulation tool has been placed in the kernel between the
layer and the underlying interfaces. The tool intercepts
and outgoing packets, and may choose to drop it, corrupt it, or
it. Dropping an incoming or outgoing packet is easy, simply don'
forward it along. Similarly, we can corrupt a packet by
some bits in the packet before forwarding it
Correctly delaying a packet is slightly more complicated. We
the delay a packet experiences as the time it takes the sender to
the packet onto the network interface plus the time it takes for
last byte to propagate to the receiver. The former, the
time, is the size of the packet divided by the available bandwidth
the latter is latency
Our approach at delay modulation is simple -- we assume that
actual network over which packets travel is much faster and of
quality than the one we are trying to emulate, and can thus
it. We delay the packet according to our latency and
targets, and then decide whether to drop or corrupt it. We take
to ensure that packet modulation does not unduly penalize
system activity, using the internal system clock to schedule packets
Since this clock is at a large granularity compared to
resolution, we try to keep the average error in scheduling to
minimum, rather than scheduling each packet at exactly the
time
Noble, et. al. Informational [Page 17]
RFC 2041 Mobile Network Tracing October 1996
5.2.2. Modulation
To tell the PaM kernel how the modulation parameters change
time, we provide it with a series of modulation-trace entries.
of these entries sets loss and corruption percentages, as well
network latency and inter-byte time, which is 1/bandwidth.
entries are stored in a trace file, the format of which is
simpler than record-format traces, and is designed for efficiency
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
Modulation traces begin with a header that is much like that found
record-format trace headers. Modulation headers additionally
the units in which latency and inter-byte time are expressed, and
maximum values for loss and corruption rates. Individual
contain the length of time for which the entry applies as well as
latency, inter-byte time, loss rate, and corruption rate
Noble, et. al. Informational [Page 18]
RFC 2041 Mobile Network Tracing October 1996
5.2.3. Trace
How can we generate these descriptive modulation traces from
recorded observational traces described in Section 4? To ensure
high-quality modulation trace, we limit ourselves to a very
set of source traces. As our experience with modulation traces
limited, we use a simple but tunable algorithm to generate them
Our basic strategy for determining latency and bandwidth is
closely to our model of packet delays: delay is equal
transmission time plus latency. We further assume that packets
traversed the network near one another in time experienced the
latency and bandwidth during transit. Given this, we look for
packets of different size that were sent close to one another
the same path; from the transit times and sizes of these packets,
can determine the near-instantaneous bandwidth and latency of
end-to-end path covered by those packets. If traced packet
contains sequence numbers, loss rates are fairly easy to calculate
Likewise, if the protocol is capable of marking corrupt packets
corruption information can be stored and then extracted from
traces
Using timestamped packet observations to derive network latency
bandwidth requires very accurate timing. Unfortunately, the
we have on hand have clocks that drift non-negligibly. We
chosen not to use protocols such as NTP [9] for two reasons. First
they produce network traffic above and beyond that in the
traced workload. Second, and perhaps more importantly, they
cause the clock to speed up or slow down during adjustment.
clock movements can play havoc with careful measurement
As a result, we can only depend on the timestamps of a single
to determine packet transit times. So, we use the ICMP ECHO
to provide workloads on traced machines; the ECHO request
timestamped on it's way out, and the corresponding ECHOREPLY
traced. We have modified the ping program to alternate between
and large packets. Traces that capture such altered ping traffic
then be subject to our transformation tool
The tool itself uses a simple sliding window scheme to
modulation entries. For each window position in the recorded trace
we determine the loss rate, and the average latency and
experienced by pairs of ICMP ECHO packets. The size and
of the sliding window are parameters of the transformation; as
gain experience both in analysis and modulation of wireless traces
we expect to be able to recommend good window sizes
Noble, et. al. Informational [Page 19]
RFC 2041 Mobile Network Tracing October 1996
Unfortunately, our wireless devices do not report corrupt packets
they are dropped by the hardware without operating
notification. However, our modulation system will also coerce
such corruptions to an increased loss rate, duplicating the
in the original network
5.3. Trace Analysis
A trace is only as useful as its processing tools. The
for such tools tools include robustness, flexibility,
portability. Having an extensible trace format places
emphasis on the ability to work with future versions. To this end
we provide a general processing library as a framework for users
easily develop customized processing tools; this library is
to provide both high portability and good performance
In this section, we first present the trace library. We
describe a set of tools for simple post-processing and preparing
trace for further analyses. We conclude with a brief description
our analysis tools that are applied to this minimally processed data
5.3.1. Trace
The trace library provides an interface that applications can use
simplify interaction with network traces, including functions
read, write, and print trace records. The trace reading and
functions manage byte swapping as well as optional integrity
of the trace as it is read or written. The library employs
buffering strategy that is optimized to trace I/O. Trace
facilities are provided for both debugging and parsing purposes
5.3.2. Processing
The processing tools are generally the simplest set of tools we
built around the trace format. By far the most complicated one
the modulation-trace transformation tool described in Section 5.2.3;
the remainder are quite simple in comparison. The first such tool
a parser that prints the content of an entire trace. With the
library, it is 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 many analysis tasks tend to work with records of the same type
an enhanced version of the parser can split the trace data by
into many files, one per track. Each line of the output text
contains a time stamp followed by the integer values of all
optional data in a track entry; in this form traces are amenable
further analysis be scripts written in an interpreted language
Noble, et. al. Informational [Page 20]
RFC 2041 Mobile Network Tracing October 1996
as perl
We have developed a small suite of tools providing simple
such as listing all the track headers and changing the
description as they have been needed. With the trace library,
such tool is trivial to construct
5.3.3. Analysis
Analysis tools depend greatly on the kind of information
experimenter wants to extract from the trace; our tools show our
biases in experimentation. Most analyses derive common
descriptions of traces, or establish some correlation between
trace data sets
As early users of the trace format and collection tools, we
developed a few analysis tools to study the behavior of the
networks at our disposal. We have been particularly interested
loss characteristics of wireless channels and their relation
signal quality and the position of the mobile host. In this section
we briefly present some of these tools to hint at the kind
experimentation possible with our trace format
Loss characteristics are among the most interesting aspects
wireless networks, and certainly among the least well understood.
shed light on this area, we have created tools to extract the
information from collected traces; in addition to calculating
standard parameters such as the packet loss rate, the tool
derives transitional probabilities for a two-state error model
This has proven to be a simple yet powerful model for capturing
burstiness observed in wireless loss rates due to fading signals.
help visualize the channel behavior in the presence of mobility,
tool can replay the movement of the mobile host while plotting
loss rate as it changes with time. It also allows us to zoom in
locations along the path and obtain detailed statistics
arbitrary time intervals
Our traces can be further analyzed to understand the
between channel behavior and the signal quality. For
devices like the NCR WaveLAN, we can easily obtain measurements
signal quality, signal strength, and noise level. We have
a simple statistical tool to test the correlation between
signal and the loss characteristics. Variations of this test
also possible using different combinations of the three
measurements and the movement of the host
Noble, et. al. Informational [Page 21]
RFC 2041 Mobile Network Tracing October 1996
The question of just how mobile such mobile hosts are can also
investigated through our traces. Position data are provided
traces that either involved GPS or user-supplied positions with
trace collection tools. This data is valuable for comparing
validating various mobility prediction algorithms. Given
network infrastructure and good signal measurements, we can
the mobile location within a region that is significantly
than the cell size. We are developing a tool to combine
information and signal measurement from many traces to identify
"signal quality" signature for different regions inside a building
Once this signature database is completed and validated, it can
used to generate position information for other traces that
only the signal quality information
6. Related
The previous work most relevant to mobile network tracing falls
two camps. The first, chiefly exemplified by tcpdump [7] and the
Packet Filter, or BPF [8], collect network traffic data. The second
notably Delayline [6], and the later Probe/Fault Injection Tool [4],
and the University of Lancaster's netowrk emulator [3],
network modulation similar to PaM
There are many systems that record network packet traffic; the
facto standard is tcpdump, which works in concert with a
filter such as BPF. The packet filter is given a small piece of
that describes packets of interest, and the first several bytes
each packet found to be interesting is copied to a buffer for
to consume. This architecture is efficient, flexible, and
rightly found great favor with the networking community
However, tcpdump cpatures only traffic data. It records
information concerning mobile networking devices nor mobile
location. Rather than adding seperate software components to a
running tcpdump to capture this additional data, we have chosen
follow an integrative approach to ease trace file administration.
have kept the lessons of tcpdump and BPF to heart; namely
only the information necessary, and transferring data up to
level in batches. It may well pay to investigate
incorporating device and location information directly into BPF,
taking the flexible filtering mechanism of BPF and including it
our trace collection software. For the moment, we do not
exactly what data we will need to explore the properties of
networks, and therefore do not exclude any data
There are three notable systems that provide packet
similar to PaM. The earliest such work is Delayline, a
designed to emulate wide-area networks atop local-area ones; a
Noble, et. al. Informational [Page 22]
RFC 2041 Mobile Network Tracing October 1996
similar to PaM's. The most striking difference between Delayline
PaM is that Delayline's emulation takes place entirely at the user
level, and requires applications to be recompiled against a
emulating the BSD socket system and library calls. While this is
portable approach that works well in the absence of kernel-
source access, it has the disadvantage that not all network
passes through the emulation layer; such traffic may have a
impact on the performance of the final system. Delayline
differs from PaM in that the emulated network uses a single set
parameters for each emulated connection; performance remains
constant, and cannot change much over time
The Lancaster network emulator was designed explicitly to
mobile networks. Rather than providing per-host modulation, it
a single, central server through which all network traffic
instrumented applications passes. While this system also does
capture all traffic into and out of a particular host, it does
modulation based on multiple hosts sharing a single emulated medium
There is a mechanism to change the parameters of emulation
hosts, though it is fairly cumbersome. The system uses
configuration file that can be changed and re-read while the
is running
The system closest in spirit to PaM is the Probe/Fault
Tool. This system's design philosophy allows an arbitrary
layer -- including device drivers -- to be encapsulated by a
below to modulate existing traffic, and a layer above to
test traffic. The parameters of modulation are provided by a
in an interpreted language, presently Tcl, providing
flexibility. However, there is no mechanism to synthesize
scripts -- they must be explicitly designed. Furthermore, the use
an interpreted language such as Tcl limits the use of PFI to user
level implementations of network drivers, and may have
implications
7. Future
This work is very much in its infancy; we have only begun to
the possible uses for mobile network traces. We have
several areas of further work
The trace format as it stands is very IP-centric. While one
imagine using unknown IP addresses for non-IP hosts, while
header-only properties to encode other addressing schemes, this
cumbersome at best. We are looking into ways to more
encode other addressing schemes, but are content to focus on
networks for the moment
Noble, et. al. Informational [Page 23]
RFC 2041 Mobile Network Tracing October 1996
Two obvious questions concerning wireless media are the following
How does a group of machines perform when sharing the same bandwidth
How asymmetric is the performance of real-world wireless channels
While we do have tools for merging traces taken from multiple
into a single trace file, we've not yet begun to examine
multiple-host scenarios in depth. We are also looking
instrumenting wireless base stations as well as end-point hosts
Much of our planned work involves the PaM testbed. First
foremost, many wireless channels are known to be asymmetric
splitting the replay trace into incoming and outgoing
entries is of paramount importance. We would like to extend PaM
handle multiple emulated interfaces as well as applying
modulation parameters to packets from or to different destinations
One could also imagine tracing performance from several
networking environments, and switching between such
under application control. For example, consider a set of
showing radio performance at various altitudes; an airplane
in a dive would switch from high-altitude modulation traces to low
altitude ones
Finally, we are anxious to begin exploring the properties of real
world mobile networks, and subjecting our own mobile system
to PaM to see how they perform. We hope others can make use of
tools to do the same
The authors wish to thank Dave Johnson, who provided early
to related work and helped us immeasurably in RFC formatting.
also wish to thank those who offered comments on early drafts of
document: Mike Davis, Barbara Denny, Mark Lewis, and Hui Zhang
Finally, we would like to thank Bruce Maggs and Chris Hobbs,
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 the State of California MICRO Program. Additional
was provided by AT&T, Hughes Aircraft, IBM Corp., Intel Corp.,
Metricom. The views and conclusions contained here are those of
authors and should not be interpreted as necessarily representing
official policies or endorsements, either express or implied,
AFMC, ARPA, AT&T, Hughes, IBM, Intel, Metricom, Carnegie
University, the University of California, the State of California,
the U.S. Government
Noble, et. al. Informational [Page 24]
RFC 2041 Mobile Network Tracing October 1996
Security
This RFC raises no security considerations
Authors'
Questions about this document can be directed to the authors
Brian D.
Computer Science
Carnegie Mellon
5000 Forbes
Pittsburgh, PA 15213-3891
Phone: +1-412-268-7399
Fax: +1-412-268-5576
EMail: bnoble@cs.cmu.
Giao T.
Room 473 Soda Hall #1776 (Research Office
University of California,
Berkeley, CA 94720-1776
Phone: +1-510-642-8919
Fax: +1-510-642-5775
EMail: gnguyen@cs.berkeley.
Mahadev
Computer Science
Carnegie Mellon
5000 Forbes
Pittsburgh, PA 15213-3891
Phone: +1-412-268-3743
Fax: +1-412-268-5576
EMail: satya@cs.cmu.
Randy H.
Room 231 Soda Hall #1770 (Administrative Office
University of California,
Berkeley, CA 94720-1770
Phone: +1-510-642-0253
Fax: +1-510-642-2845
EMail: randy@cs.berkeley.
Noble, et. al. Informational [Page 25]
RFC 2041 Mobile Network Tracing October 1996
[1] Chen, J. B., and Bershad, B. N. The Impact of Operating
Structure on Memory System Performance. In Proceedings of
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
Network File Systems. In Proceedings of the 1994 ACM
Conference on Measurement and Modeling of Computer
(Nashville, TN, May 1994).
[3] Davies, N., Blair, G. S., Cheverst, K., and Friday, A.
Network Emulator to Support the Development of
Applications. In Proceedings of the 2nd USENIX Symposium
Mobile and Location Independent Computing (April 10-11 1995).
[4] Dawson, S., and Jahanian, F. Probing and Fault Injection
Dependable Distributed Protocols. The Computer Jouranl 38, 4
(1995).
[5] Gloy, N., Young, C., Chen, J. B., and Smith, M. D. An
of Dynamic Branch Prediction Schemes on System Workloads.
The Proceedings of the 23rd Annual International Symposium
Computer Architecture (May 1996).
[6] Ingham, D. B., and Parrington, G. D. Delayline: A Wide-
Network Emulation Tool. Computing Systems 7, 3 (1994).
[7] Jacobson, V., Leres, C., and McCanne, S. The Tcpdump
Page. Lawrence Berkeley Laboratory, Berkeley, CA
[8] McCanne, S., and Jacobson, V. The BSD Packet Filter: A
Architecture for User-level Packet Capture. In Proceedings
the 1993 Winter USENIX Technical Conference (San Deigo, CA
January 1993).
[9] Mills, D. L. Improved Algorithms for Synchronizing
Network Clocks. IEEE/ACM Transactions on Networking 3, 3 (
1995).
[10] Mummert, L. B., Ebling, M. R., and Satyanarayanan, M
Exploiting Weak Connectivity for Mobile File Access.
Proceedings of the 15th Symposium on Operating System
(Copper Mountain, CO, December 1995).
Noble, et. al. Informational [Page 26]
RFC 2041 Mobile Network Tracing October 1996
[11] Nelson, M. N., Welch, B. B., and Ousterhout, J. K. Caching
the Sprite Network File System. ACM Transactions on
Systems 6, 1 (February 1988).
[12] Schilit, B., Adams, N., Gold, R., Tso, M., and Want, R.
PARCTAB Mobile Computing System. In Proceedings of the 4th
Workshop on Workstation Operating Systems (Napa, CA,
1993), pp. 34--39.
[13] Uhlig, R., Nagle, D., Stanley, T., Mudge, T., Sechrest, S.,
Brown, R. Design Tradeoffs for Software-Managed TLBs.
Transactions on Computer Systems 12, 3 (August 1994).
[14] Want, R., Hopper, A., Falcao, V., and Gibbons, J. The
Badge Location System. ACM Transactions on Information
10, 1 (January 1992), 91--102.
Noble, et. al. Informational [Page 27]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
