2009 International Conference on Intelligent Networking and Collaborative Systems

Design of Probe Intervals to Improve Accuracy of CoMPACT Monitor
Kohei Watabe, Yudai Honma, and Masaki Aida
Tokyo Metropolitan University
6–6, Asahigaoka, Hino-shi 191-0065, Japan
Email: {watabe-kouhei, yudai, maida}@sd.tmu.ac.jp
it observes the actual trafﬁc. Passive measurement can be
categorized into two-point monitoring with data-matchingprocesses (to measure one-way delay etc.) and one-point
monitoring (to measure volume of trafﬁc etc.).
Passive measurement has the advantage of accuracy.
However if we perform passive measurement in large-scale
networks, the number of monitored packets is enormous andnetwork resources are wasted by gathering the monitored
data at a data center. Moreover, in order to measure delay,
it is necessary to determine the difference in arrival time ofa particular packet at different points in the network. Thisrequires searching for the same packet pairs monitored at thedifferent points in the monitored packet data. The passive
measurement lacks scalability due to this packet matching.
Active measurement monitors QoS by injecting probe
packets into a network path and monitoring them. Active
measurement can be used to measure one-way delay, RTT,
loss, etc. It cannot obtain the per-ﬂow QoS, though it is easy
for the end user to carry out. Unfortunately, the QoS dataobtained by active measurement does not represent the QoS
for user packets, but only QoS for the probe packets.
By complementary use of the advantages of active andpassive measurements, the authors propose a new techniqueof scalable measurement called change-of-measure-based
passive/active monitoring (CoMPACT monitor) to measure
per-ﬂow QoS [1], [2], [3], [4].
The idea of CoMPACT monitor is as follows. The direct
measurement of QoS of the target ﬂow by passive measurement is difﬁcult due to the scalability problem. So, we try
to obtain QoS of the target ﬂow by using a transformationof QoS data (obtained by active measurement). The transformation can be determined by passively monitored trafﬁcdata for the target ﬂow. The problem of scalability does notarise, because the volume of trafﬁc can be measured by onepoint passive measurement without requiring data-matchingprocesses.
We have believed Poisson arrivals (intervals according toexponential distribution) is appropriate to a policy of probe
packets arrivals since we can apply PASTA (Poisson Arrivals
See Time Averages) property to it.
However, recent work [5] indicates that many distributions
exist that are more accurate than an exponential distribution
if a non-intrusive context (ignoring the effect of probe packets) can be assumed. Moreover, we can ﬁnd a distribution

Abstract—We have proposed CoMPACT monitor that
achieves scalable measurement of one-way delay distribution
for each ﬂow. CoMPACT monitor is technique that transforms
one-way delay data obtained by active measurement by using
passively monitored trafﬁc data of the target ﬂow. In a recent
study, it was reported that by using an inter-probe timethat has a Gamma distribution can improve the accuracyof simple active measurement. The improvement is in termsof the ensemble mean of stationary stochastic process. In
this paper, to improve accuracy of CoMPACT monitor, weapply Gamma-probing as an active measurement of CoMPACT
monitor. The signiﬁcant issue in this application is in the
difference between objects to measure; CoMPACT monitor
estimates not the ensemble mean but the time average of sample
path. We investigate the characteristics of CoMPACT monitor
and Gamma-probing, and verify the accuracy improvement of
CoMPACT monitor through simulations.
Keywords-CoMPACT monitor, change-of-measure, Gamma
distribution, QoS measurement.

I. I NTRODUCTION
As the Internet has grown larger over the last several
years, it came to play an important role as infrastructure. Various applications provide new services including telephonyand live video, and the trafﬁc they stream exhibits complex
characteristics. These various applications require the various quality of service (QoS) that differs from traditional
e-mail and web browsing. Then, since the new application
will be developed in the future, the diversiﬁcation of QoS
requirements will progress even more.
In order to meet such varied requirements for network
control, we need a measurement technology to produce
detailed QoS information. Measuring the QoS for each ofmultiple ﬂows (e.g., users, applications, or organizations)is important since these are used as key parameters inservice level agreements (SLAs) between an Internet service
provider (ISP) and users. One-way packet delay is one of
the most important QoS metrics. This paper focuses on themeasurement of one-way delay for each ﬂow.
Conventional means of measuring QoS can be classiﬁed
into two types: passive and active measurements.
Passive measurement monitors the target user packet
directly, by capturing the packets, including the target information. Passive measurement is used to measure the volumeof trafﬁc, one-way delay, round-trip time (RTT), loss, etc.
and can get any desired information about the trafﬁc since
978-0-7695-3858-7/09 $26.00 © 2009 IEEE
DOI 10.1109/INCOS.2009.42

335

v(t)
c

Now, let us consider the situation that Xk cannot bedirectly monitored. Let Y denote a random variable thatis observed v(t) at a different timing (e.g. timing of probe
packet arrivals) independent of Xk . Then we consider the
relationship between Xk and Y .
Characters of Xk and Y are different if their timing
is different, even if they observe a common process v(t)(see Fig. 1). Xk and Y can be related by each distributionfunctions Fk and G, and P(Xk > c) expressed by measureof Xk can be transformed into measure of Y as follows.
P(Xk > c) = 1{x>c} dFk (x)dFk (y)dG(y)= 1{y>c}dG(y)dFk (Y )= EG 1{Y >c}dG(Y )∝ P(Y > c)

∝ dG(c)timing of Y
(2/10)∝ dFk (c)ttiming of Xk(4/10)

Figure 1.

The relation between timing of arrivals and empirical QoS

that is suboptimal in accuracy by selecting an inter-probe
time according to the parameterized Gamma distribution.
This paper conﬁrms that applying Gamma-probing to
CoMPACT monitor can improve the accuracy of measurement of one-way delay distribution for individual ﬂows.
The signiﬁcant issue in this application is in the difference
between objects to measure. In [5], the process observedby probe packets is assumed to be a stationary and ergodic stochastic process. So, the accuracy improvement isguaranteed only when we estimate the ensemble mean ofstationary stochastic process. However, CoMPCT monitor
estimates the time average of sample path. Therefore, weshould carefully investigate the characteristics of CoMPACT
monitor and Gamma-probing.
The rest of the paper is organized as follows. We describe
the summary of CoMPACT monitor in Section II. Next,
we brieﬂy summarize the theory of Gamma-probing foractive measurement, shown in [5], in Section III. Section IV
discusses the difference of objects we want to estimate
between Gamma-probing [5] and CoMPACT monitor. To
conﬁrm that CoMPACT monitor is able to be improvedin accuracy by Gamma-probing, we execute simulation in
Section V. We conclude the paper in Section VI.

Therefore, P(Xk > c) can be estimated bymdFk (Y (n))
1 ,1{Y (n)>c}m n=1
dG(Y (n))(1)

for sufﬁciently large m, where Y (n) (n = 1, 2, · · · , m)denote the nth observed value. Note that this estimator
does not need to monitor the timing of Xk , if we can getdFk (Y (n))/dG(Y (n)). This means the QoS of a speciﬁc
ﬂow (as decided by k) can be estimated by just one probe
packet train that arrives with a timing of Y .
In the following, we brieﬂy summarizes the mathematicalformulation of CoMPACT Monitor [4]. We assume the
trafﬁc in the target ﬂow can be treated as a ﬂuid. In otherwords, we assume packets of the target ﬂow are more
numerous than active probe packets.
Let a(t) and v(t), respectively, denote the trafﬁc in thetarget ﬂow at time t and the virtual one-way delay on
the path that we want to measure. a(t) and v(t) are anonnegative deterministic processes assumed to be rightcontinuous with left limits and bounded on t ≥ 0. We canconsider a(t) and v(t) are sample paths of corresponding
stochastic processes.
Considering to measure the empirical one-way delay
distribution π(c), the value we want to measure is the ratio
to all trafﬁc of the target ﬂow of trafﬁc for which the delay
to exceeds c, which is given byt
1{v(s)>c} a(s)ds.
(2)π(c) = lim 0  tt→∞a(s)ds0

II. S UMMARY OF C O MPACT MONITOR
CoMPACT monitor estimates an empirical QoS for thetarget ﬂow by converting observed values of network performance at timing of probe packet arrivals into a measureof the target ﬂow timing. Now, let v(t) denote the network
process under observation (e.g. the virtual one-way delay attime t), and Xk denote a random variable which is observedv(t) with a certain timing (e.g. the timing of user packet
arrivals). The probability for Xk to exceed c isP(Xk > c) = 1{x>c} dFk (x) = EFk [1{x>c} ]This can be estimated through m times monitoring bym

Zm (c) =where Fk (x) is the distribution function of Xk .
If we can directlym monitor Xk , its distribution can be
estimated by
n=1 1{Xk (n)>c} /m, where Xk (n) (n =1, 2, · · · , m) denote the nth observed value.

a(Tn )1 
1{v(Tn )>c} mm n=1
l=1 a(Tl )/m(3)

for sufﬁciently large m (see [4] for details), where Tn(n = 1, 2, · · · , m) denotes the nth sampling time, and eachtime of sampling corresponds to a time of probe packet
336

Then variance of p̂ ism1
Y (Tn )
Var[p̂] = 2 Varmn=1arrival. Active and one-point passive measurement are used
respectively to observe v(Tn ) and a(Tn ). Note that onepoint passive measurement can be conducted very easily
here, compared with two-point passive measurement formeasuring the one-way delay.
m
If we extract the quantity n=1 1{v(Tn )>c} /m from (3),this quantity is a simple active estimator that counts thepackets for 
the delay to exceeds c. However, (3) is weightedmby a(Tn )/( l=1 a(Tl )/m), which is decided by the trafﬁcin the target ﬂow when probe packets arrive. This meansthat the one-way delay distribution (measured by active measurement without bias) is corrected to the empirical one-way
delay distribution by the bias of thetarget ﬂow (observedmby passive measurement). a(Tn )/( l=1 a(Tl )/m) in (3)corresponds to dFk (Y (n))/dG(Y (n)) in (1).

=

n=l

2 
1
= Var[Y (0)] + 2
m
m

m

 t

f (Y (t))dt0= E[f (Y (0))]

a.s.,

(4)

where f is an arbitrary positive function and the second
equality follows from the stationary and ergodicity of thetarget process Y (t). [6] proved (4) and named this property
NIMASTA (Non-Intrusive Mixing Arrivals See Time Averages).
Mixing is the requirement to guarantee jointly ergodicity between probe packet process and the target process.
For example, there are processes whose intervals obey theGamma distribution, the uniform distribution, etc [6]. Notethat periodic-probing, with determinate intervals is not a
mixing process, and does not satisfy (4).
The recent study [5] also reported that NIMASTA-based
probing is suitable for measurement. That provides an improvement in the accuracy of the measurement. We canselect a suboptimal probing process in terms of accuracy
under the speciﬁc assumption by using an inter-probe time
given by the parameterized Gamma distribution.
If we estimate the mean of Y (0) by using active measurement, estimator p̂ isg(x) =1 
Y (Tn ).
m n=1

(7)

xβ−1
Γ(β)

β
μ

β

e−xβ/μ(x > 0),(8)

where g(x) is the Gamma distribution whose shape and scaleparameters are β and μ/β, respectively. μ denotes the mean,and β is the parameter. When β = 1, g(x) reduces to the
exponential distribution. When β → ∞, the policy reduces
to periodic-probing because g(x) converges on δ(x − μ).
If the autocovariance function is convex, it is proven thatvariance of estimator p̂ sampled by intervals according to(8) monotonically decreases with increase of β. This iscaused by decrease of the covariance part that is the second
term on the right-hand side of (7). We can achieve nearoptimal variance of periodic-probing, since (8) corresponds
to periodic-probing towards limit β → ∞.
The problem of incorrectness due to phase-lock phenomenon can be avoided if we tune β to a limited value (thisgamma-probing satisfy the mixing assumption). We can get
a suboptimal probing if we give β an appropriate value.
IV. T HE APPLICATION TO C O MPACT MONITOR
This section discusses the application of Gamma-probing
to CoMPACT monitor. Comparing (5) with (3), we can con-

m

p̂ =

R(τ )f|n−l| (τ )dτwhere fk is probability density function (pdf) of Tk , R(τ ) =Cov (Y (t), Y (t − τ )) is the autocovariance function of thetarget process Y (t) and the last equality follows from thestationary of Y (t) and probe packet process.
If R(τ ) is convex, the following can be proven byusing Jensen’s inequality. No other probing process with anaverage interval of μ has a variance that is lower than that ofperiodic-probing (see [5]). A lower variance of the estimatoris connected with accuracy. Therefore, periodic-probing is
the best policy if we focus only on variance.
On the other hand, periodic-probing does not satisfy theassumptions of NIMASTA due to non-mixing, so periodicprobing is not necessarily the best. This is because a phaselock phenomenon may occur and the estimator may converge
on a false value when the cycle of the target process
corresponds to the cycle of the probing process.
To tune the tradeoff between traditional PASTA-based
probing and periodic-probing, [5] proposes a suboptimal
policy that gives an inter-probe time that obeys the parameterized Gamma distribution. The pdf that is used as theintervals between probe packets is given by

Since the PASTA property is good for non-biased measurement, Poisson arrivals have been widely used as policyof probe packets arrivals for active measurement. However,
if arrival process of the probe packets is stationary and mixing, under non-intrusive conditions, the following equation
holds and we can also ignore the effects of probe packets
under non-intrusive conditions.
1 
1f (Y (Tn )) = lim
m→∞ m
t→∞ t
n=1

(6)



n=l

III. S UBOPTIMAL PROBE INTERVALS

lim

m
1 
2 
Var[Y (Tn )] + 2
Cov (Y (Tn ), Y (Tl ))
2
m n=1
m

(5)

337

sourcerouterhost of user ﬂow
route of probe packets

10 host10 host10 host10 hostFigure 2.

tends to decrease with increase of β. Then variance of interprobe time given by (8) is μ2 /β, and decreases with increaseof β. Hence, we can also expect that the variance part thatis the ﬁrst term on the right-hand side of (10) decreases
with increase of β since each observed value y(Tn ) is notvaried. In Section V, we present the result of simulationthat variance of estimator which depends only on Tn also
decreases with increase of β by using Gamma-probing.

destination

Network model

V. T HE EFFECTIVENESS OF G AMMA - PROBING
A. Simulation modelsider that stochastic process Y (t) observed by CoMPACT
monitor isA(t)Y (t) = 1{V (t)>c},(9)
E[A(t)]

We investigated the effectiveness of Gamma-probing in
the framework of CoMPACT monitor. The network model
we used in the simulation is shown in Fig. 2.
There are 20 pairs of source and destination end hosts.
Each source end host transfers packets by UDP to thecorresponding destination end host. User ﬂows are given as
ON/OFF processes and categorized into the four types listed
in TABLE I, with there are ﬁve ﬂows in each type.
Probe packet trains are categorized into the ﬁve types
listed in TABLE II. Note that Exp and periodic in TABLE II
are special cases of Gamma distribution, and parameters of
Exp and periodic are parameters of the Gamma distribution
corresponding to each probing. 300 trains of each type are
streamed on the two routes shown in Fig. 2, so the total
number of probe packet trains in the network is 3000. To
analyze the variance of the estimator, we streamed a large
number of probe packet trains. Of course we can estimate
the empirical delay from only one probe packet train.
User ﬂow 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 corerouters, since it is a bottleneck, but no loss occures, because
there is sufﬁcient buffering.
Our simulation model is simple. However, we have conﬁrmed that CoMPACT monitor (without Gamma-probing)is effective in an actual environment. Therefore, this model
is enough to conﬁrm the combination between CoMPACT
monitor and Gamma-probing.
We ran the simulation for 500 s. The non-intrusive requirement was satisﬁed, since the ratio of the probe packet
trafﬁc (bytes) to all trafﬁc (bytes) is about 0.00197%.

where V (t) and A(t) are stochastic processes corresponding
to sample path v(t) and a(t), respectively. If it is conﬁrmedthat the autocovariance function R(τ ) of stochastic process
Y (t) is convex, we can guarantee accuracy improvement due
to Gamma-probing by applying the theory in Section III.
The convexity of the autocovariance function has beveriﬁed in cases of simple virtual delay process and loss
process by data of large-scale passive measurement andsimulations [5]. However, Y (t) observed by CoMPACT
monitor is weighted by trafﬁc A(t) of a speciﬁc ﬂow, so theproperty of Y (t) obviously differs from delay/loss processes
that are inﬂuenced by all ﬂows on the network. Therefore,
we must conﬁrm the convexity of R(τ ) in the CoMPACT
monitor case. In Section V, we will show that the assumption(R(τ ) is convex) is appropriate to CoMPACT monitor.
As described in Section II, we consider v(t) and a(t)are sample paths of corresponding stochastic processes(without stationary and ergodicity) since CoMAPCT monitor
estimates the time average of sample path given by (2).
However, as explained in Section III, the target process
Y (t) is stationary stochastic process [5], and the decreaseof variance of p̂ is guaranteed for the estimation of theensemble mean of Y (t). The variance of p̂ depends on
both stochastic variations of Y (t) and Tn . 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 ﬂows.
Therefore, it is desired in CoMPACT monitor that variance of estimator p̂ which depends only on sampling time
Tn on certain sample path rather than Y (t) decreases. In
other words, variance we want to decrease is given by
Var[p̂] =B. The convexity of the autocovariance function
In this subsection, we will discuss whether the autocovariance function of the target process Y (t) is convex. Notethat target process is treated as not sample path y(t) but
stochastic process Y (t).
The (standardized) autocovariance function for c = 0.1 forﬂow #1 with 95% conﬁdence intervals by 10 experiments is
depicted in Fig. 4. To represent at each ﬂow type, we plotted
ﬂows #6, #11 and #16. This permitted the conclusion thatnone of these results contradicted the assumption that the
autocovariance function is convex.

m
2 
1 
Var[y(Tn )] + 2
Cov(y(Tn ), y(Tl )).
2
m n=1
m
n=l

(10)
Note that (10) corresponds to (6). If the autocovariance function of Y (t) is convex, we can consider that the covariancepart that is the second term on the right-hand side of (10)338

Table II
T YPE OF PROBING

Table IT YPE OF USER FLOWS
Mean ON/OFF
period10s/5s
5s/10s
5s/10s1s/19scomplementary CDF

1Distribution of
ON/OFF length
Exp
Exp
ParetePareteempirical delay
CoMPACT
active0.1

Shapeparameter
1.5
1.5

Distribution of intervals
Exp
Gamma
Gamma
Gamma
PeriodicRate atON period
6 Mbps
6 Mbps9 Mbps9 Mbps1
empirical delay
CoMPACT
active
0.1

0.01

0.01
0

0.2

0.4
one-way delay [sec]Figure 3.

0.6

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

Mean probe interval
0.5 s
0.5 s
0.5 s
0.5 s
0.5 s

1
complementary CDF

Flow
ID
#1-5
#6-10
#11-15#16-20complementary CDF

Flow
type
type 1
type 2type 3type 4

empirical delay
CoMPACT
active

0.1

0.01
0

0.2

0.4

0.6

0

0.2

one-way delay [sec]

0.4

0.6

one-way delay [sec]The estimation of complementary CDF for (Left) β = 1, (Middle) β = 25 and (Right) β → ∞ (ﬂow #1)

C. One-way delay distribution

with a suboptimal probing process if we tune the parameterof Gamma distribution that we use as the inter-probe time.

In this subsection, we show that CoMPACT monitor canestimate the empirical one-way delay when using Gammaprobing. The estimation of the complementary cumulative
distribution function (CDF) of the one-way delay experienced by user ﬂows (as given by (2)) will be shown below.
Note that v(t) and a(t) are both sample paths in (2).
To estimate the complementary CDF of the one-way delay
experienced by ﬂow #1, we use probe packet trains withparameter β = 1, 25 and β → ∞ respectively. Each resultis shown in Fig. 3. To compare the empirical delay with theestimate from CoMPACT monitor, we include the estimate
from active measurement in the plot.
In Fig. 3, we can see that the CoMPACT monitor gives
good estimates of the true value. We cannot judge thesuperiority or inferiority of any type of probe packet trains.
To represent each ﬂow type, we have plotted for ﬂows #6,#11 and #16, getting results similar to Fig. 3.

E. The upper bounds of variance
Adding to the simulation results in previous subsection,
we prove that periodic-probing is surely more superior than
the traditional PASTA-based probing.
Let us idealize the trafﬁc process a(t) to ON/OFF process.
We assume a(t) is the binary process which takes a value
α if the target ﬂow streams, and 0 otherwise. Then p̂ isexpressed bym
a(Tn )
1{v(Tn )>c} mp̂ =l=1 a(Tl )n=1m1{v(T )>c∧a(Tn )>0}
m n
.
(11)
= n=1
l=1 1{a(Tl )>0}
Since UDP does not control the volume of trafﬁc, theassumption is appropriate to the UDP ﬂow.
Now, we consider the range of (11). 1{v(t)>c∧a(t)>0} and1{a(t)>0} are the binary processes, and we can divide theminto the periods of 0 or 1. If they are observed by periodicprobing, the difference between the maximum and minimum
observation frequency is 1 at most in one period (see Fig. 6).
The maximum range Δ of (11) is given by
k2
Δ=
,
(12)
mq − k1
where k1 denote the number of periods of 1{a(t)>0} = 1,
q denote the time average of 1{a(t)>0} and k2 denote thenumber of periods of 1{v(t)>c∧a(t)>0} = 1.
The distribution that has the maximum variance with therange Δ has pdf h(x) = δ(x−a)/2+δ(x−a−Δ)/2, whereδ(·) is Dirac δ function and a is an arbitrary constant. Hence,
the upper bounds of estimator variance is as follows.

D. Accuracy Improvement of CoMPACT monitor
In this subsection, we verify the relationship between theparameter β and the variance of estimator. Note that we
consider the variance of p̂ which depends only on probe
packets timing (namely, sampling time Tn ).
We plot the standard deviation of each point of thecomplementary CDF in Fig. 5. Error bars indicate the 95%
conﬁdence interval when the standard deviation calculated
from 30 probe packet trains is considered to be a single data
point.
The standard deviation clearly decreases as β increases
from β = 1 to β = 125. In periodic-probing corresponding
to β → ∞, the standard deviation is often larger than thatfor β = 125 and 25. This reversal is a sign of the phase-lock.
Hence, it is conﬁrmed that we can obtain adequate accuracy on variance which depends only on sampling time Tn

Var[p̂] ≤

339

Δ
2

2

=

k2 2
.
4(mq − k1 )2

(13)

5

10
lag values [sec]

15













    !



20standard deviation

frequency is 5
(min)



Figure 5.

the periods of 1
the periods of 0









0.08
0.07
0.06

parameter=1
parameter=5
parameter=25
parameter=125
parameter=in#nity

0.05
0.04
0.03
0.02
0.01
0



0

  

Autocovariance function (ﬂow #1)

frequency is 6
(max)

standard deviation

0.02
0.018
0.016
0.014
0.012
0.01
0.008
0.006
0.004
0.002
0

parameter=1
parameter=in$nity
upper bound(in$nity)

0

Figure 6.
The max/min observation frequency of periodic-probing

0.2

0.4

0.6

0.8

one-way delay [sec]Figure 7.

0.5
one-way delay [sec]1Standard deviation of estimator for (Left) ﬂow #1 and (Right) ﬂow #16

1

1.2

standard deviation

Figure 4.



autocovariance

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
-0.1 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=in(nityupper bound(in(nity)

0

0.5
one-way delay [sec]1

The upper bounds of periodic-probing for (Left) ﬂow #1 and (Right) ﬂow #16

Calculating k1 , k2 and q in above simulation, we plot
the upper bounds of periodic-probing in Fig. 7. Note thatstandard deviations of PASTA-based probing and periodicprobing (the same data as we plot in Fig. 5) are displayed.
In results of ﬂow #1, #6 and #11, we can conﬁrm that theupper bounds of periodic-probing are smaller than standard
deviation of PASTA-based probing in the domain of interest(the domain with large delay). Therefore, it is guaranteedthat periodic-probing is surely more superior than PASTAbased probing.
In result of ﬂow #16, the upper bounds of periodicprobing are larger than standard deviation of PASTA-based
probing because the combination of ﬂow type 4 (e.g.
ﬂow #16) and (13) is bad. The ﬂows of type 4 has short
ON periods and long OFF periods as shown in TABLE I.
So the maximum range given by (12) becomes large because
the denominator becomes small. Therefore, the appropriate
upper bounds cannot be given by (13).

ACKNOWLEDGEMENTS
A part of this research was made possible by the funds
provided by the Grant-in-Aid for Scientiﬁc Research (S)No. 18100001 (2006–2010) from the Japan Society for the
Promotion of Science.
R EFERENCES[1] K. Ishibashi, T. Kanazawa, M. Aida and H. Ishii,“Active/passive combination-type performance measurement
method using change-of-measure framework,” Computer Communications, Elsevier Science, vol. 27, no. 9, pp. 868-879, Jun.
2004.
[2] M. Aida, K. Ishibashi, and T. Kanazawa, “CoMPACT-Monitor:
Change-of-measure based passive/active monitoring–Weighted
active sampling scheme to infer QoS,” in Proc. IEEE SAINT
2002 Workshops, Nara, Japan, Feb. 2002, pp. 119–125.
[3] M. Aida, N. Miyoshi, and K. Ishibashi, “A scalable andlightweight QoS monitoring technique combining passive andactive approaches–On the mathematical formulation of compact monitor,” in Proc. IEEE INFOCOM 2003, San Francisco,
CA, Apr. 2003, pp. 125–133.

VI. C ONCLUSION
In a non-intrusive context where the effect of probe
packets can be ignored, it was conﬁrmed that the accuracyof estimating the complementary CDF of one-way delay canbe improved by using Gamma-probing as part of applying
CoMPACT monitor estimates. This means that Gammaprobing proposed in [5] is able to apply to CoMPACT
monitor that estimates the time average of sample path.
Then, we were able to conﬁrm that the autocovariancefunction of process observed by CoMACT monitor is convex. The convexity contributes to the accuracy improvement
when we estimate not only the ensemble mean of stochastic
process but also the time average of sample path.

[4] M. Aida, N. Miyoshi and K. Ishibashi, “A change-of-measureapproach to per-ﬂow delay measurement systems combining
passive and active methods: On the mathematical formulationof CoMPACT monitor,” IEEE Transactions on Information
Theory, vol. 54, no. 11, pp. 4966-4979, Nov. 2008.
[5] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “On optimal
probing for delay and loss measurement,” in Proc. Int. Measurement Conf. ’07, San Diego, CA, Oct. 2007, pp. 291–302[6] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “The role of
PASTA in Network Mesurement,” in Proc. ACM SIGCOMM
2006, Pisa, Italy, Sep. 2006, pp. 231–242.

340