A Scalable and Lightweight QoS Monitoring
Technique Combining Passive and Active
Approaches— On the Mathematical Formulation of CoMPACT Monitor —Masaki Aida∗ , Naoto Miyoshi† and Keisuke Ishibashi∗∗ NTT Information Sharing Platform Laboratories

NTT Corporation
Email: {aida.masaki,ishibashi.keisuke}@lab.ntt.co.jp† Department of Mathematical and Computing Sciences
Tokyo Institute of Technology
Email: miyoshi@is.titech.ac.jp

Abstract— To make a scalable and lightweight QoS monitoring
system, we have proposed a new QoS monitoring technique,
Change-of-Measure based Passive/Active Monitoring (CoMPACT
Monitor), which is based on change-of-measure framework andis an active measurement transformed by using passively monitored data. This technique enables us to measure detailed QoS
information for individual users, applications, and organizations,in a scalable and lightweight manner. In this paper, we present
the mathematical foundation of CoMPACT Monitor. In addition,
we show its characteristics through simulations in terms of typical implementation issues for inferring the delay distributions.
The results show that CoMPACT Monitor gives accurate QoS
estimations with only a small amount of extra traffic for active
measurement.

I. I NTRODUCTION
The Internet has been growing rapidly with respect to thenumber of users and the amount of traffic and has beenrecognized as an important infrastructure for information insocial and business use. So, although the initial and main
issue of the Internet has been its connectivity and transmission
capacity, attention has recently been paid to its quality too.
The traffic conveyed by the Internet is generated by a wide
variety of applications, which have different characteristics anddifferent quality requirements. Thus, Quality of Service (QoS)
and performance measurements are crucial in controlling andmanaging QoS and provisioning networks. However, it is difficult or expensive to measure QoS and performance statistics
of each flow directly.
Recently, many monitoring tools have been developed tomonitor network performance [1], [2], [3], [20] and theirmeasurement results have also been reported [10], [21], [23].
In general, conventional monitoring schemes to measure QoS
and the performance of networks are classified into two types:
active and passive monitoring. Unfortunately, both types havedrawbacks. They are briefly summarized as follows.
a) Active measurement monitors QoS and the performanceof a network by sending probe packets and monitoring them
0-7803-7753-2/03/$17.00 (C) 2003 IEEE[6], [7], [22]. There are various active methods to measure
network performance such as available bandwidth [16], delay,
loss, and to estimate their link-by-link performance [12].
They monitor the QoS/performance of the probe-packet stream
to determine the QoS/performance of the user/network indirectly. This means that we implicitly assume that the
QoS/performance of a user/networks is the same as the values
measured from active probe packets. These active monitoring
schemes have the following problems.
• If we use a probe-packet stream that simulates an actualuser traffic:– The probe-packet stream causes non-negligible
amount of extra traffic on the networks and it affects
QoS/performance of users’ traffic and– The QoS/performance obtained from the probe packets is not equal to that without the influence of theprobe-packet stream.
• If we use short probe packets and send them in certain
intervals, like ping:– The extra traffic may be negligible, but the
QoS/performance obtained from the probe packets
is not equal to the QoS/performance experienced byusers, in general.
Let us add some explanation about the last case. Since thetime for sending probe packets is independent of the users’
behaviors, QoS/performance measured by the active monitoring scheme generally differs from the actual QoS/performancethat users experience. If and only if we can assume that active
monitoring measures the time average of network performanceand that the user traffic is Poissonian, then the performanceexperienced by the users and the actively-measured performance will be the same. This well-known property is called
PASTA [25]. It is known, however, that current Internet traffic
exhibits bursty properties and does not generally have Poisson
arrivals [19]. In that case, an average user experiences worse

125

performance than the time-average performance measured by
active monitoring.
b) Passive measurement is mainly used to monitor traffic
volume but can measure network performance as well. Passive
monitoring is categorized into two types: two-point monitoringand one-point monitoring.
• Two-point monitoring requires two monitoring devices
deployed at ingress and egress points in a network.
The devices sequentially take packet 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:– All devices should have synchronized timing.
– The two-point monitoring requires identifying eachpacket at the two devices by its header and/or
contents. Since this identification process is hardwhen the packet volume is huge, as in a large-scale
network, the two-point monitoring does not havescalablility.
– To identify the monitored packets, we should collect all the packet data. This process requires nonnegligible bandwidth.
• One-point monitoring uses the TCP acknowledgment
mechanism. When a TCP-sink receives a packet froma TCP-source, it transmits an acknowledgement for the
packet [24]. Thus, by monitoring the packet-ack pair at
a point in the network, we can measure the round-trip
delay between the point and the sink. The packet loss
can also be detected in this way. However, if we apply
one-point monitoring, measurement is restricted to TCP
flows.
Our approach, Change-of-Measure based Passive/Active
Monitoring (CoMPACT Monitor), is different from the above
methods. It combines both active and passive monitoring
using easy-to-measure methods. It is based on change-ofmeasure framework and is an active measurement transformedby using passively monitored data. CoMPACT Monitor canestimate not only the mixed QoS/performance experienced
by users but also the actual QoS/performance for individual
users, organizations, and applications. In addition, CoMPACT
Monitor is scalable and lightweight, where the scalability inthis paper means the monitoring system does not becomecomplex even if the volume and/or number of target flows(e.g., user flows) that are sharing the common path increases.
We have proposed the concept of CoMPACT Monitor in[5], and have investigated the characteristics of its simple
implementation in [15]. However, our previous works do notpresent its mathematical foundation. So, the condition, in
which CoMPACT Monitor works well, has not been clarified.
In this paper, we present the mathematical foundation of
CoMPACT Monitor and show its characteristics with respect
to typical implementation issues for inferring the delay distributions.
The rest of the paper is organized as follows. In section II,

we briefly summarize the concept of CoMPACT Monitor andrelated works that combine passive and active methods. In
section III, we present mathematical formulations of the framework for CoMPACT Monitor. In section IV, we investigate
implementations of CoMPACT Monitor. To demonstrate thefeatures of CoMPACT Monitor, section V shows examples ofdelay distribution measurements for individual users via simulation. In addition, we show the characteristics of CoMPACT
Monitor with respect to implementation issues. Finally, we
conclude the paper in section VI.
II. C ONCEPT OF C O MPACT M ONITOR
A. Concept
CoMPACT Monitor is a scalable and lightweight monitoring
technique that enables us to estimate detailed characteristics
of performance for individual users, organizations, and applications. It combines simple measurements of both active andpassive types by change-of-measure framework.
We can recognize that the measurement of QoS statistics
fundamentally corresponds to integrals. This is because it isan accumulation of some quantities according to a certain
rule. Our technique enables us to obtain statistics of themeasurement objective not from the integral describing a direct
measurement of the objective, but from other integral that iseasy to measure. These integrals are in different forms but
their values are the same.
Let Xk be the measurement objective, e.g., the delay foruser k’s packets, whose distribution function is Fk . The
distribution of Xk is obtained as follows:
Pr(Xk > a) = 1{x>a} dFk (x)= EFk 1{Xk >a} ,(1)
where EFk denotes the expectation with respect to Fk and 1{·}denotes the indicator function.
Suppose we have a situation in which it is difficult tomeasure Xk directly, and an estimate of its distribution cannot
be obtained with (1). Let V (t) be the network performanceat time t and Xk be the value of V (t) measured at a certain
time. Also, let Y be the value of V (t) measured independentlyof Xk and let the distribution function of Y be G. Then,
Pr(Xk > a) in (1) is obtained, under a certain condition,as
dFk (y)dG(y)Pr(Xk > a) = 1{y>a}
dG(y)


dFk (Y )= EG 1{Y >a},(2)dG(Y )

where EG denotes the expectation with respect to G and
dFk /dG denotes the likelihood ratio of Fk with respect toG.
If Y is easy to measure and we can derive dFk (Y )/dG(Y ),then the estimator of the distribution of Xk can be derived
with the measurement values of Y . The fundamental conceptof CoMPACT Monitor is as follows: The estimation of the
distribution Pr(Xk > a) from direct measurements of Xk

126

is difficult. However, if the values Y and dFk (Y )/dG(Y )are easily obtained by respectively using active and passive monitoring, then we can easily estimate the distribution
Pr(Xk > a) from (2). The likelihood ratio can be obtained
through simple counting of user packets.
In addition, (2) means that if we have dFk (Y )/dG(Y ) for
each class k traffic (user, application, organization, and their
combination specified by k; k = 1, 2, . . . ), we can simultaneously obtain the individual QoS for each class k traffic sharing
a common path from the common active measurement of Y .
We can expect CoMPACT Monitor to have the following
advantages:• Negligible extra traffic for active probe packets:
Since the extra traffic for active probe packets can besmall, user traffic is little affected.
• Simplification of passive monitoring devices:
To measure the delay distribution, the conventional passive monitoring requires two-point monitoring. However,passive monitoring in CoMPACT Monitor only requires
packet counting. Since that is one-point monitoring, passive monitoring devices are simplified (Fig. 1).
• Simultaneous estimation of QoS for individual packet
streams:
By determining the individual likelihood ratio for eachpacket stream sharing a common path, we can obtain
QoS parameters for an individual packet stream from thecommon active monitored sequence. The likelihood ratio
is easily determined by counting the number of packets
in the packet stream filtered by any class we want tomeasure.
• Protocol independence:
CoMPACT Monitor is applicable to non-TCP protocols
as well.
Here, we add some explanations to the scalability of CoMPACT Monitor. The target flows measurable by the common
active measurement of Y are restricted to the flows sharing
the same physical and logical path. When we measure thetarget flows in different paths, it is necessary to use different
active probe packet sequences (of course, this is the samefeature as conventional active measurements). Therefore, if
all the target flows share the same path, we can measure
all the flows by using a single active probe packet sequenceand the monitoring system is not complicated with respect toincrease of the number of target flows (as well as increase of
the volume of target flows). CoMPACT Monitor has this typeof the scalability. In addition, although different active probe
packet sequences are required for measuring the target flows
in different paths, configuration of passive monitoring devices
is not always complicated. If the different paths include thecommon link, we can reduce the number of passive monitoring
devices by fixing the passive monitoring device at the common
link (Fig. 2).
B. Related Work
Lindh has proposed a new QoS monitoring technique thatcombines passive and active ways [17], [18]. In this technique,

Time synchronization
Packet identification

Passivemonitoring
deviceTwo-point passive measurement for packet delay.

Packet countPassivemonitoring
devicePassive measurement for CoMPACT Monitor.

Fig. 1.

Simplification of passive monitoring for CoMPACT Monitor.

a router sends active probe packets at regular intervals suchthat the number of target user packets passing through therouter becomes a predefined fixed value. The passive monitoring device is used to count the number of packets. Since
the density of active probe packets inserted into the network
is proportional to the density of the target user packet stream,
this technique also can measure QoS for a packet stream, e.g.,
the QoS experienced by a user. However, this technique has
the following drawbacks:• This technique inserts many active probe packets when
there are many packets in the target packet flow (e.g.,user flow). This means that the number of active probe
packets tends to increase when the network is congested.
Thus, active probe packets will affect the QoS of users’
traffic.
• If we need to measure the individual QoS for each user,
this technique inserts different active probe packet sequences corresponding to the users. Thus, this techniquedoes not have scalability with respect to an increase in
the number of target packet flows.
However, in CoMPACT Monitor, the extra traffic for active
probe packets is independent of user traffic, and an individual
QoS can be derived with the common active probe packet
sequence even when the number of target packet flows, in thesame path, increase.
III. M ATHEMATICAL F ORMULATION OF C O MPACTM ONITOR
This section presents the mathematical formulation of CoMPACT monitor in order to clarify the conditions in which
it works well. Since Internet traffic has a wide variety ofcharacteristics, we present the mathematical formulation for
nonstationary user traffic. This formulation is also applicableto stationary user traffic.
In the framework of CoMPACT Monitor, there are many
user packets in the network compared with active probe
packets. Thus, we consider a fluid approximation of user
traffic; that is, user packets are approximated as a fluid, while
the arrivals of active probe packets are modeled as a point
process.
Suppose that a path in the network is shared by K (≥1) users. Let Ak (t), k = 1, . . . , K, denote the cumulative
amount of fluid transmitted by user k observed during (0, t],127

Passive monitoring
device for path #1

hosts

hosts

hosts

hosts

routerrouter...

routerrouterrouterrouterrouter...

routerrouterPassivemonitoring
devicepath #1...

...

path #1

routerrouterrouterrouterroutercommon link...

Fig. 2.

...

Passive monitoring
device for path #2

...

hosts

hosts

0

path #2

hosts

Simplification of the configuration of passive monitoring devices.

where each {Ak (t)}t≥0 is a deterministic, real-valued andnondecreasing process satisfying Ak (0) = 0. We assume
that lim inf t→∞ Ak (t)/t > 0 and that {Ak (t)}t≥0 is absolutely
continuous with density {ak (t)}t≥0 ; that is, Ak (t) =ta(s)ds, t ≥ 0, where we also assume that {ak (t)}t≥0
k0
is right-continuous with left-limits and is bounded on t ≥ 0.
Let V (t) denote the virtual delay in the path at time t, where{V (t)}t≥0 is a deterministic, real-valued, and nonnegative process. We assume that {V (t)}t≥0 is right-continuous with leftlimits in t ≥ 0. The deterministic process {(V (t), ak (t); k =1, . . . , K)}t≥0 is considered as a sample path extracted fromthe corresponding stochastic process, where we assume neither
stationarity nor ergodicity. Note that {V (t)}t≥0 is influenced
not only by {ak (t); k = 1, . . . , K}t≥0 but also other flowsthat share all/a part of the path of {ak (t); k = 1, . . . , K}t≥0 .
Define A−1
k (x) = inf{t ≥ 0 : Ak (t) ≥ x}, k = 1, . . . , K,
for x ≥ 0. Note that A−1
k (x) represents the time at which
the cumulative fluid transmitted by user k reaches level x.
More intuitively, we can interpret A−1
k (x) as the arrival time of
the “fluid molecule (packet) labeled x” transmitted by user k.
The delay Wk (x) of the “fluid molecule x” of user k is thenrepresented by Wk (x) = V (A−1k (x)) for x ≥ 0. Therefore,
for any y > 0 and any k = 1, . . . , K, the empirical average
network delay distribution for the fluid of user k over theamount y of fluid is given by
πk,y (C)
1 y1{Wk (x)∈C} dx
=
y 0
 y
1
−1
=
1
dx
y 0 {V (Ak (x))∈C}
A−1 (y)
1
= k
y
A−1
k (y)
 A−1
(y)
k
1{V (s)∈C} ak (s) ds,
×

hosts

...

path #2

exist, we can see that there is a long-term average delay
distribution for the fluid of user k and it is given by
πk (C) = lim πk,y (C),y→∞C ∈ B(R+ ),(6)

where lim inf t→∞ Ak (t)/t > 0 is ensured by the assumption.
Now, consider estimating the long-term average delay distribution πk (C), C ∈ B(R+ ), by monitoring the network
at random sampling epochs. Let {N (t)}t≥0 denote a simple
counting process representing the monitoring epochs of the
network and let {Tn }n≥1 be the corresponding point sequence;that is, Tn = inf{t ≥ 0 : N (t) ≥ n} for n = 1, 2, . . . . We
assume that N has stationary and ergodic increments withrespect to a probability measure P and also has the positiveand finite intensity λN = E[N (1)], where E denotes the
expectation with respect to P. Then, we have the following:
Theorem 1 If, for some k ∈ {1, . . . , K} and some C ∈B(R+ ), the following hold with constants αk (C) and αk ,m1 
1{V (Tn )∈C} ak (Tn ) = αk (C),
m→∞ m
n=1
lim

P-a.s.,

(7)

m

1 
ak (Tn ) = αk ,
m→∞ m
n=1
lim

P-a.s.,(8)then limits (4) and (5) also exist for such k and C, and wehaveαk (C)αkm
n=1 1{V (Tn )∈C} ak (Tn )
m
,
= lim
m→∞
n=1 ak (Tn )πk (C) =C ∈ B(R+ ).

(3)

Thus, since A−1
k (y) → ∞ as y → ∞ due to the bounded
property of {ak (t)}t≥0 , if the limits
1 t
1{V (s)∈C} ak (s) ds,(4)limt→∞ t 0 ty
Ak (t)
1
= lim
= lim
lim
ak (s) ds(5)y→∞ A−1 (y)t→∞t→∞ t 0tk

P-a.s.

(9)

Proof: We show that limit (4) exists and coincides with
αk (C) in (7) along similar lines to the proof of Theorem 3.1
in [14]. Since {(V (t), ak (t))}t≥0 is a deterministic process,we have

 N
(t)
1
1{V (Tn )∈C} ak (Tn )
E
t n=1
  t

1
=E
1{V (s)∈C} ak (s) dN (s)
t 0

1 t
=
1{V (s)∈C} ak (s) λN ds,
(10)
t 0

128

where we use the relation E[N (t)] = λN t due to thestationarity of N . Since {ak (t)}t≥0 is bounded, for the insideof the expectation in the left-hand side above, we have
N (t)

1
N (t)
,
1{V (Tn )∈C} ak (Tn ) ≤ asup
k
t n=1
t

Tn

= supt≥0 {ak (t)} and E[N (t)/t] = λN < ∞.
Thus, applying the dominated convergence theorem to (10),we obtain


N (t)
1
1{V (Tn )∈C} ak (Tn )
E lim
t→∞ t
n=1

λN t
= lim
1{V (s)∈C} ak (s) ds.
t→∞ t
0For the limit on the left-hand side, we have by the conditionof the theorem and the ergodicity of N :
N (t)

1
1{V (Tn )∈C} ak (Tn )
t→∞ t
n=1
lim

N (t)
N (t) 1 = lim
1{V (Tn )∈C} ak (Tn )t→∞t N (t) n=1

P-a.s.,

so limit (4) exists and coincides with αk (C). The existence oflimit (5) and its coincidence with αk in (8) are immediate byreplacing C with R+ . We then have result (9) from (3) and(6).
Theorem 1 shows that the long-term average delay distribution for the fluid of user k is estimated through m-times
monitoring of the network bym
1{V (T )∈C} ak (Tn ),(11)
Zk,m (C; N ) = n=1m n
n=1 ak (Tn )which is indeed strongly consistent in the sense thatlim Zk,m (C; N ) = πk (C),m→∞

P-a.s.,

Fig. 3.

Difference in implementations.

where PAk denotes the Palm probability defined by (P, Ak )and E0N denotes the expectation with respect to thePalm probability P0N defined by (P, N ) (see [9] and[13]). In this case, we can replace the boundedness of{ak (t)}t≥0 with E0N [ak (0)] < ∞. In this formula, we seethat ak (0)/E0N [ak (0)] plays a role of the likelihood ratio dPAk /dP0N . This is just the origin of the name “Changeof-Measure-based” monitoring (see Section 2.1 and also [5],[15]).
Remark 3 In the above remarks, though {(V (t), ak (t); k =1, . . . , K)}t≥0 is considered stochastic, it is still assumed to
be independent of the sampling process N . Now, consider thecase where (V (t), ak (t)) depends on {N (s)}s<t for t > 0.
In this case, if N is Poisson and {(V (t), ak (t))}t≥0 is jointly
ergodic with N , we can verify the following by using the
Poisson calculus [11] (see also [25]);
PAk (V (0) ∈ C) =E0N [1{V (0−)∈C} ak (0−)],
E0N [ak (0−)]

where V (0−) = limt↑0 V (t) and ak (0−) = limt↑0 ak (t). The
corresponding estimator is given bym
1{V (T −)∈C} ak (Tn −)−.
(12)(C; N ) = n=1 m nZk,mn=1 ak (Tn −)IV. I MPLEMENTATION

provided that (7) and (8) hold.
Remark 1 In the above discussion, {(V (t), ak (t); k =1, . . . , K)}t≥0 is interpreted as a sample path extracted fromthe corresponding stochastic process, where we assume neither
stationarity nor ergodicity of the stochastic process. Indeed, thevalue of (αk (C), αk ) in (7) and (8) may depend on the individual samples of {(V (t), ak (t))}t≥0 , while it can not dependon the sample of {N (t)}t≥0 once a sample of (αk (C), αk )is given. Furthermore, we can weaken the assumption of{N (t)}t≥0 such that it is asymptotically ergodic. Therefore,
we can use as {N (t)}t≥0 a non-delayed renewal process witha spread-out interarrival distribution (see [8]).
Remark 2 Also, once we assume that {(V (t), ak (t))}t≥0 is
stochastic and jointly ergodic with the sampling process N ,the result (9) reduces toE0 [1{V (0)∈C} ak (0)],PAk (V (0) ∈ C) = N
E0N [ak (0)]ttime of an active probe
packet arrival.

where asupk

= λN αk (C),neighborhood
after T nδneighborhood
before T nδSince the traffic is not fluid in practice, we have to consider
the practical implementation of the estimator Zk,m (C; N )−(C; N ) in (12) for k = 1, . . . , K
in (11) as well as Zk,mand C ∈ B(R+ ). Note that the network is monitored at
the arrival epochs of the active probe packets. When theinfluence of the active probe packets on the network is
negligible, we can assume that the sampling process N and{(V (t), ak (t); k = 1, . . . , K)}t≥0 are mutually independent.
In this case, the estimator Zk,m (C; N ), C ∈ B(R+ ), in (11)can be implemented as either of the following:m
1{V (T )∈C} ã+k (Tn , δ)+Z̃k,m (C; N ) = n=1m n +,(13)
n=1 ãk (Tn , δ)m
1{V (T −)∈C} ã−k (Tn , δ)
−
Z̃k,m
,
(14)
(C; N ) = n=1 m n −n=1 ãk (Tn , δ)−
where ã+k (t, δ) and ãk (t, δ) denote the numbers of packets
transmitted by user k observed during [t, t + δ) and [t − δ, t),respectively, and δ is a small positive number (Fig. 3). In

129

TABLE I
T RAFFIC MODEL .
transport layer
packetprotocollengthTCP
1.5 KBTCP
1.5 KBTCP
1.5 KBTCP
1.5 KBmean
ON period
10 s
5s
5s
1s

mean
OFF period
5s
10 s
15 s
19 s

the implementation of (13) [resp. (14)], {V (Tn )}mn=1 [resp.
]canbeobtainedbyactivemonitoringof the{V (Tn −)}m
n=1
−
m
m
(T
,
δ)}
[resp.
{ã
(T
,
δ)}
]
network and {ã+nnn=1n=1 is bykkpassive monitoring.
Let us consider the following two ways to realize the passive
monitoring device in CoMPACT Monitor (see the bottom
figure in Fig. 1).
• Realtime counting:
The passive monitoring device performs packet filteringand counting, on-line. It records a sequence of the numberof packets observed during [t, t + δ) or [t − δ, t), for eachk.
• Non-realtime counting:
The passive monitoring device monitors all packets andrecords a part of them, which includes sufficient information for packet filtering. Another procedure extracts
packet data observed during [t, t + δ) or [t − δ, t) fromthe recorded packet data, and counts them for each k.
In the first case, the implementation of (13) is easier thanthat of (14). This is because, while the arrival of the active
probe packet at Tn , n = 1, . . . , m, triggers the counting of theuser packet arrivals during [Tn , Tn + δ) in the implementationof (13), we have to record all the arrival epochs of user packets
to keep ready for the arrivals of active probe packets in that of(14). In addition, since realtime counting requires high-speed
packet filtering, it is difficult to realize for a broadband link.
In the second case, both the implementations of (13) and(14) are easy. So, when the influence of the active probe packets on the network is not negligible, by letting the active probe
packet stream be a Poisson process (the case of Remark 3),−(C; N ) in (14) can be used as the implementation ofZ̃k,m−Zk,m (C; N ) in (12). In addition, since the passive monitoring
device is simple, it can be applicable to a broadband link.

application layer
ON/OFF length
distribution
exp
exp
paretoparetoshapeparameter
–
–
1.5
1.5

rate atON period
1 Mbps
1 Mbps
1.5 Mbps
1.5 Mbps

20 source hosts

20 destination
hosts

1

1
1.5 Mbps

23
20

1.5 Mbps2

10 Mbpsrouterrouter...

connectionID#1 – #5#6 – #10#11 – #15
#16 – #20...

traffictype
type 1
type 2type 3type 43
20

passive monitoring
device for counting
destination of
packets
active probe packets

source ofactive probe packets

Fig. 4.

Network model.

on the left in Fig. 4 is a source and transfers data to thecorresponding host on the right. Characteristics of application
traffic are ON-OFF processes and are categorized into four
different types described in Table I. Each application traffic
type is assigned to five hosts and traffic is transferred by
TCP/IP. The size of user packets is 1500 bytes.
In addition, to support the use of active probe packets, there
is a pair of hosts for sending and receiving the active probe
packets. They are connected in the same manner as user hosts.
The active probe packets are 64 bytes long and are inserted
into the network according to Poisson process.
The passive monitoring device shown in Fig. 4 is forcounting packets in order to determine the likelihood ratio.
We conducted a 3600-s simulation using ns2 [4] andmonitored the queueing delay distributions for both active
probe packets and user packets. Simultaneously, we calculated
the queueing delay distribution by using the framework of
CoMPACT Monitor. Here, queueing delay means the sum of
the waiting time at buffers in the routers on the flow, i.e., endto-end delay is obtained from the sum of the queueing delay
and fixed delay determined by link capacity and packet size.
B. Queueing Delay Distributions for Individual Users

V. C HARACTERISTICS OF C O MPACT M ONITOR :S IMULATION R ESULTS
A. Network and Traffic Models
We investigate the characteristic of CoMPACT Monitor by
simulation. We use the network model shown in Fig. 4, whichhas 20 pairs of the source/destination hosts. Although the
network model looks simple, it can be considered as part of awhole network, extracted as a pair of source and destination
subnetworks. Link capacity between hosts and a router is
1.5 Mbps and that between routers is 10 Mbps. Each hostIn this subsection, we show that CoMPACT Monitor canestimate the queueing delay distribution for each user fromone common sequence of delay measurements using active
probe packets.
We have chosen a simpler implementation of CoMPACT
Monitor (13). To obtain ã+k (Tn , δ), n = 1, 2, . . . , the passive
monitoring device counts the number of packets. The lengthof the period [Tn , Tn + δ) for counting packets is 20 ms, i.e.,δ = 20 ms. Hereafter, we call the period [Tn , Tn + δ) theneighborhood of Tn and δ the length of the neighborhood.

130

1

1
user packet

user packet

CoMPACT Monitor

CoMPACT Monitor

active probe packet

active probe packet

0.1

0.1

0.01

0.01
0

0.04 0.08 0.12 0.16 0.20 0.24 [s]00.04 0.08 0.12 0.16 0.20 0.24 [s]Fig. 5.

Queueing delay distributions for connection #1.

Fig. 7.

Queueing delay distributions for connection #11.

1

1user packet

user packet

CoMPACT Monitor

CoMPACT Monitor

active probe packet

active probe packet

0.1

0.1

0.01

0.01
0

0.04 0.08 0.12 0.16 0.20 0.24 [s]00.04 0.08 0.12 0.16 0.20 0.24 [s]Fig. 6.

Queueing delay distributions for connection #6.

Fig. 8.

Queueing delay distributions for connection #16.

We insert active probe packets into the network to have
Poisson arrivals with a mean interval of 500 ms. The extra
traffic caused by the active probe packets is only about 0.01%
of the link capacity of 10 Mbps so the influence on user traffic
is negligible.
Among the 20 connections shown in Table I, we show thequeueing delay distributions (complementary distributions) for
connections #1, #6, #11, and #16, representing four different
traffic types, in Figs. 5–8. These figures show the queueing
delay distributions of user packets, those of active probe
packets, and those obtained from CoMPACT Monitor. The
distributions of active probe packets are, of course, the samein these figures.
Although simple active probe packets cannot estimate thequeueing delay that users experience, an implementation of
CoMPACT Monitor (13) can estimate the queueing delay
according to user traffic characteristics.

The significant difference between implementations (13)and (14) is in the difference between ã+k (Tn , δ), and
(T
,
δ),
n
=
1,
2,
.
.
.
.
That
is,
the
periodfor countingã−nkpackets is after Tn , [Tn , Tn + δ), or before Tn , [Tn − δ, Tn )(Fig. 3).
Figure 9 shows queueing delay distributions for both implementations (13) and (14) with δ = 20 ms. Active probe
packets are inserted into the network to have Poisson arrivals
with a mean interval of 500 ms. From this figure, both
implementations give almost the same distributions. Since
implementation (13) is simpler than that of (14), CoMPACT
Monitor can be implemented as (13) when the extra traffic for
active probe packets is negligible.

C. Implementation and Neighborhood

Next, we investigate the characteristics of CoMPACT Monitor with respect to δ. Figure 10 shows queueing delay distributions for connection #16 obtained from the implementation(13) with δ = 20, 40, and 80 ms. Other conditions are thesame as in the above simulation.

This subsection shows the difference between two implementations (13) and (14), and investigates the influence ofneighborhood size, δ.
We show a result for connection #16 among the connections
shown in Table I. The traffic type including connection #16
has the smallest average rate and the strongest burstiness.

This figure shows that the accuracy of implementation (13)is independent of the neighborhood size, at least, in this rangeof these simulations. This means that it is not necessary to set
a very short size for δ, and we can avoid quick switching of
the packet counter between start and stop by setting a medium
length for δ.

131

1

1
before Tn

user packet

after Tn

CoMPACT Monitor(interval: 1000 msec)

0.1

0.1

0.01

0.01
0

0

0.04 0.08 0.12 0.16 0.20 0.24 [s]Fig. 9. Queueing delay distributions for two implementations, (13) and (14).

A
A
AAA
A
AAA
AA
A
A
AAA
AA
AAA
AAA
AAAAA
AAA
AA
AAA
AAAA
AAA
AA
0.1
AAAA
AAAA
AAA
AA
AA
AA
AA
AAA
AAA
0.01
A [s]
0
0.04 0.08 0.12 0.16 0.20 0.24
1

Fig. 11. Queueing delay distribution for interval of active probe packets:
1000 ms.

1

δ = 20 ms
δ = 40 ms

user packet

δ = 80 ms

CoMPACT Monitor(interval: 250 msec)

0.1

0.01
0

Fig. 10.

0.04 0.08 0.12 0.16 0.20 0.24 [s]0.04 0.08 0.12 0.16 0.20 0.24 [s]Queueing delay distributions for different neighborhood sizes.
Fig. 12.
250 ms.

Queueing delay distribution for interval of active probe packets:

D. Interval of Active Probe Packets
This subsection shows the characteristics of CoMPACT
Monitor with respect to the interval of active probe packets.
Similarly to the above simulations, we choose connection#16. Figures 11 and 12 show queueing delay distributions
for connection #16 obtained by the implementation (13) with
1000 ms and 250 ms for the mean active probe packet interval, respectively. Queueing delay distributions experienced byconnection #16 are also shown in these figures. In both cases,
the extra traffic caused by active probe packets is negligible,
about 0.005% and 0.02% of the link capacity, respectively.
We compare them with Fig. 8 for a mean interval of
500 ms. We can recognize that a smaller interval gives a moreaccurate delay estimation. Because the interval of active probe
packets does not influence the accuracy of estimation from theframework of CoMPACT Monitor, the interval is not essential
but the number of samples is. To verify this, we compare
relative errors|(x%ile from CoMPACT Monitor)−(x%ile of user delay)|(x%ile of user delay)

for the 90%ile, 95%ile, and 99%ile of the distributions forthree different mean intervals, and each is shown in Figs. 13–
15. They are obtained from five independent simulations. The
relative errors of 90%ile value are almost the same but that of
99%ile value is different. These results imply that we cannot

have enough samples to estimate the 99%ile value for a 1000ms interval of active probe packets.
From the above discussion, it is necessary to determine
an appropriate interval for active probe packet taking into
consideration the following factor:
Required accuracy of estimation,
Time constraint to finish the monitoring, and• Permissible extra traffic caused by active probe packets.
••

VI. C ONCLUSIONSIn this paper, we showed the mathematical formulation of
CoMPACT Monitor without assuming stationarity or ergodicity for user traffic. The characteristics and performance associated with the implementation issues in CoMPACT Monitor
were investigated by simulation. Unlike conventional active
measurements, CoMPACT Monitor can estimate the delay
distribution for individual flows that we want to measure. In
addition, it enables us to make a scalable and lightweightmeasurement system and can be implemented in a simple way.
Since the passive monitoring device described in this papercounts the number of packet, we can obtain the delay distribution with respect to packet. In the framework of CoMPACT
Monitor, if the passive monitoring device accumulates the

132

0.05
0.04
0.03
0.02
0.01
0
Fig. 13.

0.05
0.04
0.03
0.02
0.01
0
Fig. 14.

0.05
0.04
0.03
0.02
0.01
0
Fig. 15.

1000 ms

500 ms

250 msRelative error of 90%ile value of queueing delay.

1000 ms

500 ms

250 msRelative error of 95%ile value of queueing delay.

1000 ms

500 ms

250 msRelative error of 99%ile value of queueing delay.

bytes of packets, we can obtain the delay distribution withrespect to byte.
We focused on one-way delay in this paper. Although
this is important for video streaming, VoIP, and the otherrealtime services, there are other significant QoS parameters:for example, loss, round-trip delay, throughput, and Web server
workload experienced by a user packet flow. We should extend
CoMPACT Monitor for other QoS parameters. These issues
are for further study.
R EFERENCES[3] IPMA: Internet performance measurement and analysis.
http://www.merit.edu/ipma/ .
[4] UCB/LBNL/VINT Network Simulator – ns (version 2).
http://www.isi.edu/nsnam/ns/ .
[5] M. Aida, K. Ishibashi and T. Kanazawa. CoMPACT-Monitor: Changeof-measure based passive/active monitoring—weighted active sampling
scheme to infer QoS—. Proc. of IEEE SAINT 2002 Workshop (2002)
119–125.
[6] G. Almes, S. Kalidindi, and M. Zekauskas. A one-way delay metric for
IPPM. RFC2679, (1999).
[7] G. Almes, S. Kalidindi, and M. Zekauskas. A one-way packet loss metricfor IPPM. RFC2680, (1999).
[8] S. Asmussen. Applied Probability and Queues. Wiley (1987).
[9] F. Baccelli and P. Brémaud. Elements of Queueing Theory: Palmmartingale Calculus and Stochastic Recurrences. Springer (1994).
[10] J.C. Bolot. Characterizing end-to-end packet delay and loss in theinternet. Journal of High Speed Networks, 2(3), September (1993) 289–
298.
[11] P. Brémaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, andQueues. Springer (1999).
[12] R. Caceres, N.G Duffield, J. Horowitz, D.F. Towsley, and T. Bu.
Multicast-based inference of network-internal characteristics: Accuracyof packet loss estimation. Proc. of IEEE INFOCOM’99, (1999) 371–379.
[13] D.J. Daley and D. Vere-Jones. An Introduction to the Theory of Point
Processes. Springer (1988).
[14] P. Glynn and K. Sigman. Independent sampling of a stochastic process.
Stochastic Process. Appl., 74 (1998) 151–164.
[15] K. Ishibashi, T. Kanazawa, and M. Aida. Active/passive combinationtype performance measurement method using change-of-measure framework. Proc. of IEEE GLOBECOM 2002, (2002).
[16] S. Keshave. A control theoretic approach to flow control. Proc. of ACM
SIGCOM’91, (1991) 3–15.
[17] T. Lindh. A framework for embedded monitoring of QoS parameters in
IP-based virtual private networks. Proc. of Passive and Active Measurements (PAM 2001), 2001.
[18] T. Lindh. A new approach to performance monitoring in IP networks— combining active and passive methods. Proc. of Passive and Active
Measurements (PAM 2002), 2002.
[19] V. Paxson and S. Floyd. Wide-area traffic: The failure of Poissonmodeling. IEEE/ACM Trans. on Networking, 3(3), June (1995) 226–
244.
[20] V. Paxson, J. Mahdavi, A. Adams, and M. Mathis. An architecture forlarge-scale Internet. IEEE Communications, 36(8) (1998) 48–54.
[21] V. Paxson. End-end Internet packet dynamics, IEEE/ACM Trans. on
Networking, 7(3) (1999) 277–292.
[22] V. Paxson, G. Almes, J. Mahdavi, and M. Mathis. Framework for IP
performance metric. RFC 2330, (1998).
[23] S. Savage, A. Collins, E. Hoffman, J. Snell, and T. Anderson. The endto-end effects on Internet path selection. Proc. of ACM SIGCOM’99,(1999) 289–299[24] W.R. Stevens. TCP/IP illustrated, Vol. 1. Addison-Wesley, Reading MA,
1994.
[25] R.W. Wolff. Poisson arrivals see time averages. Oper. Res., 30 (1982)
223–231.

[1] CAIDA cooporative association for internet data analysis.
http://www.caida.org/tools/ .
[2] NLANR measurement and operation analysis team.
http://moat.nlanr.net/ .

133