IEICE TRANS. INF. & SYST., VOL.E86–D, NO.11 NOVEMBER 2003

2371

PAPER

Special Issue on New Technologies in the Internet and their Applications

Proposal and Evaluation of Method to Estimate Packet
Loss-Rate Using Correlation of Packet Delay and Loss
Keisuke ISHIBASHI† , Masaki AIDA† , and Shin-ichi KURIBAYASHI† , Regular Members

SUMMARY
We previously proposed a change-of-measure
based performance measurement method which combines active
and passive measurement to estimate performance experienced
by user packets and applied this to estimate packet delay. In
this paper, we apply it to estimating loss rate. Since packets
are rarely lost in current networks, rate measurement usuallyrequires a huge number of probe packets, which imposes a nonnegligible load on networks. We propose a loss-rate estimation
method which requires signiﬁcantly fewer number of probe packets. In our proposed method, the correlation between delay andloss is measured in advance, and at the time of measurement,
the time-averaged loss rate is estimated by using the delay ofprobe packets and the correlation. We also applied our changeof-measure framework to estimating the loss rate in user packets
by using this time-averaged loss rate. We prove that the meansquare error in our method is lower than that simple loss measurement, which is estimated by dividing the number of lost packets
by the total number of sent packets. We evaluated our method
through simulations and actual measurements and found that it
can estimate below 10−3 packet loss rate with only 900 probe
packets.
key words: packet loss rate, transmission delay, change of measure, QoS

1.

Introduction

We previously proposed a lightweight and scalable
method of measuring performance, CoMPACT Monitor, that combines active and passive measurement toestimate performance experienced by users. We also
used it to estimate the delay in user packets [1], [2]. In
this paper, we report the use of it to estimate the endto-end loss rate for user packets.
Packet losses signiﬁcantly degrade the QoS of UDP
applications such as streaming or Voice over IP [3], [4].
TCP throughput also depends on a packet loss rate in alarge bandwidth-delay product environment [5]. Therefore, it is necessary to measure the packet loss rate to
manage the service level of these applications. In termsof managing service level, we need to know not only thestationary packet loss rate as an indicator of network
performance, but also the time-varying loss rates for
relatively short time periods (e.g., duration of streaming videos), as service-level statistics.
In general, methods of measuring network performance can be divided into two types: passive and active. Passive methods capture user packets and deterManuscript received March 4, 2003.
The authors are with NTT Information Sharing Platform Laboratories, NTT Corporation, Musashino-shi, 180–
8585 Japan.
†

mine network performance using their data. For example, we can detect the loss in packets by comparing
two sets of time-series data captured with monitoring
devices deployed at ingress and egress points on the
network. By measuring the performance of the network
passively, we can evaluate the performance experienced
by users packets. However, these methods require theidentiﬁcation of each packet by header and/or content,
which is diﬃcult with the huge traﬃc volumes in highspeed networks. Furthermore, the passive devices may
fail to capture all packets [6], which leads to errors inestimating the loss rate. A management informationbase (MIB) such as “IfOutDiscards” can be used tomonitor the packet loss at the router, but cannot be
used to obtain end-to-end loss rate.
Active methods, on the other hand, can simply be
used to measure the performance of a network by sending probe packets and monitoring the delay or loss inthese. However, there are two drawbacks with current
active loss measurement.
First, when loss rate is low, active methods senda huge number of probe packets to detect packet losses
that rarely occur. This imposes a non-negligible loadon the network, especially when we measure the loss
rate for a short period of time. While there are many
tools for actively measuring packet loss rate [7], they
only make use of information on lost probe packets anddo not use other available packet information. With
those methods, the required number of probe packets to measure the loss rate is roughly an order morethan the reciprocal of the rate when losses occur independently. When there is a correlation between loss
events, which has been reported in many Internet loss
measurements [8]–[13], we do not need as many probe
packets. Yet, the required number of probe packets
is still large and those probe packets may perturb the
networks [16]. Matsumoto et al. proposed a method of
estimating packet loss rate through packet trains [14].
They used the increase in loss rate for successive packets in the train to estimate the loss rate of ﬁrst packet,
which is the time-average loss rate. Although their accuracy of estimating loss rate is expected to be improved beyond conventional methods, it also only uses
information on lost probe packets, so there is room toimprove accuracy by fully using all available information.
Second, the loss rate measured by probe packets

IEICE TRANS. INF. & SYST., VOL.E86–D, NO.11 NOVEMBER 2003

2372

may not be the same as that experienced by user packets [16]. If we assume that active monitoring measures
the time average of network performance and that user
traﬃc is Poissonian, then the performance experienced
by users and actively measured performance will be thesame. This is a well-known property called PASTA(which stands for “Poisson Arrivals See Time Average”) [17]. It is known, however, that current Internet
traﬃc exhibits burstiness and is not Poissonian, in general [18]. In that case, more user packets are transmitted during congested periods, which means that moreuser packets experience a high loss rate. Thus, the loss
rate experienced by users may actually be higher thanthat measured by those active monitoring. We previously proposed a method that can estimate the performance experienced by users by combining active andpassive monitoring [1], [2]. We also applied this method
to packet-delay estimation. However, if we simply apply it to estimating loss rate without considering theﬁrst drawback, the estimated loss rate may deviate fromthe actual loss rate when the number of probe packets
is limited.
In this paper, we propose a method of estimating packet loss-rate using delay information in probe
packets to overcome the ﬁrst drawback. We use an
intuitive expectation that when the delay of a probe
packet is large, then the loss probability of user packets sent near the probe packet is high. We propose an
estimator for the time-average loss rate that uses thecorrelation between loss and delay. As for using the delay measurement to estimate the loss rate, there is alsoa research that uses large deviation theory and estimates the buﬀer overﬂow probability (loss probability)
by measuring the buﬀer occupancy (delay) [15]. However this scheme use the buﬀer size in the estimation,
thus the size should be known, which is hard in current networks. Furthermore, the method can only beapplied single-hop case. Our method does not require
any network speciﬁc information, rather measures theinformation itself. Thus it can be applied to estimate
the loss rate for multiple-hop path. We also combine
the concept of CoMPACT Monitor and this estimator,
and propose an estimator for the loss rate experienced
by users. We prove that the mean square error (MSE)of our method is smaller than those of simple loss measurement. The method was also evaluated through simulations and actual measurements and those showedthat it can estimate below 10−3 packet loss rate with
only 900 probe packets.
The rest of this paper is organized as follows. Section 2 presents the proposed loss measurement method.
Simulations and actual measurement experiments aredescribed in Sect. 3. Finally, we give summary in
Sect. 4.

2.

Proposed Measurement Method

Our method of estimating the user-packets loss rate
involves the following two steps:
Step 1: Estimating the time-average loss rate using
actively measured delay and loss.
Step 2: Converting the time-average loss rate to theloss rate experienced by user packets by using passively measured traﬃc intensity.
These steps are explained in more details in the next
two subsections.
2.1 Time-Averaged Loss Rate
2.1.1

Loss Rate Estimation Using Delay Information

The main diﬃculty in this step is measuring rare eventswith fewer samples (probe packets). We overcome thisdiﬃculty by using delay information about probe packets that are not lost.
The objective of this step, time-average loss rateduring (t1 , t2 ] LR(t1 , t2 ), is deﬁned as t2
1
LR(t1 , t2 ) :=1{V (t)=Dl } dt,(1)t2 − t1 t1
where 1{·} is the indicator function, V (t) is the virtual
delay of the packet sent at t, Dl is a value set larger
than the maximum delay, and V (t) = Dl indicates thepacket is lost. Here, we use the word “virtual” because
there may not be any actual user packets at time t [17].
A simple estimator of LR(t1 , t2 ) with n probe
packets sent during (t1 , t2 ], SELR(n), isn

SELR(n) :=1
1{Yi =Dl } ,
n i=1

(2)

where Yi is the delay for i-th probe packet and Yi = Dl
indicates the packet is lost. We also deﬁne ti as thetransmission time for the i-th probe packet, so V (ti ) =Yi . Actually, if probe packets are sent independentlyof V (t), i.e. in a Poisson manner, (2) is a consistentestimator of (1). However, when seeing an individual
estimation for a measurement of a short time period,
it may be signiﬁcantly diﬀerent from LR(t1 , t2 ) when
the loss rate is low and the number of probe packets
is limited. Now, we can intuitively expect that even
if a probe packet is not lost, when the delay for theprobe is large, then the loss rate around the time of theprobe packet is high, as reported in [10]. Therefore,
we propose an estimation method that uses the correlation between the delay of a packet and the loss of theneighboring packets.
First, let us deﬁne the conditional loss probabilitylc (t, τ, x) as follows:ISHIBASHI et al.: PACKET LOSS-RATE ESTIMATION METHOD

2373

Fig. 1

loss rate of the neighborhood of the probe packets. By
using the delay in probe packets and the correlation
between the delay and loss probability. Actually, we
can show that the mean square error in the proposed
method is smaller than that in simple loss rate estimaδtion (2). Let R(x) be R(x) := −δ+− lc (t, x)dt/(δ+ + δ− )and f1 (Dl ) be the stationary loss probability, i.e.,f1 (Dl ) := E[1{V (0)=Dl } ] = 1 − F1 (Dl −). Then, the difference between the mean square error (MSE) of the
proposed method and MSE of the simple estimationfor one probe packet case is given as

Conditional loss probability lc (t, τ, x).

lc (t, τ, x):=Pr [V (t + τ ) = Dl V (t) = x].

(3)

For large delay x, the conditional loss probability of apacket sent near t is expected to be high and to decrease as |τ | increases (Fig. 1). Here, we assume thatlc (t, τ, x) is stationary (independent of t), and denote
this as lc (τ, x).
Then, given the delay of the i-th probe packet, Yi ,we obtain the unconditional loss probability for time
ti + τ as lc (τ, Yi ). Therefore, the loss rate in the neighborhood of ti , (ti −δ− , ti +δ+ ] (δ− , δ+ ≥ 0), is estimated
by
 δ+
1
lc (τ, Yi ) dτ.
(4)
δ+ + δ− −δ−While 1{Yi =Dl } in (2) only takes 0 or 1, (4) takes value
from 0 to 1 even if Yi = Dl .
The expectation of (4) in terms of Yi agrees with
E[LR(ti − δ− , ti + δ+ )] because
 

δ+

E
−δ−

E[(SELR(1) − LR(1, −δ− , δ+ ))2 ]−E[(ELR(1) − LR(−δ− , δ+ ))2 ] Dl −
R(x)2 dF1 (x) ≥ 0. (7)= f1 (Dl ) (1 − R(Dl ))2 +0

The proof is in the Appendix. Errors in multiple packets can roughly be obtained by dividing the MSE by
the number of probe packets if we can assume that error between probe packets is independent. Equation(7) indicates that the error in our estimator is smaller
than or equal to that of a simple loss estimator. The
ﬁrst term equals zero if the mean packet loss probability near the lost probe packet is one. The second
term is zero if the mean loss probability near a probe
packet is zero even when the delay of the probe packet
is large. Although packet loss on the Internet exhibitsa high degree of burstiness [11], a situation where bothterms equal zero can hardly be expected, especially fora relatively large δ.

δ+lc (τ, Yi ) dτ =−δ−E[lc (τ, Yi )] dτ

2.1.2

 δ+  Dl
=
−δ−

 δ+
=

−δ−

0

lc (τ, x) dFi (x) dτPr[V (ti + τ ) = Dl ] dτ

 δ+
=

−δ−

E[1{V (ti +τ )=Dl } ] dτti +δ+=Eti −δ−


1{V (τ )=Dl } dτ , (5)where Fi (x) = Pr[V (ti ) ≤ x]. Therefore, using conditional probability lc (τ, x) and n measurements of probe
packets {Y1 , Y2 , . . . , Yn } sent in (t1 , t2 ], we obtain another estimator for LR(t1 , t2 ) by changing 1{Y (i)=Dl }in SELR to (4) as
 δ+
n
1
1
ELR(n, δ+ , δ− ) :=lc (τ, Yi ) dτ. (6)n i=1 δ+ + δ− −δ−Compared to (2) which only uses the loss rate intiming the probe packet transmission, the estimator (6)is expected to be more accurate because it uses theConditional Loss Probability

Our estimator (6) requires conditional loss probabilitylc (τ, x). This can be obtained through either preprocessing or in an online way. In preprocessing, probe
packets are sent with short intervals, and we can takethe loss and delay pairs of the interval. The interval
should be suﬃciently short that the integral in (6) canbe approximated by the sum of the intervals. Then,lc (τ, x) can be calculated using the loss and delay pairs.
Of course, the accuracy of the estimate depends on thenumber of pairs used to calculate conditional probability. We will discuss this in Sect. 3.2.2. We expect
this probability remain almost unchanged in a network
path during a period of time that can be considered
as stationary (such as a busy period). Thus, once thelc (τ, x) of a period of time has been obtained, we canuse this for other measurements done in the same period of time. However, to cope with gradual changes
in network conditions, introducing an online update oflc (τ, x) may be better. In that case the delay and loss
pairs for diﬀerent intervals can be obtained by sending probe packets with diﬀerent intervals (e.g. Poissonprocess), while simultaneously measuring the loss rate.
Then, lc (τ, x) is updated with these delay and loss pairs,

IEICE TRANS. INF. & SYST., VOL.E86–D, NO.11 NOVEMBER 2003

2374

for example, by taking a moving average.
2.2 User-Packet Loss Rate
This step uses our previously proposed method to estimate the delay in user packets [1], [2]. In this subsection, we present a brief review of it and its combination
with the results obtained in Step 1. The mathematicalfoundation of the method can be found in [1], [2].
Our proposed change-of-measure based network
performance measurement method, CoMPACT Monitor, was aimed at estimating the network performanceexperienced by users. To do this, it actively measures
the performance through probe packets, and passively
measures the number of user packets sent near theprobe packets. Then, by changing the measure for the
performance of probe packets to that of user packets,
we can obtain an estimator of network performance experienced by users.
The objective of this step is to estimate theloss rate experienced by user packets sent in (t1 , t2 ],U LR(t1 , t2 ): t2
1{V (t)=Dl } dA(t)U LR(t1 , t2 ) = t1  t2
,
(8)
dA(t)
t1
where A(t) is the arrival process for user packets. Here,the denominator represents the number of user packets
sent in (t1 , t2 ] and the numerator represents the numberof lost user packets.
Modeling A(t) as a ﬂuid, we demonstrated that an
empirical distribution of the delay for any user ﬂuid
A(t) could be obtained using actively and passively
measured values [1]. Let a(i) be user traﬃc intensity at
ti , i.e., dA(t)/dt at the i-th active measurement timing.
The a(i) is obtained through passive measurement by
counting the number of user packets. Assuming thatmeasurement timing is stationary, it can be proved for
any D ∈ R+ that t2
1{V (t)>D} dA(t)lim t1  t2
t2 →∞t1 dA(t)ni=1 1{Yi >D} a(i)
n
a.s.
(9)
= lim
n→∞
i=0 a(i)Therefore, by setting D to Dl −, a(i) as the numberofnuser packets sent in (ti − δ− , ti + δ+ ], and u as thei=1 a(i), we obtain an estimator of (8) by simply applying the change-of-measure method aslasts long enough. However, because it assumes thatuser packets sent near the lost probe packet will all belost, otherwise no user packets are lost, it shares thesame problem as (2).
Therefore, by combining the results of Step 1 andthe change-of-measure based method, we propose an
estimator to determine the loss rate for user packets
EU LR(n, δ+ , δ− ) as:=

EU LR(n, δ+ , δ− ) δ+n1  a(i)u i=1 δ+ + δ−−δ−lc (τ, Yi ) dτ.

This estimator is obtained by changing 1{Yi =Dl } in (10) δ+
1to δ+ +δ−δ− lc (τ, Yi ) dτ the same as the relationship−between (2) and (6).
3.

Evaluation

3.1 Simulation Results
We evaluated our method through ns-2 simulator [19]for the network in Fig. 2. User sources generate exponential On-Oﬀ traﬃc, whose means are 1 s and 14 s,
respectively. During the On period, 1,000-byte packets were sent with an exponentially distributed intervalwith a mean of 10.6 ms. Thus, each source sent packets at 50 kbps on average. We varied the number ofsources as 100, 140, and 180 so that the utilization rateof the intermediate link was 0.5, 0.7, and 0.9, respectively. The buﬀer capacity of the router was set to 50
packets.
To obtain conditional loss probability, lc (τ, x), we
ﬁrst ran a 50,000-s simulation in advance where 64-byteprobe packets were sent with an exponential intervalwith a mean of 10 ms. Extra traﬃc caused by theseprobe packets is about 50 Kbps.
This Poisson sampling was recommended in [20]to measure unbiased statistics. The lc (τ, x) were calculated using the loss and delay information of theseprobe packets. After calculating lc (τ, x), we ran 10
simulations each lasting 1, 000 s and calculated ELR
and EU LR. In each run, probe and user packets weresent in the same way as in the ﬁrst 50,000-s simulation.
Time-average loss rate, LR, was calculated using allprobe packets, and user-average loss rate, U LR, wascalculated using all 1,000-byte packets. To estimate
loss rate, we only used one probe packet per 100 proben

SEU LR(n) :=1
1{Yi =Dl } a(i).
u i=1

(10)

Compared with (2), the estimator (10) weights theevent Y (i) = Dl by a(i) to convert the time-averageloss rate to the user-experienced loss rate. SELR has
been proved to agree with U LR if the measurement(11)

Fig. 2

Network conﬁguration for simulation.

ISHIBASHI et al.: PACKET LOSS-RATE ESTIMATION METHOD

2375

Fig. 5
hosts.

Mean square errors for time-average loss rate for 100

Fig. 6
hosts.

Mean square errors for time-average loss rate for 140

Fig. 7
hosts.

Mean square errors for time-average loss rate for 180

Fig. 3 Conditional loss probability (lc (τ, x)) for x = 0 and
20 (ms).

Fig. 4

Loss rate and its estimation for ten simulations.

packets. In other words, we only sent one probe packet
every second on average during actual measurements.
We set (δ+ , δ− ) = (100, 100) (ms) in this paper. The
maximum delay was 29 ms. Figure 3 shows lc (τ, 0) andlc (τ, 20) with 140 hosts for the δ+ side. As expected,lc (τ, 20) decreased as τ increased. We can also see thatlc (τ, 0) increased as τ increased and converged to a constant, which is expected to be the time-average loss rate(unconditional loss probability).
3.1.1

Time-Averaged Loss Rate

First, we tested ELR, the estimator for time-averageloss rate. Figure 4 shows LR (time-average loss rate),
SELR (estimates using only the loss information ofprobe packets), and ELR (estimates using both delay
and loss information of probe packets) for ten simulations with 140 hosts. We see that while SELRs deviated from LRs, ELR could estimate LR with highaccuracy. Note that while we used the same lc (τ, x)
for all estimates, ELR could estimate diﬀerent values
for LR for ten simulations, by reﬂecting diﬀerences inprobe delays. We can also see that no probe packets
were lost in simulations 2, 3, 5, and 6, while ELR could
estimate loss rate by using delay information. We also
compared mean square errors, E[(ELR − LR)2 ] andE[(SELR − LR)2 ] by varying t2 = 200, 400, 600, 800,
and 1, 000 s (we ﬁxed t1 at 0). Figures 5-7 show theresults for the case of 100, 140, and 180 hosts, respectively. The accuracy of our method was higher thanFig. 8Loss and its estimations results for ten simulations.

that for the simple loss rate estimation as (7).
3.1.2

User-Packet Loss Rate

Next, we tested EU LR, the estimator of the loss
rate in user packets. Figure 8 shows the U LR (userexperienced loss rate), SEU LR (estimates of U LR using only loss information of probe packets and numberof user packets), and EU LR (estimates of U LR using

IEICE TRANS. INF. & SYST., VOL.E86–D, NO.11 NOVEMBER 2003

2376

Fig. 9hosts.

Mean square errors for user-experienced loss rate for 100

Fig. 12 Sample path of delay and loss in measurement (Losses
are shown as 250 ms delay).

Fig. 10 Mean square errors for user-experienced loss rate for
140 hosts.
Fig. 13 Conditional loss probability (lc (τ, x)) for x = 70 and
170 (ms).

Fig. 11 Mean square errors for user-experienced loss rate for
180 hosts.

both delay and loss information of probe packets andnumber of user packets) for 140 hosts case. We can also
see from this ﬁgure that our estimation could follow
the loss rate for user packets, which was about 1%, i.e.
higher than the time-average loss rate shown in Fig. 4.
This was due to the correlation between the number ofuser packets and the loss rate, which was discussed in
Sect. 1. By weighting the loss rate with the number ofuser packets sent near probe packets, our method could
convert the time-average loss rate to an user-averageloss-rate. Figures 9-11 show the mean square error forthe case of 100, 140, and 180 hosts, respectively. Ourestimator achieved a lower mean square error comparedwith the simple change-of-measure method.
3.2 Actual Measurement Results
We did end-to-end loss and delay measurements on an
actual network to evaluate our method. We measured
one-way delay and loss from an asymmetric digital subscriber line (ADSL) customer LAN to a company LAN
during oﬃce hours (10:00-18:00) in February 2003.

The two LANs were connected via two ISPs, where
the path consisted of 15 hops. The narrowest link along
the path was the ADSL up-link, with a bandwidth ofabout 400 Kbps† . Here, we only evaluated the estimator for time-average loss rate because there were no user
packets on the link.
We sent 64-byte UDP packets between two GPSsynchronized PCs in both LANs as a Poisson process
where the mean interval was 20 ms. We ran thirty measurements each lasting 900 s and used the ﬁrst twenty to
calculate conditional loss probability, and the last ten
to estimate loss rate. The maximum, mean and minimum delay were 207, 60, and 20 ms. The time-averageloss rate for the whole measurement was 0.07%.
Figure 12 shows a sample path for the delay andloss of the probe packets (Here, loss is shown as 250 ms).
We can see the ﬂuctuations in delay and packet losses
during some peaks of ﬂuctuation. This indicates that
there is a correlation between loss and delay even in
the actual network. To provide more direct evidence of
this correlation, Fig. 13 has conditional loss probability
for delays of 70 ms and 170 ms (Broken parts of the line
indicate that the measured conditional loss probability
is zero). There is a clear correlation between loss anddelay the same as in simulation.
3.2.1

Time-Averaged Loss Rate

Figure 14 shows LR, SELR, and ELR for 10 measure†During the measurements, because no packets except
active probe packets were sent to the link, it could not cause
queueing delays or losses for the probe packets on the link.

ISHIBASHI et al.: PACKET LOSS-RATE ESTIMATION METHOD

2377

Fig. 14

Loss rate and its estimations for ten measurements.

Fig. 16 Mean square errors varing the numberof measurements to calculate the conditional loss
probability.

4.

Fig. 15

Mean square errors for time-average loss rate.

ments where LR was calculated using all probe packets,
and ELR and SELR was estimated by using one probe
packets per 50 packets. In these simulations, as the loss
rate varied from 10−5 to 10−3 , we plotted the loss ratesemi-logarithmically. Except for measurements 2 and 3,
no probe packets used for calculating ELR and SELR
were lost, and the SELR was zero, which cannot beshown in the ﬁgure. Even so, our method could estimate time-average loss rate accurately especially forloss rates over 10−4 . Figure 15 shows the mean squareerrors of proposed estimator ELR and simple loss estimator SELR. The errors for ELR are smaller thanthose for SELR for every number of probe packets.
Because our method can estimate the average loss rateof few minutes, our method is well-adopted to Internet
streaming applications such as movie trailers whose duration is reported as about few minutes [21].
3.2.2

Number of Pairs to Calculate the Conditional
Loss Probability

To see the eﬀect of the number of pairs used to calculate conditional loss probability to the accuracy of
estimates, we varied the number of measurements tocalculate lc (τ, x) and compared these with the meansquare error of ELR (Fig. 16). We can see that withconditional loss probability calculated with ten measurements, the MSE converged to a constant. Thus, inthis environment, 10,000-s measurements or 5,000,000
delay and loss pairs suﬃced to calculate conditional loss
probability.

Conclusion

We proposed a two-step method of estimating the loss
rate in user packets that involved: 1) estimating thetime-average loss rate and 2) converting that rate to
the user-experienced loss rate. We used the delay inprobe packets and the conditional loss probability givenby their delay in Step 1. In Step 2, the time-averageloss rate estimated in Step 1 was converted to the userexperienced loss rate through our previously proposedchange-of-measure based method. Our method canbe used to estimate both the time-average and userexperienced loss rate accurately with a limited numberof probe packets. It can be used to determine the average loss rate over short periods of time such as durationof a streaming videos or phone calls.
Acknowledgements
We wish to thank Ms. Kyoko Ashitagawa for her help
with the simulations and Mr. Takashi G. Inoue for assistance with the measurements in our experiment. We
also wish to thank Dr. Attila Vidacs for his valuablecomments.
References[1] M. Aida, N. Miyoshi, and K. Ishibashi, “A scalable andlightweight QoS monitoring technique combining passive
and active approaches,” Proc. IEEE INFOCOM 2003,
pp.125–133, March 2003.
[2] K. Ishibashi, T. Kanazawa, and M. Aida, “Active/passive
combination-type performance measurement method usingchange-of-measure framework,” Proc. IEEE GLOBECOM
2002, pp.2538–2542, Nov. 2002.
[3] T.J. Kostas, M.S. Borella, I. Sidhu, G.M. Schuster, J.
Grabiec, and J. Mahler, “Real-time voice over packet
switched networks,” IEEE Network, vol.12, no.1, pp.18–27,
Jan./Feb. 1998.
[4] D. Loguinov and H. Radha, “Large-scale experimental
study of Internet performance using video traﬃc,” ACM
SIGCOMM Computer Communication Review, vol.32,
no.1, pp.7–19, Jan. 2002.

IEICE TRANS. INF. & SYST., VOL.E86–D, NO.11 NOVEMBER 2003

2378

[5] J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, “Modeling TCP throughput: A simple model and its empiricalvalidation,” Proc. ACM SIGCOMM ’98, pp.303–314, 1998.
[6] K. Papagiannaki, S. Moon, C. Fraleigh, P. Thiran, F.
Tobagi, and C. Diot, “Analysis and measured single-hop
delay from an operational backbone network,” Proc. IEEE
INFOCOM 2002, pp.908–921, June 2002.
[7] “Caida: Internet measurement tool taxonomy,”
http://www.caida.org/tools/taxonomy/index.xml[8] V. Paxson, “End-to-end Internet packet dynamics,” IEEE/
ACM Trans. Netw., vol.7, no.3, pp.277–292, 1999.
[9] J.-C. Bolot, “Characterizing end-to-end packet delay andloss in the Internet,” Proc. ACM SIGCOMM’93, pp.289–
298, Sept. 1993.
[10] S.B. Moon, J. Kurose, and D. Towsley, “Correlation of
packet delay and loss in the Internet,” Technical Report98-11, Department of Computer Science, University of Massachusetts, Amherst, MA, 2003.
[11] M. Yajnik, S. Moon, J. Kurose, and D. Towsley, “Measurement and modelling of the temporal dependence in packet
loss,” Proc. INFOCOM ’99, pp.345–352, March 1999.
[12] M.S. Borella, D. Swider, S. Uludag, and G.B. Brewster,“Internet packet loss: Measurement and implications forend-to-end QoS,” Proc. International Conference on Parallel Processing, pp.3–14, Aug. 1998.
[13] K. Mochalski, J. Micheel, and S. Donnelly, “Packet delay and loss at the auckland Internet access path,” Proc.
PAM2002, March 2002.
[14] Y. Matsumoto, K. Kawahara, and Y. Oie, “Proposal andevaluation of packet loss rate inference scheme by using
packet train method for active measurement,” IEICE Technical Report, IN2002-188, Feb. 2003.
[15] S. Shioda and H. Saito, “Real-time cell loss ratio estimationand its applications to ATM traﬃc controls,” Proc. IEEE
INFOCOM ’97, pp.1072–1079, April 1997.
[16] G. Almes, S. Kalidindi, and M. Zekauskas, “A one-way
packet loss metric for IPPM,” RFC2680, Sept. 1999.
[17] R.W. Wolﬀ, Stochastic Modeling and the Theory of Queues,
Prentice-Hall, 1988.
[18] V. Paxson and S. Floyd, “Wide-area traﬃc: The failure ofPoisson modeling,” IEEE/ACM Trans. Netw., vol.3, no.3,
pp.226–244, 1995.
[19] UCB/LBNL/VINT Network Simulator - ns (version 2),
http://www.isi.edu/nsnam/ns[20] V. Paxson, G. Almes, J. Mahdavi, and M. Mathis, “Framework for IP performance metrics,” RFC2330, May 1998.
[21] A. Koike, S. Takigawa, K. Takeda, A. Kobayashi, M.
Morimoto, and K. Kawashima, “Characteristics of movie
contents and its impact for traﬃc design,” IEICE Trans.
Commun., vol.E86-B, no.6, pp.1839–1848, June 2003.

Appendix:

Proof of Equation (7)By conditioning the value of V (0), we have
E[(ELR(1, δ+ , δ− ) − LR(−δ−, δ+ ))2 ]

2 
 δ+
 Dl
1
dt
−δ− {V (t)=Dl |V (0)=x} ER(x) −=dF1 (x)
δ
+
δ
+
−
0


 δ+
 Dl
1
dt
{V
(t)=D
|V
(0)=x}l−δ−
dF1 (x)VarR(x) −=δ+ + δ−
0

 Dl
+
0

2
1
dt
{V
(t)=D
|V
(0)=x}l−δ− dF1 (x)ER(x) −δ+ + δ− δ+(A· 1)
Because R(x) is constant if V (0) is speciﬁed, and isδsame as the mean of −δ+− 1{V (t)=Dl |V (0)=x} /(δ+ + δ− ),we have
E[(ELR(1, δ+ , δ− ) − LR(−δ− , δ+ ))2 ]


δ+
 Dl
1
dt
{V
(t)=D
|V
(0)=x}l−δ−
dF1 (x).
Var=
δ+ + δ−0(A· 2)The mean square error for SELR is also obtainedby conditioning of the value V (0). However, then,
SELR(1) is either 1 (x = Dl ) or 0 (otherwise), so we
can only consider the situation for x = Dl for the corresponding second term in (A· 1). Then,
E[(SELR(1) − LR(−δ− , δ+ ))2 ]


δ+
 Dl
1
dt
{V
(t)=D
|V
(0)=x}l−δ−
dF1 (x)
Var
=
δ
+
δ−
+
0
2

δ+
 Dl
1
dt
−δ− {V (t)=Dl |V (0)=x}
 dF1 (x)+f1 (Dl ) +E
δ+ + δ−
0


δ+
1
dt
−δ− {V (t)=Dl |V (0)=Dl }−2f1 (Dl )E 
δ+ + δ−


δ+
 Dl
1
dt
−δ− {V (t)=Dl |V (0)=x}
dF1 (x)=Var
δ+ + δ−0
 Dl+f1 (Dl ) +0

R(x)2 dF1 (x)−2f1 (Dl )R(Dl ).

(A· 3)

Subtracting (A· 3) from (A· 2) yields equation (7).

Keisuke Ishibashi
received his B.S.
and M.S. in Mathematics from Tohoku
University, Sendai, Japan in 1993 and1995, respectively. Since joining NTT in
1995, he has been engaged in researchon traﬃc issues in computer communication networks. He received IEICE’s
Young Investigators Award and Information Network research award in 2002. Mr.
Ishibashi is a member of the IEEE and the
Operations Research Society of Japan.

ISHIBASHI et al.: PACKET LOSS-RATE ESTIMATION METHOD

2379

Masaki Aida
received his B.Sc.
and M.Sc. in Theoretical Physics from
St. Paul’s University, Tokyo, Japan, in
1987 and 1989, and received his Ph.D.
in Telecommunications Engineering fromthe University of Tokyo, Japan, in 1999.
Since joining NTT Laboratories in 1989,
he has been mainly engaged in researchon traﬃc issues in ATM networks. From
March 1998 to March 2001, he was a manager at the Traﬃc Research Center, NTT
Advanced Technology Corporation (NTT-AT). He is currently
a Senior Research Engineer at NTT Information Sharing Platform Laboratories. His current interests include traﬃc issues incommunications systems. He received IEICE’s Young Investigators Award in 1996. Dr. Aida is a member of the IEEE and the
Operations Research Society of Japan.

Shin-ichi Kuribayashi
received his
B.E., M.E., and Ph.D. in engineering fromTohoku University, Sendai, in 1978, 1980,
and 1988 respectively. He joined the
NTT Electrical Communications Labs in1980. He has been engaged in the design and development of DDX and ISDN
packet switching, ATM, PHS, and the
IMT2000 and IP-VPN systems. He researched distributed communication systems at Stanford University from December 1988 through December 1989. He participated in international standardization on the ATM signaling and IMT2000 signaling protocols at the ITU-T SG11 from 1990 through 2000. He
is now responsible for next-generation IP system work at NTT
Information Sharing Platform Labs.