Active probing using packet quartets.
A significant proportion of link bandwidth measurement methods are based on IP's ability to control the number of hops a packet can traverse along a route via the time-to-live (TTL) field of the IP header. A new delay variation based path model is introduced and used to analyse the fundamental networking effects underlying these methods. Insight from the model allows new link estimation methods to be derived and analysed. A new method family based on packet quartets: a combination of two packet pairs each comprising a probe following a pacesetter packet, where the TTL of the pacesetter is limited and the end-to-end delay variation of the probes is measured, is introduced. The methods provide 'pathchar-like' rate estimates over multiple links without relying on the delivery of ICMP messages, with reduced invasiveness and other advantages. The methods are demonstrated using simulations, and measurements on two different network routes are used for illustration and comparison against available tools (pathchar and clink). A comprehensive analysis of practical issues affecting the accuracy of the methods, such as link layer headers, is provided. Particular attention is paid to the consequences of 'invisible' hops: nodes where the TTL is not decreased.
INTRODUCTION
Recent papers of Lai and Baker [1] and Dovrolis [2] identify
two primary network effects at the foundation of existing probing
techniques. The one-packet methods are based on the assumption
that the transmission delay is linear in the packet size.
The idea was first introduced by V. Jacobson in his pathchar
tool: to estimate link bandwidths from round trip delays of different
sized packets from successive routers along the path [3],
[1]. The packet pair family is based on the 'spacing' effect of
the bottleneck link [4], the fact that the minimum inter-departure
time of consecutive packets from a link is attained when they
are back-to-back. This effect can be utilised to estimate bottleneck
bandwidth (the smallest link rate) [5], [6], [7], [8], [1],
[2]. Methods estimating available bandwidth are also based on
the observation of the inter-departure time of consecutive probe
packets, taking into consideration the cases when cross traffic
packets are inserted between them. This possibility is discussed
in [6], [7], [9], [1], [2], [10].
In a recent paper [11], we enhanced the packet-pair family
through thoroughly investigating its dependence on probe size
and the effects of link layer headers. In this paper we contribute
to the development of hybrid methods exploiting both of
Research Center for Ultra Broadband Information Networks,
Dept. of Electrical and Electronic Engineering, The University of Melbourne.
Hungary R&D, fa.pasztor, d.veitchg@ee.mu.oz.au
The authors gratefully acknowledge the support of Ericsson.
the above effects. In doing so we make extensive use of the IP
header time-to-live (TTL) field as a means of accessing different
hops along the path. Pathchar was the first link bandwidth estimation
method published based on this idea. It used the TTL
field to induce reverse path ICMP messages, allowing round-trip
delay measurements (figure (1)). Downey suggested a number
of improvements to the filtering method used and implemented
them in his clink tool [3].
Forward path
Backward path
ICMP returned
UDP sent
RECEIVER
FW Hop #3
FW Hop #2
FW Hop #1 FW Hop #4
Expired
Fig. 1. IP time to live (TTL) expiration explained, the TTL of the UDP packet is
set to 2. In real networks the backward route can be different for each TTL.
In this paper we expand and generalise on these ideas in several
ways. First, we describe the advantages of moving from
an approach based on measuring delays, and minimum filter-
ing, to one based on delay variation, and peak detection in his-
tograms. We give a thorough description of the nature of the
noise encountered by probes as they traverse the route, and introduce
new methods exploiting the characteristics of this noise
(for more details see [12]). We also point out the crucial importance
for all one-packet methods of probes remaining in different
busy periods at each hop. This distinction is central to
the performance of probing methods, but has not been clearly
appreciated before (see however [11], [12]). When this condition
is satisfied, the noise typically takes on symmetric characteristics
which allows highly efficient median based filtering.
Using these ideas, we propose ACCSIG as a more efficient
pathchar-like method. The resulting discussion also prepares
the ground for the second and main part of the paper, where
we follow in the steps of Lai and Baker [1] in using TTL, but
without using the returning ICMP messages, with their associated
disadvantages. We introduce a flexible packet quartet (PQ)
probe class, where probes are replaced by a probe and pacesetter
pair, and in this framework define and analyse 5 new estimation
methods based on delay variation and peak detection. We determine
their key characteristics including their susceptability to
different kinds of error. Simulation based comparisons are performed
amongst the new methods, and real network measurements
on two different network routes are used to illustrate the
methods and compare them to pathchar and clink. A full
network based validation however is beyond the scope of the pa-
per, whose main aim is to introduce the packet quartet methods
and to derive their central properties. Finally, several important
Segment Local route International route
1. 100Mbps LAN 100Mbps LAN
2x100Mbps switched 2x100Mbps switched
2. Bottleneck 10Mbps LAN
10Mbps LAN 2x10Mbps switched
3. 100Mbps FDDI
4. 155Mbps ATM
5. 155Mbps ATM
(2x155Mbps ATM)
6. 22Mbps
7. Unknown
est. 100Mbps single hop
8. Unknown
est. 10Mbps single hop
9. Suspected Bottleneck
estimated 2x2Mbps
10. Unknown
estimated 22Mbps
11. Unknown
estimated >100Mbps
12. 100Mbps LAN
(only last link known)


I
IP-SEGMENT COMPOSITION OF THE TWO TEST ROUTES.
practical issues are discussed in detail, in particular the common
problem of invisible hops, where TTL cannot be decremented,
which leads to serious estimation errors and is one of the key
drawbacks of TTL based approaches. The behaviour of the proposed
and existing methods with respect to this problem is given
a thorough treatment. It is shown how it can be detected and
in some cases corrected by combining different packet quartet
methods.
We model a route as a chain of ordered hops,
H , where a hop is a FIFO queue with deterministic service rate
h followed by a transmission link of rate  h and latency D h .
If a packet is to be dropped at hop h due to an expired TTL
field, then it does so at the instant it arrives there, without actually
entering the queue at hop h. Physically, this hop model is
consistent with store and forward routers where packet arrivals
and departures are counted from the end of the last bit: the input
queue is seen as part of the previous transmission link, and
only when the packet has fully arrived is it either dropped, or
transferred (in negligible time) to the output queue, which is the
queue modelled.
The network measurements in this paper were taken over
two one-way routes. One, in the laboratory, was only two IP-
hops (we call this a segment) long and completely known. The
other exited the country, was 12 segments long (as measured
by traceroute), and was only partially known, as detailed
in table I. A high accuracy sender, similar to that described
in [13], was used capable of sending arbitrary streams of UDP
probes. The raw experimental data is the arrival and departure
timestamps of the probes. These were collected with a modified
tcpdump using a modified software clock, described in
[14], with a skew of less than 0.1 parts per million. Software
measurement noise was measured to be significant in just a few
measurements per 10000.
II. PATHCHAR REVISITED
We begin with some generic definitions relating to packets
traversing a single hop. Although the equations hold true for
arbitrary packets, in this paper the index i refers to probe packets
only. Probe i arrives to the hop by appearing in the queue at the
time instant  i . It begins service after a waiting time of w i  0,
completes it after a service time of x i > 0, and after a constant
propagation delay of D > 0, exits the hop at time
. The 1-hop
delay is therefore
and comparing two successive probes we have the 1-hop
inter-departure time: t
delay
in which D plays no role.
Pathchar and its variants are based on measuring the
round-trip delay between the release of TTL limited UDP probes
and the receipt of their corresponding ICMP error messages. If
we label the forward route hop after which the TTL expires by
h ttl , the backward route hop at which the ICMP error message
enters by k ttl , and let K be the last hop on the backward route,
then using equation (1) the delay can be expressed as:
h=k ttl
icmp
Since the service time of probe i on hop h can be expressed
as is the probe size, and as the size of ICMP
messages is fixed, we see that there exists a deterministic linear
relationship between probe size and delay. This can be exploited
by varying the probe size, and filtering to eliminate the contribution
of the waiting time terms, which can be thought of as a
kind of noise.
In pathchar, after measuring this round-trip delay for
many probes, a filtering based on minima is applied to the delay
series, which aims to select probes for which the waiting times
were in fact zero. For such probes the delay can
be expressed as
where C represents the packet size independent remainder of
equation (6). This operation is performed for a number of different
probe sizes (default values: pathchar 45, clink 93)
to obtain samples of a function d(p) describing the minima as
a function of probe size p. Finally, a slope is fitted through the
estimated d(p) function values.
From equation (7) it is clear that the slope estimate corresponds
to
. The link rates  h are then determined
by perfoming the procedure for all TTL values from 1 up to the
number of IP hops, and estimating the  h from the increase in
the slope at each stage.
In the ACCSIG method described below, we change the above
methodology in one key respect, resulting in a significant improvement
in efficiency. The change is based on a novel approach
of observing and analysing a network route, using the
delay variation of probes, rather than the delay. We now introduce
this approach, which is also the basis of the packet quartet
methods described in section III.
A. A new delay variation based route description
Probing analysis has typically centered on the fd i g series, as
in pathchar-like methods, or on the time series of receiver
g, as in packet-pair type methods. For either
purpose, we claim that it is advantageous to focus on the delay
variation f- i g, for two reasons. First, as -
and the
are part of probe design and therefore known, f- i g includes
but allows richer structure through the choice of ft i g. Sec-
ond, up to a constant f- i g is equivalent to fd i g, but like ft
only requires accurate clock rates for its measurement, not end-
to-end clock synchronisation, an important practical advantage.
In fact,through its reliance on slope estimates, pathchar is
also based on differences of delay. Here we show some of the
advantages of moving to an explicit delay variation framework,
the development of which was motivated by repeated observations
in network measurements of very characteristic features in
delay variation histograms.
As the route delay is simply the sum of the individual hop
delays, the delay variation over an H-hop route can be written
using equation (5) as:
(w h
Consider each of the terms in the above equation. The first expresses
the contribution of the probe service times. It is a deterministic
effect independent of cross traffic which accumulates
over hops where adjacent probes have unequal service times.
The second term is due to cross traffic. It can be thought of a
kind of random noise, however the nature of that noise depends
critically upon the interaction between the cross traffic and the
probe stream.
During network experiments we observed that probe streams
with probe separations in the range of 100s of ms and above,
produce characteristic symmetric delay variation histograms.
This can be be understood in terms of the nature of the noise
in such a case, as follows.
Recall that the busy periods for a queue are the time intervals
where the server is continuously active, which separate the
idle periods when the queue is empty. If, for each hop, each
probe arrives in a different busy period, which can be achieved
with high probability by sending them well separated, then each
waiting term w h
i comes from a different busy period, and contains
no explicit probe component. Provided the cross traffic
does not change systematically over the measurement interval,
it is then reasonable to regard these waiting times as an approximately
IID sequence across probes, and hence
(w h
as a symmetric, near white noise at each hop. This does not
mean that a strong assumption of low correlations between hops
is being made. Indeed, only if a queue is unstable will we not
be able to ensure that probes arrive to it in different busy periods
for sufficiently large separation.
In figure (2a) the delay variation histogram is given from a
simulation with stationary cross traffic, where the fixed sized
probes do in fact arrive to the hop in different busy periods. The
service time term cancels, leaving only the waiting time terms,
and we observe, as argued above, that they behave as a symmetric
noise. When however consecutive probes arrive during the
same busy period the nature of the noise is substantially differ-
ent. We briefly consider this case in section II-D.3.
We now describe the accumulation signature, the - i based
observable which serves as the basis of our new estimation
methods. With constant probe size (assuming x h
accumulation term (p i
1= h vanishes, corresponding
to a peak at - in the histogram, which the noise spreads
out. If instead the probe sizes are made to alternate (the alternation
is essential, other orderings would produce different distri-
butions), the peak splits into two, and the distance between the
twin peaks is proportional to the quantity
1= h , and allows
it to be measured. In figure (2b) it is seen in the context of a
real measurement how these symmetric peaks combine with the
symmetric noise to produce a symmetric bimodal distribution -
the signature.
d [sec]
(a)
d [sec]
(b)
Fig. 2. Accumulation signature in delay variation histograms. (a) 1 hop simula-
tion. Constant probe size: the service time cancels, the noise is symmetric,
(b) 12 hop measurement. Alternating probe size: the peak splits and the
signature emerges: a symmetric bimodal histogram.
To reduce measurement error it is desirable to increase the
signature, that is to increase the distance between the peaks.
This suggests constructing a probe stream with sizes which alternate
between the minimum and maximum possible values,
rather then using a large number of different packet sizes as in
pathchar-like methods. A second order effect, the fact that
the efficiency of peak detection may depend on packet size, will
be discussed below.
The delay variation framework is inherently robust in that
the key assumption of probes arriving in different busy periods
can be verified by checking for the symmetry of the his-
togram. Although non-stationarity in the cross traffic will distort
the distribution, in practice it will remain approximately symmetric
unless a systematic change occurs over the course of the
measurement. A level shift for example in one of the cross traffic
streams, results in the received delay variation histogram being
the sum of two symmetric components, together with a non-symmetric
component consisting of just a single - i value.
B. ACCSIG - A new link bandwidth estimation method
In this section we apply the accumulation signature idea to the
TTL scenario of pathchar. Hence, as above, we assume that
well spaced probes are dropped after hop h ttl and that ICMP
messages are generated and sent back to the sender along some
backward path. Formally, we can consider these ICMP packets
as the original probes which have undergone a size change after
hop h ttl . One can then use equation (8) to write the round-trip
(sender-to-sender) delay variation as
h=k ttl
(w h
h=k ttl
(w h
where as before K is the number of hops on the backward route,
and k ttl is the hop where the ICMP packet enters the backward
route. As the ICMP packets share a common size, independently
of the size of the probe which triggered their generation, the
second component of the above equation becomes zero, leaving
an accumulation term generated by the alternating initial probe
sizes up to hop h ttl only, but noise terms corresponding to both
the forward and backward paths. By the same argument as in
section II-A, these noises should be symmetric, resulting in a
bimodal, symmetric delay variation histogram. The resulting
delay variation analogue of equation (7) is
where N i is the symmetric noise term. Here we are assuming
that the time to generate the ICMP packet is independent of the
probe size.
The estimation of link bandwidths is performed recursively,
similarly to pathchar and clink. A group of probes with a
fixed limited TTL is sent to measure
and the procedure
is repeated for steadily increasing TTL until the receiver
is reached. The  h are determined from the difference in the
estimates at consecutive steps.
To complete our description of ACCSIG the question of peak
detection in the - i histogram must be addressed. A number of
different methods could be applied to perform this task, including
kernel density estimation as suggested in [8], or using conditional
sample means or quantiles. Both here and throughout
this paper we used the following median related method which
we found to be more accurate than kernel estimation, and which
avoids the outlier sensitivity of moments.
As the probe sizes alternate, the (p i
has two possible values. Assume that p 1 < p 2 . Two subsets can
be defined depending on the parity of i:
Each of these is symmetric in its own right and corresponds
roughly to the parts of the histogram to either side of the origin.
The peaks are detected by taking the medians of these subsets.
The absolute values  + and  of the peak locations can also
Relative
error
upper
estimate
lower
Pathchar Clink Accsig Accsig* PQ1 PQ2 PQ3 PT1
Measurement method
Relative
error
upper
estimate
lower
(b) 22 Mbps
Fig. 3. Relative error of different methods over 1-hop segments. (a) Last (2 nd )
segment (10Mbps) of local route, (b) 6 th segment (22Mbps) of international
route.
be used to provide an informal interval estimate, in a similar
way to clink [3]. This is defined by the rate estimates corresponding
to the closest of the two over ttl 1 and ttl, and the
furthest.
The key advantage of the above approach is that, unlike
methods such as pathchar and variants which attempt to find
the minimum delay and in so doing discard the majority of the
delay values, the accumulation signature utilises the information
from all the probes that are received. This greatly reduces the
number of probes that need to be sent, especially in the case of
longer routes and higher link utilisations, as minimum detection
filtering requires the probes to arrive to empty queues at each
hop along the route.
C. Comparison with pathchar and clink
A full comparison of ACCSIG against pathchar and
clink is beyond the scope of this paper, as it would involve
covering many different route and traffic scenarios, as well as
tackling the issues of how to conduct a truly fair comparison
and how to measure accuracy appropriately. Instead we offer
a simple network based illustration of their comparative performance
for lightly loaded routes of short and medium length (be-
tween midnight and 6 a.m in both the the sender and receiver
timezones). Under these conditions we expect each method to
produce similar results. It is well known that under heavy traffic
conditions minimum delay detection is problematic and estimates
from pathchar and its variants typically suffer significant
errors [3], [1]. ACCSIG will perform better under these
circumstances due to the symmetry of the independence signa-
ture, which allows the detection of the delay variation peak positions
even if no probes traverse the path with minimum delay.
In effect, the nature of the noise is used to advantage.
The measurements were performed over a two and a twelve
segment route. The short route was on the local LAN and was
fully known, whereas the other was international (between the
University of Melbourne and the WAND group at the University
of Waikato in New Zealand) and only partially known. As be-
fore, by segment we mean a hop at the IP level, many of which
consist of multiple link layer hops, as indicated in table I.
As a rough measure of fairness we selected the number of
probes transmitted in the ACCSIG probe stream to be equal to
the number used by pathchar, which is roughly twice that
of clink under default settings. In addition, we produced
ACCSIG estimates with only the first quarter of the - i values
used (marked by Accsig  ), which corresponds to half the number
used by clink. Figure 3 shows the relative errors of the
link rate estimates produced by different methods on two selected
1-hop segments (the other methods will be introduced in
section III). Results over other 1-hop segments with low rate
are similar to those of figure 3b, the difference in estimates between
the three methods being usually within 10%. ACCSIG
performs better on the last hop of a route, such as in figure 3a,
as it does not rely on the generation the ICMP 'UDP port un-
reachable' packet, which incurs an additional latency, but uses
receiver timestamps instead. This however is not intrinsic to
ACCSIG, but a function of the current implementation.
-50%+50%
Bw.
Estimates
upper
estimate
lower
-50%+50%
Bw.
Estimates
upper
estimate
lower
-50%+50%
Number of probe pairs
Bw.
Estimates
upper
estimate
lower
segment #2
segment #6
segment #9
Fig. 4. Efficiency of ACCSIG. Link rate estimates as a function of the number of
probe pairs in the international route. (a) Segment #2 (2-hops), (b) Segment
#6 (1-hop) and (c) (suspected bottleneck), Segment #9 (suspected 2-hops).
The expected benefit of ACCSIG is its more efficient use of
the probes sent. To quantity this further, figure 4 plots a sequence
of estimates based on truncating the received delay variation
series from the international route to emulate shorter probe
streams. We see that the 'time' to convergence to the long term
estimates varies from as little as 10 probes, up to 200, depending
on the distance of the segment from the sender, and its link rate.
Larger distances increase the accumulated cross traffic noise, resulting
in slower convergence (compare charts 4a and 4b). How-
ever, segment #9 is further away yet convergence is faster than
at segment #6. This is due to the fact that the delay variation
increment induced by a hop is inversely proportional to its rate,
and segment #9 is the (suspected) bottleneck.
Because the assumption of probes arriving in different busy
periods is fundamental for the ACCSIG method, it is not possible
to obtain estimates more quickly by sending probes closely
spaced. It should be noted however that this assumption is of key
importance for pathchar and its variants as well: reducing the
time of the measurement while keeping the number of probes
constant has a negative impact on the accuracy of all one-packet
based methods. In the case of minimum filtering the reason for
this is particularly clear. Probes which closely follow each other
Relative
error
uncorrected est.
upper
estimate
lower
Relative
error
uncorrected est.
upper
estimate
lower
Pathchar Clink Accsig Accsig* PQ1 PQ2 PQ3 PT1
Measurement methods
Relative
error
uncorrected est.
upper
estimate
lower
(a) 100 Mbps
(c) 1.94 Mbps
Correction for invisible hops
Correction for invisible hops
Correction for invisible hops
Fig. 5. Relative error over multiple hop segments. (a) 1 st segment of local
route (2x100Mbps LAN), (b) 2 nd segment of international route (2x10Mbps
LAN), (c) 9 th segment of international route, measured as the bottleneck
(2x2Mbps).
will be likely to share busy periods with other probes in at least
one router in the route, and therefore will not be traversing the
system with minimal delay as required.
In figure 5, three further examples from the same experiments
are given for segments with multiple hops. Once again
pathchar, clink and ACCSIG give very similar estimates,
however they are half of the true link rate! One of the main contributions
of this paper is to point out that this is due to invisible
hops. We describe this problem in more detail in the next section
( II-D.1), and contribute to its resolution in section III.
D. Practical Issues
The measurement results reveal that all three methods sometimes
suffer significant errors even in the case of relatively low
bandwidth segments. This section describes a number of factors
which can significantly effect the accuracy of estimates.
Some are generic and shared by all three methods and even more
widely, others hold only for pathchar and clink.
D.1 Invisible hops
Unfortunately, in real networks not all switching elements test
and decrease the TTL value in the IP header, and therefore be-
come, for practical purposes, invisible to IP-TTL based probing
[15]. For example Ethernet and ATM switches, although store
and forward switching elements, are below the IP layer and do
not touch IP's TTL, as illustrated on figure (6). Some IP routers
are even configured to not decrease TTL.
As a result of this, TTL based measurement methods sometimes
give estimates corresponding to TTL 'segments', that is
sequences of hops between which the TTL does not change,
rather than individual hops. For example the bandwidth estimate
IP;1 from the first stage of clink, pathchar and ACC-
SIG for the route shown on figure (6) (which corresponds to the
Link level ("real")
path representation
path representation
IP,1 IP,2
level
SENDER RECEIVER
LAN Switch
Hop #3
Hop #2
Hop #1
IP Router
Packets with IP-TTL=1
dropped here
Fig. 6. Invisible hops: the lower view of the route shows all hops, the upper
only those that test and decrease IP's TTL.
three-hop two-segment local test route), will be: IP;1 =X
which, using ttl  1 to index segments, generalises to
where h ttl is the last hop before the pacesetter is dropped, and
by convention h
This effect is very likely to be responsible for the errors in
the estimates of figure (5). The original estimates are marked as
uncorrected, and show significant estimation errors. However
using our knowledge about the presence of invisible hops and
their effects, as detailed for example in equation (13) for ACC-
SIG, the estimates can be corrected. Unfortunately this correction
is impossible if the presence of invisible hops is unknown.
Packet quartet based methods, introduced in section III, provide
an efficient means of detection.
D.2 High bandwidth links
The estimates for high bandwidth links unfortunately are too
unreliable to support meaningful comparison. To understand
why this is the case for the delay variation and peak detection
underlying ACCSIG, consider that with probes of 1500 and 40
bytes, a 12sec error in the estimate of the increase in inter-
peak distance for two consecutive ttl values, corresponding to a
6sec error for a single peak, produces a 10% error in the estimate
of a 100Mbps link. The accuracy of the peak detection is
mainly a function of the number of probes used and the amount
of cross traffic noise entering via the waiting time components
of equation (9), which increase with ttl. Note that pathchar
and clink estimates are subject to time-stamping errors, ranging
from 10s of sec to 100s of ms, which can lead to similar
estimation errors.
D.3 Invasiveness
Pathchar and clink determine the sending times of
probes, by default, based on the round-trip times. This, as noted
in [8], can result in loads as high as 60% on a 10 Mbps LAN
with a round-trip delay of 1ms.
Especially on highly utilised network routes, this approach
can lead to probes joining the queues in the same busy period as
the previous probe. As such a probe by definition won't experience
minimum delay, the minimum filtering step of Pathchar
and clink either filters out these probes, in which case the
methods do not gather any information form these probes, or
they will lead to erroneous minimum delay estimates leading to
link rate estimation errors.
In the case of ACCSIG, by recursively applying Lindley's
equation (16), and using equation (8), it can be shown that the
delay variation for such a probe is
(w h
where s(i) is the last hop along the route where probe i shared a
busy period with probe i 1, and c s(i)
i is the aggregated service
time of the cross traffic entering that queue between probes
and i.
By comparing equations (8) and (14) it is clear that the accumulation
signature before hop s(i) is destroyed by this new
effect, so that if a significant number of probes experience it,
an erroneous link bandwidth estimate will result. This condition
can be detected however, as the definition of the peaks and
the symmetry of the histogram is lost, and estimates become er-
ratic. Our suggestion in this case it to send probes with increased
spacing. This is less invasive, and probably much more efficient,
than the traditional wisdom of simply transmitting more probes.
To limit invasiveness, in all the measurements in this paper the
probe streams (for ACCSIG and for the PQ methods) were dimensioned
to remain below 64kbps on average.
Increasing the spacing of probes will naturally decrease the
probability of them sharing busy periods, but, if the number of
probes remains the same the measurement time will increase
proportionally.
D.4 Lower layer packet headers
Packet pair like methods are based on estimates from the
service time of a single probe, whereas those underlying
pathchar,clink and ACCSIG are based on differences of
service times. Because of this the additional headers of link
layers can affect packet pair based estimates, as investigated
in detail in [11], but they leave unaffected the results of the
pathchar variant methods, where the packet size change cancels
out. Thus, different methods see different values, an important
point to understand regardless of whether one prefers to
measure the bandwidth as seen by IP or the link layer.
Non-linearities
Another practical problem can arise when the delay is non-linear
in packet size, as shown in [15]. Such non-linearities are
typically the result of lower layer effects, such as layer 2 frag-
mentation. If the network layer payload is fragmented, the resulting
additional lower layer header(s) decreases the effective
rate seen by the network layer. Another example could be a
minimum frame size at layer 2, as for example in the case of
Ethernet. In such cases the spread of different packet sizes used
by pathchar and clink can be an advantage. ACCSIG can
also use a large(er) number of different sized probes, at the possible
expense of an increase in peak detection errors.
D.6 Forwarding time
If the time needed to generate the ICMP message in response
to the UDP packet is not constant, for example if it has a component
depending on packet size, it can lead to erroneous band-width
estimates. This will not only effect the estimate of a given
hop, but will propagate as TTL is increased, as the link rates
are extracted using a sum over previous TTL values. This error
is large on the last hop for both pathchar and clink as
discussed above.
III. PACKET QUARTETS
The methods of the previous section rely on the accurate timing
of returning ICMP packets. The resulting reliance on appropriate
router behaviour, plus the additional noise of the return
path(s), are key drawbacks. One would prefer to exploit TTL's
ability to access hops individually along the route in some other
way. The tailgater method described by Lai and Baker in
[1] is one way of doing this. It is derived from a deterministic
model of packet delay and consists of two phases. First, by sending
isolated probes and using linear regression on the minimum
delay for each size,
1= h and
are estimated.
In the second phase pairs of packets are sent, each consisting of
two packets sent back-to-back: a packet of the smallest possible
size, the tailgater, follows the largest possible (non-fragmented)
packet with a limited TTL. The goal is to cause the tailgater to
queue directly behind the large packet at each hop until the TTL
expires, enabling the accumulated service time to be measured
from that hop on. The final bandwidth estimates are determined
using minima filtering for each TTL, combined with the components
measured in the first phase.
Pacesetter packet, with a limited TTL
Probe packet, delivered to the receiver
Sender Receiver
Fig. 7. Packet quartets: pacesetter packets have limited TTL, while the probes
reach the receiver.
Drawbacks of the tailgater method include those related
to minima filtering, and the need to perform two phases. To
address these and other issues we introduce packet quartets (PQ)
(see figures (7) and (8)) as a flexible probe pattern underlying a
new family of link bandwidth estimation methods.
A packet quartet is formed by grouping any two of a sequence
of packet pairs, each consisting of a probe packet closely following
a pacesetter packet, which has a limited TTL. The pairs,
similarly to the probes of the ACCSIG method, are sent sufficiently
separated to avoid joining queues during the same busy
period. Within pairs the opposite is true, the probe and the pace-
setter are designed to be in the same busy period at each hop.
Practical limitations to achieving this, and their consequences,
are discussed in the next paragraph. Apart from the pair spac-
ing, packet quartets have six parameters: the two probe sizes
the two pacesetter sizes p s;i 1 and p s;i , and the last
hops that the pacesetters traverse before dropping out: hops A
and B. In what follows we discuss a four packet pattern as in
figure 7. It should not be forgotten however that when i is incremented
the order of A and B reverse, negating the accumulation
terms to produce the other half of the symmetric histograms, as
before.
SENDER RECEIVER
Packet #3
Packet #2
Packet #4
Packet #1
Hop A Hop B
Fig. 8. Packet quartets: pacesetter packets #1 and #3 have limited TTL, while
probes, packets #2 and #4, reach the receiver.
Within a pair, the following effect is important to understand.
Assume that the probe and its pacesetter are back-to-back and
that the latter has just arrived at an empty queue on hop h. Because
of the store and forward router behaviour, the probe will
not enter the queue until after an interval x h 1
controlled by
the previous hop, whereas the pacesetter will leave the queue after
a time x h
controlled by hop h. Thus, as pointed out in [1],
the ability of the pacesetter to guarantee that the probe queues
behind it is bounded by the ratio of the probe and pacesetter service
times, which depends on the ratio of the link rates. Thus,
the ratio of the packet sizes is both a significant design issue and
a practical limit of the applicability of these methods to high
speed links. However, separation of the pair members does not
invalidate packet quartets for three reasons. First, as the delay
variation based model will make clear, it is not essential that
the probes and pacesetters be back-to-back, the fundamental requirement
is that they share the same busy period. Second, the
separation may only persist over a few hops. If the probe catches
up to its pacesetter's busy period then the pair will resume its
role from that point. Finally, it is not neccessary that all pairs
stay together, but only that enough do so to make the target signature
large enough to be detected.
A. A delay variation based model
We adopt the convention that probes are those packets we observe
and measure, as they arrive at the receiver. As in section II,
we focus on the delay variation of the probes, which are indexed
by i. As pacesetter packets are (typically) dropped before reaching
the receiver, they are not classified as probes. Instead, they
manifest as special components of the waiting times that probes
experience, characterised by a known duration and persistence
across hops.
From equation (8) it is obvious that - (j)
i , the delay variation
up to hop j, can be expressed as:
Lindley's equation connects the waiting times of successive
packets. With an infinite buffer, it states
If we assume that probe i will enter
hop h to join the same busy period as its pacesetter, the probe's
waiting time becomes:
where c h
s;i is the aggregate service time of cross traffic packets
which arrived at hop h between the arrival of the pacesetter at
the instant  h
s;i , and of the probe at  h
. Since by definition the
arrival time to hop h is the departure time from hop h 1, the
last component can be rewritten as:
for all h > 1. Here we are assuming that the probe and its
pacesetter also share the same busy period at hop i 1.
Recursively applying equations (15), (17) and (18), the delay
variation of the probes of a general packet quartet becomes:
A
A
(w h
(w h
(w h
s;i is the interarrival time of the pacesetters at the first
hop.
The properties of the packet quartet delay variation are qualitatively
different depending on which of the following scenarios
the TTL values lie:
where H is the number of hops. The case with
corresponds to probes only being sent from the sender, which
was discussed in section II. In each of these regions of the quartet
design space, new methods will be defined. Their properties
and limitations will be compared against each other as well as
the methods of section II.
IV. PACKET QUARTET LINK ESTIMATION METHODS
In this section 5 canonical estimation approaches, PQ1, PQ2,
PQ3, PT1 and PT2, arising out of packet quartets, will be described
and their main properties derived. Simulations are used
to illustrate these properties, but are not meant to test performance
under all conditions. Similarly, the network comparisons
provide a basis for discussion of the primary features of the
methods, and of important issues such as invisible hops, rather
than a full scale validation. A comparison against the tail-
gater method of [1] is not provided as an implementation was
not available (we expected it to be included in the nettimer
package, however its documentation states that it is not [16]).
A. PQ1 and
SENDER RECEIVER
Packet #3
Packet #2
Packet #4
Packet #1
Acc. Component Sender -> A
Acc. Component A->Receiver
Hop A
Fig. 9. Packet quartets with 0 <
This TTL scenario is illustrated in figure (9). For it
equation (19) reduces to:
A
A
(w h
(w h
There are two service time, or more specifically accumula-
tion, components in this equation. The first is an accumulation
signature due to the difference in the size of the pacesetters, and
as such it is created between hop #1 and A, after which the pace-
setters are dropped. The second is due to the difference in the
size of the probes, and is created from hop A to the receiver.
If both of these were active it would be difficult to determine
which term had contributed in what proportion to the resulting - i
value. Fortunately, they can be selectively eliminated by choosing
probes or pacesetters to be of equal size. This leads to two
more specialised probe patterns which form the basis of two new
bandwidth estimation methods.
We first define the methods, then compare them and investigate
their properties. For the remainder of this subsection we
collect the non service time components of equation (20) into
A.1 Method PQ1
Setting a constant, for each probe cancels the second
accumulation component, leaving the defining equation for
method PQ1:
A
Equations (21) and (10) differ only in their noise terms. As a
result, link bandwidth estimates of individual hops can be made
in exactly the same way as for ACCSIG.
A.2 Method PQ2
Setting constant for each pacesetter cancels the
first accumulation component, leaving the defining equation for
method PQ2:
Equations (21) and (22) are formally very similar, but the
methods defined by them have some very different properties.
A.3 PQ1 and PQ2 compared
The essential difference with PQ2 is that, to determine the
bandwidth of hop h ttl , the difference of delay variations from
stages h ttl and h ttl+1 must be taken, instead of from h ttl
and h ttl 1 as for PQ1, ACCSIG and the pathchar variant
methods.
As one important consequence of this, the link bandwidth estimates
of segments including invisible hops will be different for
the two methods. While the estimates from PQ1 will be formed
as described in equation (13) for ACCSIG, those from PQ2 will
obey
This effect is shown in figure (10), from which it is easily seen
Link level ("real")
path representation
path representation
IP,1 IP,2
level
SENDER RECEIVER
LAN Switch
Hop #3
Hop #2
Hop #1
IP Router
Packets with IP-TTL=1
dropped here
pathchar,clink,ACCSIG and PQ1 based estimate
PQ2 based estimate
Fig. 10. Invisible hops - PQ1 and PQ2 produce different hop bandwidth estimates
in the presence of an invisible hop
that the bandwidth of the last hop, hop 2, of the first segment,
can be measured. This is true more generally: the
last hop of segments containing invisible hops can be accessed.
In effect this exploits a kind of 'edge effect' arising from the
differences in the two equations.
The second important consequence regards the peak detection
accuracy needed. Recall that measuring the distance between
the symmetric peaks in the - i histogram is the basis of the accumulation
signature based estimate here just as for ACCSIG. In
PQ2 the peak detection is based on the difference in the probe
sizes. However this is necessarily small, since by the definition
of packet quartets, probes are significantly smaller than the
pacesetters, and this will also be true of their difference. As a result
the distance between the peaks for PQ2 will be significantly
smaller than that for PQ1 on the same hop, which makes PQ2
intrinsically less accurate than PQ1.
The third consequence again favors PQ1. Comparing
equation (20) to equation (9), we find the additional noise component
c A
describing the cross traffic arriving between
probes and their pacesetters. On heavily loaded hops this term
can significantly bias the estimates. Now for simplicity assume
stationary cross traffic on hop A and let the components of each
pair be back-to-back on leaving hop A 1. Since for PQ1 the
probe size is constant, the time period x A 1
i in which the cross
traffic may infiltrate between the probe and its pacesetter on hop
A is the same for all i. The cross traffic components will then be
statistically identical and tend to cancel each other. For PQ2 this
is not the case, as the probes sizes are different (in fact deliberately
as different as possible to minimise sensitivity to peak detection
errors). For PQ2 this additional asymmetric cross traffic
breaks the symmetry of the distributions of - causing
significant problems for median based peak detection. Other
peak detection methods should therefore be used under heavy
network load.
A.4 PQ1, PQ2 simulation results
Simulations results of a 6 hop route with both zero and moderate
cross traffic are shown in table II. The accuracy of PQ2
drops sharply in the presence of cross traffic, whereas PQ1 performs
extremely well in both cases.
Similar simulations of the same 6 hop route, but with two
hops made invisible, leaving 4 segments, is given in table III.
Just as for ACCSIG, the results for segments may not correspond
directly to the known link rates, but are predicted by the
'hop mixing' equations, equation (13) for PQ1 (and ACCSIG)
and equation (23) for PQ2. Of these, that of PQ1 is easier to
interpret. From table III (no CT) we see that for single hop segments
we recover the link rate, and for segments with two hops
of the same rate, the method recovers half of the rate. Although
less obvious, with no cross traffic PQ2 also gives values which
obey its respective mixing equation. Method PQ2 however performs
less well under cross traffic, as can be seen by comparing
the method's no CT and with CT columns of table III. Large
differences between PQ1 and PQ2 can be seen as evidence for
the presence of invisible hops.
A.5 PQ1, PQ2 measurement based comparisons
Results for selected segments of the 2 netork routes our new
methods are shown in figures 3 and 5.
The PQ1 based estimates are in good agreement with
pathchar, clink and ACCSIG results. The main difference
with PQ1 is that the number of noise components only depends
on the number of hops, rather than varying with TTL across
the different stages of the measurement. The aggregate noise
is therefore lower, roughly speaking, for the second half of the
route, due to the lack of backward path. This is a great advantage
on long routes. The above feature of PQ1 is shared by PQ2.
Another is that neither rely on receiving ICMP error messages,
which eliminates forwarding time errors entirely.
The cost of these advantages is a higher sensitivity to peak
detection errors. For example, the PQ1 measurements were performed
using 1500 and 730 byte pacesetter packets followed by
probes, and the PQ2 measurements employed 1500 byte
pacesetters followed by 40 and 100 byte probes. With these val-
ues, a given peak detection error would cause an estimation error
for PQ1 approximately twice as large as that for ACCSIG, and
this ratio increases to approximatly 20 for PQ2. PQ2's higher
sensitivity to peak detection errors is demonstrated by the first
hop estimate of the two hop route (fig. 5), which is off by 50%
from the 100Mbps expected from equation (23).
The PQ2 based estimates of the 1 st and 2 nd , and 8 th and 9 th
segments of the international route, by their inconsistency with
Nominal PQ1 PQ2 PQ3 PT1 PT2
link bandwidth no CT with CT no CT with CT no CT with CT no CT with CT no CT with CT
100 100 100 20:7 100 143 100 143 inf 0
1. 100Mbps 100 100 99.99 15.8 100 120 100 120 0.4 0
2. 10Mbps
4. 2Mbps 2
5. 2Mbps 2 2.02 2 3.08 2 2.00 2 1.98 2 0.24


II
SIMULATION BASED LINK BANDWIDTH ESTIMATES OF A 6 HOP ROUTE. FOR EACH METHOD: COLUMN #1 NO CROSS TRAFFIC, COLUMN #2 60% CROSS
TRAFFIC LOAD ON HOP #4, 30%ON THE OTHER HOPS.
PQ1 as discussed above, reveal the invisible hops we know (seg-
ments 1, 2) or expect (9) are there.
B.
SENDER RECEIVER
Packet #3
Packet #2
Packet #4
Packet #1
Hop A Hop B
Acc. Component Sender -> A
Edge Component A Edge Component B
Acc. Component B->Receiver
Acc. Component
Fig. 11. Packet quartets with 0 < A < B
This TTL scenario is illustrated in figure (11). Unlike the
case where A = B, here even when the probes sizes are chosen
and the pacesetter sizes also, p an accumulation
term remains, and the delay variation equation (19
reduces to:
where N A;B
denotes all the non service time terms. In the special
case of becomes the defining equation of
method PQ3:
With this method in effect a single hop has been isolated
through an edge effect. It is also different in that the histograms
have only a single peak if we set t . If we assume
that  A is known, and the noise term has symmetric char-
acteristics, then an estimate of the unique peak ^
- can be easily
obtained, leading to:
The link bandwidth of the first hop, the access link rate of the
sender, is usually known, allowing the remaining bandwidths to
be estimated recursively from equation (25) (if it is not known
it can be estimated by starting the measurement from A = 0,
which results in -
. Further discussion of the
cases is deferred until section IV-C). Note that the estimate
from one stage of the measurement is used to obtain the
estimate for the next, which can potentially lead to a magnification
of errors. This is not the case with the previously discussed
pathchar variants, nor with PQ1 and PQ2, as there the estimates
follow directly from the difference of the estimates of
only two measurement stages.
PQ3's estimates for segments with invisible hops will suffer
from estimation errors of a different nature to those seen so far,
as can be understood from setting
equation (24). From the difference of equations (24) and (25),
the bandwidth estimate in such a case, the hop mixing equation,
is seen to be: IP;h ttl
1+h ttl
which is similar to equation (13), and for sufficiently small p=p s
ratio, it would give the same results. For the packet sizes used
in our measurements, 1500 byte pacesetters and 40 byte probes,
this ratio is 0:026.
B.1 PQ3 simulation results
Returning to the 6 hop simulation comparison in table II, we
find that PQ3 performs similarly to PQ1, but with some positive
bias for large link rates. In the case of invisible hops in table III
it is again very consistent with PQ1 with no cross traffic, but has
more errors with it.
Nominal link bandwidth PQ1 PQ2 PQ3 PT1
(Segment details) no CT with CT no CT with CT no CT with CT no CT with CT
100 100 9:09 15:8 100 143 100 143
1. 100Mbps 100 100 9.09 10.5 100 120 100 120
100 100 9:09 7:8 100 103 100 103
5 5:06 1:67 1:83 5:07 5:18 5:07 5:09
2. 10Mbps 5 5.04 1.67 1.74 5.07 5.15 5.07 5.04
3. 2Mbps 1


III
SIMULATION BASED LINK BANDWIDTH ESTIMATES OF THE SAME 6 HOP ROUTE, 2 HOPS (2ND AND 4TH) MADE INVISIBLE. FOR EACH METHOD: COLUMN
#1 NO CROSS TRAFFIC, COLUMN #2 60% CROSS TRAFFIC LOAD ON HOP #3, ELSE 30%.
B.2 PQ3 measurement based comparison
Returning to figures 3 and 5, we find that, again, the estimates
are in good agreement with pathchar, clink and ACCSIG
results for link bandwidths up to approximately 30Mbps, however
the differences seem to be slightly larger than in the case of
PQ1.
The differences could be caused by the somewhat different
estimation of invisible segments, as well as by the fact that estimates
from equation (25) are affected by lower layer packet
headers in a similar way to packet pair based estimates, as discussed
in section II-D.4.
PQ3's sensitivity to peak detection errors is similar to that of
ACCSIG, which is an advantage over PQ1. Another advantage
is that due to the fixed and equal probe sizes, and pacesetter
sizes, the achievable pacesetter/probe ratio is higher than that of
PQ1 and PQ2, allowing the measurement of a wider spectrum
of hop bandwidths. However, the possible magnification of estimation
errors is an important disadvantage of this method.
C. PT1 and
The special case of packet quartets with
to only one pacesetter packet being sent out from the sender,
as illustrated in figure (12), in effect reducing the quartets to
triplets.
SENDER RECEIVER
Packet #3
Packet #2
Packet #4
Packet #1
Acc. Component B+1->Receiver
Acc. Component Sender -> B
Edge Component B
Fig. 12. Packet quartets with
As before, packet sizes can be selected to cause the cancellation
of the accumulation terms. However it is impossible to
cancel both terms simultaneously, unless the probes and their
pacesetters have the same size, which is incompatible with the
latter's aim of causng the probes to queue, of controlling their
pace. Hence, two methods, corresponding to the cancellation of
only one accumulation term at a time, will be defined.
Setting for each probe cancels the second accumulation
component, leaving the defining equation for method PT1:
The properties of this method are very similar to those of PQ3.
The link bandwidths in this case can be estimated from the estimate
of the unique delay variation peak ^
as:
where again we have set t . The comment
regarding the potential accumulation of errors in the case of
method PQ3 is also valid here, and the effect of invisible hops on
PT1's bandwidth estimates, equation (27), is exactly the same.
Note, that PT1 holds a similar relation to the tailgater
method as ACCSIG does to pathchar and clink. As a con-
sequence, most of the causes of error in PT1's estimates are
shared with tailgater. The most important differences between
the two are the result of the delay variation foundation of
replacing delay: there is no need for two different probing
phases, nor for minimum filtering or linear regression.
C.2 Method PT2
Setting constant for each pacesetter results
in the cancellation of the first accumulation component, leaving
the defining equation for method PT2:
Unfortunately, as the result of increased sensitivity to the peak
detection errors and the propagation of these errors, this method
is useless in practice as we now show. For completeness we
include here the hop mixing equation, which is similar but different
to equation (23): IP;h ttl
1+h ttl+1
C.3 PT1, PT2 simulation results
We return a final time to the 6 hop simulation comparison
in table II. The striking result is that even with no cross traf-
fic, PT2's sensitivity and error propagation causes its estimates
to deteriorate rapidly. The initial peak detection error in this
case has its origin in the limited resolution of the simulation
timestamps, which was chosen to be equivalent to the 2
resolution of the timestamp representation of our measurement
infrastructure. This tiny error becomes exponentially amplified.
In constrast, the results of PT1 are generally very good, and very
consistent with PQ3 as expected. The same is true for the invisible
hop results of table III for PT1.
C.4 PT1 measurement results
We only present measurement results in the case of PT1, as
performs so poorly. Again, from figures 3 and 5 we find that
the estimates are very similar to those of PQ3. The comments
regarding the effect of the link layer headers, the sensitivity to
peak detection errors, and the propagation of errors, also hold.
Note that PT1, in conjunction with other methods, has the
potential to detect invisible hops. Let us assume the knowledge
of the
1= h of the ttl segments, for example using PQ1. In
this case, x B
remains the only unknown of equation (28), which
corresponds to the service time of the probes on the last hop
of the route segment containing an invisible hop or hops, ie.,
the service time of an invisible hop. However, the sensitivity to
peak detection errors becomes similar to that of PQ2, although
the propagation of the errors won't affect the estimates of  B for
fixed. However, the fact that PT1's estimate can potentially
suffer from the link layer header error, means that PQ2 seems
a more efficient tool for detecting the invisible hop anatomy of
segments.
V. INVESTIGATING THE BOTTLENECK
Based on the properties discussed above of PQ1 and PQ2
in estimating segments with invisible hops (see equations (13)
and (23)) and the results for segments 8 to 10 of the international
route (PQ1: [10:1; 0:98; 22:2] Mbps, and PQ2: [2:13; 1:9; 27:4]
Mbps), we concluded that the ninth hop consists of two
2Mbps hops. This conclusion is supported by independent measurements
made using the fundamentally different packet-pair
based methods [11].
VI. CONCLUSIONS
A variety of link bandwidth measurement methods were presented
that exploit the ability of the IP-TTL field to target hops
within a route to enable measurements over multiple links. The
approach is novel in its use of delay variation, and histogram
based peak detection using medians, rather than delay series and
filtering on minima. The information of each probe packet is
used, resulting in greater efficiency, that is using less probes for
fixed accuracy. The first new method presented, ACCSIG, uses
returning ICMP messages like pathchar and clink, and
gives similar results, but is more efficient. ICMP based methods
however suffer from greater noise due to a longer round-trip
path, and router dependent processing delays. To avoid these,
packet quartets were introduced: a 6 parameter probe stream
class incorporating pairs consisting of probes trapped behind
larger pacesetter packets with limited TTL values. From this
class, 5 new measurement methods were defined: PQ1, PQ2,
PQ3, PT1 and PT2, their main characteristics analysed, and their
performance illustrated and evaluated with simulation and accurate
network measurements over two routes. One of these, PT1,
is closely related in terms of TTL use to the existing tail-
gater method, but with the advantages of being delay variation
based.
The properties of the new methods are summarized in table VI
with respect to several metrics of practical importance, which
were described in detail. Rows 1-4 give rankings, where
best.
We analysed in detail the consequences of invisible hops: the
fact that TTL detects IP hops or segments, which often consist of
multiple link layer hops. The methods were shown to fall into 2
fundamental categories depending on their behaviour over seg-
ments. The first group includes Pathchar (and its variants),
ACCSIG, PQ1, PQ3 and PT1, while PQ2 and PT2 belong to the
second group. Invisible hops can be detected by comparing the
results from a member of each group. The last invisible hop in
the segment can be accessed by cancelling terms between the
methods, for example by combining results from PQ1 and PQ2.
Each group can be divided further into two sub-categories, defined
by their hop mixing equations, summarised in table VI.
In summary, method PQ1 is the best overall, offering accurate
estimates with few probes and low noise. ACCSIG is also
efficient and accurate. PQ2 can also be useful but is less ac-
curate, whereas PQ3 is considerably less accurate. PT1 is very
similar to PQ3 but even less accurate. Finally PT2 is very sensitive
and magnifies errors, and is useless in most situations.
Performance Metric ACCSIG PQ1 PQ2 PQ3 PT1 PT2
Sensitivity to peak 2 3
detection errors (1-4)
Sensitivity to lower
layer headers (1-3)
propagation
Sensitivity to
forwarding errors (1-2)
Mixing equation


IV
COMPARISON OF NEW METHODS.
Further work is needed to fully characterise and compare the
methods' performance under a variety of traffic conditions and
parameter settings. In addition, methods to automatically detect
invisible hops and to fully resolve them are the subject of
ongoing work.



--R

"Measuring link bandwidths using a deterministic model of packet delay,"
"What do packet dispersion techniques measure?,"
"Using pathchar to estimate internet link characteristics,"
"Congestion avoidance and control,"
"Characterizing end-to-end packet delay and loss in the inter- net,"
"Measuring bottleneck link speed in packet-switched networks,"
"End-to-end internet packet dynamics,"
"Measuring bandwidth,"
"Multifractal cross-traffic estimation,"
"End-to-End Available Band- Measurement Methodology, Dynamics, and Relation with TCP Throughput,"
"The packet size dependence of packet-pair like methods,"
"On the scope of end-to-end probing methods,"
"A precision infrastructure for active probing,"
"PC based precision timing without GPS,"
"patchar - a tool to infer characteristics of internet paths,"
"Nettimer: A tool for measuring bottleneck link bandwidth,"
--TR
Congestion avoidance and control
Measuring bottleneck link speed in packet-switched networks
End-to-end Internet packet dynamics
Using pathchar to estimate Internet link characteristics
Measuring link bandwidths using a deterministic model of packet delay
PC based precision timing without GPS
End-to-end available bandwidth

--CTR
A. Novak , P. Taylor , D. Veitch, The distribution of the number of arrivals in a subinterval of a busy period of a single server queue, Queueing Systems: Theory and Applications, v.53 n.3, p.105-114, July      2006
Guojun Jin , Brian L. Tierney, System capability effects on algorithms for network bandwidth measurement, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA
Matthew Luckie , Tony McGregor, Path diagnosis with IPMP, Proceedings of the ACM SIGCOMM workshop on Network troubleshooting: research, theory and operations practice meet malfunctioning reality, September 03-03, 2004, Portland, Oregon, USA
Sridhar Machiraju , Darryl Veitch , Franois Baccelli , Jean Bolot, Adding definition to active probing, ACM SIGCOMM Computer Communication Review, v.37 n.2, April 2007
Constantinos Dovrolis , Parameswaran Ramanathan , David Moore, Packet-dispersion techniques and a capacity-estimation methodology, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.963-977, December 2004
Sridhar Machiraju , Darryl Veitch, A measurement-friendly network (MFN) architecture, Proceedings of the 2006 SIGCOMM workshop on Internet network management, p.53-58, September 11-15, 2006, Pisa, Italy

Neil Spring , David Wetherall , Thomas Anderson, Reverse engineering the Internet, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004
Mahajan , Neil Spring , David Wetherall , Thomas Anderson, User-level internet path diagnosis, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
active probing;cross-traffic;delay variation;bottleneck bandwidth;TTL;internet measurement