CoMPACT-Monitor: Change-of-Measure based Passive/Active Monitoring— Weighted Active Sampling Scheme to Infer QoS —Masaki Aida, Keisuke Ishibashi, and Toshiyuki Kanazawa
NTT Information Sharing Platform Laboratories, NTT Corporation
3-9-11 Midori-cho, Musashino-shi 180-8585, Japanaida.masaki@lab.ntt.co.jp

Abstract
This paper proposes a new performance measurement
scheme which can infer performance and/or quality experienced by individual user, organization and application, viaa scalable and lightweight measurement way. The proposed
scheme is based on change-of-measure framework and is anactive measurement transformed by using passively monitored data. We give the theoretical basis of the proposed
scheme and show its typical implementations for inferring
the delay distributions. The validation of the implementations of the proposed scheme is investigated through simulation with respect to both the accuracy of estimation and theamount of the extra trafﬁc added by active measurement.

to monitor network performance [1]. They monitor the performance of the probe packets to determine the performanceof the network indirectly. This means that we implicitly assume the QoS/performance of a user/networks is identicalwith the values measured from active probe packets. There
are following problems in these active monitoring schemes.
• If we use a probe-packet stream that simulates an actual user trafﬁc,– The probe-packet stream incurs non-negligible
extra trafﬁc into the networks and it affects
QoS/performance of users’ trafﬁc, and– The QoS/performance obtained from the probe
packets is not equal to the unbiased one without
inﬂuences of the probe-packet stream.

1. Introduction
The Internet has been growing rapidly with respect tothe number of users and the amount of trafﬁc and has beenrecognized as an important lifeline for information in social and business use. So, although initial and basic interestof the Internet has been its connectivity and transmission
capacity, recent attention is also paid to its quality. The trafﬁc conveyed by the Internet is generated by wide variety
applications, which have different characteristics and havedifferent quality requirements. Thus, Quality of Service(QoS) and performance measurements are crucially important in controlling and managing QoS and in provisioning
networks.
In general, monitoring schemes to measure QoS and theperformance of networks are, divided into two types, active and passive monitoring. Unfortunately, both types havedrawbacks. They are brieﬂy summarized as follows.
Active measurement monitors QoS and the performanceof a network by sending probe packets and monitoring
them. Many active monitoring tools have been developed• If we use probe packets that have small length and aresent periodically, like ping,– The extra trafﬁc may be negligible, but the
QoS/performance obtained from the probe packets is not equal to the QoS/performance experienced by users, in general.
We add some explanation about the last case. Since
the time for sending probe packets is independent of theusers’ behaviors, QoS/performance measured by the active monitoring scheme generally differs from the actual
QoS/performance that users experience. If and only if we
can assume that active monitoring measures the time average of network performance and that the user trafﬁc is Poisson, then the performance experienced by the users and theactively-measured performance will be the same. This wellknown property is called PASTA (which stands for “Poisson Arrivals See Time Average”). It is known, however,that current Internet trafﬁc exhibits bursty properties and is
not generally Poisson [2]. In that case, an average user experiences worse performance than the time-average performance measured by active monitoring.

Proceedings of the 2002 Symposium on Applications and the Internet (SAINT’02w)
0-7695-1450-2/02 $17.00 © 2002 IEEE

Incidentally, the relationship between the network performance experienced by a user and the measured performance at an arbitrary time can be obtained with the Palm
measure [4]. However, to obtain the distribution of performance experienced by users, we require information about
the distributions of interarrival time and service time to calculate the Palm measure. It is hard to measure these distributions, so this way is not feasible.

scheme, we propose a simple scheme for estimating the actual delay experienced by users, which is easy to implement.
In addition, we show the validity of the scheme throughsimulation. In section 4, we extend the proposed scheme
to estimate the performance experienced by an individualuser. Finally, we conclude the paper in section 5.

Passive measurement is mainly used to monitor trafﬁcvolume but can measure network performance as well. Passive monitoring is categorized into two types, two-point
monitoring and one-point monitoring.

This section proposes a new measurement scheme basedon a change-of-measure framework. The proposed scheme
is scalable and lightweight and enables accurate estimation of detailed characteristics of performance for individual users, organizations, and applications. In this scheme, a
combination of simple measurements of both the active andpassive types enables the change-of-measure framework.

• Two-point monitoring requires two monitoring devices
deployed at ingress and egress points in a network. The
devices sequentially take packets’ data, and network
performance parameters such as delay and loss can becalculated by comparing the data of the corresponding
packets taken at each point. If we apply the two-point
monitoring to measure QoS/performance,– The all devices should have synchronized timing,and– The two-point monitoring requires identiﬁcationof each packet at the two devices by its header orcontents. Since this identiﬁcation process is hardwhen the packet volume is huge as in a largescale network, the two-point monitoring does nothave scalablility.
• One-point monitoring uses the TCP acknowledgment
mechanism. When a TCP-sink receives a packet froma TCP-source, the TCP-sink transmits the acknowledgement for the packet [3]. Thus, by monitoring thepacket-ack pair at a point in the network, the roundtrip delay between the point and the sink can be measured. The packet loss can also be detected in this way.
If we apply the one-point monitoring, measurement isrestricted for TCP ﬂows.
In this paper, we propose a new performance measurement scheme to estimate the actual network performanceexperienced by users. Our scheme requires both active
and passive monitoring using easy-to-measure methods. It
is based on change-of-measure framework and is an active measurement transformed by using passively monitored data. Our scheme can estimate not only the mixed
QoS/performance experienced by users but also the actual
QoS/performance for individual users, organizations, andapplications. In addition, the proposed scheme is scalable
and lightweight.
The rest of the paper is organized as follows. In section 2, we give a mathematical formalization of the framework of our scheme. In section 3, as an application of the

2. Proposed Measurement Scheme

2.1.

Change-of-Measure
SchemeBased

Measurement

We can recognize that almost all measurements fundamentally correspond to the integrals. This is because it isa cumulation of some quantities according to a certain rule.
Our scheme enables us to obtain the measurement objective
not from the integral describing a direct measurement of theobjective, but from other integral that is easy-to-measure.
These integrals are in different forms but their values are
the same.
Let X be the measurement objective, e.g., the delay foruser packets, whose distribution function P is as follows:
Pr(X > a) =1{x>a} dP (x)= Ep 1{X>a} ,(1)
where 1{·} is the indicator function. We consider how to estimate the distribution P via measurements of X. Suppose
there are n arrivals in a measurement period, e.g., n packets
arrived. X(i) denotes the i-th value of X. Then an estimator Zx (n, a) of the distribution P of X can be obtained byusing X(i) as follows:n

Zx (n, a) :=1 
1{X(i)>a} .
n i=1

(2)

The estimator Zx (n, a) satisﬁes unbiasedness
Ep [Zx (n, a)] = Pr(X > a).

(3)

In addition, if X(i) is ergodic, then 1 {X(i)>a} is also ergodic for arbitrary a ∈ R, and the estimator Z x (n, a)strongly converges toProceedings of the 2002 Symposium on Applications and the Internet (SAINT’02w)
0-7695-1450-2/02 $17.00 © 2002 IEEElim Zx (n, a) = Pr(X > a) a.s.

n→∞

(4)

X(3)

traffic arrival
AA :: User
Active measurement
A
V(t)
AA A
AA
A
AA A
A A
AA
A
AA AA
AA
A
AA A
A A

Y(2)
X(2)
X(1)
Y(1)

A
A
A
A
A
s1

A
A
A
A
A
A
A
A
s2

X(i)

Y(j)

Y(3)

s3

sj-1

t1 t2 t3sj

ti-1 ti

sj+1

ti+1

t

ti+2

Figure 1. Relationship between V (t) and X(i), Y (j).
Suppose we have a situation in which it is difﬁcult tomeasure X(i) directly, and an estimate of its distribution
cannot be obtained with (2). Let V (t) be the network performance at time t such that if the i-th arrival occurs at t i ,then V (ti ) = X(i). In the example of delay measurements,
V (t) is the virtual weighting time. Also, let Y be the valueof V (t) measured independently of the arrivals X(i) and
let the distribution function of Y be Q. We assume that fora, b ∈ R,
P (b) − P (a) > 0 ⇒ Q(b) − Q(a) > 0.

(5)This assumption indicates that the network performance forarrivals can be measured with a positive probability. This isnatural when the measurement lasts long enough. We canthen deﬁne dP/dQ, and the distribution of X can be written
using the distribution of Y asdP (y)dQ(y)Pr(X > a) =1{y>a}dQ(y)dP (Y )= Eq 1{Y >a},(6)
dQ(Y )by (1). Now, suppose V (t) is measured m times, and let
Y (j) be the j-th measurement at s j such that Y (j) = V (sj )(j = 1, 2, . . . , m) (Fig. 1). Then an estimator of Pr(X >a) can be derived with Y (j) as follows:

lim Zy (m, a) = Pr(X > a) a.s.

m→∞

If we can derive L(j), then the estimator of the distribution P of X can be derived with the measurement value Y .
The fundamental concept of our scheme is as follows: The
estimation of the distribution P from direct measurementsof X is difﬁcult. However, since the values Y (j) and L(j)are easily obtained by respectively using active and passive
monitoring, we can easily estimate the distribution P by using (7). The derivation of the likelihood ratio is describedin the next subsection.

2.2. Likelihood Ratio
Let ρx (t) be the trafﬁc volume arriving (e.g., the numberof packets arriving) in an interval [t, t + δ(t)). Let ρ y (t) be
the number of measurements in [t, t + δ(t)). We assume
that the interval δ(t) is short enough compared to the time
variance of V (t) so that
V (s)  V (s ) for ∀s, s ∈ [t, t + δ(t)).

dP (Y (j)),(8)
dQ(Y (j))
which we call the likelihood ratio [5]. Equations (3) and (4)also hold for Z y (m, a) as
L(j) :=

Eq [Zy (m, a)]= Pr(X > a), andL(j) =

(7)

where

(9)

(11)

The assumption indicates that one measurement of Y in
the interval [t, t + δ(t)) can be interpreted as ρ x (t)/ρy (t)measurements of X. Note that we can always deﬁneρx (sj )/ρy (sj ) because at the time sj of measurement Y (j),ρy (sj ) > 0. Then the likelihood ratio can be obtained asm

1 
1{Y (j)>a} L(j),Zy (m, a) :=
m j=1

(10)

ρx (sj ) m,ρy (sj ) n(12)because the total number of events of X is n and that of Y
is m.
The likelihood ratio (12) can be obtained with passive
measurements, and the distribution of X is estimated asmρx (sj )1 .
(13)
1{Y (j)>a}
Zy (m, a) =n j=1
ρy (sj )Proceedings of the 2002 Symposium on Applications and the Internet (SAINT’02w)
0-7695-1450-2/02 $17.00 © 2002 IEEE

1.5 Mbps

2.3. Strength of Our Scheme
We can expect the proposed scheme has the following
superior points:• Since the extra trafﬁc for active probe packets is negligible, users’ trafﬁc is little affected.

Exp ON-OFF
Source x 60.
.
.

Aggregate
Router

Probe Source• We have a dependable estimation of QoS/performancemeasure.

Sink x 60

Probe Sink

Figure 2. Network conﬁguration for simulation.

• Since passive measurement is only required counting
the amount of trafﬁc (the number of packets), the twopoint measurement is not necessary and the passive
monitoring devices are simpliﬁed.

Packet delay
Probe delay

Delay [msec]

3. Simple Application for the Delay Measurement
As an application of the proposed scheme described in
the previous section, we propose a simple scheme for estimating the actual delay experienced by user which is easy
to implement.

1600

150

1200

100

800

50

400

0
1420

3.1. Formalization

Packet count

200

1425

1430

1435

Number of packet arriving• We can apply our scheme to non-TCP protocols as
well.

0
1440

Time [sec]Let Y (j) (j = 1, 2, . . . , m) be the delay measured withprobe packets, such as ping or other active monitoring, attime sj . The probe packet interval s j+1 − sj is chosen to
be a constant τ and δ(s j ) is also chosen to be the sameinterval, as a simple implementation. 1 Then suppose thatthe number of user packets arriving in [s j , sj+1 ) is ρ(j)and the total numberof packets arriving in the measureρ(j)= n. As an example of a delay
ment period is m
j=1
estimation case, V (t) is considered as the virtual waitingtime of the network, which is the delay for a packet arriving (virtually) at t. If we assume that τ is short enoughcompared to the ﬂuctuation of V (t), then we derive the estimator of the packet-delay distribution by applying (13) forρx (sj ) = ρ(j), ρy (sj ) = 1 and δ(sj ) = τ asm

Zy (m, a) =10 Mbps.
.
.

1 
1{Y (j)>a} ρ(j).
n j=1

(14)

Figure 3. Sample paths for the number ofpackets arriving, user packet delay, and probe
packet delay.

3.2. Evaluation
To demonstrate our simple application described above,
we use the ns2 [6] network simulator. Figure 2 shows the
network topology for the simulation. Sixty sources are connected to a bottleneck router with 1.5-Mbps links, and tworouters are connected with a 10-Mbps link.
We measure the queueing delay at the bottleneck router,which does not include the service time for the packets
themselves. Other simulation conditions are as follows:As can be seen from (14), estimating the user delay requires measuring the network delay periodically with active
probe packets and measuring the number of packets arriving
between active measurements, which is far easier than measuring the delay for user packets directly with two probes
deployed at the network edges.
1 It prefers that τ is exponentially distributed values because τ should
not synchronize any trafﬁc patterns in the networks.

Proceedings of the 2002 Symposium on Applications and the Internet (SAINT’02w)
0-7695-1450-2/02 $17.00 © 2002 IEEE

• The user packets are generated by ON-OFF sources.
Both the ON and OFF durations are distributed as i.i.d.
exponentials, where the mean ON duration is 1 second
and the mean OFF duration is 14 seconds. The packet
size is ﬁxed at 1000 bytes.
• As the transport protocol for the user packets, both
TCP and UDP are evaluated.

1

1

User delay
Probe delay
Estimated delay

Pr(delay > a)Pr(delay > a)User delay
Probe delay
Estimated delay
0.1

0.1

0.01

0.01

0.001

0.001
0

50

100

150

200

0

250

500

1000

1500

2000

a [msec]a [msec]

Figure 4. Distributions of queueing delay forpackets generated by TCP On-Off sources,
probe packets, and estimator.

Figure 5. Distributions of queueing delay forpackets generated by UDP On-Off sources,
probe packets, and estimator.

• Probe packets to actively measure the queueing delay
are generated every second. The size of each probe
packet is ﬁxed at 64 bytes.

of this paper, we use TCP as the transport protocol for user
packets.
In the above examples, the extra trafﬁc for active probe
packets is 512 bps. This is about 0.005% of the bandwidthand is negligible.

• The bottleneck link utilization is 0.6.
• Simulation time is 2,500 sec, i.e., 2,500 active probe
packets are sent.
First, we show results for TCP. Figure 3 shows a sample
path for the user packet delay, probe packet delay, and number of user packets arriving between probe packets. It canbe seen that the delay measured with probe packets captures
well the time variance of delay for the user packets. We
can also, however, see ﬂuctuation in the number of packets,
which synchronizes with the delay ﬂuctuation. This ﬂuctuation causes the discrepancy between the distribution ofdelay for bursty user packets and periodical probe packets,
because the number of packets with worse delay is larger
for user packets than probe packets.
Figure 4 shows the delay distributions of user packets
and probe packets and an estimation, for TCP. As expectedfrom the sample path, we can observe the discrepancy between the distribution of user packet delay and that for active measurements. Using our proposed scheme, however,user delay can be estimated with high accuracy for active
measurements.
Figure 5 shows results for UDP. Although the delay
grows larger than for TCP because packets are sent without congestion control, it can be seen that our scheme estimates the user packet delay with high accuracy. In the rest

4. Simple Application for the Individual User
Delay Measurement
We describe here a proposed simple application using
our change-of-measure-based measurement scheme, which
can be extended to estimate the packet delay for individual
users with one series of active measurements and passive
trafﬁc monitoring. user.

4.1. Formalization
Let Xk be the packet delay of user k (k = 1, 2, . . . , K)
and Y (j) (j = 1, 2, . . . , m) be the delay measured withactive packets, such as ping, at time s j . Assume the intervalof probe packets s j+1 − sj is a constant τ , the number ofpackets for user k arriving in [s j , sj+1 ) is ρk (j), and thenumber of total packets for user k is
nk :=

m


ρk (j).

(15)

j=1

Then the likelihood ratio for user k ism
Lk (j) := ρk (j) ,nk

Proceedings of the 2002 Symposium on Applications and the Internet (SAINT’02w)
0-7695-1450-2/02 $17.00 © 2002 IEEE

(16)

Exp ON-OFF
TCP Source x 55

.
.
.
.
.
.

Probe Source

1

1.5 Mbps
10 Mbps
Aggregate
Router.
.
.

ParetoPareto (Estimated)

TCP Sink x 60
0.1

Probe Sink

Pr(delay > a)Pareto ON-OFF
TCP Source x 5

Figure 6. Network model.

m
1 
1{Y (j)>a} ρk (j).
nk j=1

0.01

0.001

and we can obtain the estimator as follows:
Zy (k, m, a) =Exp
Exp (Estimated)(17)0.0001
0

0.02

0.04

0.06

0.08

0.1

0.12

a [msec]

Thus, by counting the number of packets arriving for eachuser every τ seconds, we can estimate the delay experienced
by individual users.
The classiﬁcation of trafﬁc is not limited to individual
users or groups of users. An typical other example is theclassiﬁcation of trafﬁc by by kind of applications. The trafﬁc pattern generated by an application depends on the application, so the performance for packets may also depend on
the application generating the packets. Using our scheme,
we can monitor the performance for each application with
one series of active measurements, on the condition thatpackets for every class are treated with the same priority
in the network.

4.2. Evaluation
We next describe the proposed scheme to estimate theperformance experienced separately by two groups of users.
We separate the 60 sources from the simulation run in subsection 3.2 in 5 bursty sources and 55 non-bursty sources(Fig. 6). For the bursty sources, the ON-OFF durations are
distributed in a Pareto distribution with a shape parameter of
1.5, where the mean ON duration is 1 second and the mean
OFF duration is 14 seconds. For the non-bursty sources, theON-OFF durations are distributed in a exponential, where
the mean ON duration is 10 seconds and the mean OFF duration is 5 seconds.
Simulation time is 25,000 sec, i.e., the number of generated probe packets is 25,000. The other parameters are thesame as before.
Figure 7 shows the distribution of the user packet delay and the estimated distribution using (17). We see thatthe proposed scheme can estimate the distributions of bothgroups of users with high accuracy for one series of active
measurements.
The extra trafﬁc for active probe packets is 512 bps andthis is about only 0.005% of the bandwidth.

Figure 7. Estimations of delay distributions
for two types of users.

5 Conclusion
In this paper, we have proposed a new performance measurement scheme, the change-of-measure
based measurement scheme, which can estimate detailed
QoS/performance via a scalable and lightweight method.
Our scheme only requires counting the trafﬁc volume as
passive monitoring and simple measurement of network
performance as active monitoring, which is feasible andtractable compared to a conventional scheme. We have applied our change-of-measure scheme as an example of asimple implementation. We used simulation to validate theproposed application. As a result, Our scheme has beenshown to give a good estimation of the performance seen
by a user. The extra trafﬁc for active probe packet is negligible. We extended the scheme to estimate individual user
performance, and conﬁrmed the validity of this approach bysimulation.
We should evaluate the relationship between measurement interval of active probe packets and the accuracy ofthe estimation. The result will address how to measure
QoS/performance in various situation and will clarify thestrength of our scheme in the practical implementations.
These issues are for further study.

References[1] CAIDA cooporative association for internet data analysis.
http://www.caida.org/tools/ .

Proceedings of the 2002 Symposium on Applications and the Internet (SAINT’02w)
0-7695-1450-2/02 $17.00 © 2002 IEEE

[2] V. Paxon and S. Floyd, “Wide-area trafﬁc: The failureof Poisson modeling,” IEEE/ACM Trans. on Networking, June 1995.
[3] W. R. Stevens, “TCP/IP illustrated, Vol. 1,” AddisonWesley, Reading MA, 1994.
[4] F. Baccelli and P. Brémaud, “Palm probabilities and stationary queues,” Springer-Verlag, 1980.
[5] P. J. Smith, M. Shaﬁ, and H. Gao, “Quick simulation: areview of importance sampling techniques in communications systems,” IEEE J. Selected Areas in Commun.,vol. 15, No. 4, May 1997.
[6] UCB/LBNL/VINT Network Simulator - ns (version 2).
http://www.isi.edu/nsnam/ns .
[7] K. Thompson, G. J. Miller, and R. Wilder, “Wide-area
Internet trafﬁc patterns and characteristics,” IEEE Network, November/December 1997.

Proceedings of the 2002 Symposium on Applications and the Internet (SAINT’02w)
0-7695-1450-2/02 $17.00 © 2002 IEEE