Multicast-based inference of network-internal delay distributions.
Packet delay greatly influences the overall performance of network applications. It is therefore important to identify causes and locations of delay performance degradation within a network. Existing techniques, largely based on end-to-end delay measurements of unicast traffic, are well suited to monitor and characterize the behavior of particular end-to-end paths. Within these approaches, however, it is not clear how to apportion the variable component of end-to-end delay as queueing delay at each link along a path. Moreover, there are issues of scalability for large networks.In this paper, we show how end-to-end measurements of multicast traffic can be used to infer the packet delay distribution and utilization on each link of a logical multicast tree. The idea, recently introduced in [3] and [4], is to exploit the inherent correlation between multicast observations to infer performance of paths between branch points in a tree spanning a multicast source and its receivers. The method does not depend on cooperation from intervening network elements; because of the bandwidth efficiency of multicast traffic, it is suitable for large-scale measurements of both end-to-end and internal network dynamics. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the estimator through simulation and observe that it is robust with respect to moderate violations of the underlying model.
Introduction
Background and Motivation. Monitoring the performance of large communications networks
is essential for diagnosing the causes of performance degradation. There are two broad approaches
to monitoring. In the internal approach, direct measurements are made at or between network
elements, e.g. of packet loss or delay. In the external approach, measurements are made across a
network on end-to-end or edge-to-edge paths.
The internal approach has a number of potential limitations. Due to the commercial sensitivity
of performance measurements, and the potential load incurred by the measurement process, it is
expected that measurement access to network elements will be limited to service providers and,
possibly, selected peers and users. The internal approach assumes sufficient coverage, i.e. that
measurements can be performed at all relevant elements on paths of interest. In practice, not all
elements may possess the required functionality, or it may be disabled at heavily utilized elements
in order reduce CPU load. On the other hand, arranging for complete coverage of larger networks
raises issues of scale, both in the in the gathering of measurement data, and joining data collected
from a large number of elements in order to form a composite view of end-to-end performance.
This motivates external approaches, network diagnosis through end-to-end measurements, without
necessarily assuming the cooperation of network elements on the path. There has been much
recent experimental work to understand the phenomenology of end-to-end performance (e.g., see
[3, 9, 19, 26, 27, 29]). Several research efforts are working on the developments of measurement
infrastructure projects (Felix [13], IPMA [15], NIMI [18] and Surveyor [35]) with the aim to collect
and analyze end-to-end measurements across a mesh of paths between a number of hosts.
Standard diagnostic tools for IP networks, ping and traceroute report roundtrip loss and de-
lay, the latter incrementally along the IP path by manipulating the time-to-live (TTL) field of probe
packets. A recent refinement of this approach, pathchar [17], estimates hop-by-hop link capac-
ities, packet delay and loss rates. pathchar is still under evaluation; initial experience indicates
many packets are required for inference leading to either high load of measurement traffic or long
measurement intervals, although adaptive approaches can reduce this [10]. More broadly, measurement
approaches based on TTL expiry require the cooperation of network elements in returning
Internet Control Message Protocol (ICMP) messages. Finally, the success of active measurement
approaches to performance diagnosis may itself cause increased congestion if intensive probing
techniques are widely adopted.
In response to some of these concerns, a multicast-based approach to active measurement has
been proposed recently in [4, 5]. The idea behind the approach is that correlation in performance
seen on intersecting end-to-end paths can be used to draw inferences about the performance characteristics
of the common portion (the intersection) of the paths, without the cooperation of network
elements on the path. Multicast traffic is particular well suited for this since a given packet only
occurs once on a given link in the (logical) multicast tree. Thus characteristics such as loss and
end-to-end delay of a given multicast packet as seen at different endpoints are highly correlated.
Another advantage of using multicast traffic is scalability. Suppose packets are exchanged on a
mesh of paths between a collection of N measurement hosts stationed in a network. If the packets
are unicast, then the load on the network may grow proportionally to N 2 in some parts of the
network, depending on the topology. For multicast traffic the load grows proportionally only to N .
Contribution The work of [4, 5] showed how multicast end-to-to measurements can be used to
per link loss rates in a logical multicast tree. In this paper we extend this approach to infer the
probability distribution of the per link variable delay. Thus we are not concerned with propagation
delay on a link, but rather the distribution of the additional variable delay that is attributable to
either queuing in buffers or other processing in the router. A key part of the method is an analysis
that relates the probabilities of certain events visible from end-to-end measurements (end-to-end
delays) to the events of interest in the interior of the network (per-link delays). Once this relation
is known, we can estimate the delay distribution on each link from the measured distributions of
end-to-end delays of multicast packets.
For a glimpse of how the relations between end-to-end delay and per link delays could be
found, consider a multicast tree spanning a source of multicast probes (identified as the root of the
tree) and a set of receivers (one at each leaf of the tree). We assume the packets are potentially
subject to queuing delay and even loss at each link. Focus on a particular node k in the interior of
the tree. If, for a given packet, the source-to-leaf delay does not exceed a given value on any leaf
descended from k, then clearly the delay from the root to the node k was less than that value. The
stated desired relation between the distributions of per-link and source-to-leaf delays is obtained
by a careful enumeration of the different ways in which end-to-end delay can be split between the
portion of the path above or below the node in question, together with the assumption that per-link
delays are independent between different links and packets. We shall comment later upon the
robustness of our method to violation of this independence assumption.
We model link delay by non-parametric discrete distributions. The choice of non parametric
distributions rather than a parameterized delay model is dictated by the lack of knowledge of
the distribution of link delays in networks. While there is significant prior work on the analysis
and characterization of end-to-end delay behavior (see [2, 24, 27]), to the best of our knowledge
there is no general model for per link delays. The use of a non-parametric model provides the
flexibility to capture broadly different delay distributions, albeit at the cost of increasing the number
of quantities to estimate (i.e. the weights in the discrete distribution). Indeed, we believe that our
inference technique can shed light on the behavior and dynamics of per link delays and so provide
useful results for the analysis and modeling; this we will consider in future work.
The discrete distribution can be a regarded as binned or discretized version of the (possibly
continuous) true delay distribution. Use of a discrete rather than a continuous distribution allows
us to perform the calculations for inference using only algebra. Formally, there is no difficulty in
formulating a continuous version of the inference algorithm. However, it proceeds via inversion
of Laplace transforms, a procedure that is in practice implemented numerically. In the discrete
approach we can explicitly trade-off the detail of the distribution with the cost of calculation; the
cost is inversely proportional to the bin widths of the discrete distribution.
The principle results of the analysis are as follows. Based on the independent delay model,
we derive an algorithm to estimate the per link discrete delay distributions and utilization from the
measured end-to-end delay distributions. We investigate the statistical properties of the estimator,
and show it to be strongly consistent, i.e., it converges to the true distribution as the number of
probes grows to infinity. We show that the estimator is asymptotically normal; this allows us to
compute the rate of convergence of the estimator to its true value, and to construct confidence
intervals for the estimated distribution for a given number of probes. This is important because the
presence of large scale routing fluctuation (e.g. as seen in the Internet; see [26]) sets a timescale
within which measurement must be completed, and hence the accuracy that can be obtained when
sending probes at a given rate.
We evaluated our approach through extensive simulation in two different settings. The first set
used a model simulation in which packet delays obey the independence assumption of the model.
We applied the inference algorithm to the end-to-end delays generated in the simulation and compared
the (true) model delay distribution. We verified the convergence to the model distribution,
and also the rate of convergence, as the number of probes increased.
In the second set of experiments we conducted an ns simulation of packets on a multicast tree.
Packet delays and losses were entirely due to queueing and packet discard mechanisms, rather than
model driven. The bulk of the traffic in the simulations was background traffic due to TCP and
UDP traffic sources; we compared the actual and predicted delay distributions for the probe traffic.
Here we found rapid convergence, although with some persistent differences with respect to the
actual distributions.
These differences appear to be caused by violation of the model due to the presence of spatial
dependence (i.e., dependence between delays on different links). In our simulations we find
that when this type of dependence occurs, it is usually between the delays on child and parent
links. However, it can extend to entire paths. As far as we know there are no experimental results
concerning the magnitude of such dependence in real networks. In any case, by explicitly introducing
spatial correlations into the model simulations, we were able to show that small violations
of the independence assumption lead to only small inaccuracies of the estimated distribution. This
continuity property of the deformation in inference due to correlations is also to be expected on
theoretical grounds.
We also verified the presence of temporal dependence, i.e., dependence between the delays
between successive probes on the same link. This is to be expected from the phenomenology of
queueing: when a node is idle, many consecutive probes can experience constant delay; during
congestion, probes can experience the same delay if their interarrival time is smaller than the congestion
timescale. This poses no difficulty as all that is required for consistency of the estimator is
ergodicity of the delay process, a far weaker assumption than independence. However, dependence
can decrease the rate of convergence of the estimators. In our experiments, inferred values closely
tracked the actual ones despite the presence of temporal dependence.
Implementation Requirements Since the data for delay inference comprises one-way packet
delays, the primary requirement is the deployment of measurement hosts with synchronized clocks.
Global Positioning System (GPS) systems afford one way to achieve a synchronization to within
tenths of microseconds; it is currently used or planned in several of the measurement infrastructures
mentioned earlier. More widely deployed is the Network Time Protocol (NTP) [20]. However, this
provides accuracy only on the order of milliseconds at best, a resolution at least as coarse as the
queueing delays in practice. An alternative approach that could supplement delay measurement
from unsynchronized or coarsely synchronized clocks has been developed in [28, 30, 21]. These
authors propose algorithms to detect clock adjustments and rate mismatches and to calibrate the
delay measurements.
Another requirement is knowledge of the multicast topology. There is a multicast-based measurement
tool, mtrace [23], already in use in the Internet. mtrace reports the route from a
multicast source to a receiver, along with other information about that path such as per-hop loss
and rate. Presently it does not support delay measurements. A potential drawback for larger
topologies is that mtrace does not scale to large numbers of receivers as it needs to run once for
each receiver to cover the entire multicast tree. In addition, mtrace relies on multicast routers
responding to explicit measurement queries; a feature that can be administratively disabled. An
alternative approach that is closely related to the work on multicast-based loss inference [4, 5] is to
infer the logical multicast topology directly from measured probe statistics; see [31] and [7]. This
method does not require cooperation from the network.
Structure of the Paper. The remaining sections of the paper are organized as follows. In Section
2 we describe the delay model and in Section 3 we derive the delay estimator. In Section 4 we
describe the algorithm used to compute the estimator from data. In Section 5 we present the model
and network simulations used to evaluate our approach. Section 6 concludes the paper.
Model & Framework
2.1 Description of the Logical Multicast Tree
We identify the physical multicast tree as comprising actual network elements (the nodes) and the
communication links than join them. The logical multicast tree comprises the branch points of the
physical tree, and the logical links between them. The logical links comprise one or more physical
links. Thus each node in the logical tree, except for the leaf nodes and possibly the root, must
have 2 or more children. We can construct the logical tree from the physical tree by deleting all
links with one child (except for the root) and adjusting the links accordingly by directly joining its
parent and child.
denote the logical multicast tree, consisting of the set of nodes V , including
the source and receivers, and the set of links L, which are ordered pairs (j; of nodes, indicating
a link from j to k. We will denote f0g. The set of children of node j is denoted by
these are the nodes whose parent is j. Nodes are said to be siblings if they have the same
parent. For each node j, other than the root 0, there is a unique node f(j), the parent of j, such
that (f(j); Each link can therefore be also identified by its "child" endpoint. We shall
define f n (k) recursively by f n We say that j is a descendant of
the corresponding partial order in V as j OE k.
For each node j we define its level '(j) to be the non-negative integer such that f '(j)
root represents the source of the probes and the set of leaf nodes R ae V (i.e., those with no
children) represents the receivers.
2.2 Modeling Delay and Loss of Probe Packets
Probe packets are sent down the tree from the root node 0. Each probe that arrives at node k results
in a copy being sent to every child of k. We associate with each node k a random variable D k taking
values in the extended positive real line R+ [ f1g. By convention D is the random
delay that would be encountered by a packet attempting to traverse the link (f(k); L. The
value indicates that the packet is lost on the link. We assume that the D k are independent.
The delay experienced on the path from the root 0 to a node k is Y
. Note that Y
i.e. if the packet was lost on some link between node 0 and k.
Unless otherwise stated, we will discretize each link delay D k to a set f0; q;
Here q is the bin width, is the number of bins, and the point 1 is interpreted as "packet
lost" or "encountered delay greater than i max q". The distribution of D k is denoted by ff k , where
the probability that D 1. For each link, we denote u k the
link utilization; then, u (0), the probability that a packet experience delay or it is lost in
traversing link k.
For each k 2 V , the cumulative delay process Y k , k 2 V , takes values in f0; q;
i.e., it supports addition in the ranges of the constituent D j . We set A k
A k (1) the probability that Y 1. Because of delay independence, for finite i, A k
by convention A 0
We consider only canonical delay trees. A delay tree consists of the pair (T ; ff),
delay tree is said to be canonical if ff k (0) ? 0, 8k 2 U , i.e., if there
is a non-zero probability that a probe experiences no delay in traversing each link.
3 Delay Distribution Estimator and its Properties
Consider an experiment in which n probes are sent from the source node down the multicast tree.
As result of the experiment we collect the set of source-to-leaf delays (Y k;l ) k2R;l=1;:::;n . Our goal is
to infer the internal delay characteristics solely from the collected end-to-end measurements.
In this section we state the main analytic results on which inference is based. In Section 3.1
we establish the key property underpinning our delay distribution estimator, namely the one-to-
one correspondence between the link delay distributions and the probabilities of a well defined set
of observable events. Applying this correspondence to measured leaf delays allows us to obtain
an estimate of the link delay distribution. We show that the estimator is strongly consistent and
asymptotically normal. In Section 3.2 we present the proof of the main result which also provides
the construction of the algorithm to compute the estimator we present in Section 4. In Section 3.4
we analyze the rate of convergence of the estimator as the number of probes increase.
3.1 The Delay Distribution Estimator
denote the subtree rooted at node k and
of receivers which descend from k.
denote the event fmin j2R(k) Y j  iqg that the
end-to-end delay is no greater than iq for at least least one receiver in R(k) . Let fl k
P[\Omega k (i)] denote its probability. Finally let \Gamma denote the mapping associating the link distributions
k2U;i2f0;:::;imaxg to the probabilities of the
. The
proof of the next result is given in the following section.
Theorem 1 Let
\Gamma(ff)g. \Gamma is a bijection from A to G which is
continuously differentiable and has a continuously differentiable inverse.
Estimate fl by the empirical probabilities bfl , where
denotes the indicator function of the set S and ( b
are the subsidiary quantities
Our estimate of ff k (i) is b
(i). We estimate link k utilization by b
Let A
denote the open
interior of A. The following holds:
Theorem 2 When
almost surely to ff, i.e., the
estimator is strongly consistent.
is continuous on \Gamma(A (1) ) and A (1) is open in A, it follows that \Gamma(A (1) ) is an
open set in \Gamma(A). By the Strong Law of large numbers, since bfl is the mean of n independent
random variables, bfl converges to fl almost surely for n !1. Therefore, when
exists n 0 such that bfl 2 \Gamma(A (1) Then, the continuity of \Gamma \Gamma1 insures that b
ff converges
almost surely to ff as n !1.
3.2 Proof of Theorem 1
To prove the Theorem, we first express fl as function of ff and then show that the mapping from A
to G is injective.
3.2.1 Relating fl to ff
Denote obeys the recursion
Then, by observing that
readily obtain
The set of equations (5) completely identifies the mapping \Gamma from A to G. The mapping is clearly
continuously differentiable. Observe that the above expressions can be regarded as a generalization
of those derived for the loss estimator in [4] (by identifying the event no delay with the event no
loss).
3.2.2 Relating ff to fl
It remains to show that the mapping from A to G is injective. To this end, below we derive an
algorithm for inverting (5). We postpone to Appendix A the proof that the inverse is unique and
continuously differentiable. For sake of clarity we separate the algorithm into two parts: in the first
we derive the cumulative delay distributions A from fl; then, we deconvolve A to obtain ff.
Computing A
Step 0:
Solve (5) for amounts solving the equation
Y
and
This equation is formally identical to the one of the loss estimator [4]. From [4], we have that the
solution of (6) exists and is unique in (0; 1) provided that
which holds
for canonical delay trees. We then compute fi k
Step i:
Given A k (j) and fi k (j), k 2 U , 1, in this step we compute A k (i) and fi k (i),
. For k 2 U n R, in expression (5) we replace fi d (i) with fl d (i)\Gamma
A k (0)
(from (4)) and obtain the following equation
ae Q
A k (0)
oe
(the unknown term A k (i) is highlighted in boldface). This is a polynomial in A k (i) of degree
#d(k). As shown in Appendix A we consider the second largest solution of (8).
For directly compute A k (i) from (5), A k
(j). Then we
compute
A f(k) (0)
Computing ff
Once step i max is completed, we compute ff k (i), k 2 U as follows
A k (0)
A
A k (i)\Gamma
A
3.3 Example: the Two-leaf Tree
In this section we illustrate the application of the results of Section 3.1 to the two-leaf tree of

Figure

1. We assume that on each link, a probe either suffers no delay, a unit amount of delay, or
is otherwise lost; for k 2 f1; 2; 3g, therefore, delay takes values in f0; 1; 1g.
For this example, equations (6) and (8) can be solved explicitly; combined with (9) we obtain
Figure

1: TWO-LEAF MULTICAST TREE.0752

Figure

2: FOUR-LEAF MULTICAST TREE.
the estimates
3.4 Rates of Convergences of the Delay Distribution Estimator
3.4.1 Asymptotic Behavior of the Delay Distribution Estimator
In this section, we study the rate of convergence of the estimator. Theorem 2 states that b
ff converges
to ff with probability 1 as n grows to infinity; but it provides no information on the rate of
convergence. Because of the mild conditions satisfied by \Gamma \Gamma1 , we can use Central Limit Theorem
to establish the following asymptotic result
Theorem 3 When
converges in distribution to a multivariate
normal random variable with mean vector 0 and covariance matrix
denotes the transpose.
Proof: By the Central Limit Theorem, it follows that the random variables bfl are asymptotically
Gaussian as n !1 with
Here D denotes convergence in distribution. Following the same lines of the proof of Theorem
continuously differentiable on G, the Delta method (see Chapter 7 of [34]) yields that b
is also asymptotically Gaussian as n !1:
Theorem 3 allows us to compute confidence intervals of the estimates, and therefore their
accuracy and their convergence rate to the true values as n grows. This is relevant in assessing:
(i) the number of probes required to obtain a desired level of accuracy of the estimate; (ii) the
likely accuracy of the estimator from actual measurements by associating confidence intervals to
the estimates.
For large n, the estimator b
ff k (i) will lie in the interval
r  (k;i)(k;i)
where z ffi=2 is the quantile of the standard distribution and the interval estimate is a 100(1 \Gamma
ffi)% confidence interval.
To obtain the confidence interval for b
ff derived from measured data from n probes, we estimate
by b
and D(bff) is the Jacobian of the inverse computed for
ff. We then use confidence
intervals of the form
3.4.2 Dependence of the Delay Distribution Estimator on Topology
The estimator variance determines the number of probes required to obtain a given level of ac-
curacy. Therefore, it is important to understand how the variance is affected by the underlying
a
(a)0.20.61
a
(b)

Figure

3: ASYMPTOTIC ESTIMATOR VARIANCE AND TREE DEPTH. Binary tree with depth 2, 3
and 4. Left: Minimum and Maximum Variance of the estimates b ff k (0) (a) and b ff k (1) (b) over all
links.
parameters, namely the delay distributions and the multicast tree topology. The following Theo-
rem, the proof of which we postpone to Appendix C, characterizes the behavior of the variance for
small delays. Set k ff
Theorem 4 As k ff k ! 0,
Theorem 4 states that the estimator variance is, to first order, independent of the topology. To
explore higher order dependencies, we computed the asymptotic variance for a selection of trees
with different depths and branching ratio. We use the notation T (r to denote a tree of
apart from node 0 that has one descendent, nodes at level j have exactly
children. For simplicity, we consider the case when link delay takes values in f0; 1g, i.e., we
consider no loss, and study the behavior as function of ff k
In

Figure

3 we show the dependence on tree depth for binary trees of depth 2, 3 and 4. We plot
the maximum value of the variance over the links max k Var(bff k (0)) (a) and max k Var(bff k (1)) (b).
In these examples, the variance increases with the tree depth. In Figure 4 we show the dependence
Variance
a
(a)0.20.61
Variance
a
(b)

Figure

4: ASYMPTOTIC ESTIMATOR VARIANCE AND BRANCHING RATIO. Binary tree with
depth 2 and 2, 4 or 6 receivers. Left: Variance of b ff k (0) (a) and b
ff k (1) (b) for link 1 (common link)
and 2 (generic receiver).
on branching ratio for a tree of level 2. We plot the estimator variance for both link 1 (the common
link) and link 2 (a generic receiver). In these examples, increasing the branching ratio decreases
the variances, especially those of the common link estimates which increases less than linearly for
ff up to 0.7 when the branching ratio is larger than 3. In all cases, the variance of b
ff k (1) is larger
than b
In all cases, as predicted by Theorem 4, the estimator variance is asymptotically linear in ff
independently of the topology as ff ! 0. As ff increases, the behavior is affected by different
factors: increasing the branch ratio results in a reduction of the variance, while increasing the tree
depth results in variance increase. The first can be explained in terms of the increased number of
measurements available for the estimation as the number of receivers sharing a given link increases;
the second appears to be the effect of cumulative errors that accrue as the number of links along a
path increases (ff is computed iteratively on the tree). We also observe that the variance increases
with the delay lag; this appears to be caused by the iterative computation on the number of bins
that progressively cumulate errors.
4 Computation of the Delay Distribution Estimator
In this section we describe an algorithm for computing the delay distribution estimate from measurements
based on the results presented in the previous section. We also discuss its suitability for
distributed implementation and how to adapt the computation to handle different bin sizes.
We assume the experimental data of source-to-leaf delays (Y k;m ) k2R;m=1;:::n from n probes, as
collected at the leaf nodes k 2 R. Two steps must be initially performed to render the data into a
form suitable for the inference algorithms: (i) removal of fixed delays and (ii) choosing a bin size
q and computing the estimate bfl .
The first step is necessary since it is generally not possible to apportion the deterministic component
of the source-to-leaf delays between interior links. (To see this, it is sufficient to consider
the case of the two receiver tree; expressing the link fixed delays in terms of the source-to-leaf
fixed delays results in two equations in three unknowns). Thus we normalize each measurement
by subtracting the minimum delay seen at the leaf. Observe that to interpret the observed minimum
delay as the transmission delay assumes that at least one probe has experienced no queuing delay
along the path).
The second step is to choose the bin size q and discretize the delays measurements accordingly.
This introduces a quantization error which affects the accuracy of the estimates. As our results have
shown, the accuracy increases as q decreases (we have obtained accurate results over a significant
range of values of q up to the same order of magnitude of the links average delay). The choice of
q represents a trade-off between accuracy and cost of the computation as a smaller bin size entails
a higher computational cost due to the higher dimensionality of the binned distributions.
These two steps are carried out as follows. From the measured data (Y k ) k2R , we recursively
construct the auxiliary vector process b
m2f1;:::;ng
The binned estimates of bfl are
with
Y k;m
Here dxe denotes the smallest integer greater than x and N k 1g.
Observe that i max represents the largest value at which the estimate b
The estimate can be computed iteratively over the delay lag and recursively over the tree.
The pseudo code for carrying out the computation is found in Figure 5. The procedure find y
calculates b
Y k and bfl k , with b
Y k;l initialized to Y k;l \Gamma minm2f1;:::;ng Y k;m for k 2 R and 1 (a value
procedure main f
find y
foreach
procedure find y
foreach
foreach ng )
foreach
return b
procedure infer delay ( k, i
A k [i] ==
else f
A k [0]
ae Q
oe
A k [j]
A
A f(k) [0]
A
A f(k) [0]
foreach

Figure

5: PSEUDOCODE FOR INFERENCE OF DELAY DISTRIBUTION.
larger than any observed delay suffices) otherwise. The procedure infer delay calculates b
for a fixed i recursively on the tree, with b
initialized to 0, except for
A 0 [0] set to 1. The output of the algorithm are the estimates b
Within the code, an empty product (which occurs when the first argument of infer is a leaf)
is assumed to be zero. The routines solvefor1 and solvefor2 return the value of the first
symbolic argument that solves the equation in the second argument. solvefor1 returns a solution
in (0; 1); from Lemma 1 in [4] this is known to be unique. solvefor2 returns the unique
solution if the second argument is linear in b
A k (i) ( this happen only if k is a leaf-node), otherwise
it returns the second largest solution.
4.1 Distributed Implementation
As with the loss estimator [4] the algorithm is recursive on trees. In particular, observe that the
computation of bfl and b
A k only requires the knowledge of ( b
are computed
recursively on the the tree starting from the receivers. Therefore it is possible to distribute the
computation among the nodes of the tree (or representative nodes of subtrees), with each node k
being responsible for the aggregation of the measurements of its child nodes through (14) and for
the computation of b
A k .
4.2 Adopting Different Bin Sizes
Following the results of the previous section, we presented the algorithm using a fixed value of q
for all links. This can be quite restrictive in a heterogeneous environment, where links may differ
significantly in terms of speed and buffer sizes; a single value of q could be at the same time too
coarse grained for describing the delay of a high bandwidth link but too fine-grained to efficiently
capture the essential characteristics of the delay experienced along a low bandwidth link.
A simple way to overcome this limitation is to run the algorithm for different values of q, each
best suited for the behavior of a different group of links, and retain each time only the solutions for
those links. A drawback of this approach is that each distribution is computed for all the different
bin sizes. The distributed nature of the algorithm suggests we can do better; indeed, since A k ,
can be computed independently from one another, it is possible to compute each link
delay distribution only for the bin size best suited to its delay characteristics. More precisely, let
q k denote the bin size adopted for link k. In order to compute b
ff k with bin size q k we need to
compute both b
A k and b
A f(k) with bin size q k . Thus, the overall computation requires calculating
each cumulative distribution b
A k only for the bin sizes q j , only for the bin
sizes adopted for the links terminating at node k and at all its child nodes rather than for bin sizes
adopted for all links.
In an implementation, we envision that a fixed value for all links is used first. This can be
chosen based on the measurements spread and the tree topology or delay past history. Then, with
a better idea of each link delay spread, it would be possible to refine the value of the bin size on a
link by link basis.
5 Experimental Evaluation
We evaluated our delay estimator through extensive simulation. Our first set of experiments focus
on the statistical properties of the estimator. We perform model simulation, where delay and loss
are determined by random processes that follow the model on which we based our analysis. In
our second set of experiments we we investigate the behavior of the estimators in a more realistic
setting where the model assumption of independence may be violated. To this end, we perform
TCP/UDP simulation, using the ns simulator. Here delay and loss are determined by queuing
delay and queue overflows at network nodes as multicast probes compete with traffic generated by
TCP/UDP traffic sources.
5.1 Comparing Inferred vs. Sample Distributions
Before examining the results of our experiments, we describe our approach to assessing the accuracy
of the inferred distributions. Given an experiment in which n probes are sent from the source
to the receivers, for k 2 V , the inferred distribution b
is computed from the end-to-end measurements
using the algorithm described in Section 4. Its accuracy must be measured against the
actual data, represented by a finite sequence of delays fD k;m g n
experienced by
the probes in traversing (reaching) that link. For simplicity of notation we assume, hereafter, that
each set of data has been already normalized by subtracting the minimum delay from the sequence.
We compare summary statistics of link delay, namely the mean and the variance. A finer evaluation
of the accuracy lies in a direct comparison of the inferred and sample distributions. To this
end, we also compute the largest absolute deviation between the inferred and sample c.d.f.s. This
measure is used in statistics for the Kolmogoroff-Smirnoff test for goodness of fit of a theoretical
with a sample distribution. A small value for this measure indicates that the theoretical distribution
provides a good fit to the sample distribution; a large value leads to the rejection of the hypoth-
esis. We cannot directly apply the test as we deal with an inferred rather than a sample c.d.f.;
however, we will use the largest absolute deviation as a global measure of accuracy of the inferred
distributions.
We compute the sample distributions ~ ff and ~
A using the same bin size q of the estimator. More
precisely, we compute (~ff k ) k2V and ( ~
(Observe that in computing (~ff k ) k2V , the sum
is carried out only over N f(k) 1g, the set over which the delay
along link k is defined either finite or infinite.)
The largest absolute deviation between the inferred and sample c.d.f.s is, then,
ff k (i)j. In other words, \Delta k is the smallest nonnegative number such that
lies between
. The same result holds for the tail
probabilities,
(a)0.050.150.250 2000 4000 6000 8000 10000
a
(1)
n. of probes
link 1
link 2
link 3
a k (1)=0.2
(b)

Figure

Simulation topology. (b): Convergence of b
ff k (1) to ff k (1).
a
(1)
n. of probes
a 1 (1)
a 1 (1) 2 std
a 2 (1)
a 2 (1) 2 std
(a)0.050.150.250 2000 4000 6000 8000 10000
a
(1)
n. of probes
a 1 (1)=a 2 (1)
a 1 (1) 2 std
a 2 (1) 2 std
(b)

Figure

7: AGREEMENT BETWEEN SIMULATED AND THEORETICAL CONFIDENCE INTERVALS.
(a): Results from 100 model simulations. (b): Prediction from (10). The graphs show two-sided
confidence interval at 2 standard deviation for link 1 and 2. Parameters are ff k
links.
5.2 Model Simulation
We first consider the two-leaf topology of Figure 6(a), with source 0 and receivers 2 and 3. Link
delays are independent, taking values in f0; 1; 1g; if a probe is not lost it experiences either
no delay or unit delay. In Figure 6(b) we plot the estimate b
versus the model values for a
run comprising 10000 probes. The estimate converges within to 2% of the model value within
4000 probes. In Figure 7 we compare the empirical and theoretical 95% confidence intervals.
The theoretical intervals are computed from (10). The empirical intervals are computed over 100
independent simulations. The agreement between simulation and theory is close: the two sets of
curves are almost indistinguishable.
Next we consider the topology of Figure 8. Delays are independently distributed according
to a truncated geometric distribution taking values in f0; (in ms) . This topology
is also used in subsequent TCP/UDP simulations, and the link average delay and loss probability
are chosen to match the values obtained from these. The average delay range between 1 and 2ms
for the slower edge links and between 0:2 and 0:5ms for the interior faster links; the link losses
range from 1% to 11%. In Figure 9 we plot the estimated average link delay and standard deviation
with the empirical 95% confidence interval computed over 100 simulations. The results are very
accurate even for several hundred probes: the theoretical average delay always lies within the
confidence interval and the standard deviation does so for 1500 or more probes.
To compare the inferred and sample distributions, we computed the largest absolute deviation
between the inferred and sample c.d.f.s. The results are summarized in Figure 10 where we plot
the minimum, median and the maximum largest absolute deviation in 100 simulations computed
over all links as a function of n (a) and link by link for (b). The accuracy increases with
the number of probes as 1=
n with a spread of two orders of magnitude between the minimum
and maximum. For more than 3000 probes, the average largest deviation over all links is less
than 1%. The accuracy varies from link to link: when the number of probes is
at one extreme we have link 4 with 0:18%  \Delta 4  0:8% and at the other extreme link 6 with
simulations. We observe that the inferred distributions are less accurate
as we go down the tree. This is in agreement with the results of Section 3.4 and is explained in
terms of the larger inferred probabilities variances of downstream with respect to upstream nodes.
5.3 TCP/UDP Simulations
We used the topology shown in Figure 8. To capture the heterogeneity between edges and core
of a WAN, interior links have higher capacity (5Mb/sec) and propagation delay (50ms) then at the
1Mb/sec, 10ms
5Mb/sec, 50ms6 79 11

Figure

8: Simulation Topology: Link are of two types: edge links of 1MB/s capacity and 10ms
latency, and interior links of 5Mb/s capacity and 50ms latency.0.20.611.41.82.2
Average
Delay
(ms)
n. of probes
link 1 - estimated
link 6 - estimated
link 8 - estimated
link 11 - estimated
link 1 - model
link 6 - model
link 8 - model
link 11 - model
(a)12345
Standard
Deviation
(ms)
n. of probes
link 1 - estimated
link 6 - estimated
link 8 - estimated
link 11 - estimated
link 1 - model
link 6 - model
link 8 - model
link 11 - model
(b)

Figure

9: MODEL SIMULATION: TOPOLOGY OF FIGURE 8. ESTIMATED VERSUS THEORETICAL
DELAY AVERAGE AND STANDARD DEVIATION WITH 95% CONFIDENCE INTERVAL COMPUTED
OVER 100 MODEL SIMULATIONS.
1e-031e-010 2000 4000 6000 8000 10000
Largest
Absolute
Vertical
Deviation
n. of probes
Maximum
Median
Minimum
(a)1e-031e-01
Largest
Absolute
Vertical
Deviation
Link
Maximum
Median
Minimum
(b)

Figure

10: MODEL SIMULATION: TOPOLOGY OF FIGURE 8. ACCURACY OF THE ESTIMATED
DISTRIBUTION. LARGEST VERTICAL ABSOLUTE DEVIATION BETWEEN ESTIMATED AND
SAMPLE C.D.F. Minimum, median and the maximum largest absolute deviation in 100 simulations
computed over all links as function of n (a) and link by link for
edge (1Mb/sec and 10ms). Each link is modeled as a FIFO queue with a 4-packet capacity.
probes as a 20Kbit/s stream comprising 40 byte UDP packets according to
a Poisson process with a mean interarrival time of 16ms; this represents 2% of the smallest link
capacity. Observe that even for this simple topology with 8 end-points, a mesh of unicast measurements
with the same traffic characteristics would require an aggregate bandwidth of 160Kbit/s at
the root. The background traffic comprises a mix of infinite data source TCP connections
and exponential on-off sources using UDP. Averaged over the different simulations, the link loss
ranges between 1% and 11% and link utilization ranges between 20% and 60%.
For a single experiment, Figure 11 compares the estimated versus the sample average delay
for representative selected links. The analysis has been carried out using 1ms (a) and
0:1ms (b). In this example, we practically obtain the same accuracy despite a tenfold difference
in resolution. (Observe that 1ms is of the same order of magnitude of the average delays.)
The inferred averages rapidly converge to the sample averages even though we have persistent
systematic errors in the inferred values due to consistent spatial correlation. We shall comment
upon this later.
In order to show how the inferred values not only quickly converge, but also exhibit good dynamics
tracking, in Figure 12 we plot the inferred versus the sample average delay for 3 links (1,
3 and 10) computed over a moving window of two different sizes with jumps of half its width. To
allow greater dynamics, here we arranged background sources with random start and stop times.
Under both window sizes (approximately 300 and 1200 probes are used, respectively), the esti-
0Average
Delay
(ms)
n. of probes
link 1 - estimated
link 6 - estimated
link 9 - estimated
link 11 - estimated
link 1 - sample
link 6 - sample
link 9 - sample
link 11 - sample
(a)0.51.52.5
Average
Delay
(ms)
n. of probes
link 1 - estimated
link 6 - estimated
link 9 - estimated
link 11 - estimated
link 1 - sample
link 6 - sample
link 9 - sample
link 11 - sample
(b)

Figure

TCP/UDP SIMULATIONS. (a): bin-size 0:1ms. The graphs shows
how the inferred values closely track the sample average delays.0.51.52.53.54.5
Average
Delay
(ms)
Seconds
link 1 - estimated
link 3 - estimated
link estimated
link 1 - sample
link 3 - sample
link
(a)0.51.52.53.54.5
Average
Delay
(ms)
Seconds
link 1 - estimated
link 3 - estimated
link estimated
link 1 - sample
link 3 - sample
link
(b)

Figure

12: DYNAMIC ACCURACY OF INFERENCE. Sample and Inferred average delay on links
of the multicast tree in Figure 8. (a): 5 seconds window. (b): 20 seconds windows.
Background traffic has random start stop times.
RMS
normalized
error
(Average
n. of probes
link 1
link 3
link 5
link 6
link
link 11
(a)0.050.150.250.350.450 2000 4000 6000 8000 10000
RMS
normalized
error
(Average
n. of probes
link 1
link 3
link 5
link 6
link
link 11
(b)

Figure

13: ACCURACY OF INFERENCE: AVERAGE DELAY. Left: 1ms. Right: 0:1ms.
The graphs show the normalized Root Mean Square error between the estimated and sample average
delay over 100 simulations.
mates of the average delays of links 1 and 10 show good agreement and a quick response to delay
variability revealing a good convergence rate of the estimator. For link 3 with a smaller average
delay, the behavior is rather poor, especially for the 5 seconds windows size.
For a selection of links, in Figure 13 we plot the Root Mean Square (RMS) normalized error
between the estimated and sample average delays calculated over 100 simulations using
and 0:1ms. The two plots demonstrate that the error drops significantly up to 2000 probes
after which it becomes almost constant. In this example, increasing the resolution by a factor of
ten improves, although not significantly, the overall accuracy of the estimates especially for those
links that enjoy smaller delays. After 10000 probes the relative error ranges from 1% to 23%. The
higher values occur when link average delays are small due to the fact that for these links the same
absolute error results in a more pronounced relative error.
The persistence of systematic errors we observe in Figure 13 is due to the presence of spatial
correlation. In our simulations, a multicast probe is more likely to experience similar level of congestion
on consecutive links or on sibling links than is dictated by the independence assumption.
We also verified the presence of temporal correlation among successive probes on the same link
caused by consecutive probes experiencing the same congestion level at a node.
To assess the extent to which our real traffic simulations violate the model assumptions, we
computed the delay correlation between links pairs and among packets on the same link. The analysis
revealed the presence of significant spatial correlations up to 0:3  0:4 between consecutive
links. The smallest values are observed for link 5 which always exhibits a correlation with its
parent node that lies below 0.1. From Figure 13 we verify that, not surprisingly node 5 enjoys
the smallest relative error. We believe that these high correlations are a result of the small scale
of the simulated network. We have observed smaller correlations in large simulations as would be
expected in real networks because of the wide traffic and link diversity.
The autocorrelation function rapidly decreases and can be considered negligible for a lag larger
than (approximatively 2 seconds). The presence of short-term correlation does not alter the key
property of convergence of the estimator as it suffices that the underlying processes be stationary
and ergodic (this happens for example, when recurrence conditions are satisfied). The price of
correlation, however, is that the convergence rate is slower than when delay are independent.
Now we turn our attention to the inferred distributions. For an experiment of 300 seconds
during which approximately 18000 probes were generated, we plot the complementary c.d.f. conditioned
on the delay being finite in Figures 14. In Figure 15 we also plot the complement c.d.f
of the node cumulative delay. (we show only the internal links as b
1ms.
From these two sets of plots, it is striking to note the differences between the accuracy of the
estimated cumulative delay distributions b
A k and the estimated link delay distributions b
while the
former are all very close to the actual distributions, the latter results are inaccurate in many cases.
This is explained by observing that in presence of significant correlations, the convolution among
A k , ff k , and A f(k) , used in the model, does not well capture the relationship between the actual
distributions. We verified this by convolving ff k and A f(k) and comparing the result with A k ; as
expected, in the presence of strong local correlation, the results exhibit significant differences that
account for the discrepancies of the inferred distributions. Nevertheless, results should be affected
in a continuous way with small violations leading to small inaccuracies. Indeed, we have good
agreement for the inferred distributions of links 4, 5, 10 and 12 that are the nodes with smallest
spatial correlations. Unfortunately it is not easy to determine whether the correlations are strong
and therefore assess the expected accuracy of the estimates, even though pathological shapes of the
inferred distributions could provide evidence of strong local correlations 1 . A solution could be the
extension of the model to explicitly account for the presence of spatial correlation in the analysis.
This will be the focus of future research.
The accuracy of the inferred cumulative delay distributions, on the other hand, derives from
the fact that even in presence of significant local correlations, equation (8), which assumes inde-
1 To this end, we observed that under strong spatial correlation inaccuracies of the estimator b
ff are often associated
to the existence of significant increasing behavior portions in the complement c.d.f. that reveals the presence of
negative inferred probabilities with possibly non negligible absolute values.
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 1 delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 2 delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 4 delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 7 delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 10 delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 12 delay c.d.f
sample
estimated

Figure

14: Sample vs. Estimated Delay c.d.f. for selected links.
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 1 cumulative delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 2 cumulative delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 3 cumulative delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 6 cumulative delay c.d.f
sample
Complement
of
the
Cumulative
Density
Function
Delay (ms)
Estimated vs. sample node 7 cumulative delay c.d.f
sample
estimated

Figure

15: Sample vs. Estimated node k cumulative delay c.d.f.
c.d.f.
Largest
Absolute
Vertical
Deviation
n. of probes
Maximum
Median
Minimum
(a)1e-021e+00
c.d.f.
Largest
Absolute
Vertical
Deviation
Link
Maximum
Median
Minimum
(b)

Figure

8. ACCURACY OF THE ESTIMATED
DISTRIBUTION. LARGEST VERTICAL ABSOLUTE DEVIATION BETWEEN ESTIMATED
AND THEORETICAL C.D.F. Minimum, median and the maximum largest absolute deviation in 100
simulations computed over all links as function of n (a) and link by link for
pendence, is still accurate. This can be explained by observing that (8) is equivalent to (4) which
consists of a convolution between A f(k) and fi k ; we expect the correlation between the delay accrued
by a probe in reaching node f(k) and the minimum delay accrued from node f(k) to reach
any receiver be rather small, especially as the tree size grows, as these delays span the entire multicast
tree.
Finally in Figure 16 we plotted the minimum, median and maximum largest deviation between
inferred and theoretical c.d.f. over 100 simulations computed over all links as function of n (left)
and link by link as for (right). Due to spatial correlation, the largest deviation level
off after the first 2000 probes with the median that stabilize at 5%. The accuracy again exhibits a
negative trend as we descend the tree.
6 Conclusions and Future Work
In this paper, we introduced the use of end-to-end multicast measurements to infer network internal
delay in a logical multicast tree. Under the assumption of delay independence, we derived an
algorithm to estimate the per link discrete delay distributions and utilization from the measured
end-to-end delay distributions. We investigated the statistical properties of the estimator, and show
it to be strongly consistent and asymptotically normal.
We evaluated our estimator through simulation. Within model simulation we verified the accuracy
and convergence of the inferred to the actual values as predicted by our analysis. In real
traffic simulations, we found rapid convergence, although some persistent difference to the actual
distributions because of spatial correlation.
We are extending our delay distribution analysis in several directions. First we plan to do more
extensive simulations, exploring larger topologies, different node behavior, background traffic and
probe characteristics. Moreover, we are exploring how probe delay is representative of the delay
suffered by other applications and protocols, for examples TCP.
Second, we are analyzing the effect of spatial correlation among delays and we are planning
to extend the model by directly taking into account the presence of correlation. Moreover, we
are studying the effect of the choice of the bin size on the accuracy of the results. To deal with
continuously distributed delay, we derived a continuous version of the inference algorithm we are
currently investigating.
Finally, we believe that our inference technique can shed light on the behavior and dynamics
of per link delay and so allow us to develop accurate link delay models. This will be also object of
future works.
We feel that multicast based delay inference is an effective approach to perform delay mea-
surements. The techniques developed are based on rigorous statistical analysis and, as our results
show, yield representative delay estimates for all traffic which receive the same per node behavior
of multicast probes. The approach does not depend on cooperation from networks elements and
because of bandwidth efficiency of multicast traffic is well suited to cope with the growing size of
today networks.



--R

"The Laplace Transform"
"Characterizing End-to-End Packet Delay and Loss in the Internet."
"The case for FEC-based error control for packet audio in the Internet"
"Multicast-Based Inference of Network Internal Loss Characteristics"
"Multicast-Based Inference of Network Internal Loss Characteristics: Accuracy of Packet Estimation"
"Inferring Link-Level Performance from End- to-End Measurements"
"Loss-Based Inference of Multicast Network Topology"
"Measurements Considerations for Assessing Unidirectional Latencies"
"Measuring Bottleneck Link Speed in Packet-Switched Networks,"

"Multicast Inference of Packet Delay Variance at Interior Networks Links"
"Probabilistic Inference Methods for Multicast Network Topology"
Felix: Independent Monitoring for Network Survivability.
"Random Early Detection Gateways for Congestion Avoidance,"
IPMA: Internet Performance Measurement and Analysis.
IP Performance Metrics Working Group.

"Creating a Scalable Architecture for Internet Mea- surement,"
"Diagnosing Internet Congestion with a Transport Layer Performance Tool,"
"Network Time Protocol (Version 3): Specification, Implementation and Analysis"
"Estimation and Removal of Clock Skew from Network Delay Measurements"
"Correlation of Packet Delay and Loss in the Internet"

"On the Dynamics and Significance of Low Frequency Components of Internet Load"

"End-to-End Routing Behavior in the Internet,"
"End-to-End Internet Packet Dynamics,"
"Measurements and Analysis of End-to-End Internet Dynamics,"
"Automated Packet Trace Analysis of TCP Implementations,"
"On calibrating measurements of Packet Transit Times"
"Inference of Multicast Routing Tree Topologies and Bottleneck Bandwidths using End-to-end Measurements"
"Experimental assessment of end-to-end behavior on Internet"
"Study of network dynamics"
"Theory of Statistics"






--TR
Measuring bottleneck link speed in packet-switched networks
End-to-end routing behavior in the Internet
End-to-end Internet packet dynamics
Automated packet trace analysis of TCP implementations
On calibrating measurements of packet transit times
Using pathchar to estimate Internet link characteristics
Network Delay Tomography from End-to-End Unicast Measurements
Multicast-Based Inference of Network-Internal Delay Distributions TITLE2:

--CTR
Fabio Ricciato , Francesco Vacirca , Martin Karner, Bottleneck detection in UMTS via TCP passive monitoring: a real case, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, October 24-27, 2005, Toulouse, France
Earl Lawrence , George Michailidis , Vijay N. Nair, Local area network analysis using end-to-end delay tomography, ACM SIGMETRICS Performance Evaluation Review, v.33 n.3, December 2005
N. G. Duffield , V. Arya , R. Bellino , T. Friedman , J. Horowitz , D. Towsley , T. Turletti, Network tomography from aggregate loss reports, Performance Evaluation, v.62 n.1-4, p.147-163, October 2005
Zhen Liu , Laura Wynter , Cathy H. Xia , Fan Zhang, Parameter inference of queueing models for IT systems using end-to-end measurements, Performance Evaluation, v.63 n.1, p.36-60, January 2006
Omer Gurewitz , Israel Cidon , Moshe Sidi, One-way delay estimation using network-wide measurements, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2710-2724, June 2006
N. G. Duffield , Francesco Lo Presti, Network tomography from measured end-to-end delay covariance, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.978-992, December 2004
Nick Duffield , Francesco Lo Presti , Vern Paxson , Don Towsley, Network loss tomography using striped unicast probes, IEEE/ACM Transactions on Networking (TON), v.14 n.4, p.697-710, August 2006
Azer Bestavros , John W. Byers , Khaled A. Harfoush, Inference and Labeling of Metric-Induced Network Topologies, IEEE Transactions on Parallel and Distributed Systems, v.16 n.11, p.1053-1065, November 2005
network tomography;queueing delay;estimation theory;multicast tree;end-to-end measurements