CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

Accurate Delay Measurement
for Parallel Monitoring of Probe Flows

Background
Assumptions
Proposal
Estimators
Experiments

Kohei Watabe,
Shintaro Hirakawa,and Kenji Nakagawa

Conclusion

Graduate School of Engineering, Nagaoka University of Technology

November 30, 2017aa1

Outline
CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa
Background

Background

Assumptions
Proposal

Assumptions and models

Estimators

The key idea of the proposed method

Experiments
Conclusion

How to estimate delay metrics
Experiments
Conclusions and future works

aa2End-to-end Delay Measurements
CNSM 2017

End-to-end delay is fundamental for a performance evaluation.

K. Watabe
S. Hirakawa
K. Nakagawa

An active measurement is a common method for end-to-end
delay measurements.

Background

Probe packets are injected into a network for measurement.

Assumptions

It is important to achieve accurate measurement without increasing
the number of probe packets.

Proposal
Estimators

Since a large delay is a rare event in the modern Internet, highquantile of delay distribution is still hard to measure.

ExperimentsConclusion

User host	Probe Host	

User packet	Probe packet	

Network	We record injecting time of probe 	 We record receive time of probe	

aWe calculate thea delay of probe by matching the two data	

3

Parallel Monitoring of Probe FlowsCNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

Multiple probe flows are monitored to measure delays on
multiple paths in parallel for most measurement applications.

Backgrounde.g., SLA monitoring by Internet Service Providers.

Assumptions

In previous works, only one probe flow of the multiple probe
flows is utilized to measure the end-to-end delay on a path.

Proposal
Estimators
Experiments

However, the information concerning a flow can be utilized
supplementary for improving a measurement of another flow.

Conclusion

Flow A

Physical/Virtual Link
RouterFlow B

Flow Caa4

Objectives
CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

We propose a novel parallel flow monitoring method in which
information concerning all flow can be utilized.

Background
Assumptions
Proposal

The observation results of multiple flows are partially converted into
the results of a flow that we want to measure.

Estimators
Experiments

It does not require any internal information of a measured network(i.e. a topology, current queue size).

Conclusion

We evaluate the proposed method though simulations.
We confirm that the observation results of 72 parallel flows of active
measurement are appropriately converted between each other.

aa5

Network Model
CNSM 2017

A network considered within the scope of this work isrepresented by a directed graph.

K. Watabe
S. Hirakawa
K. Nakagawa

edge : a physical/virtual link and interfaces at both ends of the link.
Backgroundvertex : a part of a network device other than its interfaces.

Assumptions
Proposal

Physical/Virtual Link
RouterEstimators

Edge
VertexExperiments

ModelConclusion

Interface

An end-to-end delay is consisted of propagation delay andqueueing delay.
Propagation delay can be regarded as a constant.
Edges with large queueing delay are sparse.

To measure delay on paths, probe packets are periodicallyinjected for all or a part of paths.
aa6

Network Model (2)CNSM 2017

A network considered within the scope of this work isrepresented by a directed graph.

K. Watabe
S. Hirakawa
K. Nakagawa

edge : a physical/virtual link and interfaces at both ends of the link.
Backgroundvertex : a part of a network device other than its interfaces.

Assumptions
Proposal

Physical/Virtual Link
RouterEstimators

EdgeVertex

Experiments

ModelConclusion

InterfaceEdge

An end-to-end delay is consisted of propagation delay andqueueing delay.
Propagation delay can be regarded as a constant.
Edges with large queueing delay are sparse.

To measure delay on paths, probe packets are periodicallyinjected for all or a part of paths.
aa7

Overlap of Queueing Delay Processesχ̂A (t) : A virtual delay which is the queueing delay experienced by a virtual
packet injected into the path of Flow A at time t.

CNSM 2017

Delay

K. Watabe
S. Hirakawa
K. Nakagawa
Background

Flow A

Flow A

Assumptions

Flow B

1

3

ProposalTime

Estimators

A congestion periodcaused by Edge 2

Experiments
Conclusion

A congestion periodcaused by Edge 3

24
Flow C

5
Flow BIf χ̂A (t) and χ̂B (t) in a congestion period tightly overlap,
information of the period can be utilized each other.
Sufficient conditions for overlap is as follows:

a1The two paths of Flow A and B have the same source;

2Routes from the source to the last congested edge on the paths arecommon;

3A queueing delay that packets experience on edges after the lastcongested edge can be negligible.
a8Sample Conversion Technique
CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

It is, however, difficult to discriminate the above conditions
and 3 without using topology and current queue size.

Background2

We design a method that uses samples of a virtual queueing
delay process by probe packets.

Assumptions

Delay

Proposal
Estimators
Experiments

Overlap or not?

Conclusion

TimeSamples by probe packets

We discriminate whether processes overlap by the following twosteps:

a1

Conversion Process2

Clustering Processa9Conversion Process
CNSM 2017

We consider that virtual delay processes overlap if the two flows
satisfy the following conditions:

K. Watabe
S. Hirakawa
K. Nakagawa

1

The two flows have the same source;

2

The interval between the packet injection times of the first samples
in a congestion period is smaller than δ;3

The interval between the packet injection times of the last samples
in a congestion period is smaller than δ.

Background
Assumptions
Proposal
Estimators

Delay

Experiments
Conclusion

Samples of Flow A

Delay

Packet injection time

Conversion

The distance of injection timesof first/last samples are within
Samples of Flow B
Packet injection timeaSimilar conversion can be considered
for destination version.
a10

Clustering Process
If multiple edges are congested at the same time, the conversion
process may convert inappropriate samples.

CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

Delay

Background
Assumptions
Proposal

Samples of Flow A
Samples of Flow B
Samples of Flow C

Flow A

EstimatorsExperiments

1Conclusion

32

4
Flow C

5Flow B

A congestion periodcaused by Edge 2

A congestion periodcaused by Edge 3

To remove inappropriate samples, we utilize a clusteringtechnique in machine learning.

aBased on samples that are converted, we construct clusters offlows using a clustering technique.
a11Clustering Process (2)To use general clustering techniques, we transform samples ofeach flow into n-dimensional vectors.

CNSM 2017

1K. Watabe
S. Hirakawa
K. Nakagawa

Samples are connected by a solution of the widest path problem.
The cost of the edge between two samples is set to the reciprocal ofdistance1√Background
Assumptions
Proposalj
β2 ii − x j )2(t − tB )2 + (xAB
δ2 A.

i : the injection time of ith probe packet of Flow A.
tA

Estimatorsi : the delay of ith probe packet of Flow A.
xAExperiments

β : a control parameter to tune scale of distance of injection time and delay.

Delay2aFor each flow, we transform the path into an n-dimensional vector bymaking the vertices evenly spaced.
DelayConclusion

A solution of widest path problem for Flow A a A solution of widest path problem for Flow A 12

Limitations
The proposed method has the following limitations.

CNSM 2017

Momentary congestion: it cannot improve accuracy by converting
samples in very short congestion periods.

K. Watabe
S. Hirakawa
K. Nakagawa

Non-sparse congestion: it cannot detect start and end times of acongestion period if congested edges are not sparse.

Background
Assumptions

Estimators

Delay

Experiments
Conclusion

Delay

Complex routes: it cannot convert samples between flows that areonce forked and rejoined.

ProposalTimeTimeNon-sparse congestion

DelayMomentary congestion

TimeaComplex routesa13

Estimators for Parallel Flow Monitoring
CNSM 2017

The samples by our method is not uniformly distributed.

K. Watabe
S. Hirakawa
K. Nakagawa

It is needed to give weight wi for ith sample with delay di .

N j /N j for samples in jth congestion period,
wi = 
1otherwise.

Background
Assumptions
Proposal

Average end-to-end delay can be estimated by weighted average

Estimators

1 ∑wi di ,N sExperiments
Conclusion

q-quantile of end-to-end delay can be estimated by kth delay whendelays are arranged in ascending order, where j∑k = arg max wi ≤ qN .


ji=1

N : The number of original sample.
N j : The number of original sample in jth congestion period.
N j : The number of all sample in jth congestion period.
aa14

Simulation Settings
We perform NS-3 simulations to confirm that samples of parallel
flows are appropriately converted between each other.

CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

3 types of traffic stream between all pairs of 9 nodes in a
network (i.e., 72 flows stream for each type).

Background
Assumptions

StationaryProposal
Estimators

BurstExperiments
Conclusion

Probe

𝐶#Packet size
Traffic pattern
Traffic intensity
Packet size
Traffic pattern
Traffic intensity
Burst period
Idle period
Packet size
Traffic pattern

9.13

𝐶$13.03

600 [Byte]
Poisson arrivals
388.8 [Kbps] (4% of a link capacity)
500 [Byte]
On/off process with periodic arrivals
8,000 [Kbps] in burst periods
Exponential distribution with mean 0.1 [s]Exponential distribution with mean 4.0 [s]
74 [Byte]
Periodic arrivals

13.29

𝐶%

8.18

6.89

𝐶&𝐶'

2.77

10.45
9.05

13.42
𝐶+

a

10.00

17.05

𝐶*

Internal linka13.85

𝐶)

6.99
External link

𝐶(15Simulation Settings (2)CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

The parameters in the proposed method are as follows:
β = 0.16 : The tuning parameter in clustering process.
δ = 0.2 : Probe packet intervals.

Background
Assumptions

xth = 0.01 : The threshold to define start/end time of congestion

Proposalperiods.

Estimators

In the clustering process, we use Minimum Entropy Clustering(MEC) with 2 parameters:

Experiments
Conclusion

α = 0.001 : The radius parameter.
e = 10 : The expected number of clusters.

The simulation time is 42 [s] and we only use the data from20 [s] to 42 [s].
The simulation is repeated 10 times by changing the phase ofthe probe packet injection time.
aa16

Examples of Added/removed Samples
CNSM 2017

We depict examples of samples by the conventional and theproposed method.

K. Watabe
S. Hirakawa
K. Nakagawa

Flow ID 5-3
Background

0.4

Assumptions0.35

Virtual delay
Proposed method
Conventional method
Removed samples

0.3
Delay [sec]Proposal
Estimators
Experiments
Conclusion

0.25
0.2
0.15
0.1
0.05
037

38

39
40
Packet injection time [sec]41

The number of samples of the proposed method is larger thanthose of the conventional method.
The samples tightly approximate the virtual delay.
Most of removed samples are not on the virtual delay.
aa17

Examples of Added/removed Samples (2)CNSM 2017

We depict examples of samples by the conventional and theproposed method.

K. Watabe
S. Hirakawa
K. Nakagawa

Flow ID 6-4
0.16

Assumptions

0.14

Proposal

0.12
Delay [sec]BackgroundEstimators
Experiments
Conclusion

Virtual delay
Proposed method
Conventional method
Removed samples

0.1
0.08
0.06
0.04
0.02
020

20.5
21
21.5
Packet injection time [sec]22

The number of samples of the proposed method is larger thanthose of the conventional method.
The samples tightly approximate the virtual delay.
Most of removed samples are not on the virtual delay.
aa18

Delays, Number of samples
CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

The number of added samples by the proposed method isshown.

BackgroundWe display only flows that experience large delay.

Assumptions

The numberof samples

Proposal
Estimators
Experiments

6040
200
0-2
0-3
0-4
0-7
0-8
1-2
1-3
1-4
1-6
1-7
1-8
2-4
2-5
2-7
2-8
3-0
3-1
3-2
3-5
3-6
4-0
4-1
4-2
4-5
4-6
5-2
5-3
5-4
5-8
6-3
6-4
7-1
7-2
8-0
8-1
8-2

Conclusion

80

Flow ID

The number of original samples that are obtained from probe
packets is 110 samples.
Up to 78 samples are converted into samples of a flow.

aa19

Delays, Number of samples (2)CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

We also evaluate Root Mean Squared Errors (RMSE) when the99th-percentile of end-to-end delay is measured.

BackgroundThe error bars represent 95% confidence intervals.

Assumptions

RMSE [s]Proposal
Estimators
Experiments

Conventional method

Proposed method

0-2
0-3
0-4
0-7
0-8
1-2
1-3
1-4
1-6
1-7
1-8
2-4
2-5
2-7
2-8
3-0
3-1
3-2
3-5
3-6
4-0
4-1
4-2
4-5
4-65-2
5-3
5-4
5-8
6-3
6-4
7-1
7-2
8-0
8-1
8-2

Conclusion

0.14
0.12
0.1
0.08
0.06
0.04
0.02
0

Flow ID

The proposed method provides up to 95% reduction of RMSE
(Flow ID 8-2).
The RMSE reduction rate of the worst flow is reduced by 28%(Flow ID 0-7 vs 5-3).
aa20

Dependency of RMSE on Probe Intervals δCNSM 2017

We compare RMSE of 99th-percentile of end-to-end delay bychanging probe packet interval δ from 0.1 to 1.0 [s].

K. Watabe
S. Hirakawa
K. Nakagawa

Maximum RMSE reduction rate for flows
RMSE reduction rate of the worst flow
Median of RMSE reduction rate

Background
Assumptions

1Estimators

0.8

Reduction rate

ProposalExperiments
Conclusion

0.6
0.4
0.2
000.2

0.4
0.6
0.8
Probe packet intervals

1The values of maximum RMSE reduction rate for flows are high.
RMSE reduction rate of the worst flow and median of RMSE
reduction rate occasionally decrease to nearly 0.
aa21

Independency of RMSE in MEC
CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

We confirm the dependency of RMSE on parameters of MEC.

Background
Assumptions

1

Maximum RMSE reduction rate for flows
RMSE reduction rate of the worst flow
Median of RMSE reduction rate

Reduction rate

Proposal
Estimators
Experiments
Conclusion

0.8
0.6
0.4
0.2
0
0.00001

0.00010.001

Radius parameter

0.01

0.1

in MEC

It is confirmed that the RMSE is independent of the parameterfrom the figure.
aa22

Independency of RMSE in MEC (2)CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

We confirm the dependency of RMSE on parameters of MEC.
Maximum RMSE reduction rate for flows
RMSE reduction rate of the worst flow
Median of RMSE reduction rate

Background
Assumptions

1Reduction rate

Proposal
Estimators
Experiments
Conclusion

0.8
0.6
0.4
0.2
0051015

The expected number

2025of clusters in MEC

It is confirmed that the RMSE is independent of the parameterfrom the figure.
aa23

Dependency of RMSE on β
We verify the dependency of the performance of the proposed
method on parameter β.

CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

Maximum RMSE reduction rate for flows
RMSE reduction rate of the worst flowMedian of RMSE reduction rate

Background
Assumptions

1Reduction rate

Proposal
Estimators
Experiments
Conclusion

0.8
0.6
0.4
0.2
00.0010.01

0.1

110Parameter

The maximum RMSE reduction rate for flows increases asparameter β increases.

aThe other reduction rate decrease due to the inappropriate
conversions of samples when βis between 0.64 and 2.56.
a24

Conlusion
CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa

In this paper, we proposed a parallel flow monitoring methodthat achieves accurate measurement by partially converting
the observation results each other.

Background
Assumptions
Proposal
Estimators

The proposed method adds to samples of a flow from thesamples of the other flows.

Experiments
Conclusion

It also removes inappropriate samples using a clustering
technique in machine learning.
It provides up to 95% reduction of errors, and the error of theworst flow among all flows is reduced by 28%.

aa25

Future WorksCNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa
Background
Assumptions

We have the following 4 directions for future works.

Proposal

Automatic tuning of the parameters.

EstimatorsDevelopment of a method that utilizes a network topology for theconversion process.

Experiments
Conclusion

Extension toword measurements of other metrics.
Evaluation of the proposed method using real network traffic.

aa26

CNSM 2017
K. Watabe
S. Hirakawa
K. Nakagawa
Background
Assumptions
Proposal
Estimators

Thank you for your kind attention.

Experiments
Conclusionaa27