This is the post-print version of the following article: Kohei Watabe and Kenji Nakagawa, ``Intrusiveness-Aware Estimation for High Quantiles of a Packet Delay Distribution,'' in Proceedings of 2015 IEEE International Conference on
Communications (ICC 2015), 2015. The original publication is available at https://doi.org/10.1109/ICC.2015.7249306 (DOI: 10.1109/ICC.2015.7249306). (c) 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be
obtained for all other users, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work inother works.

Intrusiveness-aware Estimationfor High Quantiles of a Packet Delay Distribution
Kohei WatabeandKenji Nakagawa

Department of Electrical Engineering, Nagaoka University of Technology
Kamitomioka 1603-1, Nagaoka, Niigata 940-2188, Japan
Email:{k watabe, nakagawa}@vos.nagaokaut.ac.jp

Abstract—The active measurement of network quality, inwhich probe packets are injected into a network, is hinderedby the intrusiveness problem, where the load of the probe traffic
itself affects network quality. In this paper, we first demonstratethat there exists a fundamental bound on the accuracy of the conventional active measurement of delay. Second, to transcend thatbound, we propose INTEST (INTrusiveness-aware ESTimation),
an approach that compensates for delays produced by probe
packets for wired networks. We show that INTEST enables anaccurate high quantile estimation of delay. We do so through two
simulations: a single-hop network composed of a router modeledby M/M/1 queuing, and a realistic multi-hop network modeledby a network simulator.

I. I NTRODUCTION
In network and application design, it is often necessary toaccurately estimate end-to-end delay and evaluate path quality.
Large end-to-end delay lowers the quality of real-time applications, such as audio/video conferencing and IP telephony. ITUT Recommendation G.114 [1] mentions that an end-to-end
delay of 150 msec or over adversely affects the communication
quality of interactive Voice over IP (VoIP) applications. It isespecially important to accurately estimate not only average
delay, but also high 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 endto-end delay. Prior work on active measurement has left us
with a rich collection of literature [3], [4], [5], [6].
A problem with active measurement, however, is that when
we inject many probe packets into the network (so as toimprove accuracy), the load imparted by this probe traffic itself
acts to impair path quality [7], [8]. In the active measurementof end-to-end delay, probe packet injection is treated as amethod of sampling of the delay process of target path. Thus,
were there no such intrusive effect, estimation accuracy would
improve as the number of probe packets increases. As above,
however, the transmission of probe packets itself consumes
network resources. Thereby, the delays experienced by probe
packets in a network with probe packets tend to be larger thanthe delays that would be experienced by normal packets in thesame network without probe packets.
Needless to say, network researchers and practitioners areinterested not in delay within a network with probe packets,
but rather in delay within that network without probe packets. Nonetheless, because of this intrusiveness, conventional

estimators based on the delay experienced by probe packets
produce figures larger than the true value (i.e., the delay
experienced by normal packets within the network without
probe packets). In other words, conventional estimators ofdelay are biased. Baccelli et al. [7] indicates that the mean ofa conventional estimator corresponds to network delay when
injecting probe packets upon Poisson arrivals. Note, however,that under this treatment, the mean corresponds to the delay of
a network with probe packets. Roughan [8] discusses accuracy
as defined by variances of conventional estimators but does not
focus on bias. Accordingly, discussion is needed in which suchbias is taken into consideration.
In this paper, we first show that the conventional estimationof delay has a fundamental accuracy bound due to bias. To
evaluate effect of bias on accuracy, we calculate Mean Squared
Error (MSE) of a conventional estimator when we estimate thenumber of packets in a router modeled by M/M/1. Throughthis evaluation, we show that MSE has a lower bound acrossvarying probing rates.
To transcend this MSE bound, we next propose
INTrusiveness-aware ESTimation (INTEST), an approach thatallows us to estimate the delay of a wired network without
probe packets from the delay of that same network withprobe packets. INTEST does this by compensating for theincreased delay brought about by the load imposed by probe
traffic. Performing simulations with single M/M/1 queuing
and a multi-hop network, we show that INTEST enables
a more accurate estimation of delay quantiles than does aconventional estimator.
The remainder of this paper is organized as follows. We
formulate the intrusiveness problem of active measurement in
Section II. In Section III, by theoretically calculating MSE, weshow that there exists a lower bound to MSE when estimating
the number of packets in a router modeled by M/M/1 queuing.
In Section IV, we summarize INTEST, and in Section V, weevaluate it through simulations. Finally, we conclude our paper
and present issues for future research in Section VI.
II. F ORMULATION OF THE I NTRUSIVENESS P ROBLEMFirst of all, we formulate the intrusiveness problem of active
measurement, and show how we evaluate effect of bias on
accuracy. Let us consider a network with some network edges.
We define the target traffic as traffic that streams from anedge a to an edge b. We let Dg (t) denote a delay that isexperienced by a packet that is enqueued to a queue of sourceside edge a at time t. The subscript g indicates that the processrepresents the so-called ground truth of the delay (i.e., thedelay is not affected by probe load). We define cross traffic as
the traffic that excludes the target traffic from the whole traffic
in the network. If applying active measurement to determine
characteristic of Dg (t), we add probe traffic to the traffic thatstreams from the edge a to the edge b.
On the network with probe packets, a packet of traffic thatstreams from the edge a to the edge b experiences a delay
Dgp (t) [sec], where the subscript p stands for probe traffic.
Note that Dgp (t) differs from Dg (t), even if cross traffic is
unchanged.
Based on delays that are experienced by n probe packets,
we estimate mean, quantile, and other parameters descriptiveof end-to-end delay. We let Ti (i = 1, . . . , n) denote timeat which ith probe packet is injected into the network (i.e.,
the packet is enqueued to a queue of source side edge). The
delay that is experienced by ith probe packet is expressedby Dgp (Ti ). When estimating mean delay, the conventional
estimator isn1∑D̂ave =
Dgp (Ti ).
(1)
n i=1
Furthermore, when we estimate q-quantile of delay, we defineκ(q) = ⌈(1 − q)n⌉, where ⌈·⌉ denotes ceiling function. Here,the conventional estimator is taken as the κ(q)th largest delay
among the delays Dgp (Ti ) experienced by the probe packets.
Since Dgp (t) ̸= Dg (t), the above estimators are generally
not unbiased. A delay experienced by a probe packet is notmuch affected by other probe packets when the number ofprobe packets n is small. However, when n is small, estimator
variance is large (and accurate estimation is difficult) since
there are only a few samples. On the other hand, the accuracyof the estimator increasingly suffers from bias if we increase
the number of samples because of the delays experienced byother packets. In short, there is a trade-off 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 target delay.
III. A F UNDAMENTAL B OUND ON THE ACCURACY OF
ACTIVE M EASUREMENT
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 accuracy due
to bias. Here, we evaluate the accuracy of estimation by MSE
and then, by plotting the MSE of the estimator as a functionof probing rate, verify the degree to which accuracy improves
with higher probing rates.
To theoretically verify the dependence of accuracy on probing rate while taking such bias into consideration, we consider

MSE upon an estimation of the number of packets (not delay)in a router under an M/M/1 queuing model. We assume
that probe packets and target traffic packets are generated
according to a Poisson arrival, and follow an exponential
distribution with mean service time 1/µ. Here, n probe packets
are injected with rate λp , and the sending rate of target
traffic is λg . We estimate the mean number of packets in
the router without∑n probe packets by an arithmetical meanM̂ave = n−1 i=1 Mgp (Ti ), where Mgp (Ti ) denotes thenumber of packets in the router at time Ti . Under active
measurement, we cannot practically determine the number ofpackets in a router by injecting probe packets. A verification of
the number of packets in a router can, however, provide good
insights on accuracy characteristics since we can analyticallyderive the MSE.
We can express the autocovariance function of the processof the number of packets in a router by primary functions asfollows [8]:()ρ−A(ρ)|τ |−B(ρ)|τ |r(ρ, τ ) ≃e+e,2(1 − ρ)2
(1 − ρ)2(1 − ρ)2
A(ρ) =
B(ρ) =√ ,√ ,1+ρ+ ρ
1+ρ− ρ
where ρ denotes utilization.
The variance σ 2 = Var[M̂ave ] that corresponds to Var[P̂ ]in Eq. (2) can be expressed by r(ρ, τ ) and ρgp ≡ (λg + λp )/µas11 ∑σ 2 = Var[r(ρgp , 0)] + 2r(ρgp , |Ti − Tj |)
n
n
i̸=j
∫
1
1 ∑ ∞
r(ρgp , t)f (t, |i − j|, 1/λp )dt= Var[r(ρgp , 0)] + 2nni̸=j 0{n
ρgp
2 ∑ ρgp (n − k)≃+ 2n(1 − ρgp )2n2(1 − ρgp )k=1()}(λp )k(λp )k×,+
λp + A(ρgp )k
λp + B(ρgp )kwhere f (t, k, α) denotes the probability density function of an
Erlang distribution with shape parameter k and scale parameter
α. 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 [8]
ρ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 andvarying the number n of probe packets, we derive the MSE
relation shown in Fig. 1. Assuming link capacity and mean
packet length to be 155.52 Mbps and 600 byte, respectively,
we set µ of M/M/1 to 32400 packet/sec. We set the mean
measurement period l to 1.0 sec. To inject n probe 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

MSE [packet2]

Delay	
10.0 !
9.0 !
8.0 !
7.0 !
6.0 !
5.0 !
4.0 !
3.0 !
2.0 !
1.0 !
0.0 !

MSE!
Variance!
Square of bias!

0!
Ratio

0.005!
0.01!
0.015!
0.02!
of probe load to the link capacity!

time	
B	

A	

B	

A	
 B	

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

Fig. 2. Relationship between Dg (t) and Dgp (t)time follows Poisson arrivals though the mean time is l. Notethat in Fig 1, the horizontal axis represents the ratio of probeload to the link capacity.
In Fig. 1, we see that MSE has a lower bound (i.e., alimit to 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 sufficient sampling.
When the ratio of probe load to the link capacity 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 a more accurate estimation
by increasing nor decreasing the number of probe packets.
Furthermore, in practical measurements, it is very difficult todetermine the optimal number of probe packets because of adependency on the ratio ρg of traffic load to link capacity.
The process of the number of packets in a router may notcorrespond to that of delay, as mentioned above. The delayis, however, proportional to the number of packets, and we
confirm that similar results are obtained upon delay estimation
based simulation (see Section V).

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 sent at time t is related
to Bgp (t) as Dgp (t) = Bgp (t)/c + d, where d denotes a
propagation delay.
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.

IV. I NTRUSIVENESS - AWARE E STIMATION
We here propose INTEST, an approach that compensates fordelays produced by probe packets on wired networks and, by
that, transcends the accuracy bound mentioned in Section III.
INTEST estimates the delay Dg (t) of the network without
probe packets from the delay Dgp (Ti ) of the network withprobe packets. It does this by subtracting the delay producedby the load imparted by probe traffic. Note that Dgp (t) isalways larger than Dg (t) as shown in Fig. 2.
We first consider a network composed of single router with
FIFO queuing, and we clarify the relationship between delay
Dg (t) of the network without probe packets and delay Dgp (t)of the network with probe packets. Letting c [bps] denote link
capacity, we define the amount of data Bgp (t) [bit] in queue
at time t as
Mgp (τ )

∑


lim
xh − c(t − u0 (t)), (Mgp (t) > 0),
Bgp (t) = τ →t−0
h=1


0 ,
(M (t) = 0),gp

Bgp (t2 ) = Bgp (t1 ) + Xgp (t1 , t2 ) − c(t2 − t1 ),where Xgp (t1 , t2 ) denotes the total amount of traffic arrived
in interval [t1 , t2 ). We let [sj , ej ) denote the start and end
time of the jth busy period of a network with probe packets(see Fig. 2). We derive the following equation regarding theamount of data Bgp (t) [bit] in the network with probe packets.
Bgp (Ti ) = Bgp (Ti−1 ) + Xg (Ti−1 , Ti ) + xpi−1 − c(Ti − Ti−1 ),( i ∈ { x |sj ≤ Tx−1 , Tx < ej }).
Here, Xg (t1 , t2 ) [bit] denotes the total amount of cross andtarget traffic in an interval [t1 , t2 ) and xpi [bit] denotes thelength of ith probe packet. Note that Bgp (Ti ) does not include
the data of a probe packet sent at time Ti .
We can clarify relationship between Dg (Ti ) and Dgp (Ti )since a similar relationship holds for Bg (t) [bit] in[skj , ekj ) (k = 1, 2, . . . , mj ) (intervals A in Fig. 2). Here, we
let skj (k = 1, 2, . . . , mj ) and ekj denote the start and end timesof the kth busy period of the network without probe packets
within an interval [sj , ej ). Then, we have
Bg (Ti ) = Bg (Ti−1 ) + Xg (Ti−1 , Ti ) − c(Ti − Ti−1 ),Bg (Ti ) = Bg (Ti−1 ) + Bgp (Ti ) − Bgp (Ti−1 ) − xpi−1 ,xp
Dg (Ti ) = Dg (Ti−1 ) + Dgp (Ti ) − Dgp (Ti−1 ) − i−1 (3)cfor i ∈ { x |skj ≤ Tx−1 , Tx < ekj }. Note that each busy period
for the network without probe traffic is included in a busy
period for the network with probe traffic.
Moreover, since the right hand side of Eq. (3) can be
expressed by d−(Ti −Ti−1 ) when Ti and Ti−1 are in [sj , s1j ),m[ekj , sk+1
) (k = 1, 2, . . . , mj − 1) or [ej j , ej ) (intervals B injFig. 2), the equation,(
Dg (Ti ) = max Dg (Ti−1 ) + Dgp (Ti ))xpi−1− Dgp (Ti−1 ) −, d , (4)cholds for all i that do not satisfy sj < Ti−1 ≤ skj < Ti < ejor sj < Ti−1 ≤ ekj < Ti < ej . Eq. (4) means that we
can estimate Dg (Ti ) from delays Dgp (Ti ) and Dgp (Ti−1 )experienced by probe packets.
We consider that Eq. (4) approximately holds when i satisfies sj < Ti−1 ≤ skj < Ti < ej or sj < Ti−1 ≤ ekj < Ti < ej ,although we cannot express Dg (Ti ) unless we use traffic in aninterval [Ti−1 , Ti ) as a function of time t. The approximation isreasonable when we can assume that the traffic including crossand target traffic have a constant rate X(Ti−1 , Ti )/(Ti −Ti−1 )in an interval [Ti−1 , Ti ).
In practical measurements, we must estimate a start time
sj of a busy period, an end time ej of a busy period, apropagation delay d, and link capacity c. They are also possible
to obtain Dgp (Ti ) as a delay experienced by a probe packet.
By using threshold δ, we can detect start of busy periods by
U = {Ti | Dgp (Ti−1 ) ≤ d + δ < Dgp (Ti )}. Hence, ŝj that isa jth smallest element of U is an estimator of sj . Similarly,êj that is jth smallest element of V = {Ti | Dgp (Ti−1 ) ≥d + δ > Dgp (Ti )} is an estimator of ej . When the probing
rate is λp , the threshold δ need not be longer than 1/λp ,because the amount of data in a router has been never 0 in theinterval [t, t + 1/λp ] if delay at time t is greater than 1/λp .
ˆ the minimum
A propagation delay d can be estimated by d,delay of delays experienced by probe packets. With regards toc, the following equation holds:

According to the definition of ŝj , Dg (Ti ) = Dgp (Ti ) wheni = 1. We can estimate an average delay of a network without
probe packets by replacing Dgp (Ti ) with D̂g (Ti ) in Eq. (1).
The κ(q)th largest value within the values of D̂g (Ti ) is theq-quantile estimator of a network without probe packets.
INTEST can be used to estimate delay in multi-hop networks composed of multiple routers, using timestamps provided by each router. Letting Tik denote a timestamp of kthrouter recorded on ith probe packet, we can estimate a queuingkk−min2≤i≤n (Tik −delay of kth router by Dgp(Ti ) = Tik −Ti−1
k
k
(Ti )
Ti−1 ). Replacing Dgp (Ti ) in Eqs. (5) and (6) with Dgp
and setting dˆ in Eq. (6) to 0, we can estimate a queuing delayof kth router without probe packets. By calculating the sum ofˆ we can estimate thethe queuing delays of each router and d,
end-to-end delay of a multi-hop network composed of multiple
routers. Note that time synchronization across routers is not
required to make this estimate.
V. E VALUATION
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 network composed ofa single router. We then move on to a valuation of INTEST as
applied to a multi-hop network. Because the theoretical valueof MSE of an estimator can be derived in M/M/1 queueing,
we estimate the number of packets in a router in addition todelay when evaluating of single-hop network.
A. A Network Composed of Single Router

We evaluate INTEST in a single-hop network composedof a router that is modeled by M/M/1 queuing, and show thatINTEST can produce more accurate estimations than can conventional active measurement. So as to clarify the fundamental
xpi + Xg (Ti−1 , Ti )= (Ti + Dgp (Ti )) − (Ti−1 + Dgp (Ti−1 )). characteristics of INTEST through a simple scenario, we focuschere on average number of packets in a router and on quantilesof delay.
Since Xg (Ti−1 , Ti ) ≥ 0, the estimator ĉ of c is
We first perform a simulation under an assumption thatpxi
= min ((Ti + Dgp (Ti )) − (Ti−1 + Dgp (Ti−1 )))we can determine the number of packets in a router at the2≤i≤nĉtime of the probe packet injection. The simulation is useful in()
xpiĉ = max. (5) evaluating the fundamental characteristics of INTEST. Note2≤i≤n Ti − Ti−1 + Dgp (Ti ) − Dgp (Ti−1 )that in practice, we cannot determine the number of packets
ˆBased on Eq. (4), ŝj , êj , d, and ĉ, we can estimate a delay in a router by a probe packet injection by measurement. We
Dg (Ti ) of a network without probe packets from a delay can, however, theoretically calculate the MSE, as described
Dgp (Ti ) of a network with probe packets. Let D̂g (Ti ) denote above. Parameters for this simulation are the same as thosean estimator for Dg (Ti ). Considering D̂g (Ti ) = Dgp (Ti ) for the simulation shown in Section III.
To estimate the number of packets in a router, we modify
if Ti is in an idle period (i.e., a maximal interval wherethe
INTEST estimator of Eq. (6) as follows.
the number of packets in a router is 0), the estimator of(
Dg (Ti ) (1 < i ≤ n) is given bymaxM̂g (Ti−1 ) + Mgp (Ti )


(

)

M̂
(T
)
=

g
i
−M
(T
)
−
1,
0
, ŝ′j ≤ Ti ≤ ê′j
gp i−1
max D̂g (Ti−1 )+Dgp (Ti )







Mgp (Ti ),otherwise,)p(6)D̂g (Ti ) =xi−1
−Dgp (Ti−1 )− ĉ , dˆ , ŝj ≤ Ti ≤ êjwhere M̂g (t) [packet] is the estimator of the number of packets




in
a router without probe packets at time t. Also, ŝ′j and ê′j
Dgp (Ti ),otherwise.
that are jth smallest elements of U ′ = {Ti | Mgp (Ti−1 ) <Conventional estimator!
INTEST estimator!
Conventional estimator (theoretical)!
INTEST estimator (theoretical)!

0!

0.02!
0.04!
0.06!
0.08!
0.1!
Ratio
of probe load to the link capacity

Delay [sec] 

MSE [packet2]

20!
18!
16!
14!
12!
10!
8!
6!
4!
2!
0!

0.0016 !
0.0014 !
0.0012 !
0.0010 !
0.0008 !
0.0006 !
0.0004 !
0.0002 !
0.0000 !
0.02!

0.03!
Time [sec]!

0.04!

Fig. 4. A comparison of a delay process of the network without probe packets
and samples D̂g (Ti ) by INTEST

Fig. 3. MSEs of the conventional and INTEST estimators when we estimate
the number of packets in a router modeled by M/M/1 queuingδ ≤ Mgp (Ti )} and V ′ = {Ti | Mgp (Ti−1 ) > δ ≥ Mgp (Ti )}are estimators of s′j and e′j , respectively. We set threshold δ
to 7.5 packets.
Upon changing the number of probe packets for each simulation from 2 packets to 2048 packets, we calculate MSE forthe conventional estimator and INTEST estimator of Eq. (6).
Results are shown in Fig. 3. In the calculation of MSE, werepeated the simulation 5,000 times at each number of probe
packets. The theoretical values for the conventional estimatorin Fig. 3 are the same as the MSE values shown in Fig. 1, andthe theoretical values for the INTEST estimator are σ 2 , whichis the MSE for an unbiased estimator. We can confirm from
Fig. 3 that the minimum value of the MSE of the INTEST
estimator is smaller than that of the conventional estimator.
This shows that INTEST achieves highly accurate measurement beyond the bound of conventional active measurement.
Next, we evaluate network delay under the same conditions
as the above simulation. To confirm that D̂g (Ti )—a sample
of a delay process obtained by compensation with INTEST
in Eq. (6)—corresponds to the delay of the network without
probe packets at time Ti , we derive a delay process of the
network without probe packets and compare D̂g (Ti ) to it. We
set the threshold δ to 0.2 msec when deriving D̂g (Ti ). In
Fig. 4, we show D̂g (Ti ) and delay processes over the interval[0.02, 0.04) sec. In the example, the number n of probe is1024. From the figure, we note that samples D̂g (Ti ) of the
INTEST estimator are very close to delay process Dg (t) of
the network without probe packets, although samples Dgp (Ti )of the conventional estimator differ greatly from the process.
Repeating similar simulations 5,000 times for each numberof probe packets, we derive the bias and MSE of the estimatorat 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 −λ −(µ−λ)te,µ(0 ≤ t).

Mean difference between true
values and estimators (Bias) [sec]!

0.002!

INTEST estimator!
Conventional estimator!

0.0015!
0.001!
0.0005!
0!
0!

0.02!

0.04!

0.06!

0.08!

0.1!

-0.0005!
-0.001!

Ratio

of probe load to the link capacity!

Fig. 5. Biases of the conventional and INTEST estimators when we estimate
95%-quantile of delay of a router modeled by M/M/1 queuing∗(q) of q-quantile isThen, the true value Dqua− 1 log µ (1 − q), 1 − λ ≤ q
∗
µ−λ
λ
µ
Dqua
(q) =

0,
otherwise.

(7)

We show the bias (i.e., mean difference between the value ofEq. (7) and an estimator) of the conventional and INTEST
estimator in Fig. 5. We find that the INTEST estimator can
provide an unbiased estimation when the number of probe
packets sufficiently large. The conventional estimator and
INTEST estimator both show a bias when the ratio of probeload to the link capacity is small. This is because the numberof probe packets, at 2 to 64 packets, is too small. As for MSE,
we obtained results similar to those shown in Fig. 3.
From the results of the above simulations, we confirm thatINTEST goes beyond the fundamental accuracy bound pointed
out in Section III and enables highly accurate measurementsof delay in a single-hop network. In INTEST, when the
probing rate increases, accuracy does not suffer but instead
improves. In conventional estimation, the parameter area (inwhich both bias and variance are small) is itself very small.
With INTEST, however, we can conduct unbiased and small
variance estimations as long as the probing rate is fairly high.

B. A Network Composed of Multiple Routers

VI. C ONCLUSION
In this paper, we demonstrated that there exists a fundamental accuracy bound to conventional active measurement of
delay and proposed INTEST as a means to take us beyond
that bound. We evaluated accuracy in terms of MSE, taking
bias into consideration in the case of an estimation of thenumber 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
and a multi-hop network, we demonstrated that our INTEST
estimator provides unbiased and small variance estimationof high quantile end-to-end delay, whereas the conventional
estimator does not provide unbiased estimation.

N0	

N5	

N6	

N7	

N1	

N2	

N3	

Node	
Ps	

Target traffic	

N4	

Link	

Probe traffic	

Pd	

Fig. 6. Simulation model

A difference between the true
value and an estimator [sec]

To confirm that INTEST enables accurate estimation for a
network composed of multiple routers, we perform a simulation with an ns-3 simulator [9]. INTEST can estimate end-toend delay of a network that is composed of multiple routers
by recording the timestamps of routers along the target path.
We perform a simulation of the network shown in Fig. 6
with an ns-3 simulator. From the results, we then estimate
the end-to-end delay of the network without probe packets
from the end-to-end delay experienced by probe packets. The
capacity of bottleneck links (i.e., N1 -N2 and N2 -N3 ) is taken
as 15.552 Mbps, and that of the other links as 62.208 Mbps. In
the simulation, the target traffic is streamed from node N0 to
node N4 . The packet length of the target traffic is 600 bytes.
The sending time of the packets follow a Poisson arrival; here,
we tuned the sending rate so as to occupy 10% of the link
capacity of the bottleneck links. As for cross traffic, traffic
streams along two routes (i.e., from N5 to N6 and from N6 to
N7 ), and there are two flows for each route. The cross traffic
flows over repetitive ON/OFF intervals (mean 0.5 sec), withthe constant bit rate of 8 Mbps during ON periods. When two
flows sharing the same route are both in an ON interval, thetotal amount of traffic exceeds the bottleneck link capacity,
thereby producing packet delays on node N1 or N2 . Packet
loss does not occur since the size of the buffers on node N1
or N2 is supposed to be sufficiently large. Probe traffic isstreamed from Ps to Pd , and the size of the probe packets
is 64 byte. The injecting time of the probe packets follows a
Poisson arrival, and we tuned the probing rate so as to occupy
0.125%, 0.25%, 1.0%, 2.0%, and 4.0% of the link capacityof the bottleneck links. All of the packets in the simulation
are UDP packets, and the simulation time is 10.0 sec. On an
assumption that the link capacity is already known, we did not
estimate the link capacity with Eq. (5).
In Fig. 7, we show the differences between estimators andthe true value of 95%-quantile end-to-end delay. From thefigure, we note that the INTEST estimators are very closed
to the true value while the conventional estimators become
increasingly separated from the true value with an increasing
ratio of probe load to link capacity. Through this simulation,
we confirm that INTEST can accurately estimate the end-toend delay of a network composed of multiple routers.

Cross traffic	

0.04!
0.03!
0.02!
0.01!
0!
-0.01!
-0.02!
-0.03!
-0.04!

0!

0.01!

0.02!

0.03!

0.04!

INTEST estimator!
Conventional estimator!
Ratio of probe load to the link capacityFig. 7. Estimation by INTEST and conventional estimators of end-to-end
delay of a network composed of multiple routers

We plan to evaluate INTEST on a real network and extend
it to packet loss estimation and to wireless networks in future
works.
ACKNOWLEDGMENT
This work was partly supported by JSPS Grant-in-Aid forYoung Scientists (Start-up) Number 26880008.
R EFERENCES[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, Jun. 2014.
[3] J.-C. Bolot, “Characterizing End-to-End Packet Delay and Loss in theInternet,” Journal of High Speed Networks, vol. 2, no. 3, pp. 289–298,
1993.
[4] L. De Vito, S. Rapuano, and L. Tomaciello, “One-way Delay Measurement: State of the Art,” IEEE Transactions on Instrumentation andMeasurement, vol. 57, no. 12, pp. 2742–2750, Dec. 2008.
[5] H. X. Nguyen and M. Roughan, “Rigorous Statistical Analysis of Internet
Loss Measurements,” IEEE/ACM Transactions on Networking, vol. 21,
no. 3, pp. 734–745, Jun. 2013.
[6] J. Strauss, D. Katabi, and F. Kaashoek, “A Measurement Study of
Available Bandwidth Estimation Tools,” in Proceedings of the 3rd ACM
SIGCOMM Conference on Internet Measurement (IMC 2003), Miami,
FL, USA, Oct. 2003, pp. 39–44.
[7] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “The Role of PASTA
in Network Measurement,” ACM SIGCOMM Computer Communication
Review, vol. 36, no. 4, pp. 231–242, Oct. 2006.
[8] M. Roughan, “Fundamental Bounds on the Accuracy of Network Performance Measurements,” ACM SIGMETRICS Performance Evaluation
Review, vol. 33, no. 1, pp. 253–264, Jun. 2005.
[9] T. R. Henderson, M. Lacage, G. F. Riley, G. Dowell, and J. B. Kopena,“Network Simulations with the ns-3 Simulator,” in Proceedings of ACM
SIGCOMM 2008, Seattle, WA, USA, Aug. 2008, p. 527.