High Precision
Active Probing for Internet Measurement
Attila Pásztor
<Attila.Pasztor@eth.ericsson.se>
Ericsson Hungary R&D / EMULab at the dept. of E&EE, The University
of Melbourne
Hungary
Darryl
Veitch <D.Veitch@ee.mu.oz.au>
EMULab at the dept. of E&EE, The University of Melbourne
Australia
Abstract
Internet measurement
based on active measurement techniques is becoming a fundamental part of
performance management systems. The increasing importance of these methods
is due to their fundamentally end-to-end nature and great flexibility. However,
in order to remain non-invasive, active measurement methods in wide use
today are typically restricted to measurements on coarse time scales of
seconds or minutes. The goal of our work is to create and explore the benefits
of a highly accurate active probing system for very fine time scale measurements.
A structured overview of network-edge measuring approaches, and issues in
accurate traffic monitoring and non-invasive active probing, will be given.
Traffic metrics that can be derived from available measurements will also
be introduced. A wide range of measurement infrastructures will be presented
and compared, including highly accurate systems with GPS synchronisation
and special measurement cards, and systems based on off the shelf PC's.
Finally, to demonstrate the benefits of high precision active probing, some
measurement results will be presented and possible applications outlined.
Contents
1.
Introduction
2. Internet Measurement
3. Active Probing
3.1 Timing
Control
4. Active Probing Infrastructure
4.1
A High Precision Infrastructure
4.2 Comparison
5. Applications
5.1 Example
Application
6. Conclusion
Acknowledgments
References
1.
Introduction
Measurement
techniques are traditionally used in telecommunications networks to support
a wide range of activities including network planning and design, network
operation and research .
A classic
example of a traditional technique to obtain measurements would be the
various traffic counters built into network switching equipment. Passive
measurement of this type is in principle ideally suited for monitoring
such quantities as backbone link utilisation, or understanding and modeling
aggregate link traffic for dimensioning purposes, and has dominated tele-traffic
studies in the past. Obtaining end-to-end measures from collections of
such data however constitutes a difficult, data intensive, and time consuming
inversion task, motivating the direct measurement of end-to-end network
performance metrics, as well as of quality of service measures.
In contrast
to traditional measurement, we consider measurements made at the network
edge, and focus not on aggregate statistics, but on individual data flows
between specific origins and/or destinations. Note that the concepts
of "core" and "edge" remain relative. The origins and destinations on
the "edge" of the network could mean end users, or alternatively nodes
at the edge of some core network..
An important
reason for moving away from traditional core-network measurements is that
performing them on a large scale, routine basis, implies building measurement
infrastructure into the network elements, such as routers, themselves.
As traffic measurement will always be a secondary consideration for router
manufacturers, obtaining measurements which are adequate both in
terms of their time resolution and descriptive ability, is unlikely.
This is particularly true during high load where measurements are the
most relevant, but the routers the most preoccupied. Furthermore the kinds
of measurements required changes over time, and it is difficult to build
a sufficiently generic set into a switch which is also high performance.
We therefore focus on newer network-edge based methodologies, based on
monitoring packet streams in fine to very fine detail, rather than examining
counters or control information from network elements.
Active measurement,
where controlled probe traffic is generated, injected into a network,
and measured at a receiving node, is becoming increasingly important due
its great flexibility, intrinsically end-to-end nature, and freedom from
the need to access core network switching elements. Existing large
scale active measurement programs [1], [2],
[3], [4], [5]
have used probe traffic to measure connectivity, delay, and loss
statistics on coarse time scales, seconds or more commonly, minutes. Typically
simple probe streams have been used such as isolated probes, and low rate
periodic or (pseudo) Poisson streams. On finer time scales, several
milliseconds to seconds, periodic as well as more sophisticated probe
streams have been employed to measure bottleneck bandwidth [6],
[7], [8], [9], [10]
and available bandwidth [7], [10],
and to investigate the detailed statistical structure of delay and
loss [7], [11], [12],
[13], [14]. However, at such time
scales timing problems in common measurement infrastructures can result
in measurement errors of the order of the time intervals one is trying
to measure, and the inter-departure times of the packet probes one
is trying to control. Post processing techniques aimed at redressing or
at least monitoring these errors [11], [15],
can only imperfectly address a subset of the issues involved. Even for
the less demanding low resolution measurements, errors in individual
measurements of delay are no less significant, even if less critical.
The primary
goal of this paper is to report on active probing systems which are both
highly accurate and which allows high resolution measurements and probe
stream definition. In addition to enabling the detailed modelling
of the structure of losses and delays suffered by probe streams,
high accuracy increases the reliability and power of tools for the
measurement of network metrics such as bottleneck bandwidth, and
makes feasible the broader exploration of the scarcely tapped potential
of probing methods.
2.
Internet Measurement
Measurements
collected in the Internet, organised into the functional groupings as described
in [29], are those focusing on the areas of topology
(mapping, connectivity), workloads, performance, and routing. Topological
data describes the network link infrastructure on different protocol layers.
Workload measurements are those related to the resource usage of routers
or switches and the utilisation of links. Performance measurements focus
on the analysis of end-to-end behaviour and on the diagnosis of network
problems. Routing measurements provide insights into the dynamics of routing
protocols such as routing table updates. These are of great importance as
the reliability and robustness of the Internet depends on the stability
and efficiency of routing.
Passive and
active measurement are the two fundamental approaches used in communication
networks. By passive measurement we mean the standard approach of tracking
the performance and behaviour of packet streams simply by monitoring the
traffic passing by the measurement point(s). By active measurement we
mean the injection of artificial probe traffic into the network, and the
measurement of its characteristics at different points, typically back
at the origin (round-trip end-to-end measurement), or at some terminating
destination (one-way end-to-end).
Passive measurements
are usually used to measure metrics pertaining to a certain network element,
that is at-a-point metrics such as link throughput and packet size statistics.
However from the application point of view, particularly real-time applications,
end-to-end quality of service metrics are primordial, and for these the
passive approach is inappropriate as the presence of traffic between the
end points is not guaranteed. Thus active measurement methods are typically
used to obtain end-to-end statistics such as latency, loss and route availability.
While workload
and routing measurements typically utilise passive measurements, performance
and topology measurements rely on active measurement methods to a large
extent. In spite of this general classification the choice of the most
appropriate measurement technique to measure a certain metric will depend
on the actual circumstances and requirements, and in most cases both passive
and active measurement techniques can be applied. To make the right choice
a good understanding of the advantages and disadvantages of these fundamental
approaches is indispensable.
3.
Active Probing
Aside from being
able to generate traffic at will between selected points, there are many
other advantages of active measurement. Chief among these is the flexibility
to design probe streams with particular properties to match measurement
requirements: if we think of the route followed by the probes as a black
box, then by sending in different test input `signals' and measuring the
transformed output, we can shift the measurement focus from simple quantities
such as average delay and loss on a route, to bottleneck and available bandwidth,
and even to cross traffic estimation [6], [18].The
design parameters are the sequence of packet types, sizes and inter-departure
times, and can be chosen according to any deterministic and/or statistical
criteria. Other advantages include enormously reduced volume of measurement
data compared to the passive monitoring of high bandwidth links, and the
avoidance of data privacy issues and the corresponding need for payload
anonymization.
The main
disadvantage of active measurement is its invasive character. The probes
modify the very route conditions, and perturb the very traffic, that one
is trying to measure. In an attempt to minimize these effects measurement
projects typically use probe streams of average bandwidth lower than 10kbps
[19]. Since these streams are periodic or pseudo Poisson (the two are
very similar in practice), such low rate streams correspond to sampling
at low time resolution. The challenge for probe design is to deepen the
time resolution without unduly increasing the average bit rate.
3.1
Timing Control
Obtaining accurate
timing information is essential to minimize the measurement errors both
at the monitors and at the sender. The sender needs to send probe packets
at the designated target times, while the monitors must generate accurate
time stamps for packet arrivals.
The highest
accuracy available is that of dedicated hardware for probe stream generation
and monitoring. We use the purpose built DAG3.2e measurement cards for
monitoring as described below, but find that RT-Linux offers a software
solution for the Sender with adequate accuracy. While this monitoring
solution is expensive, other aspects of the system are not. In common
with the majority of measurement projects in the Internet community, we
focus on commercial PCs running Unix operating systems such as FreeBSD
and Linux. RT-Linux, although less common and less mature, is also inexpensive.
We use the
hardware monitors not only in the experimental infrastructure itself,
but as a reliable reference system with which to investigate the accuracy
of Unix based software solutions in general, and the RT-Linux Sender in
particular.
To discuss
issues related to clock accuracy in more detail some basic terminology
is needed. The clock resolution is the smallest unit by which a clock's
time is updated. The offset is the difference between the time reported
by the clock and the true reference time at a particular moment . The
skew is roughly the difference between the clock's frequency and a reference
frequency, or more precisely the coefficient of the linear component of
the offset.
Our clock
skew and stability measurements performed on commercial PCs running Linux
are consistent with the results of [20] stating that
the clock skew of commercial PCs is typically in the 50 PPM range, with
stability of the order of 0.1 PPM. These values can be used to estimate
the range of measurement errors of clocks not synchronized to a reference
source.
Unfortunately
the fine clock resolution available on some processors does not imply
low skew, nor high oscillator stability, nor accurate initialization to
absolute time. At boot time the software clock is initialized either from
the hardware clock or from an external reference. However, in addition
to the skew the frequency of the quartz oscillator varies over time due
to a number of different factors including changes in the ambient temperature,
power level and ageing. Thus besides accurate initialization the clock
also has to be continuously corrected for the skew and the smaller time
scale effects of oscillator stability [22].
The Network
Time Protocol (NTP) is used by the Internet to synchronize computer clocks
to an external reference source. The servers providing the synchronization
service are hierarchically organized, with primary servers synchronized
directly to external reference clocks such as GPS, and secondary servers
synchronized to primary servers and others in the synchronization subnet.
The clock synchronization is based on the exchange of time stamps between
the client and the server, and possibly some other peer. The round-trip
delay and the clock offset is then estimated from these time stamps. An
upper bound in the offset error estimation is half of the round-trip time
[23] , which is in the order of milliseconds even
in the case of LANs.
Errors of
the order of milliseconds, such as those generated by NTP based synchronization,
primarily affect the precision of one-way metrics such as one-way delay,
where the accurate synchronization of the monitoring host clocks is essential.
However a range of other performance metrics, such as round-trip time,
inter-arrival time and delay variation, do not require absolutely synchronized
clocks. The known stability of system clocks can then result in much higher
accuracy then what is achievable using NTP. This implies that for the
measurement of metrics involving small time scales using NTP is not only
unnecessary, it could even significantly degrade the measurement accuracy.
In cases
when the accuracy of network based clock synchronization is not sufficient,
GPS receivers can be used instead as high precision external references.
The accuracy of modern GPS receivers output signal is well below 1ms.
Large scale measurement projects collecting statistics of one-way metrics
such as Surveyor [2], RIPE [3] and
AMP [24], all use GPS synchronized measurement hosts.
For monitoring high bandwidth links an accuracy of 10ms is not sufficient.
In these cases special measurement cards like the DAG series, capable
of synchronizing to a GPS signal with much greater accuracy, can be used.
The DAG series
cards (see http://dag.cs.waikato.ac.nz/)
are special hardware boards designed primarily for the purpose of high
accuracy and high performance passive monitoring. They incorporate their
own processor and PCI interface. The main design aims of the DAG series
includes high performance capture up to OC48 and beyond, on board intelligence
to filter data before it is passed to the host processor, industry standard
interfaces, programmable and re-configurable structure, and highly accurate
timing referenced to a universal time standard [16].
We used two DAG3.2e cards designed for monitoring 10/100 Mbit/s Ethernet,
synchronized to a GPS receiver, yielding a time stamping accuracy below
100ns. They were used not only as the monitoring components of the probing
infrastructure but as timing references in all of the comparison experiments.
The hardware design of these cards allows them to be used as traffic generators,
and to perform filtering. However the firmware does not currently support
either of these.
The periodic
timer interrupts used to increment the system clock counter in Linux and
BSD form the basis of the allowed times for the scheduling of all tasks
for execution, both system and user. This finite scheduling granularity
can not be improved as simply as in the case of the clock resolution,
where a processor register counting CPU clock cycles can be used for interpolation
at intermediate time points. The default value in both operating systems
is 100, corresponding to 100 interrupts per second resulting in 10 ms
scheduling resolution. Unfortunately finite resolution is not the only
problem. All the periodically executed tasks and timed events queue behind
these interrupts, leading to synchronization, increased delays, and timing
errors.
The sending
of a precise probe stream is a real-time task which is ill-suited to the
imposition of a rigid scheduling grid. It is therefore natural to include
a real-time operating system in our comparison.
Real-Time
Linux [17] was selected because it is implemented
as an extension to the Linux operating system. It provides the capability
of running real-time tasks on the same machine as Linux, acting as a lower
layer which Linux sees as part of the hardware. The RT-Linux tasks execute
whenever they need to, independently of the status of the tasks under
Linux. The performance of a real-time task is determined mainly by hardware
characteristics such as interrupt latency. Process pre-emption is now
strictly limited, being possible only through hardware interrupts or possibly
other RT-Linux tasks as determined by the RT scheduler. In this paper
only one RT task was ever running, eliminating this latter possibility.
Another extremely
useful feature is that the real-time tasks can be connected to ordinary
Linux processes, either via a device interface or through shared memory.
As a result only real-time critical parts have to be implemented in RT-Linux,
other parts of the application can be run as normal Linux processes. An
example of this is given by the RT-Linux Sender application, where a user
process defines a probe stream and a real-time task actually sends the
packets on schedule, the two communicating via shared memory.
4.
Active Probing Infrastructure
The basic components
of an end-to-end active probing infrastructure are shown in figure 1. In
each probing experiment, the Sender creates and transmits a probe stream
which traverses some route in the network and terminates at the Receiver,
a sink. Together with the probe sequence numbers available from the payloads,
the packet arrival and departure time stamps define the raw outcome of the
experiment. They are recorded by the Sender Monitor and Receiver Monitor
respectively. Thus, although the task of the Sender is to send a probe stream
with designed characteristics, it is the actual probe characteristics which
constitute the experimental data and which are measured for use in analysis.
Note that in the case of round-trip measurements the Sender and Receiver
are two processes running on a single computer with a single Internet address.

Figure
1: The basic components of an active probing infrastructure.
Each of the components above is a potential source of errors, which all
involve timing in some form. These can be broken down further into errors
due to reference timing sources (including synchronization issues), hardware
issues such as interrupt cycles which drive process scheduling, and software
issues including the performance of algorithms for software clock correction.
4.1
A High Precision Infrastructure
In existing
systems timing problems of diverse origins, including inaccurate reference
time sources, computer process scheduling, and lack of synchronization (in
the case of one-way measurements), combine to produce time varying errors
which can range from milliseconds to seconds. Each of these sources of error
is quantified and addressed in the present system. The monitoring components
at both sender and receiver are based on Global Positioning System (GPS)
synchronized DAG3.2e [16] measurement cards with time
stamping accurate to 100ns. The transmission component is based on a Real-Time
Linux [17] Unix system transmitting over 100Mbps Ethernet,
and is capable of delivering packets at an accuracy (using a 600MHz machine)
limited by that of the interrupt latency in delivering packets to the card.
For User Datagram Packet (UDP) probe packets varying from 30 to 1500 bytes
this is uniformly below 10ms. The sender is capable of taking a specification
of an arbitrary probe stream, given as a list of packet sizes and target
inter-departure times, and of sending them consistently with this accuracy
with almost no disruption due to kernel scheduling. In particular packets
can be reliably sent back-to-back when required, an important dimension
in probe stream design.
4.2
Comparison
Part of the
attraction of active measurement has been its low cost, and ease of deployment,
arising from the use of commodity equipment and software. Although we retain
a commodity PC, Ethernet card, and freely available operating system software
as the core of the system, clearly both of these advantages have been largely
lost. However, the availability of a high accuracy reference system is an
essential prerequisite to the evaluation of less complete solutions. A second
goal of the project is to investigate the limitations of simpler systems.
The variants considered are with or without GPS, using RT-Linux time stamping
instead of the DAG, and using well designed sender programs in Linux and
FreeBSD rather than RT-Linux. By bench marking against the full system,
it is determined which combinations provide adequate performance for different
tasks, allowing cheaper and therefore more numerous measurement nodes with
limited but known precision.
To assess
the accuracy of software based monitoring using the three operating systems
we compared the time stamps generated by the receiver host against those
from the DAG card, connected via passive Ethernet tap. (due to the high
performance of the DAG its current lack of filtering ability is not a
limitation).
All the computers
involved in the test were 500 MHz Pentium III based systems equipped with
the same type of network interface card. The test hosts are connected
in a star configuration to our switch using 100 Mbps Ethernet connections.
Under FreeBSD and Linux the tcpdump utility was used to generate the time
stamps, while under RT-Linux a real-time process performed this task.
The test
packet stream consisted of 10000 packets each of 10 bytes with a lower
end truncated exponentially distributed inter-departure time of mean 10
ms. This truncation is described further in the next section where similar
test streams were used. For our purposes here the details of the stream
are not important.
To better
study timing errors arising in a single node we avoid metrics requiring
end-to-end synchronization such as delay. We choose the inter-arrival
time of the test packets as a basis for comparison. Over a 10 ms time
interval, the mean inter-departure time of the test stream, the typical
50PPM clock skew would result in an average 0.5ms offset error, which
is below the clock resolution of the compared host. Hence we do not use
NTP but rely on the software clock, which is sufficiently accurate over
these time scales.
There are
two fundamentally different types of measurement errors. Those due to
scheduling problems typically result in spikes in the order of ms. These
appear when the operating systems performs a high priority task, which
delays the processing of the arrived packet or the time stamp generation.
The second group are due to the clock reading inaccuracies, which are
typically in the range of ms.
Figure
2. Monitoring comparison of BSD, Linux and RT-Linux comparing inter-arrival
time errors
Comparing the
results for RT-Linux to those for FreeBSD and Linux reveals the fundamental
difference between multi-tasking and real-time operating systems. However,
even the real-time system is limited by the constraints of the available
hardware.
A number
of experiments were performed to compare the suitability of the different
operating systems for running an active probe sending application. All
versions of the sender software use the so called hybrid timing
[11]. In each case the sending algorithm is implemented
in two modules, the timing process running separately from the process
generating the time series, the two communicating via shared memory. In
the case of RT-Linux only the timing process is implemented as a real-time
task.
As the measure
of timing accuracy we use the difference of the targeted and measured
packet inter-departure times. This choice is based on the same reasoning
as in the monitor comparison. In each experiment 10000 packets were used
of the same size.
Figure
3. Sender comparison of BSD and Linux
The top graph
of figure 3 shows the result of the experiment run with a sender on a FreeBSD
host. This plot shows very similar characteristics to the results of the
monitoring test (see figure 2). The delays due to scheduling problems appear
as errors in the range of a couple of milliseconds. The schedulers of the
Linux and FreeBSD kernels allow the root user to set the scheduling policy
and priority of the executed processes using the sched_setscheduler system
call. This helps to minimize the errors due to the execution of other processes.
The results shown on the top graph of figure 3 are from a host, configured
as an average client with a window manager and only a single user logged
on, running the sending process as its only application. The same measurement
was repeated using the sched_setscheduler system call to set maximum priority
and to avoid pre-empting the execution of the sending process as much as
possible. (The scheduling policy was set to SCHED_FIFO and its priority
to sched_get_priority_max.) Running the sender with these changes on the
FreeBSD host did not appreciably affect the measurement result compared
to the application run on a minimally loaded system.
The experiment
was repeated with a host running Linux, and the results shown in the bottom
graphs of figure 3. The graph in the middle shows the results from a host
running a window manager, serving a single user running a number of applications.
The user changed the virtual screens displayed a couple of times during
the measurement which resulted in spikes due to scheduling problems as
high as 180 ms. The bottom graph shows the result of the experiment repeated
on an idle host not running even a window manager, and running the sending
process as the only active user application. The effect of decreasing
the system load is is dramatically demonstrated by the difference between
these plots. The first Linux measurement was then repeated using the sched_setscheduler
system call as in the case of FreeBSD. The results then became practically
identical to those of the second experiment, decreasing the maximum error
of 180 ms of the first experiment to below 1 ms.
The results
of our tests demonstrate that the worst case scheduling accuracy in the
case of the non real-time operating systems can exceed even 100's of milliseconds.
However, with careful configuration and prioritization of the sender task
the scheduling errors can be kept in the millisecond range. We have also
observed that the frequency of these `ms' size errors, on our test machines
running a very limited number of tasks, was in the range of tens per 10000
packets sent.
The RT-Linux
sender essentially eliminates scheduling errors. The accuracy of the RT-Linux
timing is limited by the properties of the hardware, determined mainly
by the interrupt handling characteristics of the CPU, resulting in an
upper bound on scheduling inaccuracies observed to be below 15ms on our
600 MHz Pentium III based test machines.
These tests
provide information on the accuracy achievable on different platforms,
however the final choice of Sender platform will depend on the requirements
of the application and the nature of the metrics to be measured.
5.
Applications
Active measurements
are successfully used in a wide variaty of applications. The dominating
application field of these measurement methods is the area of end-to-end
performance measurements, benefiting from most of the advantages of the
active probing. Besides the end-to-end performance metrics like latency
and loss statistics, active measurements are used to measure availability
and are also widely deployed in the area of topology discovery.
5.1
Example Application - Bandwidth Estimation
The benefits
of an accurate infrastructure are apparent from figure 4, where many of
the `visible queueing' lies in the millisecond range, which would be lost
to noise in other systems. Estimates of metrics based on measuring these
slopes would obviously suffer, and indeed many methods involved complex
and heuristic aspects, involving much averaging, in an attempt to reduce
the impact of `noise'. With the accurate infrastructure, rather than averaging,
one can meaningfully examine high resolution histograms, which yields important
new information.
Figure 4. Two plots demonstrating the benefits of the high accuracy infrastructure
- The delay plot of a probe stream with a transmission rate exceeding
the bottleneck bandwidth (2 Mbps) compared to a stream remaining below
it (0.3 Mbps)
The figures
presented in this paper are the results of some initial one-way measurements
over the Internet, between EMULab in Melbourne and the WAND group at the
University of Waikato.
The measured
route consisted of 13 hops, both the sender and the receiver residing
on a 100Mbps LAN. It is also known that the bandwidth of the outgoing
link from EMULab's gateway is 10Mbps and the bottleneck bandwidth of the
route was somewhat below 2 Mbps. The results presented in this paper are
based on a measurement setup using GPS synchronized DAG cards both as
sender and receiver monitors and a RT-Linux based sender.
The plot
of the lower rate stream on figure 4 clearly illustrates the effect of
the background traffic on the one-way delay. On the arrival of background
traffic bursts, or even just larger sized packets, the delay value jumps
higher and then gradually falls back. This effect corresponds to a number
of probe packets catching up to each other in a queue, then leaving the
queue with a rate corresponding to the transmission rate of the given
link. This effect is seen in on the lower plot of figure 4. As a result
of this packet bunching, the slope of the delay decrease can be used to
estimate the link bandwidth, as for example in [6].
Alternatively, similar information is carried in the inter-arrival time
series. As is well known, the link rate determines the inter-packet times
of the `spaced out' back-to-back packets leaving it, which when appearing
as inter-arrival times at the receiver can be used to estimate the link
bandwidth. Methods described in [6,26,27,28]
are all based on this fundamental property.
The higher
rate streams saturate the route and experiences loss. The upper plot of
figure 4 shows a close up of the 2Mbps stream. Packet losses lead to decreased
delay for packets immediately following the lost one (as the queue size
at the router with loss is smaller), while consecutive arrivals with a
steady rate exceeding the bottleneck rate leads to linear increase in
the delay. The slope of the increase is again determined by the link bandwidth
in a simple way.
Figures 5
and 6 demonstrate the importance and benefits of probe stream design and
of high accuracy, high resolution active probing.
Two very
different streams are used in this experiment. The 300kbit rate stream
is a simple periodic one of 1500Byte packets with constant 40ms inter-departure
time. Figure 5 shows the phase plot and the histogram of the one-way delay
and it's differenced series, the delay variation experienced by this stream.
Figure 5. Delay and delay variation phase plot and histogram of the periodic
stream
The second stream
is a simple `designer' stream constructed from packet pairs where the inter-departure
time within the pair is a constant 130ms, corresponding to back-to-back
packets on the outgoing 100Mbps link, and pairs are independently separated
according to an exponential distribution with a mean of 2 seconds. As the
packet size used in the experiment is 1500 bytes the average rate of this
stream is only 18kbps. Sending the packet pairs ensures that many packets
will queue behind each other in queues along the route, whereas the periodic
stream has to rely on background traffic to create this effect. The difference
is shown very clearly in the delay variation histograms on figure 5 and
6. The 18kbps stream's histogram shows clearly a peak corresponding to the
of packets spaced out by the bottleneck link while the same information
is much less apparent from the histogram of the periodic stream. The phase
plots of figure 6 clearly demonstrate the deterministic effect of the bottleneck
on the delay characteristics while the plots of figure 5 are dominated by
the random effects of the background traffic.
Figure 6. Delay and delay variation phase plot and histogram of the 'designer'
probe stream
While the results
shown on these figures are based on traces from the highly accurate and
GPS synchronized DAG card monitors and an RT-Linux based Sender, the results
of the same measurement repeated using only Linux applications for each
task showed no qualitative differences compared to those shown above. This
is the result of using inter-arrival time as a metric, and thereby not requiring
the synchronization of the measurement hosts, and controlling the measurement
errors via careful design of the infrastructure implementation.
This simple
example demonstrates the benefits of using specially designed probe streams
for active measurements. Bandwidth measurements proposed by [27,26]
rely on sending probes back-to-back if possible while the methods proposed
in [10,18]
require precise control of the inter-departure times between the probe
packets. These developments in the active probing methodology require
more and more control over measurement errors and emphasize the importance
of a high precision, reliable and simple measurement infrastructures.
Our future work is focusing on the development and analysis of new measurement
methods based on high resolution probing and benefiting from the accuracy
of the new measurement infrastructure.
6.
Conclusion
An overview
of Internet measurement was presented, contrasting traditional passive and
network core measurement techniques from the more end-to-end oriented network
edge measurement, which is generally performed actively. The advantages
of the active network-edge combination were given, motivating a detailed
discussion of active measurement.
The difficulties
inherent in active measurement on inexpensive PC based systems were discussed,
in particular timing difficulties. To evaluate the performance of various
alternatives, a highly accurate reference active probing infrastructure
was developed, allowing the reliable measurement of network wide delays,
and the reliable transmission of high resolution active probe streams,
with well under millisecond accuracy. The system employs DAG card based
monitors and a flexible RT-Linux based probe sender application.
After comparing
different Unix on PC based solutions for the sender component of the infrastructures,
RT-Linux was found to be clearly superior, controlling scheduling errors
down to 10 microseconds, whereas Linux and FreeBSD systems have errors
in the millisecond range. However, carefully designed sender software
and procedures can reduce these errors significantly, to the point where
they are viable for measurements of some metrics which do not require
end-to-end synchronization. Network based synchronization using
NTP was examined in detail and was found to produce highly undesirable
effects in the sub-millisecond range, and is not recommended.
Finally the
reference infrastructure was used to perform preliminary experiments
over an Internet route, illustrating the clarity with which queueing
can be visualized with the reference system. Finally the benefits
of using low rate `designer probe' streams as an efficient means
of measuring link rates was discussed and illustrated.
Acknowledgments
The authors wish to thank Andrew Anderson and Michael Dwyer at EMULab
for their invaluable expertise in Unix systems, and to David Hornsby for
his assistance in accessing GPS. The generous support of the WAND group
at the University of Waikato, particularly that of Jörg Micheel and
including the loan of a DAG3.2e, is warmly acknowledged. This work was
supported by Ericsson.
References
[1] L. Cottrell and W. Matthews,
``Comparison of surveyor and ripe,'' SLAC -http://www.slac.stanford.edu/comp/net/wan-mon/surveyor-vs-ripe.html,
March 2000.
[2]
S. Kalidindi and M. J. Zekauskas, ``Surveyor: An infrastructure for
internet performance measurements,'' INET'99 -http://telesto.advanced.org/
kalidindi/papers/INET/inet99.html, June 1999.
[3]
H. Uijterwaal and O. Kolkman, ``Internet delay measurements using test
traffic: Design note,'' Tech. Rep. RIPE-158, RIPE NCC -http://www.ripe.net/ripencc/mem-services/ttm/Notes/RIPE_158.ps.gz,
June 1997.
[4]
T. McGregor, H.-W. Braun, and J. Brown, ``The nlanr network analysis
infrastructure,'' IEEE Communications Magazine special issue on "Network
Traffic Measurements and Experiments", http://wand.cs.waikato.ac.nz/wand/publications/,
May 2000.
[5]
W. Matthews and L. Cottrell, ``The pinger project: Active internet
performance monitoring for the henp community,'' IEEE Communications
Magazine special issue on "Network Traffic Measurements and Experiments",
http://www-iepm.slac.stanford.edu/paperwork/ieee/ieee.ps.gz,
May 2000.
[6]
J. C. Bolot, ``Characterizing end-to-end packet delay and loss in the
internet,'' Journal of High-Speed Networks, vol. 2, pp. 305-323, September
1993.
[7]
V. Paxson, ``End-to-end internet packet dynamics,'' in Proceedings
of ACM Sigcomm'97, (Cannes, France), pp. 139-152, September 14-18 1997.
[8]
V. Jacobson, Pathchar - a tool to infer characteristics of Internet
paths, available at: http://www.employees.org/bmah/software/pchar/
ed., 1997.
[9]
K. Lai and M. Baker, ``Measuring bandwidth,'' in Proceedings of
IEEE Infocom'99, (NY, NY), March 21-25 1999.
[10]
B. Melander, M. Björkman, and P. Gunningberg, ``A new end-to-end
probing and analysis method for estimating bandwidth bottlenecks,''
in Proceedings of Globecom'00, (San Francisco), November 2000.
[11]
J. Andren, M. Hilding, and D. Veitch, ``Understanding end-to-end internet
traffic dynamics,'' in IEEE GLOBECOM'98, vol. 2, (Sydney, Australia),
pp. 1118-1122, November 1998.
[12]
J.-C. Bolot and A. Vega-Garcia, ``The case for FEC-based error control
for packet audio in the internet,'' ACM/Springer Multimedia Systems,
1999.
[13]
S. Moon, J. Kurose, P. Skelly, and D. Towsley, ``Correlation of packet
delay and loss in the internet,'' Tech. Rep. TR 98-11, Department
of Computer Science, University of Massachusetts, January 1998.
[14]
M. Yajnik, S. Moon, J. Kurose, and D. Towsley, ``Measuring and modeling
of the temporal dependence in packet loss,'' in Proceedings of IEEE
Infocom'99, (NY, NY), March 21-25 1999.
[15]
S. B. Moon, P. Skelly, and D. Towsley, ``Estimation and removal of
clock skew from network delay measurements,'' Tech. Rep. 98-43, Department
of Computer Science, University of Massachusetts at Amherst, 1998.
[16]
J. Cleary, S. Donnelly, I. Graham, A. McGregor, and M. Pearson, ``Design
principles for accurate passive measurement,'' in PAM 2000, The First
Passive and Active Measurement Workshop,http://pam2000.cs.waikato.ac.nz/final_program.htm,
(Hamilton, New Zealand), April 2000.
[17]
V. Yodaiken, ``The rtlinux manifesto,'' tech. rep., Department
of Computer Science, New Mexico Institute of Technology, 1999.
available at http://www.rtlinux.org.
[18]
V. Ribeiro, M. Coates, R. Riedi, and S. Sarvotham, ``Multifractal cross-traffic
estimation,'' in Proceedings of the ITC Specialist Seminar on IP Traffic
Measurement, Modelling and Management 2000, (Monterey, CA), September
18-20 2000.
[19]
L. Cottrell, ``Comparison of some internet active end-to-end performance
measurement projects,'' SLAC -http://www.slac.stanford.edu/comp/net/wan-mon/iepm-cf.html,
July 1999.
[20]
D. Mills, ``The network computer as precision timekeeper,'' in
Proc. Precision Time and Time Interval (PTTI) Applications and Planning
Meeting, (Reston VA), December 1996.
pages 96-108.
[21]
P. Abry, D. Veitch, and P. Flandrin, ``Long-range dependence: revisiting
aggregation with wavelets,'' Journal of Time Series Analysis, vol.
19, pp. 253-266, May 1998.
[22]
D. Mills, ``Precision synchronization of computer network clocks,''
Tech. Rep. Report 93-11-1, Electrical Engineering Department, University
of Delaware, November 1993.
66 pages.
[23]
D. Mills, ``Internet time synchronization: the network time protocol,''
IEEE Trans. Communications COM, vol. 39, pp. 1482-1493, October 1991.
Condensed from RFC-1129.
[24]
A. McGregor and H.-W. Braun, ``Balancing cost and utility in active
monitoring: The amp example,'' NLANR -http://wand.cs.waikato.ac.nz/wand/publications/inet2000-amp-html/paper.html
, February 2000.
[25]
M. Aron and P. Druschel, ``Soft timers: efficient microsecond software
timer support for network processing,'' Operating Systems Review,
vol. 34, pp. 232-246, December 1999.
Also in 17th ACM Symposium on Operating System Principles (SOSP'99).
[26]
K. Lai and M. Baker, ``Measuring link bandwidths using a deterministic
model of packet delay,'' in Proceedings of IEEE Infocom'00, (Tel Aviv),
March 2000.
[27]
R. Carter and M. Crovella, ``Measuring bottleneck link speed in packet-switched
networks,'' Tech. Rep. 1996-006, Department of Computer Science, Boston
University, 15, 1996.
[28]
V. Paxson, Measurements and Analysis of End-to-End Internet Dynamics.
PhD thesis, U.C. Berkeley, 1997.
ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.ps.gz.
[29]
K. Claffy., Internet measurement and data analysis: topology, workload,
performance and routing statistics.
NAE '99 workshop, CAIDA -http://www.caida.org/outreach/papers/Nae/,
1999.
|