VOL. E100-B NO. 8
AUGUST 2017
The usage of this PDF file must comply with the IEICE Provisions
on Copyright.
The author(s) can distribute this PDF file for research andeducational (nonprofit) purposes only.
Distribution by anyone other than the author(s) is prohibited.

IEICE TRANS. COMMUN., VOL.E100–B, NO.8 AUGUST 2017

1377

PAPER

Packet Delay Estimation That Transcends a Fundamental Accuracy
Bound due to Bias in Active Measurements∗
Kohei WATABE†a) and Kenji NAKAGAWA†b) , Members

SUMMARY For network researchers and practitioners, active measurement, in which probe packets are injected into a network, is a powerful tool
to measure end-to-end delay. It is, however, suﬀers the intrusiveness problem, where the load of the probe traﬃc itself aﬀects the network QoS. In
this paper, we first demonstrate that there exists a fundamental accuracy
bound of the conventional active measurement of delay. Second, to transcend that bound, we propose INTrusiveness-aware ESTimation (INTEST),an approach that compensates for the delays produced by probe packets in
wired networks. Simulations of M/M/1 and MMPP/M/1 show that INTEST
enables a more accurate estimation of end-to-end delay than conventional
methods. Furthermore, we extend INTEST for multi-hop networks by using timestamps or multi-flow probes.
key words: active measurement, probe packets, bias, intrusiveness, delay

1.

Introduction

It is important to accurately estimate end-to-end delay andevaluate the path quality when we design networks and applications. Real-time applications, such as audio/video conferencing and IP telephony, require low end-to-end delay
compared to traditional applications such as e-mail, webbrowsing, etc. ITU-T Recommendation G.114 [1] mentions
that an end-to-end delay of more than or equal to 150 [msec]
adversely aﬀects the communication quality of interactive
Voice over IP (VoIP) applications. It is especially important to accurately estimate not only average delay, but alsohigh quantile delays, since the communication quality of a
VoIP application is characterized by them. Active measurement [2], in which probe packets are injected into a network,
is one representative measurement technique for end-to-end
delay.
Prior works on active measurement have left us with arich collection of literature. Many tools that estimate endto-end delay [3]–[5], packet loss [6], [7], available bandwidth [8], [9], link delay [10], traﬃc characteristics [11],node failure [12], [13] have been proposed in prior works,
and large-scale measurements in real networks have allowed
a better understanding of variable characteristics of the networks [14], [15]. Additionally, some works have focused on
the accuracy or overhead of active measurements [16]–[21].
Manuscript received September 26, 2016.
Manuscript revised January 5, 2017.
Manuscript publicized February 9, 2017.
†
The authors were with the Graduate School of Engineering,
Nagaoka University of Technology, Nagaoka-shi, 940-2188 Japan.
∗
An earlier version of this paper was presented at the 2015
IEEE International Conference on Communications (ICC 2015).
a) E-mail: k watabe@vos.nagaokaut.ac.jpb) E-mail: nakagawa@nagaokaut.ac.jp
DOI: 10.1587/transcom.2016EBP3364

A problem with active measurement, however, is thatwhen we inject many probe packets into network (so as toimprove accuracy), the load given by this probe traﬃc itself
acts to impair path quality [22], [23]. In the active measurement of end-to-end delay, probe packet injection is treatedas a method of sampling of the delay process of target path.
If there were no such intrusive eﬀect, estimation accuracy
would be improved as the probe load increases. In reality, however, the transmission of probe packets itself consumes network resources. Thereby, the delays experienced
by probe packets in a network with probe load tend to belarger than the virtual delay in the same network without
probe load.
Needless to say, network researchers and practitioners
are not interested in the delay of a network with probe load,
but rather in the delay of that network without probe load.
Nonetheless, because of this intrusiveness, conventional estimators based on the delay experienced by probe packets
estimates larger value than the true value (i.e., the virtual delay of the network without probe load). In other words, conventional estimators of delay are biased. Baccelli et al. [22]clarified the utility of Poisson Arrivals See Time Average(PASTA) when we measure the delay without bias. They
indicated that the delay experienced by probe packets corresponds to the virtual delay of the network if the injecting
time of probe packets follows Poisson arrivals. Note, however, that under this treatment, the obtained estimation is themean delay of a network with probe load. Roughan [23]discusses accuracy in terms of the variances of conventional
estimators but does not consider the bias. Accordingly, discussion is needed in which such bias is taken into consideration.
In this paper, we first show that the conventional estimation of delay has a fundamental accuracy bound due tobias. To evaluate the eﬀect of bias on accuracy, we calculate the Mean Squared Error (MSE) of a conventional estimator for the number of packets in a router modeled by
M/M/1. Through this evaluation, we show that MSE has alower bound varying the probing rate.
To transcend this MSE bound, we next propose
INTrusiveness-aware ESTimation (INTEST), an approachthat allows us to estimate the virtual delay of a wired network without probe load from the delay of that same network with probe load. INTEST achieves the estimation bycompensating for the increased delay brought about by theload imposed by probe traﬃc. Performing simulations withsingle M/M/1 queuing, MMPP/M/1, and a multi-hop net-

c 2017 The Institute of Electronics, Information and Communication Engineers
Copyright ⃝IEICE TRANS. COMMUN., VOL.E100–B, NO.8 AUGUST 20171378

work, we show that INTEST enables more accurate estimation of delay quantiles than conventional estimator.
The remainder of this paper is organized as follows.
Section 2 summarizes previous works regarding active measurements of delay. We formulate the intrusiveness problemof active measurement in Sect. 3. In Sect. 4, by theoreticallycalculating MSE, we show that there exists a lower boundof MSE when estimating the number of packets in a routermodeled by M/M/1 queuing. In Sect. 5, we summarize INTEST, and in Sect. 6, we extend it for multi-hop networks.
We evaluate it through simulations in Sect. 7. Finally, we
conclude the paper and present issues for future research in
Sect. 8.

Aside from reference [24], the works [17], [20], [22], [23]measure virtual delay of the network. If the probe packets follow Poisson arrival, the mean delay experienced byprobe packets corresponds to the mean virtual delay of the
network [22]. Even if we inject the probe packets upon Poisson arrival, the delay experienced by probe packets does notcorrespond to the delay experienced by user packets unlessuser packets follow Poisson arrival. By using the techniqueof [24], we can estimate delay experienced by user packets
from virtual delay measured by probe packets. Needless tosay, accuracy of a delay estimation of user packets improvesas the accuracy in estimating the virtual delay improves.
3. Formulation of the Intrusiveness Problem

2.

Related Works

As mentioned above, it is important to estimate high quantile of end-to-end delay of networks, though accurate estimation is a diﬃcult task. Some prior works [17], [20] have
tried to estimate high quantile of end-to-end delay. Choi etal. [17] has proposed a scheme that estimates a high quantile with bounded error. The scheme allows us to know theminimum number of probe packets needed to bound the error of quantile estimation within a prescribed accuracy. In[17], the error of the quantile estimation is theoretically obtained as a function of the number of probe packets. Therefore, we can optimize the measurement overheads of active
measurement using the function. Sommers [20] also haveproposed an estimator of high quantile. Since the estimator provides confidence intervals, we can tune the numberof probe packets to achieve the required accuracy. The loadof probe packets is, however, not taken into consideration in[17], [20]. These works cannot transcend the fundamental
accuracy bound due to bias.
There are a few works that mention the eﬀect of theprobe traﬃc on the path quality. Baccelli et al. [22] haveshown that an arrival process of the probe packets aﬀects anestimator. In [22], Baccelli et al. indicated that the mean
delay experienced by probe packets is equal to the mean
delay of the network when the injected probe packets follow Poisson arrival. If we inject the probe packets upon
the other arrival processes, the mean delay experienced byprobe packets does not correspond to the mean virtual delay of the network. The estimator in the work, however,cannot estimate the delay of a network without probe load
though it estimates the delay of a network with probe load.
Roughan [23] has indicated that the variance of an estimator is increased by both excessive and insuﬃcient numbersof probe packets. The excess of the number of probe packets increases the total traﬃc, and the deficiency of that leads
lack of samples. The optimal probe rate is theoretically derived for the router that is modeled by M/M/1 queuing in[23]. Roughan [23] has not taken the accuracy bound due tothe bias into consideration, though he has shown the accuracy bound of active measurement due to the variance.
Aida et al. [24] proposed a technique that transforms
virtual delay into the delay experienced by user packets.

First of all, we formulate the intrusiveness problem of active measurement, and show how we evaluate the eﬀect ofbias on accuracy. We define the target traﬃc as a traﬃc thatstreams from an edge node a to an edge node b of a network.
We let Dg (t) [sec] denote a virtual one-way delay from a tob at time t. The subscript g indicates that the process represents the so-called ground truth of the delay. We definecross traﬃc as the traﬃc that excludes the target traﬃc fromthe whole traﬃc in the network. Dg (t) is the virtual delay of
the network without probe load. If applying an active measurement to determine a characteristic of the virtual delay
Dg (t), we add probe traﬃc to the traﬃc that streams fromthe edge node a to b.
Similarly, we let Dgp (t) [sec] denote a virtual one-way
delay from a to b on the network with probe load at timet, where the subscript gp stands for ground truth and probe
traﬃc. Note that Dgp (t) diﬀers from Dg (t). Our goal is toaccurately estimate a characteristic of Dg (t) from the active
measurement.
Based on delays that are experienced by n probe packets, we estimate the mean, quantile, and other statistics
about the one-way delay. We let T i (i = 1, . . . , n) denotethe time at which ith probe packet is injected into the network (i.e., the packet is dequeued from the queue of sourceside edge node a). The delay that is experienced by ith probe
packet is expressed by Dgp (T i ). When estimating the mean
virtual delay, the conventional estimator is1∑
Dgp (T i ).
n i=1nD̂ave =

(1)

Furthermore, when we estimate the q-quantile of delay, wedefine κ(q) = ⌈(1 − q)n⌉, where ⌈·⌉ denotes the ceiling function. Then, the conventional estimator for the q-quantile isthe κ(q)th largest value D̂qua (q) among the delays Dgp (T i )experienced by the probe packets [20].
In this paper, we consider the case that network researchers and practitioners estimate the characteristics ofDg (t). When they measure characteristics of a network, they
perform active measurement temporally. In this situation,
they want to estimate the characteristics in an usual stateof the network. Conversely, in a part of applications where

WATABE and NAKAGAWA: PACKET DELAY ESTIMATION THAT TRANSCENDS A FUNDAMENTAL ACCURACY BOUND DUE TO BIAS

1379

probe packets are always injected into a network (e.g., SLA
monitoring), we may consider that they want to estimate thecharacteristics of Dgp (t). This type of continuous measurements are out of scope of this paper.
Since Dgp (t) , Dg (t), D̂ave and D̂qua (q) are generally
not unbiased. A delay experienced by a probe packet is notmuch aﬀected by other probe packets when the number ofprobe packets n is small. However, if n is small, the estimator variance is large (and accurate estimation is diﬃcult)since there are only a few samples. On the other hand, if
n is large, the accuracy of the estimator increasingly suﬀers
from bias because of the delays experienced by other probe
packets. In short, there is a trade-oﬀ between the varianceand bias of an estimator.
A biased estimator can be assessed by MSE, which is astatistic composed of the variance and bias of an estimator.
The MSE of an arbitrary estimator P̂ is defined as follows:
Var[P̂] + {E[P̂] − P∗ }2 = E[(P̂ − P∗ )2 ],(2)where P∗ denotes the true value of the virtual delay.
4.

A Fundamental Bound on the Accuracy of Active
Measurement

By analyzing a router modeled by M/M/1 queuing, we showthat the conventional estimation by active measurement of
delay is restricted by a fundamental bound on the accuracy
due to bias. Here, we evaluate the accuracy of estimation by
MSE. We verify the dependence of the accuracy on probing
rate by plotting the MSE of the estimator as a function ofprobing rate.
To theoretically verify the dependence of accuracy on
probing rate while taking such bias into consideration, we
consider MSE regarding the number of packets in a routermodeled by M/M/1 queuing. In this first analysis, we estimate the mean or quantile of the number of packets in arouter, and next we will estimate the delay. We assume
that target traﬃc packets and probe packets are generated
according to Poisson processes with rate λg [packet/sec] andλp [packet/sec], respectively. Because the superposition of
two Poisson process is also Poisson, the queue is modeled by M/M/1. The service rate of the M/M/1 queue isµ [packet/sec]. We estimate the mean number of packets
in the router∑without probe load by the sample averageM̂ave = n−1 ni=1 Mgp (T i ), where Mgp (T i ) [packet] denotes
the number of packets in the router at time T i . Note that thetrue value of the estimator is the mean number of packets
in a router without probe load, though Mgp (T i ) is the number of the packets in a router with probe load. Under active
measurement, we cannot observe the number of packets ina router. However, we can analytically derive the MSE ofthe estimator regarding the number of packets in a router,and the results provide good insights on accuracy characteristics.
We will calculate the MSE by using the autocovariancefunction r(ρ, τ) of the process M(t) of the number of packets
of M/M/1 queue. r(ρ, τ) is given byr(ρ, τ) = E [(M(t) − E[M(t)])(M(t + τ) − E[M(t)])]()ρ−A(ρ)|τ|−B(ρ)|τ|e+e,≃2(1 − ρ)2
(1 − ρ)2(1 − ρ)2
A(ρ) =
B(ρ) =√ ,√ ,1+ρ+ ρ
1+ρ− ρ
where ρ denotes the utilization of M/M/1 queue [23], [25].
The variance σ2 = Var[ M̂ave ] that corresponds toVar[P̂] in Eq. (2) can be expressed by r(ρ, τ) and ρgp ≡(λg + λp )/µ as
1 ∑1r(ρgp , 0) + 2
E[r(ρgp , |T i − T j |)]nn i, j∫1
1 ∑ ∞= r(ρgp , 0) + 2r(ρgp , t) f (t, |i − j|, 1/λp )dtnn i, j 0n {ρgp
2 ∑ ρgp (n − k)≃+n(1 − ρgp )2 n2 k=1 2(1 − ρgp )()}(λp )k(λp )k×+,
λp + A(ρgp )k λp + B(ρgp )kσ2 =where f (t, k, α) denotes the probability density function of
an Erlang distribution with shape parameter k and scale parameter α [23]. On the other hand, the bias ε that corresponds to E[P̂] − P∗ in Eq. (2) can be expressed in terms ofρg ≡ λg /µ and ρ p ≡ λp /µ as
ε=

ρgp
ρg
ρp
−
=
.
1 − ρgp 1 − ρg (1 − ρg )(1 − ρgp )As a result, we can calculate MSE as σ2 + ε2 .
Substituting concrete values into the MSE variables
and varying the number n of probe packets, we derive theMSE relation shown in Fig. 1. Assuming the link capacity and the mean packet length to be 155.52 [Mbps] and600 [byte], respectively, we have µ = 32400 [packet/sec].
The link utilization ρg of the target traﬃc is set to 0.9. We
set the mean measurement period l to 1.0 [sec]. To inject nprobe packets in the period, we set probing rate λp to n/l.
We will finish the measurement by the nth probe packet.
Note that injecting time of the nth probe packet is not always l since injecting time follows Poisson arrivals though
the mean time is l. Note that in Fig. 1, the horizontal axis
represents the ratio of probe load to the link capacity.
In Fig. 1, we see that MSE has a lower bound (i.e., alimit of accuracy). When the ratio ρp of probe load to thelink capacity is low, the variance σ2 is large, hence MSE islarge. This is because we cannot obtain suﬃcient sampling.
When ρp is large, MSE also becomes large, even though
the variance is low, because the bias ε is large. The lower
bound of MSE is around 1.5 [packet2 ]. We cannot obtain amore accurate estimation by increasing nor decreasing thenumber of probe packets.
Furthermore, in practical measurements, it is very difficult to determine the optimal probe load because of a dependency on the ratio ρg of traﬃc load to link capacity. The

IEICE TRANS. COMMUN., VOL.E100–B, NO.8 AUGUST 20171380

Fig. 1 MSE of an estimator for the number of packets in a router modeled by M/M/1 queuing.
Fig. 2

process of the number of packets in a router may not correspond to that of delay, as mentioned above. The delay is,however, proportional to the number of packets, in the queue
and we confirm that similar results are obtained upon delay
estimation based simulation (see Sect. 7).
5.

Intrusiveness-Aware Estimation

We here propose INTEST, an approach that compensatesfor delays produced by probe packets on wired networks
and transcends the accuracy bound mentioned in Sect. 4.
INTEST estimates the delay Dg (t) of the network without
probe load from the delay Dgp (T i ) of the network with probeload. This estimation is done by subtracting the delay produced by the load given by probe traﬃc. Note that Dgp (t) isalways larger than Dg (t) as shown in Fig. 2.
5.1

Delay in Busy Periods

We first consider a network in which a single router with
FIFO queuing is connected between two edges a and b, andthe delay from the egress port of a to the ingress port of b
is measured. We clarify the relationship between the delay
Dg (t) of the network without probe load and the delay Dgp (t)of the network with probe load. Letting c [bps] denote thelink capacity, we define the amount of data Bgp (t) [bit] in thequeue at time t asM∑
gp (τ)xh − c(t − u0 (t)), (Mgp (t) > 0), lim
Bgp (t) = 
τ→t−0

h=1



0 ,
(Mgp (t) = 0),(3)
where xh [bit] (h = 1, 2, . . . , Mgp (t)) denotes the length of
hth packets in the queue and u0 (t) denotes the transmission
start time of a packet transmitting at time t. A delay Dgp (t)that is experienced by a packet injected at time t into the
network is related to Bgp (t) as Dgp (t) = Bgp (t)/c + d, whered denotes a propagation delay of end-to-end path (i.e., d isthe sum of the propagation delays on the two link).
Letting an interval [s, e) denote a busy period (i.e., amaximal interval where the number of packets in the routeris positive), amounts of data Bgp (t1 ) and Bgp (t2 ) at times t1
and t2 (s ≤ t1 ≤ t2 < e) are related as follows.

Relationship between Dg (t) and Dgp (t).

Bgp (t2 ) = Bgp (t1 ) + Xgp (t1 , t2 ) − c(t2 − t1 ),where Xgp (t1 , t2 ) [bit] denotes the total amount of traﬃc arrived in interval [t1 , t2 ). We let [s j , e j ) denote the start andend time of the jth busy period of the router with probe load(see Fig. 2). We derive the following equation regarding theamount of data Bgp (t) [bit] in the network with probe load.
p

Bgp (T i ) = Bgp (T i−1 ) + Xg (T i−1 , T i ) + xi−1 − c(T i − T i−1 ),( i ∈ { ι |s j ≤ T ι−1 , T ι < e j }).
p

Xg (T i−1 , T i ) = Bgp (T i ) − Bgp (T i−1 ) − xi−1 + c(T i − T i−1 ),( i ∈ { ι |s j ≤ T ι−1 , T ι < e j }). (4)Here, Xg (t1 , t2 ) [bit] denotes the total amount of cross andtarget traﬃc that stream the same path with the probe packp
ets in an interval [t1 , t2 ) and xi [bit] denotes the length ofith probe packet. Note that Bgp (T i ) does not include probe
packet injected at time T i since Bgp (t) is defined by Eq. (3).
The last term on the right-hand side of Eq. (4) represents theamount of transmitted data in [T i−1 , T i ). Since we assume
that [s j , e j ) is a busy period, the amount of transmitted data
can be expressed as the product of the capacity c and time
T i − T i−1 .
We can clarify relationship between Dg (T i ) and
Dgp (T i ) since a similar relationship holds for Bg (t) [bit] in[skj , ekj ) (k = 1, 2, . . . , m j ) (intervals A in Fig. 2). Here, we letskj (k = 1, 2, . . . , m j ) and ekj denote the start and end times of
the kth busy period of the router without probe load within
an interval [s j , e j ). m j denotes the number of the busy periods of the router without probe load within an interval[s j , e j ). Then, we have
Bg (T i ) = Bg (T i−1 ) + Xg (T i−1 , T i ) − c(T i − T i−1 ),(5)for i ∈ { ι |skj ≤ T ι−1 , T ι < ekj } (T i and T i−1 are in one of theintervals A in Fig. 2). The amount of transmitted data can be
expressed as the product of the capacity c and time T i − T i−1
as similar to Eq. (4), since T i−1 and T i are in a busy period[skj , ekj ). By substituting Eq. (4) into Eq. (5), we obtainp

Bg (T i ) = Bg (T i−1 ) + Bgp (T i ) − Bgp (T i−1 ) − xi−1 ,(6)for i ∈ { ι |skj ≤ T ι−1 , T ι < ekj }. Dividing the both sides ofEq. (6) by c,WATABE and NAKAGAWA: PACKET DELAY ESTIMATION THAT TRANSCENDS A FUNDAMENTAL ACCURACY BOUND DUE TO BIAS

1381
p

Dg (T i ) = Dg (T i−1 ) + Dgp (T i ) − Dgp (T i−1 ) −

xi−1
c

(7)

p

for i ∈ { ι |skj ≤ T ι−1 , T ι < ekj }. Note that each busy period forthe router without probe traﬃc is included in a busy period
for the router with probe traﬃc.
∪Dg (T i ) is equal to d for i ∈ { ι |s j ≤ T ι < s1j } { ι |ekj ≤∪mT ι < sk+1
{ ι |e j j ≤ T ι < e j } (T i is in one of the intervals
j }B in Fig. 2). Since the right hand side of Eq. (5) is less than0 when T i is in one of the intervals, the right hand side ofEq. (7) is less than d. Therefore, when T i is in one of theintervals A or T i is in the intervals B, the equation,(
Dg (T i ) = max Dg (T i−1 ) + Dgp (T i )− Dgp (T i−1 ) −p
xi−1 ),d ,c(8)holds. We consider that Eq. (8) approximately holds whenT i is in A but T i−1 is in B. In this case, the relation between
Bg (T i ) and Bg (T i−1 ) cannot express as Eq. (5) by using total
amount of traﬃc Xg (T i−1 , T i ). If T i−1 is in [ekj , sk+1j ) and T i is
k+1 k+1
in [s j , e j ),k+1
Bg (T i ) = Bg (T i−1 ) + Xg (sk+1
j , T i ) − c(T i − s j ).

(9)

Eq. (9) does not correspond to Eq. (5). The approximationis reasonable when we can assume that the traﬃc including
cross and target traﬃc have a constant rate Xg (T i−1 , T i )/(T i −T i−1 ) > c in an interval [T i−1 , T i ). If the traﬃc have a constant rate, Bg (t) increases Xg (T i−1 , T i )/(T i − T i−1 ) − c bit
per second. Hence, Bg (T i ) = Xg (T i−1 , T i ) − c(T i − T i−1 )and Eq. (5) hold since Bg (T i−1 ) = 0. As a result, Eq. (8)means that we can estimate Dg (T i ) from delays Dgp (T i ) and
Dgp (T i−1 ) experienced by probe packets.
5.2

one hop networks, the following inequality holds:

Estimator

In practical measurements, we must estimate a start time s jof a busy period, an end time e j of the busy period, and a
propagation delay d. s j , e j , and d are also possible to obtain
Dgp (T i ) as a delay experienced by a probe packet. A propagation delay d can be estimated by d̂, the minimum delay ofdelays experienced by probe packets. By using thresholdδ, we can detect start of busy periods by U = {T i | Dgp (T i ) ≤d̂ + δ < Dgp (T i+1 )}. Hence, ŝ j that is a jth smallest elementof U is an estimator of s j . Similarly, ê j that is jth smallest element of V = {T i | Dgp (T i−1 ) ≥ d̂ + δ > Dgp (T i )} is an
estimator of e j . The threshold δ aﬀects the performance of
INTEST. Since we should tune the value of δ appropriately,
we discuss the sensitivity of δ to the performance later.
The link capacity c should also be estimated if the INTEST is used by a person who is not a network manager.
The diﬀerence (T i+1 + Dgp (T i+1 )) − (T i + Dgp (T i )) between
receiving times of consecutive probe packets is longer than
the transmission time of the traﬃc that arrives between thearrival times of the two packets. Hence, with regards to c inxi + Xg (T i , T i+1 )≤ (T i+1 + Dgp (T i+1 )) − (T i + Dgp (T i )).
c
Since Xg (T i , T i+1 ) ≥ 0, the estimator ĉ of c ispxi
(T i+1 + Dgp (T i+1 )) − (T i + Dgp (T i ))


p
xi


 .
ĉ = max 
1≤i≤n−1 T i+1 − T i + Dgp (T i+1 ) − Dgp (T i )
c≥

(10)

Needless to say, we should ĉ = c when we can use the information of the link capacity.
Based on Eq. (8), ŝ j , ê j , d̂, and ĉ, we can estimate adelay Dg (T i ) of a network without probe load from a delay
Dgp (T i ) of a network with probe load. Considering the estimator of Dg (T i ) should be Dgp (T i ) if T i is in an idle period(i.e., a maximal interval where the number of packets in arouter is 0), the estimator of Dg (T i ) (1 < i ≤ n) is given by

(
)
p

xi−1



max D̂g (T i−1 )+Dgp (T i ) − Dgp (T i−1 )−, d̂ ,ĉD̂g (T i ) = ŝ j < T i ≤ ê j for some j





Dgp (T i ),otherwise.
(11)
Note that the first case of the estimator is the equationin which Dg (t), d, and c are replaced by D̂g (t), d̂, and ĉ
in Eq. (8), respectively. According to the definition of ŝ j ,Dg (T i ) = Dgp (T i ) when i = 1. We can estimate an aver∑age delay of a network without probe load by ni=1 D̂g (T i )/n.
The κ(q)th largest value D̂qua (q) within the values of D̂g (T i )is the q-quantile estimator of a network without probe load.
INTEST is applicable for any model of probe and target
traﬃc. INTEST can provide non-intrusive samples D̂g (T i )of a virtual delay process if an arrival process of probe packets satisfies T 1 < T 2 < · · · < T n . Therefore, we can use
any arrival process in a large set of arrival processes thatsatisfy the assumption of NIMASTA (Non-Intrusive Mixing
Arrivals See Time Averages) [22] (e.g., Poisson arrivals, a
process with inter-arrival time that follows Gamma distribution, etc.). Moreover, we can estimate a characteristic of virtual delay process Dg (t) for any arrival process of packets oftarget traﬃc. Our purpose is to accurately estimate a characteristic of a virtual delay process. A characteristic of virtual
delay process does not correspond to that of target traﬃc if
an arrival process of packets of target traﬃc is not Poisson
arrivals [22]. However, the technique that transforms virtual delay to delay of target traﬃc has been proposed in aprevious work [24].
6. Extension for Multi-Hop Network
We can extend INTEST to estimate the delay in multi-hop
networks composed of multiple routers. In Eq. (11), we
use the information regarding link capacity ĉ in the case of

IEICE TRANS. COMMUN., VOL.E100–B, NO.8 AUGUST 20171382

busy periods, i.e., [s j , e j ). When we use INTEST in multihop network, we have to find the congested link that causes
each busy period since link capacity is diﬀerent in each link.
There are two options to extend INTEST to multi-hop networks.
6.1

Use of Timestamp

Fig. 3First option is to utilize timestamps provided by each router.
Letting T ik denote a timestamp of kth router (k = 1, . . . , K)
recorded on ith probe packet, we can estimate a queuing
delay of kth router by Dkgp (T i ) = T ik−1 − T ik − min1≤l≤n (T lk −T lk−1 ), where n denotes the total number of packets. As wedefined in Sect. 3, T i is the time at which ith probe packet
is dequeued from the queue of source side edge node. Notethat we do not require time synchronization of routers since
we measure queueing delay Dkgp (T i ). Replacing Dgp (T i ) in
Eqs. (10) and (11) with Dkgp (T i ) and setting d̂ in Eq. (11) to 0,
we can estimate a queuing delay of kth router without probe
load.
p

xi

ck ≥

k
(T i+1+ Dkgp (T i+1 )) − (T ik + Dkgp (T i ))


p
xi




ĉk = max  kkkk1≤i≤n−1 T
i+1 − T i + Dgp (T i+1 ) − Dgp (T i )

(




max D̂kg (T i−1 )+Dkgp (T i )





)


p
xi−1
D̂kg (T i ) = 
k

−D
(T
)−
,
0
, ŝkj < T i ≤ êkj
gp i−1
ĉk





Dk (T ),otherwise,
gpi

where ck [bit] and ĉk [bit] denote link capacity of a link
between kth and (k + 1)th routers and its estimator.
D̂kgp (T i ) [sec] denotes an estimator of queueing delay of thekth router recorded on the ith probe packet. ŝkj and êkj are theestimators of the start and end time of the jth busy periodof kth router, and they are estimated in a similar manner asŝ j and ê j . The estimator D̂tsg (T i ) of end-to-end delay of a
network without probe load when we utilize timestamp is asfollows:D̂tsg (T i ) = d̂ +K∑

D̂kg (T i ).

(12)

k=1

By using Eq. (12), we can estimate an end-to-end delayof a multi-hop network without probe load. Note thatD̂kg (T i ) [bit] denotes an estimator of queueing delay, and it
does not include propagation delay. Ping tool used ICMP
packet provides an option to record a timestamp of intermediate routers using header space (The number of hops islimited to 9 hops in Linux ping tool). On the other hand,
we can record timestamps at intermediate routers or capture
cards on network.

Probe flow design for a multi-hop measurement.

6.2 Use of a Multi-Flow Probe
To perform a measurement of multi-hop networks using INTEST, we have a second option in which measurement results of the multi-flow probe are utilized. In multi-flow
approach, we design paths of probe packets as a tree (seeFig. 3). This type of path design of probe flow is commonlyused in network tomography [26], [27]. Since Eq. (11) contains link capacity ĉ, we have to specify a congested link
to compensate for the increased delay brought about by theload. We can specify the congested link by comparing delay patterns of probe flows, assuming that a path contains
at most one congested link at the same time. For example,
in Fig. 3, when large delay is observed by probe A and B(probe C and D do not observe a large delay), we can specify congested link is the link between N2 -N3 .
In multi-flow approach, we measure end-to-end delayof each paths of probe flows, and estimate start and end timeof congestion for each paths. Let rL denote L hop path that
we want to measure end-to-end delay by INTEST. We letrl (1 ≤ l < L) denote paths that share first l hop path withrL . We measure end-to-end delay on r1 , r2 , . . . , rL by probe
packets. Note that these end-to-end delays are increased by
the load of probe traﬃc. Here, we define busy periods ona path as periods in which at least one router on the path isin a busy period. In the same manner as estimator of ŝ j andê j , we estimate start time ŝ j,l and end time ê j,l of jth busy
period on path rl .
Comparing the estimated busy periods on each paths,
we specify congested link corresponds to each busy perij
ods on path rL . Let lmin
denote minimum l that satisfies| ŝ j,L − ŝ j′ ,l | < ∆ and |ê j,L − ê j′ ,l | < ∆ (1 ≤ j′ ) for a jth busy
period on the path rL . The threshold ∆ should be proportional on the mean of probe generation intervals since large
probe interval degrades the estimation accuracy of start andend time of busy periods. It is expected that rl that satisfies | ŝ j,L − ŝ j′ ,l | < ∆ and |ê j,L − ê j′ ,l | < ∆ (1 ≤ j′ ) havea common busy period and a common router of congested
link. The router of congested link is in common routers onjth link forthese paths. We can specify congested link is lminjjth busy period on rL . Let c [bps] denote bandwidth cl j ofminjth link.
lmin
Therefore, we can obtain the following estimator for
multi-hop network.

WATABE and NAKAGAWA: PACKET DELAY ESTIMATION THAT TRANSCENDS A FUNDAMENTAL ACCURACY BOUND DUE TO BIAS

1383


)
(
p

Xi−1



,
d̂
,
max
D̂
(T
)+D
(T
)
−
D
(T
)−

g i−1
gp i
gp i−1cj
D̂g (T i ) = ŝ j,L < T i ≤ ê j,L for some jDgp (T i ),otherwise,(13)p

where Xi [bit] denotes the sum of the length of probe packets that were injected in [T i , T i+1 ).
In some cases, it is diﬃcult to measure end-to-end delay on the path that share first l′ hops with rL . If we cannot
measure end-to-end delay on the path that share first l′ hoppath with rL , we consider the l′ th link and (l′ + 1)th link as
an virtual link with bandwidth max(cl′ +1 , cl′ ). In this case,jif lmin= l′ + 1 for jth busy period, c j = max(cl′ +1 , cl′ )in Eq. (13). We cannot distinguish which one is the congested link between l′ th and l′ + 1th links without delay ofprl′ . By using max(cl′ +1 , cl′ ) as c j , since both of Xi−1 /cl′ andpp
Xi−1 /cl′ +1 are greater than or equal to Xi−1 / max(cl′ +1 , cl′ ),we underestimate the compensated delay, thereby returning
closer estimator to the conventional estimator.
7.

Evaluation

We next evaluate the performance of INTEST through simulations to confirm that it can produce more accurate estimates than conventional active measurement. Through simulation, we first evaluate INTEST in a single-hop networkmodeled by M/M/1. Because the theoretical value of MSE
of an estimator can be derived in M/M/1 queueing, we estimate the number of packets in a router in addition to delay
when evaluating the single-hop network. We then move on
to a valuation of INTEST as applied to a multi-hop network.
7.1
7.1.1

A Network Composed of Single Router
A Estimation of the Number of Packets in a Router

We evaluate INTEST in a single-hop network composed ofa router that is modeled by M/M/1 queuing, and show thatINTEST can produce more accurate estimations than conventional active measurement can. So as to clarify the fundamental characteristics of INTEST through a simple scenario, we focus here on the average number of packets in arouter and on quantiles of delay. In a simulation of M/M/1
model, we can compare the simulation results with the theoretical results shown in Sect. 4, though M/M/1 model is nota realistic model of a router. By comparing both results,
we can confirm the estimator behaves as expected. Notethat the estimator shown in Sect. 5 does not assume M/M/1
model, and we later evaluate the estimation on a more realistic model in Sect. 7.2.
We first perform a simulation under an assumption that
we can observe the number of packets in a router at the timeof the probe packet injection. The simulation is useful inevaluating the fundamental characteristics of INTEST. Notethat in practice, we cannot observe the number of packets
in a router by a probe packet injection. We can, however,Fig. 4 MSEs of the conventional and INTEST estimators when we estimate the number of packets in a router modeled by M/M/1 queuing.

theoretically calculate the MSE, as described in Sect. 4. Parameters for this simulation are the same as those for thesimulation shown in Sect. 4.
To estimate the mean number of packets in a router, we
modify the INTEST estimator of Eq. (11) as follows.
(
)



max M̂g (T i−1 ) + Mgp (T i ) − Mgp (T i−1 ) − 1, 0 ,M̂g (T i ) = ŝ′j < T i ≤ ê′j for arbitrary j Mgp (T i ),otherwise,(14)
where M̂g (t) [packet] is the estimator of the number of packets in a router without probe load at time t. Also, ŝ′j and ê′jthat are jth smallest elements of U ′ = {T i | Mgp (T i ) < θ ≤Mgp (T i+1 )} and V ′ = {T i | Mgp (T i−1 ) > θ ≥ Mgp (T i )} are estimators of s′j and e′j , respectively. We can obtain Eq. (14)pby replacing Dgp (t), D̂g (t), d̂, xi /ĉ, ŝ j , and ê j with Mgp (t),M̂g (t), 0, 1, ŝ′j , and ê′j in Eq. (11). In estimation of the number of packets in a router, we do not have to consider a propagation delay. The number of packets in a router increasesby 1 if a probe packet is injected though the delay in a routerpincreases by xi /ĉ. We set threshold θ to 7.5 [packets]. Weshould tune the threshold carefully to bring out the INTEST
performance (we confirm the sensitivity of the accuracy on
the threshold later).
By varying the number of probe packets for each simulation from 2 [packets] to 2048 [packets] (i.e., the probeload is changed from 0.0062% to 6.3%), we calculate MSE
for the conventional estimator and INTEST estimator of
Eq. (14). Results are shown in Fig. 4. In the calculation ofMSE, we repeated the simulation 5,000 times at each number of probe packets. The theoretical values for the conventional estimator in Fig. 4 are the same as the MSE values
shown in Fig. 1, and the theoretical values for the INTEST
estimator are σ2 , which is the MSE for an unbiased estimator. We can confirm from Fig. 4 that the minimum value ofthe MSE of the INTEST estimator is smaller than that of theconventional estimator. This shows that INTEST achieves
highly accurate measurement that broke the bound of conventional active measurement.
We also calculate MSE for the conventional estimatorand INTEST estimator for the simulation with low link uti-

IEICE TRANS. COMMUN., VOL.E100–B, NO.8 AUGUST 20171384

Fig. 5 A comparison of a delay process of the network without probeload and samples D̂g (T i ) by INTEST.

lization. In the above simulation, we changes the target traffic so that the link utilization is 0.5. The other conditions of
the simulation are the same as the above simulation. In thesimulation with low link utilization, MSEs of INTEST estimator are similar to those of conventional estimator. The
deferences are lower than 0.16% of MSE of conventional
estimators. When a link utilization is low, INTEST estimator behaves as a conventional estimator since the number ofpackets in a router is almost always lower than the threshold θ. INTEST estimator can give similar performance withconventional estimator in uncongested networks in which
delay measurement is not necessarily important.
7.1.2

A Estimation of the Delay

Next, we evaluate the network delay under the same conditions as the above simulation. To confirm that D̂g (T i )—asample of a delay process obtained by compensation withINTEST in Eq. (11)—corresponds to the delay of the network without probe load at time T i , we derive a delay process of the network without probe load and compare D̂g (T i )to the process. We set the threshold δ to 0.2 [msec] when
deriving D̂g (T i ). We should tune the threshold carefully tobring out the INTEST performance (we confirm the sensitivity of the accuracy on the threshold later). In Fig. 5,
we show D̂g (T i ) and delay processes over the interval [0.02,
0.04) [sec]. In the example, the number n of probe is 1024.
From the figure, we note that samples D̂g (T i ) of the INTEST
estimator are very close to delay process Dg (t) of the network without probe load, although samples Dgp (T i ) of theconventional estimator diﬀer greatly from the process.
Repeating similar simulations 5,000 times for eachprobe load, we derive the bias and MSE of the estimator at
95%-quantile of delay and evaluate the accuracy. It is wellknown that the cumulative distribution function of M/M/1
queuing delay is
λF(t) = 1 − e−(µ−λ)t ,µ(0 ≤ t).

Then, the true value D∗qua (q) of q-quantile isFig. 6 Biases of the conventional and INTEST estimators when we estimate 95%-quantile of delay of a router modeled by M/M/1 queuing.


µ
1



log (1 − q),
−
∗
µ
−
λ
λ
Dqua (q) = 


0,

λ
≤q
µ
otherwise.

1−

(15)

We show the bias (i.e., mean diﬀerence between the value ofEq. (15) and an estimator) of the conventional and INTEST
estimator in Fig. 6. We find that the INTEST estimator can
provide an unbiased estimation when the probe load is sufficiently large. The conventional estimator and INTEST estimator both show a bias when the ratio of probe load tothe link capacity is small. This is because the number ofprobe packets, at 2 to 64 [packets], is too small. The resultsof INTEST estimator without bandwidth estimation is also
shown in the figure for comparison. The biases of INTEST
estimator without bandwidth estimation are slightly better
than those of INTEST estimator with bandwidth estimation
when the probe load is small. When the probe rate is too
small, it is diﬃcult to accurately estimate bandwidth sinceprobe packet intervals are large. As for MSE, we obtained
results similar to those shown in Fig. 4. We also calculate
MSE for the conventional estimator and INTEST estimator
for the simulation with low link utilization. In the simulation with low link utilization, MSEs of INTEST estimator
are similar to those of conventional estimator.
We compare Eq. (8) and virtual delay to confirm thevalidity of the approximation on Eq. (8). In the simulation of
M/M/1 queueing, we derive virtual delay (i.e., true values),
and calculate the mean error of Eq. (8) for i ∈ { ι |T ι−1 <skj ≤ T ι < ekj } (i.e., T i is in A but T i−1 is in B). Note thata bandwidth is not estimated, but given for the calculation.
The results are shown in Fig. 7. In the figure, mean error ofa sample increase as probing rate increases. When probing
rate is large, a busy period [s j , e j ) of the router with probeload includes many busy period [skj , ekj ) of the router without
probe load. The error can be raised for every busy period[skj , ekj ) of the router without probe load. As a result, error of
Eq. (8) is accumulated in a busy period [s j , e j ) of the routerwith probe load. Though the results of INTEST estimatorin Fig. 6 include the error, the estimator is accurate than theconventional estimator even if the probe load is high. The
results in Fig. 6 indicate that the error can be negligible with

WATABE and NAKAGAWA: PACKET DELAY ESTIMATION THAT TRANSCENDS A FUNDAMENTAL ACCURACY BOUND DUE TO BIAS

1385

Fig. 7

Mean error of Eq. (8).
Fig. 9 Sensitivity of the performance of INTEST on the threshold δ when
we estimate 95%-quantile of delay of a router modeled by M/M/1 queuing.

Fig. 8 Sensitivity of the performance of INTEST on the threshold θ when
we estimate the number of packets in a router modeled by M/M/1 queuing.

respect to the bias of conventional estimators.
7.1.3

The Sensitivity of Performance on the Threshold

We verify the sensitivity of performance on the thresholdθ and δ. Changing the threshold θ and δ, we perform two
simulations regarding the average number of packets in arouter and quantiles of delay. Except the threshold θ and δ,
the parameters for these simulations are almost the same as
the simulation with high link utilization in Sect. 7.1.2. For
the estimation of the average number of packets in a router,
we change θ between 0 and 80.5, and we show the results ofthe simulation in Fig. 8. For the estimation of quantiles ofdelay, we change δ between 0 and 0.0064, and we show theresults of the simulation in Fig. 9. We can confirm that MSE
of INTEST estimator converges to that of the conventional
estimator when θ → ∞ and δ → ∞. As θ and δ becomelarge, periods in ( ŝ j , ê j ] became short. Therefore, Eq. (11)approaches D̂g (T i ) = Dgp (T i ). Namely, INTEST estimatorapproaches conventional estimator. On the other hand, θ = 0
and δ = 0 do not achieve the best performance. When thethreshold θ and δ are too small, it is diﬃcult to estimate ŝ jand ê j since Dgp (t) frequently exceeds the threshold. Hence,
there are the optimal values for the thresholds θ and δ.

Fig. 10 Biases of the conventional and INTEST estimators when we estimate 95%-quantile of delay of a router modeled by MMPP/M/1 queuing.

use is
Q=

(

−5
5

)
5
.
−5

The link utilization on states 1 and 2 are 0.5 and 0.9, respectively. The results are shown in Fig. 10, and we got thesimilar results with the simulation of M/M/1 queueing.
From the results of the above simulations, we confirm
that INTEST transcends the fundamental accuracy boundpointed out in Sect. 4 and enables highly accurate measurements of delay in a single-hop network. In INTEST, when
the probing rate increases, accuracy does not suﬀer but instead improves. In conventional estimation, the parameterarea (in which both bias and variance are small) is itselfvery small. With INTEST, however, we can conduct unbiased and small variance estimations as long as the probing
rate is fairly high.
7.2 A Network Composed of Multiple Routers

7.1.4

An Arrival Process Other than Poisson Process

Finaly, to confirm that INTEST can be applied to an arrival process other than Poisson processes, we also calculate MSE of conventional and INTEST estimators undera Markov-Modulated Poisson Process (MMPP) [28]. Wechange the arrival process of the target process in the above
simulation to a two-state MMPP. We set the threshold δ to
0.2 [msec]. The transition rate matrix Q of the MMPP we

To confirm that INTEST enables accurate estimation for a
network composed of multiple routers, we perform a simulation with ns-3 simulator [29]. We perform a simulationof the network shown in Fig. 11, and estimate end-to-end
delay of the network without probe load, using probe flows
from node N0 to node P1 and from N0 to P2 . Note that therouter model in the simulation is not M/M/1 model in ns3. The capacities of links N1 -N2 and N2 -N3 are taken as

IEICE TRANS. COMMUN., VOL.E100–B, NO.8 AUGUST 20171386

Fig. 11

Simulation model.

15.552 [Mbps] and 31.104 [Mbps], respectively. That of theother links as 62.208 [Mbps]. In the simulation, the target
traﬃc streams from node N0 to node N4 . The packet lengthof the target traﬃc is 600 [bytes]. The sending time of thepackets follow a Poisson arrival; here, we tuned the sending
rate so as to occupy 10% of the link capacity of the bottleneck link N1 -N2 . As mentioned above, INTEST is not
restricted by a Poisson arrival of the target traﬃc. However,
it is diﬃcult to exactly know the true value of the virtual
delay on the path by measuring delay of target traﬃc unless the sending time of the packets follows a Poisson arrival [22]. As for cross traﬃc, traﬃc streams along tworoutes (i.e., from N5 to N6 and from N6 to N7 ), and there
are two flows for each route. The cross traﬃc streams overrepetitive ON/OFF intervals, with the constant bit rate of
8 [Mbps] during ON periods. The ON and OFF periods
follow exponential distribution with mean 1.0 and 4.0, respectively. In ON periods, the cross traﬃc generated withconstant bit rate. The packet length of the cross traﬃc is
600 [byte]. When two flows sharing the same route areboth in an ON interval, the total amount of traﬃc exceeds thebottleneck link capacity, thereby producing packet delays on
node N1 or N2 . Packet loss does not occur since the size ofthe buﬀers on node N1 or N2 is supposed to be suﬃciently
large. If there is no probe packets in the network, the total
link utilization of the bottleneck link N1 -N2 is about 0.306.
The length of the probe packets is 64 [byte]. The injecting
time of the probe packets follows a Poisson arrival, and wetuned the probing rate so as to occupy 0.125%, 0.25%, 1.0%,
2.0%, and 4.0% of the link capacity of the bottleneck link.
All of the packets in the simulation are UDP packets, andthe simulation time is 50.0 [sec]. On an assumption that thelink capacity is already known, we did not estimate the link
capacity with Eq. (10).
In Fig. 12, we show the diﬀerences between estimatorsand the true value of 95%-quantile end-to-end delay. From
the figure, the conventional estimators become increasingly
separated from the true value with an increasing ratio ofprobe load to link capacity. We note that the INTEST estimators are closer to the true value than the conventional estimators. Through this simulation, we confirm that INTEST
can accurately estimate the end-to-end delay of a network
composed of multiple routers.

Fig. 12 Estimation by INTEST and conventional estimators of end-toend delay of a network composed of multiple routers.

8. Conclusion
In this paper, we demonstrated that there exists a fundamental accuracy bound to conventional active measurement of
delay in the M/M/1 case and proposed INTEST to transcend
the bound.
We evaluated the accuracy in terms of MSE, taking
bias into consideration in the case of estimating the number of packets in a router modeled by M/M/1 queuing, andshowed that MSE has a lower bound across varying probing
rates. Performing simulations of a single M/M/1 queuing,
MMPP/M/1, and a multi-hop network, we demonstrated that
our INTEST estimator provides unbiased and small varianceestimation of high quantile end-to-end delay, whereas theconventional estimator does not provide unbiased estimation.
We plan to evaluate INTEST on a real network and extend it to packet loss estimation and to wireless networks infuture works.
Acknowledgment
This work was partly supported by the Telecommunications Advancement Foundation and JSPS KAKENHI Grant
Number JP26880008, JP17K00008.
References[1] “One-way Transmission Time,” ITU-T Recommendation G.114,
May 2003.
[2] S. Lee, K. Levanti, and H.S. Kim, “Network monitoring: Present andfuture,” Computer Networks, vol.65, no.2, pp.84–98, June 2014.
[3] J.C. Bolot, “Characterizing end-to-end packet delay and loss in theInternet,” J. High Speed Networks, vol.2, no.3, pp.289–298, 1993.
[4] K.P. Gummadi, S. Saroiu, and S.D. Gribble, “King: Estimating latency between arbitrary Internet end hosts,” Proc. 2nd ACM SIGCOMM Workshop on Internet Measurment (IMW 2002), pp.5–18,
Marseille, France, Nov. 2002.
[5] L. De Vito, S. Rapuano, and L. Tomaciello, “One-way delay measurement: State of the art,” IEEE Trans. Instrum. Meas., vol.57,
no.12, pp.2742–2750, Dec. 2008.
[6] J. Sommers, P. Barford, N. Duﬃeld, and A. Ron, “Improving accuracy in end-to-end packet loss measurement,” ACM SIGCOMM
Computer Communication Review, vol.35, no.4, pp.157–168, Oct.
2005.

WATABE and NAKAGAWA: PACKET DELAY ESTIMATION THAT TRANSCENDS A FUNDAMENTAL ACCURACY BOUND DUE TO BIAS

1387

[7] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “Probing for loss:
The case against probe trains,” IEEE Commun. Lett., vol.15, no.5,
pp.590–592, March 2011.
[8] J. Strauss, D. Katabi, and F. Kaashoek, “A measurement study ofavailable bandwidth estimation tools,” Proc. 3rd ACM SIGCOMM
Conference on Internet Measurement (IMC 2003), pp.39–44, Miami, FL, USA, Oct. 2003.
[9] V.J. Ribeiro, R.H. Riedi, R.G. Baraniuk, J. Navratil, and L. Cottrell,“pathChirp: Eﬃcient available bandwidth estimation for network
paths,” Proc. 4th Passive and Active Measurement Conference (PAM
2003) Workshop, San Diego, CA, USA, April 2003.
[10] K.G. Anagnostakis, M. Greenwald, and R.S. Ryger, “cing: Measuring network-internal delays using only existing infrastructure,” Proc.
22nd IEEE International Conference on Computer Communication(INFOCOM 2003), pp.2112–2121, San Francisco, CA, USA, March
2003.
[11] A. Rizk, Z. Bozakov, and M. Fidler, “H-probe: Estimating traﬃccorrelations from sampling and active network probing,” IFIP Networking 2013 Conference, Brooklyn, NY, USA, March 2013.
[12] A. Habib, M. Khan, and B. Bhargava, “Edge-to-edge measurementbased distributed network monitoring,” Computer Networks, vol.44,
no.2, pp.211–233, Feb. 2004.
[13] L. Cheng, X. Qiu, L. Meng, Y. Qiao, and R. Boutaba, “Eﬃcient active probing for fault diagnosis in large scale and noisy networks,”
Proc. 29th IEEE International Conference on Computer Communication (INFOCOM 2010), San Diego, CA, USA, March 2010.
[14] M. Yajnik, S. Moon, J. Kurose, and D. Towsley, “Measurement andmodelling of the temporal dependence in packet loss,” Proc. 18th
IEEE International Conference on Computer Communication (INFOCOM 1999), pp.345–352, New York, NY, USA, March 1999.
[15] H. Pucha, Y. Zhang, Z.M. Mao, and Y.C. Hu, “Understanding network delay changes caused by routing events,” ACM SIGMETRICS
Performance Evaluation Review, vol.35, no.1, p.73, June 2007.
[16] M. Aida, N. Miyoshi, and K. Ishibashi, “A scalable and lightweight
QoS monitoring technique combining passive and active approaches,” Proc. 22nd IEEE International Conference on Computer
Communication (INFOCOM 2003), pp.125–133, San Francisco,
CA, USA, March 2003.
[17] B.Y. Choi, S. Moon, R. Cruz, Z.L. Zhang, and C. Diot, “Quantile sampling for practical delay monitoring in Internet backbone
networks,” Computer Networks, vol.51, no.10, pp.2701–2716, July
2007.
[18] M. Roughan, “A comparison of Poisson and uniform sampling foractive measurements,” IEEE J. Sel. Areas Commun., vol.24, no.12,
pp.2299–2312, 2006.
[19] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “On optimal probing for delay and loss measurement,” Proc. 7th ACM Conferenceon Internet Measurement (IMC 2007), pp.291–302, San Diego, CA,
USA, Oct. 2007.
[20] J. Sommers, P. Barford, N. Duﬃeld, and A. Ron, “Accurate andeﬃcient SLA compliance monitoring,” ACM SIGCOMM Computer
Communication Review, vol.37, no.4, pp.109–120, Oct. 2007.
[21] N. Zhu, J. He, Y. Zhou, and W. Wang, “On the accuracy of packet delay estimation in distributed service networks,” J. Netw. Syst. Manage., vol.21, no.4, pp.623–649, Feb. 2013.
[22] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “The role of
PASTA in network measurement,” ACM SIGCOMM Comput. Commun. Rev., vol.36, no.4, pp.231–242, Oct. 2006.
[23] M. Roughan, “Fundamental bounds on the accuracy of network performance measurements,” ACM SIGMETRICS Performance Evaluation Review, vol.33, no.1, pp.253–264, June 2005.
[24] M. Aida, N. Miyoshi, and K. Ishibashi, “A change-of-measure approach to per-flow delay measurement combining passive and active
methods: Mathematical formulation for CoMPACT monitor,” IEEE
Trans. Inf. Theory, vol.54, no.11, pp.4966–4979, Nov. 2008.
[25] J. Abate and W. Whitt, “The correlation functions of RBM andM/M/1,” Stochastic Models, vol.4, no.2, pp.315–359, 1988.

[26] Y. Tsang, M. Yildiz, P. Barford, and R. Nowak, “Network radar: Tomography from round trip time measurements,” Proc. 11th ACM
SIGCOMM Conference on Internet Measurement (IMC 2004),
pp.175–180, Sicily, Italy, Oct. 2004.
[27] Y. Gu, G. Jiang, V. Singh, and Y. Zhang, “Optimal probing for unicast network delay tomography,” Proc. 29th IEEE International Conference on Computer Communication (INFOCOM 2010), pp.1244–
1252, IEEE, Shanghai, China, March 2010.
[28] W. Fischer and K. Meier-Hellstern, “The Markov-modulated Poisson Process (MMPP) cookbook,” Performance Evaluation, vol.18,
no.2, pp.149–171, Sept. 1993.
[29] T.R. Henderson, M. Lacage, G.F. Riley, G. Dowell, and J.B. Kopena,“Network simulations with the ns-3 simulator,” Proc. ACM SIGCOMM 2008, p.527, Seattle, WA, USA, Aug. 2008.

Kohei Watabe
received his B.E. and M.E.
degrees in Engineering from Tokyo Metropolitan University, Tokyo, Japan, in 2009 and 2011,
respectively. He also received the Ph.D. degree from Osaka University, Japan, in 2014. He
was a JSPS research fellow (DC2) from April
2012 to March 2014. He has been an AssistantProfessor of Graduate School of Engineering,
Nagaoka University of Technology since April
2014. He is a member of the IEEE and the
IEICE.

Kenji Nakagawa
received the B.S., M.S.
and D.S. degrees from Tokyo Institute of Technology, Tokyo, Japan, in 1980, 1982 and 1986,
respectively. In 1985, he joined NTT (Nippon
Telegraph and Telephone Corp.). Since 1992,
he has been an associate professor of Graduate
School of Engineering, Nagaoka University ofTechnology. He is an associate editor of the
IEICE Transactions on Communications. His
research interests include queueing theory, performance evaluation of networks, and geometrictheory of statics. Dr. Nakagawa is a member of the IEEE, SITA, and Mathematical Society of Japan.