2009 Ninth Annual International Symposium on Applications and the Internet

Veriﬁcation of Accuracy Improvement for CoMPACT Monitor
Due to Suboptimal Inter-probe TimeKohei Watabe Yudai Honma and Masaki Aida / Graduate School of System Design
dept. Management Systems Engineering
Tokyo Metropolitan University,
Hino-shi, Japan{watabe-kouhei, yudai, maida}@sd.tmu.ac.jp

Abstract

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
the different points in the monitored packet data. This packet
matching process lacks scalability, so passive measurement
lacks scalability.
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].
The idea of CoMPACT monitor is as follows. The direct measurement of the one-way delay distribution of thetarget ﬂow by passive measurement is difﬁcult due to thescalability problem. So, we try to obtain the one-way delay
distribution of the target ﬂow by using a transformation of
one-way delay data obtained by active measurement. The
transformation can be determined by passively monitored
trafﬁc data for the target ﬂow of the measurement. The
problem of scalability does not arise, because the volume of
trafﬁc can be measured by one-point passive measurement
without requiring data-matching processes.
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

CoMPACT monitor gives the one-way delay distributionof a target ﬂow by using a transformation of one-way delay
data obtained by active measurement. The transformation
can be determined from passively monitored trafﬁc data forthe target ﬂow of the measurement. In a recent study, it
was reported that by using an inter-probe time that has
a Gamma distribution can improve the accuracy of simple
active measurement. In this study, we show that CoMPACT
monitor is improved in accuracy by the application of newactive measurement.

1. Introduction
Today the Internet is used not only as a private tool
but also a business tool, and plays an important roleas infrastructure. The trafﬁc generated by emerging new
applications, including telephony and live video in addition to the traditional e-mail and web browsing, exhibits
complex characteristics. Moreover, the quality of service(QoS) required by various applications is also quite different.
When new applications are developed in the future, the QoS
requirements will be changed 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 network performanceand 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-3700-9/09 $25.00 © 2009 IEEE
DOI 10.1109/SAINT.2009.30

133See Time Averages) property to it.
However, recent work [3] 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, according to [3] we canﬁnd a distribution that is suboptimal in accuracy by selecting
an inter-probe time according to the parameterized Gamma
distribution.
In this study, we have applied this Gamma-probing to theactive measurement part of CoMPACT monitor and tried to
improve CoMPACT monitor’s in accuracy. This paper conﬁrms that Gamma-probing is appropriate when measuring
the complementary cumulative distribution function (CDF)
of individual ﬂows by simulation.

In the following, we brieﬂy summarizes the mathematicalformulation of CoMPACT Monitor [2].
Let a(t) and V (t), respectively, denote the trafﬁc in thetarget ﬂow at time t and the virtual one-way delay on thepath that we want to measure. Considering to measure theempirical one-way delay distribution, the value we want tomeasure 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)ds0This can be estimated through m times monitoring bym

Zm (c) =2. Summary of CoMPACT monitor(3)

for sufﬁciently large m (see [2] for details), where Tn(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 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).

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 delayin the network path at time t), and Xk denote a randomvariable which is observed V (t) with a certain timing (e.g.
the timing of user k’s packet arrivals). The probability for
Xk to exceed c isP(Xk > c) = 1{x>c} dFk (x) = EFk [1{x>c} ]where Fk (x) is the CDF of Xk .
If we can directlym monitor Xk , its distribution can be
estimated by
n=1 1{Xk (n)>c} /m, for sufﬁciently large
m. Now, let us consider the situation that Xk cannot bedirectly monitored. Let Y denote a random variable that isobserved 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 .
Observed values of Xk and Y are different if their timing
is different, even if they observe a common process V (t).
Xk and Y can be related by each CDF Fk (x) and G(y), andP(Xk > c) expressed by measure of Xk can be transformed
into measure of Y as follows.

dFk (y)dG(y)P(Xk > c) = 1{x>c} dFk (x) = 1{y>c}
dG(y)


dFk (Y )= EG 1{Y >c}dG(Y )

3. Suboptimal probing
Since the PASTA property is good for non-biased measurement, Poisson arrivals (intervals with an exponential
distribution) have been widely used as policy of 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 andwe can also ignore the effects of probe packets under nonintrusive conditions.
m
1 X(Tn ) = E[X(0)]
a.s.,
(4)
lim
m→∞ m
n=1

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

a(Tn )1 
1{V (Tn )>c} mm n=1
l=1 a(Tl )/mwhere we assume the target process X(t) is stationary andergodic. [4] proved (4) and named this property NIMASTA(Non-Intrusive Mixing Arrivals See Time Averages).
The recent study [3] also reported that NIMASTA-based
probing is suitable for measurement. That provides an improvement in the accuracy of the measurement. We can(1)where Y (n) (n = 1, 2, · · · , m) denote the nth observed
value. Note that this estimator does not need to monitor thetiming of Xk , if we can get dFk (Y (n))/dG(Y (n)).
134

Table 2. Type of probing

Table 1. Type of user ﬂows
Flow
type

Flow
ID

type 1
type 2type 3type 4#1-5#6-10#11-15#16-20Mean
ON/OFF
period10s/5s
5s/10s
5s/10s1s/19sDistribution of
ON/OFF length

Shapeparameter

Exp
Exp
PareteParete1.5
1.5

Rate atON
period
6 Mbps
6 Mbps9 Mbps9 MbpsDistribution ofprobe intervals
Exp
Gamma
Gamma
Gamma
Periodic

sourceselect 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m of X(0) by using active measurement, estimator p̂ is n=1 X(Tn )/m. It is assumed thatthe autocovariance function R(τ ) = Cov (X(t), X(t − τ ))of the target process X(t) is convex. It can be proven that
under the foregoing assumptions, no other probing processwith an average interval of μ has a variance that is lower
than that of periodic-probing with determinate intervals (see[3]). A lower variance of the estimator is connected withaccuracy. 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 policies obeying
Poisson arrivals and periodic-probing, [3] proposes a suboptimal policy that gives an inter-probe time that obeys theparameterized Gamma distribution. The probability density
function that is used as an inter-probe time is given byg(x) =

xβ−1
Γ(β)



β
μ

β

e−xβ/μ(x > 0),10 hostParameter of Gamma
distribution(β = 1)β=5
β = 25β = 125(β → ∞)

Mean probe
intervals
0.5 s
0.5 s
0.5 s
0.5 s
0.5 s

destination
10 hostrouter10 host10 hosthost of user ﬂow
route of probe
packets

Figure 1. Network model

4. The effectiveness of suboptimal probing
We investigated the effectiveness of Gamma-probing in
the framework of CoMPACT monitor, through NS-2 based
simulations. The network model is shown in Figure 1.
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 1, with there are ﬁve ﬂows in each type.
Probe packet trains are categorized into the ﬁve types
listed in Table 2. 300 trains of each type are streamed on thetwo routes shown in Figure 1, so the total number of probe
packet trains in the network is 3000. To analyze the varianceof the estimator, we streamed a large number of probe packet
trains. Note that parameters of Exp and periodic in Table 2
are parameters of the Gamma distribution corresponding toeach probing.
User ﬂow packets and probe packets are 1500 bytes
and 64 bytes, respectively. Link capacities are identicalat 64 Mbps. No loss occures, since there is sufﬁcientbuffering. We ran the simulation for 500 s. The non-intrusive
requirement was satisﬁed (the effect of probe packets can beignored), since the ratio of the probe stream to all streams
is about 0.00197%. We observed the trafﬁc by passive
measurement of queue for the edge router on the source
side.
First, we show that CoMPACT monitor can estimate theempirical one-way delay when using Gamma-probing. 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 Figure 2. Note that the horizontal axis, which is
the one-way delay, corresponds to c in (2). To compare theempirical delay with the estimate from CoMPACT monitor,
we include the estimate from active measurement in the plot.

(5)

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 with mean μ. When β → ∞, thepolicy reduces to periodic-probing because g(x) convergeson δ(x − μ).
If the autocovariance function is convex, it is proven thatthe variance of estimator p̂ sampled by intervals according
to (5) monotonically decreases with β. We can achieve nearoptimal variance of periodic-probing, since (5) corresponds
to periodic-probing towards limit β → ∞. The problem ofincorrectness due to phase-lock phenomenon can be avoided
if we tune β to a limited value (a probing process that
has intervals as set by (5) is mixing). Solving the tradeoff
between a traditional policy obeying Poisson arrivals andperiodic-probing, we can get a suboptimal probing process
if we give β an appropriate value.
135

0.1

0.01

parameter=25

1

empirical delay
CoMPACT
active
0.1

0.2
0.4
0.6
one-way delay [sec]parameter=in#nity

1

empirical delay
CoMPACT
active

0.1

0.01

0.01

0

complementary CDF

empirical delay
CoMPACT
activecomplementary CDF

complementary CDF

parameter=1

1

0

0.2
0.4
0.6
one-way delay [sec]

0

0.2
0.4
one-way delay [sec]0.6

Figure 2. The estimation of comprementary CDF (ﬂow #1)

   




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.





      5. Conclusion               

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



Acknowledgements               A part of this research was made possible by the Grant-inAid for Scientiﬁc Research (B) No. 21300027 (2009- 2011)
from the Japan Society for the Promotion of Science.





   

References

[1] 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.

Figure 3. Standard deviation of estimator

In Figure 2, 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 Figure 2.

[2] 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.

Second, we verify the relationship between the parameterof Gamma distribution that is used as the inter-probe time,
and the variance of estimator. If we can apply the theoryof [3] to CoMPACT monitor, the variance of the estimator
decreases as the parameter increases.

[3] 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[4] 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.

We show the standard deviation of estimator (ﬂow #1
and ﬂow#11) in Figure 3. The standard deviation clearlydecreases as β increases from β = 1 to β = 125. In resultof ﬂow #1 (0.1s), the standard deviation of periodic-probing
corresponding to β → ∞ is larger than that for β = 125.
This reversal may be a sign of incorrectness due to thephase-lock that occurs when the cycle of the target process
corresponds to the cycle of the probing process.
Consequently, for the case of UDP ﬂow, it is conﬁrmedthat we can obtain adequate accuracy with a suboptimal
probing process if we tune the parameter of Gamma distribution that we use as the inter-probe time.
136