This is the post-print version. The original publication is available at https://doi.org/10.1016/j.simpat.2010.06.019 (DOI: 10.1016/j.simpat.2010.06.019). (c) Elsevier, 2011. This is the author's version of the work. It is posted here bypermission of Elsevier for your personal use. Not for redistribution.

Procedia Computer
Science
Procedia Computer Science 00 (2010) 1–17

Probe Interval Designs
that Improve Accuracy of CoMPACT Monitor
K. Watabea , Y. Honmaa , M. Aidaa
a The author are with the Graduate School of System Design, Tokyo Metropolitan University, Hino-shi 191-0065, Japan.

Abstract
We have proposed the CoMPACT monitor; it achieves the scalable measurement of the oneway delay distribution for each flow. CoMPACT monitor transforms the one-way delay dataobtained by active measurement by using the passively monitored traﬃc data of the target flow.
A recent study reported that using an inter-probe time with Gamma distribution can improve theaccuracy of simple active measurements. The improvement is in terms of the ensemble meanof the stationary stochastic process. In this paper, to improve accuracy of CoMPACT monitor,
we apply Gamma-probing as the active measurement component of CoMPACT monitor. The
significant issue in this application is in the diﬀerence between objects targeted for measurement;
CoMPACT monitor estimates the time average of sample path rather than the ensemble mean.
We investigate the characteristics of CoMPACT monitor and Gamma-probing, and verify the
improved accuracy of CoMPACT monitor through simulations.
Keywords: QoS measurement, delay measurement, change-of-measure, Gamma distribution
1. Introduction
With the rapid growth of the Internet over the last few years, it has come to play an importantrole as a key social infrastructure. Various applications provide new services including telephonyand live video on the Internet, and the traﬃc they stream exhibits complex characteristics. Thesevarious applications require various quality of service (QoS) guarantees and so diﬀer from traditional e-mail and web browsing applications. Given that even more unusual applications willarise in the future, the diversification of QoS requirements can only strengthen.
In order to meet such the varied network control requirements, we need a measurement technology that can produce detailed QoS information. Measuring the QoS for each flow (e.g., users,
applications, or organizations) is important since it is a key parameter in service level agreements

Email addresses: watabe-kouhei@sd.tmu.ac.jp (K. Watabe), yudai@sd.tmu.ac.jp (Y. Honma),
maida@sd.tmu.ac.jp (M. Aida)

/ Procedia Computer Science 00 (2010) 1–17

2

Figure 1: Two-point passive measurement

Figure 2: Active measurement(SLAs) between the Internet service provider (ISP) and the user. One-way packet delay is one of
the most important QoS metrics. This paper focuses on the measurement of one-way delay foreach flow.
Many tools have been proposed to assess QoS including one-way delay ([1, 2]), and have also
been evaluated in previous studies ([3, 4, 5]). Conventional techniques of measuring network
performance and QoS can be classified as either passive or active measurements.
Passive measurement monitors the target user packet directly, by capturing the packets, including the target information (see Fig. 1). Passive measurement is used to measure the volumeof traﬃc, one-way delay, round-trip time (RTT), loss, etc. It can get any desired information
about the traﬃc since it observes the actual traﬃc. Passive measurement can be categorized
into two-point monitoring with data-matching processes (to measure one-way delay etc.) andone-point monitoring (to measure the volume of traﬃc etc.).
Passive measurement has the advantage of accuracy. However, if we perform passive measurements in a large-scale network, the number of monitored packets is enormous, and network
resources are wasted by gathering the monitored data at the data center. Moreover, in order tomeasure delay, it is necessary to determine the diﬀerence in arrival time of a particular packet
at diﬀerent points in the network. This requires searching for the packet which was recorded in
the data monitored at one point from the data monitored at other point. This packet matchingprocess lacks scalability, so passive measurement lacks scalability.
Active measurement monitors QoS by injecting probe packets into a network path and monitoring them (see Fig. 2 and [6, 7, 8, 9]). Active measurement can be used to measure one-way
delay, RTT, loss, available bandwidth [10], etc. It cannot obtain the per-flow QoS, but this is easy
for the end user to perform. Unfortunately, the QoS data obtained by active measurement does
not represent the QoS of the user packets, only QoS of the probe packets.
The authors previously described how the advantages of active and passive measurements
could be joined in their scalable measurement proposal called change-of-measure-based passive/active
monitoring (CoMPACT monitor); it oﬀers per-flow QoS measurement ([11, 12, 13]).

/ Procedia Computer Science 00 (2010) 1–17

3

Figure 3: The transformation of QoS by CoMPACT monitor

Figure 4: The composition of CoMPACT monitor

The idea of CoMPACT monitor is as follows. The direct measurement of QoS of the target
flow by passive measurement is not really feasible due to the scalability problem. Instead, the
QoS of the target flow is gained by transforming QoS data obtained by active measurement.
The transformation reflects the passively monitored traﬃc data (volume of traﬃc) of the target
flow (see Fig. 3). We show the composition of CoMPACT monitor in Fig. 4. The problem ofscalability is well suppressed, because the volume of traﬃc can be measured by one-point passive
measurement without requiring data-matching processes.
We original assumed that Poisson arrivals (intervals follow an exponential distribution) would
be most appropriate for designing a policy of probe packet arrival since it permits the applicationof PASTA (Poisson Arrivals See Time Averages) property [14]. In addition, we applied theexponential distribution, as an inter-probe time distribution, in verifying CoMPACT monitor.
However, recent work [15] indicates that there maybe many distributions that are more accurate than an exponential distribution if a non-intrusive context (ignoring the existence of probe
packets) can be assumed. Moreover, according to [16], we can find a distribution that is suboptimal in accuracy by setting the inter-probe time according to a parameterized Gamma distribution.
This paper confirms that applying Gamma-probing to CoMPACT monitor can improve its
accuracy in measuring the one-way delay distribution of individual flows. The significant issue
in this application lies in the diﬀerence between the objects targeted for measurement. In [16], theprocess observed by probe packets is assumed to be stationary and ergodic stochastic. This meansthat accuracy improvement is guaranteed only when the ensemble mean of a stationary stochastic
process is estimated. However, CoMPCT monitor estimates the time average of the sampled
path. Therefore, we should carefully investigate the characteristics of CoMPACT monitor withGamma-probing.
The rest of the paper is organized as follows. We describe the concept and mathematical for-/ Procedia Computer Science 00 (2010) 1–17

4

mulation of CoMPACT monitor in section 2. Next, we briefly summarize the theory of Gammaprobing for active measurement in section 3. Section 4 discusses the diﬀerence in objects targeted
between Gamma-probing and CoMPACT monitor. To confirm that the accuracy of CoMPACT
monitor can be improved by Gamma-probing, we execute some simulations in section 5 andsection 7. We conclude the paper in section 8.
2. Summary of CoMPACT monitor
2.1. The concept
CoMPACT monitor estimates an empirical QoS for the target flow by converting observed
values of network performance at timing of probe packet arrivals into a measure of the target
flow timing. Now, let v(t) denote the network process under observation (e.g. the virtual oneway delay in the network path at time t), and Xk denote a random variable which is observed v(t)with a certain timing (e.g. the timing of user k’s packet arrivals). The probability of Xk exceeding
c is!
Pr(Xk > c) =1{x>c} dFk (x)= EFk [1{x>c} ]where Fk (x) and 1{·} denote, respectively, the distribution function of Xk and the indicator function, and EFk denotes the expectation with respect to Fk .
If we can directly monitor Xk , its distribution can be estimated bym

1 "1{X (n)>c} ,m n=1 kfor suﬃciently large m.

where Xk (n) (n = 1, 2, · · · , m) denotes the nth observed value of Xk . Now, let us consider thesituation that Xk cannot be directly monitored (actually, we cannot directly monitor Xk by using
passive measurement in large-scale networks). Let Y denote a random variable which is observedv(t) with a diﬀerent timing (e.g. timing of probe packet arrivals), independent of Xk . This forces
us to consider the relationship between Xk and Y.
Observed values of Xk and Y are diﬀerent if their timing is diﬀerent, even if they observe acommon process v(t) (see Fig. 5). Xk and Y can be related by each distribution functions Fk (x)and G(y), and Pr(Xk > c) expressed by measure of Xk can be transformed into measure of Y as
follows.
!
Pr(Xk > c) =1{x>c} dFk (x)!
dFk (y)dG(y)=1{y>c}dG(y)#$dFk (Y)= EG 1{Y>c}dG(Y)where EG denotes the expectation with respect to G.
Therefore, Pr(Xk > c) can be estimated bym

1 "dFk (Y(n))
1{Y(n)>c},m n=1
dG(Y(n))for suﬃciently large m.

(1)

/ Procedia Computer Science 00 (2010) 1–17

5

Figure 5: The relation between timing of arrivals and empirical QoS

where Y(n) (n = 1, 2, · · · , m) denotes the nth observed value of Y. Note that this estimator does
not need to know Xk (n), if we can get dFk (Y(n))/dG(Y(n)). This means the QoS of a specificflow (as decided by k) can be estimated by just one probe packet flow which arrives with timingof Y.
2.2. Mathematical formulation
This subsection briefly summarizes the mathematical formulation of the CoMPACT monitor
with regard to one-way delay ([13]). We assume the traﬃc in the target flow can be treated as a
fluid. In other words, we assume the target flow packets outnumber the active probe packets.
Let a(t) and v(t) denote, respectively, the traﬃc in the target flow at time t (≥ 0) and the virtual
one-way delay on the path that we want to measure. a(t) and v(t) are nonnegative deterministic
processes assumed to be right-continuous with left limits and bounded on t ≥ 0. We can take a(t)and v(t) as sample paths of the corresponding stochastic processes.
Considering the measurement of the empirical one-way delay distribution π(c), the value wewant to measure is the ratio of traﬃc whose delay exceeds c to all traﬃc of the target flow, which
is given by%t
1{v(s)>c} a(s)ds
π(c) = lim 0 % t
.
(2)
t→∞
a(s)ds0π(c) can be estimated by estimator Zm (c) as follows (see [13] for details).
m

Zm (c) ==1 "a(T n )
1{v(Tn )>c} &mm n=1
l=1 a(T l )/m

(3)

m
"

a(T n )
1{v(Tn )>c} &m
l=1 a(T l )n=1

for suﬃciently large m, where T n (n = 1, 2, · · · , m) denotes the nth sampling time, and eachtime of sampling corresponds to a time of probe packet arrival. Active and one-point passive

/ Procedia Computer Science 00 (2010) 1–17

6

measurement are used to observe v(T n ) and a(T n ), respectively. Note that measuring the volumeof traﬃc by one-point passive measurement is achieved much more easily than measuring theone-way delay by two-point passive measurement.
&
If we extract quantity m
n=1 1{v(T n )>c} /m from equation (3), we can use it as a simple active
estimator that counts the packets whose delay exceeds c. However, equation (3) is weighted by&a(T n )/( ml=1 a(T l )/m), which is decided by the traﬃc in the target flow when probe packets arrive.
This means that the one-way delay distribution (measured by active measurement without bias) iscorrected to the empirical one-way delay distribution by the bias of the target flow (observed by&passive measurement). a(T n )/( ml=1 a(T l )/m) in equation (3) corresponds to dF k (Y(n))/dG(Y(n))
in equation (1).
Since the traﬃc is not really a fluid, we use the number of packets that are in the δ-neighborhoodof T n [max{T n − δ/2, T n−1 }, min{T n+1 , T n + δ/2}) instead of a(T n ), where δ is a predefined small
positive number ([13]).
3. Suboptimal probe intervals
3.1. NIMASTA
Since the PASTA property is good for non-biased measurement, Poisson arrivals (intervals
follow an exponential distribution) have been widely used as the design policy of probe packet
arrivals for active measurement. However, recent work [15] indicates that there may be manyother distributions that can estimate the true value if a non-intrusive context (the eﬀect of probe
packets is ignored) can be assumed. This property was named NIMASTA (Non-Intrusive Mixing
Arrivals See Time Averages) in [15].
NIMASTA contains three assumptions. First, the stochastic process that expresses the network state we are interested in (e.g. virtual delay) is stationary and ergodic. This process iscalled the ground truth process in [16]. Second, the point process of probe packets arrivals{T n } (n = 1, 2, · · · , m) is stationary and mixing. Mixing is the requirement to guarantee joint ergodicity between the probe and ground truth processes (see [15] for details). The last assumption
is the non-intrusive context, i.e. we can ignore the impact of probe packets. Namely, the ratio of
the probe stream to all streams is very small.
Under the above assumptions, [15] proved that the following equation holds.
!
m
1 "
1 t
lim
f (Y(T n )) = limf (Y(t))dt
m→∞ m
t→∞ t 0n=1
= E[ f (Y(0))]

a.s.,

(4)

where f and Y(t) denote an arbitrary positive function and the ground truth process, respectively. Equation (4) means that we can estimate the ensemble mean of the ground truth process
E[ f (Y(0))] by using any probe packet policy if the point process of probe packet arrival {T n }is mixing. An example of the mixing point process has processes whose intervals follow theGamma distribution and the uniform distribution. Note that periodic-probing with fixed intervals
is not a mixing process, and does not satisfy equation (4).
3.2. Setting probe intervals to decrease variance
A recent study [16] reported that NIMASTA-based probing oﬀers improved measurement
accuracy. We can select a suboptimal (in terms of accuracy) probing process under a specificassumption by using the inter-probe time given by the parameterized Gamma distribution.

/ Procedia Computer Science 00 (2010) 1–17

7

If we estimate the mean of Y(0) by using active measurement, estimator p̂ ismp̂ =Thus the variance of p̂ isVar[ p̂] =1 "Y(T n ).
m n=1

⎤
⎡ m
⎥
⎢⎢⎢"
1
⎢⎢⎣ Y(T n )⎥⎥⎥⎥⎦
Var
2
m
n=1

m
1 "
2 "
Var[Y(T)]+
Cov (Y(T n ), Y(T l ))nm2 n=1m2 n!l!
1
2 "R(τ) f|n−l| (τ)dτ= Var[Y(0)] + 2
m
m n!l

=

(5)

(6)
(7)

where fk is probability density function (pdf) of T k , R(τ) = Cov (Y(t), Y(t − τ)) is the autocovariance function (ACF) of the ground truth process Y(t) (we can express R(τ, t) by τ alone, because
Y(t) is stationary) and the last equality follows from the stationary property of Y(t) and the probe
packet process.
If R(τ) is convex, the following can be proven by using Jensen’s inequality. No other probing
process with an average interval of µ has a variance that is lower than that of periodic-probing(see [16]). Estimator variance is connected with accuracy, lower is better, so periodic-probing is
the best policy if we focus only on variance.
On the other hand, periodic-probing does not satisfy the assumptions of NIMASTA due tonon-mixing, so periodic-probing is not necessarily the best. This is because a phase-lock phenomenon may occur and the estimator may converge on a false value when the cycle of theground truth process corresponds to the cycle of the probing process. Namely, periodic-probing
has a bias.
To tune the tradeoﬀ between traditional policies obeying Poisson arrivals and periodic-probing(which has a bias but has the advantage in terms of variance), [16] proposes a suboptimal policythat gives an inter-probe time that obeys the parameterized Gamma distribution. The pdf that isused as the interval between probe packets is given by- .β
xβ−1 βg(x) =
e−xβ/µ(x > 0),(8)
Γ(β) µwhere g(x) is the Gamma distribution whose shape and scale parameters are β and µ/β, respectively. µ (> 0) denotes the mean, and β (> 0) is the parameter. When β = 1, g(x) reduces tothe exponential distribution with mean µ. When β → ∞, the policy reduces to periodic-probing
because g(x) converges on δ(x − µ).
If ACF is convex, it has been proven that the variance of estimator p̂ sampled by intervals
that follow equation (8) monotonically decreases as β increases. This decrease is caused by thedecrease of the covariance part which is the second term on the right-hand side of equation (7).
We can achieve small variance (it approaches the variance of periodic-probing) by setting β to alarge value since equation (8) converges on periodic-probing towards limit β → ∞.
The problem of bias due to the phase-lock phenomenon can be avoided if we tune β to alimited value (the probing process that has intervals set by equation (8) is mixing). Resolving thetradeoﬀ between a traditional policy that assumes Poisson arrivals and periodic-probing yields a
suboptimal probing process if we give β an appropriate value.

/ Procedia Computer Science 00 (2010) 1–17

8

4. The application to CoMPACT monitor
This section discusses the application of Gamma-probing to CoMPACT monitor. First, wemust determine the ground truth process observed by CoMPACT monitor. Comparing equation (5) with equation (3), we can consider that stochastic process Y(t) observed by CoMPACT
monitor isA(t)Y(t) = 1{V(t)>c},(9)
E[A(t)]
where V(t) and A(t) are stochastic processes corresponding to sample path v(t) and a(t), respectively. If it is confirmed that the ACF R(τ) of stochastic process Y(t) is convex, we can guarantee
an improvement in accuracy due to Gamma-probing by applying the theory in section 3.
The convexity of ACF has been verified for cases of simple virtual delay process and loss
process using data of large-scale passive measurements and simulations ([16]). However, Y(t)observed by CoMPACT monitor is weighted by traﬃc A(t) of a specific flow, so the property ofY(t) clearly diﬀers from the delay/loss processes that are influenced by all flows on the network.
Therefore, we must confirm the convexity of R(τ) in the CoMPACT monitor case. In section 5
and section 7, we will show that the assumption (R(τ) is convex) is appropriate to CoMPACT
monitor.
As described in section 2, we consider v(t) and a(t) are sample paths of corresponding
stochastic processes since CoMPACT monitor estimates the time average of sample path given
by equation (2). However, as explained in section 3, the ground truth process Y(t) is stationary
stochastic process in [16], and the decrease of variance of p̂ is guaranteed for the estimationof the ensemble mean of Y(t). The variance of p̂ depends on both stochastic variations of Y(t)and T n . On the other hand, CoMPACT monitor observe sample path y(t) rather than stochastic
process Y(t), because CoMPACT monitor estimates one-way delay that is experienced by user
flows.
Therefore, it is desired in CoMPACT monitor that variance of estimator p̂ which depends
only on sampling time T n on certain sample path rather than Y(t) decreases. In other words,
variance we want to decrease is given by
m
1 "
1 "
Var[y(T n )] + 2
Var[ p̂] = 2
Cov(y(T n ), y(T l )).
(10)
m n=1
m n!l
Note that equation (10) corresponds to equation (6). If the ACF of Y(t) is convex, we can consider
that the covariance part, which is the second term on the right-hand side of equation (10), tends
to decrease as β increases. Thus the variance of inter-probe time given by equation (8) is µ2 /β;
and it to decreases as β increases. Hence, we can also expect that the variance part, which isthe first term on the right-hand side of equation (10), decreases as β increases since none of theobserved values y(T n ) vary. In section 5 and section 7, we will show that the variance of estimatorwhich depends only on T n decreases with increase of β by using Gamma-probing through thesimulation.
5. The eﬀectiveness of suboptimal probe intervals
5.1. Simulation model
We used NS-2 [17] based simulations to investigate the eﬀectiveness of Gamma-probing in
the framework of CoMPACT monitor. The network model we used in the simulation is shown in
Fig. 6.

/ Procedia Computer Science 00 (2010) 1–17

9

Figure 6: Network model
Table 1: Type of user flows

Flow
type
type 1
type 2type 3type 4

Flow
ID
#1-5
#6-10
#11-15#16-20Mean ON/OFF
period10s/5s
5s/10s
5s/10s1s/19sDistribution of
ON/OFF length
Exponential
Exponential
ParetePareteShapeparameter
1.5
1.5

Rate atON period
6 Mbps
6 Mbps9 Mbps9 MbpsThere are 20 pairs of source and destination end hosts. Each end host on the left in Fig. 6 is asource and transfers packets by UDP to the corresponding destination end host on the right. User
flows are given as ON/OFF processes and categorized into the four types listed in TABLE 1;
there are five flows in each type.
Probe packet flows are categorized into the five types listed in TABLE 2. Note that Exponential and Deterministic in TABLE 2 are special cases of Gamma distribution, and parameters ofExponential and Deterministic are parameters of the Gamma distribution corresponding to eachprobe type. 300 flows of each type are streamed over the two routes shown in Fig. 6, so the total
number of probe packet flows in the network is 3000. To analyze the variance of the estimator,
we streamed a large number of probe packet flows. Of course, we can estimate the empiricaldelay from just one probe packet in each flow.
User flow packets and probe packets are 1500 bytes and 64 bytes, respectively. Link capacities are identical at 64 Mbps. Delay occurs mainly in the link between the core routers, since it
is a bottleneck, but no loss occurs, because there is suﬃcient buﬀering.
We observed the traﬃc by passive measurement at the queue of the edge router on the sourceside. Let δ denote 40 ms.
We ran the simulation for 500 s. The non-intrusive requirement (the eﬀect of probe packets
can be ignored) was satisfied, since the ratio of the probe stream to all streams is only 0.00197%
or so.
5.2. The convexity of ACF
In this subsection, we will discuss whether the ACF of the ground truth process Y(t) is convex.
Note that the ground truth process is treated as stochastic process Y(t), not sample path y(t).

/ Procedia Computer Science 00 (2010) 1–17

10

Table 2: Type of probe

autocovariance

Distribution of probe intervals
Exponential
Gamma
Gamma
Gamma
Deterministic (Periodic)

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
-0.1 05

Parameter β(β = 1)β=5
β = 25β = 125(β → ∞)

10
lag values [sec]Mean probe intervals
0.5 s
0.5 s
0.5 s
0.5 s
0.5 s

15

20

Figure 7: Autocovariance function (flow #1)

The ground truth process observed by CoMPACT monitor is given by equation (9). We
compute V(t), which is the virtual one-way delay, by using the queue occupancy (byte) of thecore router on the source side. In our simulation model, the greatest part of the delay occurs at
the core router on source side, because the link between the core routers is a bottleneck. Thus
we can ignore any delay at other routers.
The (standardized) ACF for c = 0.1 for flow #1 with 95% confidence intervals on 10 experiments is depicted in Fig. 7. To plot Fig. 7, we used data where the queue occupancy and the traﬃcwere recorded every 0.01 seconds. Representing each flow type, we also plotted flows #6, #11
and #16. This permitted the conclusion that none of these results contradicted the assumptionthat ACF is convex.
5.3. One-way delay distribution
In this subsection, we will show that CoMPACT monitor can estimate the empirical one-way
delay by using Gamma-probing. The estimation of the complementary cumulative distributionfunction (CDF) of the one-way delay experienced by user flows (as given by equation (2)) will
be shown below. Note that v(t) and a(t) are both sample paths in equation (2).
To estimate the complementary CDF of the one-way delay experienced by flow #1, we usedprobe packet flows with parameter β = 1, 25 and β → ∞. Note that β = 1 corresponds totraditional PASTA-base probing. Each result, with 95% confidence intervals, is shown in Fig. 8.
Note that the horizontal axis, which is the one-way delay, corresponds to c in equation (2). To
compare the empirical delay with the estimate from CoMPACT monitor, we include the estimate
from active measurement in the plot.

/ Procedia Computer Science 00 (2010) 1–17

parameter=1
1
complementary CDF

11empirical delay
CoMPACT
active

0.1

0.01
0

0.2

0.4
one-way delay [sec]parameter=infinity

parameter=25
1
empirical delay
CoMPACT
active0.1

0.01

complementary CDF

1complementary CDF

0.6

empirical delay
CoMPACT
active

0.1

0.01
0

0.2

0.4
one-way delay [sec]

0.6

0

0.2

0.4

0.6

one-way delay [sec]Figure 8: The estimation of comprementary CDF (flow #1)

In Fig. 8, we can see that the CoMPACT monitor gives good estimates of the true value. We
cannot judge the superiority or inferiority of any type of probe packet flows. Representing eachflow type, we have plotted for flows #6, #11 and #16 and similar results are gained.
5.4. Accuracy Improvement of CoMPACT monitor
In this subsection, we will verify the relationship between the parameter of Gamma distribution, used as the inter-probe time, and the variance of estimator. Note that we consider thevariance of p̂, which depends only on probe packet timing (namely, sampling time T n ).
We plot the standard deviation of each point of the complementary CDF (shown in subsection 5.3) in Fig. 9. Note that the horizontal axis corresponds to the one-way delay, which is cin equation (2). Error bars indicate the 95% confidence intervals when the standard deviation
calculated from 30 probe packet flows is considered to be a single data point.
The standard deviation clearly decreases as β increases from β = 1 to β = 125. Note thatβ = 1 corresponds to traditional PASTA-base probing. In periodic-probing, i.e. β → ∞, thestandard deviation is often larger than that with β = 125 or β = 25. Our belief is that this reversal
is a sign of the phase-lock phenomenon, which occurs when the cycle of the ground truth process
corresponds to the cycle of the probing process. In section 6, we verify phase-lock phenomenon
in detail. We got similar results for other flows though Fig. 9 shows only the results of flow #1
and #11.
Consequently, it was confirmed that we can obtain adequate accuracy on variance, which
depends only on sampling time T n with a suboptimal probing process, if we tune the parameterof Gamma distribution, which is used as the inter-probe time.

/ Procedia Computer Science 00 (2010) 1–17

flow ID#11
parameter=1
parameter=5

standard deviation

standard deviation

flow ID#1
0.02
0.018
0.016
0.014
0.012
0.01
0.008
0.006
0.004
0.002
0

parameter=25
parameter=125
parameter=infinity

0

0.2

0.4

0.6

12

0.8

1

0.016
0.014
0.012
0.01
0.008
0.006
0.004
0.002
0

1.2

parameter=1
parameter=5
parameter=25
parameter=125
parameter=infinity

0

one-way delay [sec]0.5
one-way delay [sec]1

Figure 9: Standard deviation of estimator

5.5. The upper bounds of variance
Supplementing the simulation results in previous subsection, we prove that periodic-probing
is assuredly superior to the traditional PASTA-based probing.
Let us idealize the traﬃc process a(t) as an ON/OFF process. We assume a(t) is the binary
process which takes value α if the target flow streams, and 0 otherwise. Thus p̂ is expressed by
p̂ =

m
"

m
"
α · 1{a(Tn )>0}
a(T n )
1{v(Tn )>c} &m=
1{v(Tn )>c} &m
l=1 a(T l )l=1 α · 1{a(T l )>0}
n=1
n=1
&m
1{v(T )>c∧a(Tn )>0}
= n=1&m n.
l=1 1{a(T l )>0}

(11)

Since UDP does not control the volume of traﬃc, this assumption is appropriate for UDP flows.
Now, we consider the range of equation (11). 1{v(t)>c∧a(t)>0} and 1{a(t)>0} are the binary processes, and we can divide them into the periods in which the processes take 0 and 1. If they areobserved by periodic-probing, the diﬀerence between the maximum and minimum observation
frequency is 1 at most in one period (see Fig. 10).
The maximum range ∆ of equation (11) is given by∆=k2,
mq − k1(12)

where k1 and k2 denote the number of periods of 1{a(t)>0} = 1 and 1{v(t)>c∧a(t)>0} = 1, respectively,
and q denotes the time average of 1{a(t)>0} .
The distribution that has maximum variance with range ∆ has the following pdf h(x).
h(x) =11
δ(x − a) + δ(x − a − ∆),22where δ(·) denotes Dirac δ function and a is an arbitrary constant. Therefore, the upper boundsof estimator variance are as follows.
- .2∆
Var[ p̂] ≤
2
=

k2 2
.
4(mq − k1 )2(13)

/ Procedia Computer Science 00 (2010) 1–17

13

Figure 10: The observation frequency of periodic-probing

flow ID#16
parameter=1
parameter=infinity
upper bound(infinity)

0

0.2

0.4

0.6

0.8

one-way delay [sec]1

1.2

standard deviation

standard deviation

flow ID#1
0.02
0.018
0.016
0.014
0.012
0.01
0.008
0.006
0.004
0.002
0

0.1
0.09
0.08
0.07
0.06
0.05
0.04
0.03
0.02
0.01
0

parameter=1
parameter=infinity
upper bound(infinity)

0

0.5
one-way delay [sec]1

Figure 11: The upper bounds of periodic-probing

Calculating k1 , k2 and q in the above simulation, we plot the upper bounds of periodicprobing in Fig. 11. Note that standard deviations of PASTA-based probing and periodic-probing(the same data as plotted in Fig. 9) are displayed.
The results of flow #1 confirm that the upper bounds of periodic-probing are smaller than
the standard deviation of PASTA-based probing in the domain of interest (the domain with large
delay). Therefore, it is guaranteed that periodic-probing is surely superior to PASTA-based probing. The results of flows #6, #11 (not displayed in Fig. 9) are similar to the results of flow #1.
The results of flow #16 show that the upper bounds of periodic-probing are larger than
the standard deviation of PASTA-based probing because the combination of flow type 4 (e.g.
flow #16) and equation (13) is bad. The type 4 flows have short ON periods and long OFF periods as shown in TABLE 1. Thus the maximum range given by equation (12) becomes large
because the denominator becomes small. Therefore, the appropriate upper bounds cannot begiven by equation (13).
6. Phase-lock phenomenon
In this section, we will discuss the phase-lock phenomenon in sample path observation. We
will show that the accuracy reversal between periodic-probing (β → ∞) and Gamma-probing(β = 125) in Fig. 9 occurs because periodic-probing locks the phase of the ground truth process.

/ Procedia Computer Science 00 (2010) 1–17
Periodic-probing

14

Gamma-probing (beta=125)
0.01

0.000025

0.01

0.00002

0.008
0.007

0.000015

0.006
0.005

0.00001

0.004
0.003

0.000005

0.002

0.009
Power
(Power spectrum)
Variance of estimation(CoMPACT monitor)

Variance of estimation(CoMPACT monitor)

0.009
0.00002

0.008
0.007

0.000015

0.006
0.005

0.00001

0.004
0.003

0.000005

0.002

0.001
0
970

980

990

1000

1010

1020

Phase (Number of probe packets)
CoMPACT monitor (Periodic)

Power spectrum

0
1030

Power
(Power spectrum)

0.000025

0.001
0
970

980

990

1000

1010

1020

0
1030

Phase (Number of probe packets)
CoMPACT monitor (beta=125)

Power spectrum

Figure 12: Power spectrum and variance of estimator

Convex ACF means that the ground truth process does not have any specific periodicity. If the
ACF is strictly convex, the variance of estimator with periodic-probing is minimum as describedin section 3.
However, there is the possibility that sample path y(t) has, over a finite interval, accidental
periodicity, even if the ACF of the ground truth process Y(t) is convex. This is because thesample path over a finite interval fails to well represent the characteristics of the corresponding stochastic process. Namely, it is possible that the sample path has, over a short time, somespecific periodicity by chance, even if there is no specific periodicity over the long term. This
accidental periodicity destroys the convexity of ACF with regard to the time average and thus
causes the phase-lock phenomenon. If the interval in which we want to measure QoS is suﬃciently long, the phase-lock phenomenon will not happen because the ACF of y(t) over the longterm converges on the ACF of Y(t) in the meaning of ensemble mean (we must assume that Y(t)is ergodic). Therefore, the phase-lock phenomenon is possible with finite observation intervals.
To verify the relation between accidental periodicity and accuracy, we altered the simulation
described in section 5. All conditions were unchanged except for the characteristics of probe
packets which were altered as follows. The parameter of inter-probe time was set at β → ∞(periodic-probing) and β = 125. We examined probe packets with 61 diﬀerent inter-probe times(namely 61 kinds of periodicity). Mean number of probe packets in the 500 s simulation (corresponding to m) ran from 970 to 1030 (e.g. if mean number of probe packets is 1000, the meaninter-probe time is 500 s / 1000 packet = 0.5 s).
We estimated one-way delay by probe packet flows which have 61 kinds of periodicity, andcompared the variance of estimator with the power spectrum of the sample path over the simulation time |F [y(t)]|2 (0 ≤ t < 500) (F [·] denotes Fourier transform and power spectrum refers to
the energy of each frequency component). The result for flow #1 is shown in Fig. 12. Note that
we used 0.1s as the threshold of one-way delay c.
We can see that periodic-probing yields high estimator variance at the points with strong
periodicity, which is indicated by power spectrum of finite time sample path. On the other hand,variance of estimator by Gamma-probing does not depend on the power spectrum. Therefore,
the phase-lock phenomenon, which happens because probing locks due to accidental periodicity
within a finite time sample path, was confirmed even if the ACF of the ground truth process isconvex (namely the ground truth process does not have any specific periodicity).

traffic[packets/40ms]/ Procedia Computer Science 00 (2010) 1–17

15

UDP
100
50
0
0

20

40

60

80

100

60

80

100

traffic[packets/40ms]

time [sec]
TCP
100
50
0
0

20

40
time [sec]

$
"#,
"#+
"#*
"#)
"#(
"#'
"#&
"#%
"#$
"
!"#$ "#
2&45/(4('6+7,-89:.289691.:;.<63

Figure 13: Traﬃc process

(

$"

$(

%"

-./01.-234054367

Figure 14: Autocovariance function in the case of TCP(45;7;2+/-.(/+,
8&<=>8?
+26;@(

!"#

!"!#
!"!

!"#

!"$

!"%

&'()*+,-.(/+,-01(23Figure 15: The estimation in case of TCP

7. Additional simulation
We used UDP flows in the simulation of section 5, but we also simulated the network carrying
TCP flows. We used the same conditions as used in section 5, expect for replacing UDP flows
with TCP flows. 300 packets was specified as the maximum window size.
In the case of TCP, user traﬃc is strongly aﬀected by TCP traﬃc control. Therefore, theobserved traﬃc of a TCP flow can diﬀer greatly depending on the timing of the sampling, unlike
UDP. A key characteristic of this simulation is that user traﬃc is very unstable (see Fig. 13).
Comparing these results with those from the UDP simulation allows us to confirm whether
Gamma-probing can be applied to flows with unstable traﬃc, or not.
In fact, we were able to confirm that the ACF of the ground truth process was convex andthat the estimator converged on the true value, as in the UDP simulation. The ACF for c = 0.1
for flow #11 with 95% confidence intervals taken over 15 experiments is depicted in Fig. 14. The
result of the estimation for flow #16 by using probe packets with parameter β = 25 is shown in
Fig. 15. The traﬃc control of TCP has no negative eﬀect on the convexity of ACF.
However, the standard deviation of the estimator was slightly diﬀerent from that in the UDP
simulation. Fig. 16 shows a plot of the standard deviation of each point versus the corresponding CDF point. The error bars indicate 95% confidence intervals with the standard deviation
calculated from 30 probe packet flows taken to be a single datum, as in the UDP simulation.

/ Procedia Computer Science 00 (2010) 1–17
flow ID#11

flow ID#1

standard deviation

0.02
0.015

standard deviation

parameter=1
parameter=5
parameter=25
parameter=125
parameter=infinity

0.025

0.01
0.005
0
0

0.1

16

0.2
0.3
one-way delay [sec]

0.4

0.04
0.035
0.03
0.025
0.02
0.015
0.01
0.005
0

parameter=1
parameter=5
parameter=25
parameter=125
parameter=infinity

0

0.1

0.2
one-way delay [sec]

0.3

0.4

Figure 16: Standard deviation of estimator in the TCP caseWe can confirm that there is no significant diﬀerence. There is a tendency to decrease fromβ = 1 to β = 125, but confidence intervals overlap each other. This overlap is caused by traﬃcinstability. The variance of estimator is not steady when the target flow has strongly variable
traﬃc. To stabilize the variance of estimator, we should set a longer observation period comparedto the UDP case. However, we can well judge the tendency as regards the accuracy improvementfrom Fig. 16.
Now let us focus on β → ∞ (corresponding to periodic-probing) in Fig. 16. The phase-lockphenomenon can be observed quite clearly by comparing these results with those of the UDP
simulation. A clear reversal of the standard deviation is observed only with periodic-probing.
This is the same as in the UDP simulation, though the reversal does not always happen. This
result proves that periodic-probing is not optimal, even when the variance depends only on probe
packet timing.
8. Conclusion
In a non-intrusive context where the eﬀect of probe packets can be ignored, it was confirmedthat the accuracy of estimating the complementary CDF of one-way delay can be improved byusing Gamma-probing as part of determining CoMPACT monitor estimates. This means that theGamma-probing proposed in [16] can be useful added to CoMPACT monitor for estimating thetime average of sample paths.
The requirement that assures the achievement of accuracy improvement was clarified. [16]assumed that the ACF of a stochastic process taken to express the network state is convex. Using
CoMACT monitor, we elucidated the stochastic process that expresses the network state and wereable through simulations to confirm that its ACF is convex. The stochastic process observed by
CoMPACT monitor depends on the traﬃc process of the observed flow. Compared to simple
delay/loss processes, which are influenced by all traﬃc in the network, the traﬃc process of a
specific flow sometimes exhibits periodicity. When we apply Gamma-probing to a real network,
the convexity of ACF requires special attention because periodicity can destroy the convexityof ACF. The convexity contributes to the accuracy improvement possible when we estimate not
only the ensemble mean of stochastic processes but also the time average of sample paths.
We have not addressed the issue of how to tune parameter β of Gamma-probing and it remains
as a key future task.

/ Procedia Computer Science 00 (2010) 1–17

17

References[1] CAIDA: The Cooperative Association for Internet Data Analysis http://www.caida.org/.
[2] V. Paxson, J. Mahdavi, A. Adams, M. Mathis, An architecture for large scale internet measurement, IEEE Communications Magazine 36 (8) (1998) 48–54.
[3] J. Bolot, Characterizing End-to-End Packet Delay and Loss in the Internet, Journal of High Speed Networks 2(1993) 305–323.
[4] V. Paxson, End-to-end Internet packet dynamics, IEEE ACM Trans Networking 7 (3) (1999) 277–292.
[5] S. Savage, A. Collins, E. Hoﬀman, J. Snell, T. Anderson, The end-to-end eﬀects of Internet path selection, ACM
SIGCOMM Computer Communication Review 29 (4) (1999) 289–299.
[6] G. Almes, S. Kalidindi, M. Zekauskas, A one-way delay metric for IPPM, RFC2679 (1999).
[7] G. Almes, S. Kalidindi, M. Zekauskas, A one-way packet loss metric for IPPM, RFC2680 (1999).
[8] A. Pásztor, D. Veitch, High precision active probing for Internet measurement, in: Proceedings of INET 2001,
2001.
[9] V. Paxson, G. Almes, J. Mahdavi, M. Mathis, Framework for IP Performance Metrics, RFC2330 (1998).
[10] M. Jain, C. Dovrolis, End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation withTCP Throughput, in: Proceedings of ACM SIGCOMM 2002, 2002, pp. 295–308.
[11] M. Aida, N. Miyoshi, K. Ishibashi, A scalable and lightweight QoS monitoring technique combining passive andactive approaches, in: Proceedings of IEEE INFOCOM 2003, 2003, pp. 125–133.
[12] K. Ishibashi, M. Aida, S. Kuribayashi, Proposal and evaluation of method to estimate packet loss-rate using correlation of packet delay and loss, IEICE Transactions on Information and Systems E86-D (11) (2003) 2371–2379.
[13] M. Aida, N. Miyoshi, K. Ishibashi, A Change-of-Measure Approach to Per-Flow Delay Measurement Combining
Passive and Active Methods: Mathematical Formulation for CoMPACT Monitor, IEEE Transactions on Information Theory 54 (11) (2008) 4966–4979.
[14] R. Wolﬀ, Poisson arrivals see time averages, Operations Research 30 (2) (1982) 223–231.
[15] F. Baccelli, S. Machiraju, D. Veitch, J. Bolot, The role of PASTA in network measurement, ACM SIGCOMM
Computer Communication Review 36 (4) (2006) 231–242.
[16] F. Baccelli, S. Machiraju, D. Veitch, J. Bolot, On optimal probing for delay and loss measurement, in: Proceedingsof the 7th ACM SIGCOMM conference on Internet measurement, 2007, pp. 291–302.
[17] The Network Simulator – ns-2 http://moat.nlanr.net/.