K. Watabe
K. Nakagawa
Importance of Active
Measurement
Fundamental Problemand Objective

Intrusiveness-aware Estimationfor High Quantiles of a Packet Delay Distribution

What is an Acculate
Estimator?
Bounds ofConventional Estimator
INTEST:
INTrusiveness-aware
ESTimation

Kohei Watabe, Kenji Nakagawa

Evaluation in M/M/1

Graduate School of Engineering, Nagaoka University of Technology

Evaluation throughns-3 Simulations

June 11, 2015

Conclusion and futureworksaICC 2015

1

Importance of Active Measurement
Real-time applications have been widely spread.
(e.g. audio/video conferencing and IP telephony)

K. Watabe
K. Nakagawa
Importance of Active
Measurement

Large end-to-end delay lowers the quality of real-time
applications.

Fundamental Problemand Objective

It is often necessary to accurately estimate end-to-end delay andevaluate path quality.

What is an Acculate
Estimator?
Bounds ofConventional Estimator

Active measurement is one representative measurement
technique for end-to-end delay.

INTEST:
INTrusiveness-aware
ESTimation

User host	

Evaluation in M/M/1

User packet	

Probe packet	

Evaluation throughns-3 Simulations
Conclusion and futureworks

Probe Host	Network	We record injecting time of probe 	 We record receive time of probe	
We calculate the delay of probe by matching the two data	aICC 2015

2

Fundamental Problem and Objective
A problem with active measurement is that probe traffic
increases network delay.

K. Watabe
K. Nakagawa
Importance of Active
Measurement: Increased delay 	by probe traffic	

Delay	

Fundamental Problemand Objective
What is an Acculate
Estimator?

: True delay	

Bounds ofConventional Estimator

Conventional estimators	
of delay are biased. 	

INTEST:
INTrusiveness-aware
ESTimation
Evaluation in M/M/1
Evaluation throughns-3 Simulations
Conclusion and futureworksTime	Objectivea

To estimate the delay of a network without probe packets
from the delay of that same network with probe packets.
ICC 2015


3

What is an Acculate Estimator?
An accurate estimator must have a smaller variance and asmaller bias.

K. Watabe
K. Nakagawa
Importance of Active
Measurement

pdf	

Fundamental Problemand Objective

Distribution of good estimator	

What is an Acculate
Estimator?

Distribution of biased estimator	

Bounds ofConventional Estimator

Distribution of estimator	
with large variance	

INTEST:
INTrusiveness-awareESTimation

Estimator value	

True value	

Evaluation in M/M/1
Evaluation throughns-3 Simulations

We evaluate estimators by using Mean Square Error (MSE).

Conclusion and futureworks(MSE) = Var[P̂] +{E[P̂] − P∗ }2 = E[(P̂ − P∗ )2 ]| {z }| {z }

Variance

BiasP∗ : True valueP̂ : Estimatora(1)ICC 2015

4

Bounds of Conventional Estimator
We calculated MSE of conventional estimator for the mean
number of packets in M/M/1.

K. Watabe
K. Nakagawa
Importance of Active
Measurement

MSE [packet2]Fundamental Problem
and Objective
What is an Acculate
Estimator?
Bounds ofConventional Estimator
INTEST:
INTrusiveness-aware
ESTimation
Evaluation in M/M/1
Evaluation throughns-3 Simulations
Conclusion and futureworks

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

Inaccuracy	
MSE!
due to large variance	 Variance!
Square of bias!

Inaccuracy	
due to bias	

Accuracy bounds	

0!

0.005!
0.01!
0.015!
0.02!
Ratio of probe load to the bandwidth!

Bandwidth : 155.52 Mbps

Traffic load : 90% of bandwidth

Packet size : Exponential distribution withmean 600 byteaICC 2015

Measurement period : 1.0 [sec]5

INTEST: INTrusiveness-aware ESTimation
K. Watabe
K. Nakagawa

To transcend that bound, we propose INTrusivenessaware ESTimation (INTEST), an approach that modifies fordelays increased by probe packets for networks.

Importance of Active
Measurement
Fundamental Problem
and Objective
What is an Acculate
Estimator?

: Increased delay 	by probe traffic	(measurable)	

Delay	

Bounds ofConventional Estimator
INTEST:INTrusiveness-awareESTimation: True delay	(unmeasurable)	

Estimation	

Evaluation in M/M/1
Evaluation throughns-3 Simulations
Conclusion and future
works

Time	
We can know increment of delay using the information of thenumber of probe packets.
aICC 2015

6

INTEST: INTrusiveness-aware ESTimation (2)For busy period [s j , e j ), delay Dgp (T i ) experienced by a probe
packet can be expressed by the following:

K. Watabe
K. Nakagawa
Importance of Active
Measurement

Dgp (T i ) = Dgp (T i−1 ) +Fundamental Problemand Objective
What is an Acculate
Estimator?

Xgp (T i , T i−1 )− (T i − T i−1 ), (s j ≤ T i ≤ T i−1 ≤ e j )cDelay	Bounds ofConventional Estimator
INTEST:
INTrusiveness-aware
ESTimation

Time	A busy period	

Evaluation in M/M/1
Evaluation throughns-3 Simulations

A busy period	

T i : Time of an arrival of ith probe packetc : Bandwidth [bps]Xgp (t0 , t1 ) : traffic in a period [t0 , t1 ) [bit]Conclusion and future
works

Bussy periods can be estimated by probe delay.
Based on the above equation, we can modify the inclement ofdelay since the traffic of probe packets in Xgp (T i , T i−1 ) is known.
aICC 2015

7

INTEST: INTrusiveness-aware ESTimation (3)K. Watabe
K. Nakagawa

We can estimate the true delay by the following recurrence
equation.

Importance of Active
Measurement
Fundamental Problem
and Objective

Decreasing the increased delay	
by probe traffic	

What is an Acculate
Estimator?

Busy case and idle case	

Bounds ofConventional Estimator
INTEST:
INTrusiveness-aware
ESTimation
Evaluation in M/M/1
Evaluation throughns-3 Simulations

D̂g (T i ) : The delay of the network without probe packets at time T ipxi : The size of ith probe packets [bit]Conclusion and futureworksŝ j : jth smallest element of {T i | Dgp (T i−1 ) ≤ d + δ < Dgp (T i )}ê j : jth smallest element of {T i | Dgp (T i−1 ) ≥ d + δ > Dgp (T i )}ŝ j and ê j are estimators of start and end time of a busy period,respectively.
aICC 20158

Evaluation in M/M/1
We estimated the number of the packets in the router modeledby M/M/1.

K. Watabe
K. Nakagawa
Importance of Active
Measurement
Fundamental Problem
and Objective

Delay [sec] What is an Acculate
Estimator?
Bounds ofConventional Estimator
INTEST:
INTrusiveness-aware
ESTimation
Evaluation in M/M/1
Evaluation throughns-3 Simulations
Conclusion and future
works

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

INTEST	
There are large differences between
probe delay and true value. 	
INTEST estimator
corresponds the true value	

0.03!
Time [sec]!

Bandwidth : 155.52 Mbps

Target traffic rate : 90% of bandwidth

Packet size : It follows the exponential distribution with mean 600 byte

a0.04!

Probe rate : About 3.16% of bandwidth
Threshold δ : 7.5 packet
ICC 2015

9Evaluation in M/M/1 (2)We calculated the MSE by repeating the simulation 5000 times.

K. Watabe
K. Nakagawa

INTEST can achieves acculate estimation though theconventional estimator has a accuracy bounds.

Importance of Active
Measurement
Fundamental Problem
and Objective
What is an Acculate
Estimator?

MSE [packet2]

Bounds ofConventional Estimator
INTEST:INTrusiveness-aware
ESTimation
Evaluation in M/M/1
Evaluation throughns-3 Simulations
Conclusion and future
works

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

Conventional estimator!
INTEST estimator!
Conventional estimator (theoretical)!
INTEST estimator (theoretical)!

MSE of INTEST estimator islower than the accuracy
bounds. 	

0!
a0.02!
0.04!
0.06!
0.08!
0.1!
Ratioof probe load to the link capacity
ICC 2015

10Evaluation through ns-3 Simulations
We performed INTEST in ns-3 simulation.

K. Watabe
K. Nakagawa

Cross traffic	

Importance of Active
Measurement
Fundamental Problem
and Objective

N5	N6	N7	

N1	N2	N3	Target traffic	

What is an Acculate
Estimator?
Bounds ofConventional Estimator

N0	

INTEST:
INTrusiveness-aware
ESTimation

Node	Ps	

Evaluation in M/M/1
Evaluation throughns-3 Simulations

Probe traffic	

Bandwidth of N1 -N2 and N2 -N3 : 15.552 Mbps

Conclusion and futureworks

Probe packet size : 64 byte

N4	Link	Pd	

Bandwidth of the other links : 62.208 Mbps
Packet size of the other traffic : 600 byte

Target traffic rate : 10% of the bottleneck bandwidth
Cross traffic pattern : ON-OFF process in which ON/OFF period follows
exponential distribution with mean 0.5 sec
Cross traffic rate : 8 Mbps
aICC 201511

Evaluation through ns-3 Simulations (2)We evaluated the bias when we estimated 95%-quantile of delay.

K. Watabe
K. Nakagawa

We obtained a similar result to the M/M/1 result.

Importance of Active
Measurement

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

Fundamental Problem
and Objective
What is an Acculate
Estimator?
Bounds ofConventional Estimator
INTEST:INTrusiveness-aware
ESTimation
Evaluation in M/M/1
Evaluation throughns-3 Simulations
Conclusion and futureworks

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

a0!

0.01!

0.02!

0.03!

0.04!

INTEST estimator!
Conventional estimator!
Ratio of probe load to the link capacity

ICC 2015

12

Conclusion and future works
K. Watabe
K. Nakagawa

In this paper, we demonstrated that there exists a fundamental accuracy bound to conventional active measurementof delay and proposed INTEST that estimates the delay of a
network without probe packets from the delay of that same
network with probe packets.

Importance of Active
Measurement
Fundamental Problem
and Objective
What is an Acculate
Estimator?
Bounds ofConventional Estimator

INTEST modify the increased delay by the load imposed byprobe traffic.

INTEST:
INTrusiveness-aware
ESTimation

Performing simulations of M/M/1 and ns-3, we demonstrated thatINTEST provides unbiased and small variance estimation.

Evaluation in M/M/1
Evaluation throughns-3 Simulations

Future works

Conclusion and futureworks

Evaluation of INTEST on a real network.
To extend it to packet loss estimation and to wirelessnetworks.

aICC 2015

13

K. Watabe
K. Nakagawa
Importance of Active
Measurement
Fundamental Problemand Objective
What is an Acculate
Estimator?
Bounds ofConventional EstimatorThank you for your kind attention.

INTEST:
INTrusiveness-aware
ESTimation
Evaluation in M/M/1
Evaluation throughns-3 Simulations
Conclusion and futureworksaICC 201514