ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

Accurate Measurement Techniqueof Packet Loss Rate
in Parallel Flow Monitoring
Kohei Watabe,
Norinosuke Murai,
Shintaro Hirakawa,
Kenji Nakagawa
Graduate School of Engineering, Nagaoka University of Technology
July 31, 20191

Outline
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

Background
Assumptions and models
Parallel flow monitoring method for delay
The proposed loss monitoring methodExperiments
Conclusions and future works

2

Outline
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

Background
Assumptions and models
Parallel flow monitoring method for delay
The proposed loss monitoring method
Experiments
Conclusions and future works

3End-to-end Measurements
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments

End-to-end metrics are fundamental for a network evaluation.
An active measurement is a common method to measureend-to-end metrics.
Probe packets are injected into a network for a measurement.
It is important to achieve accurate measurement without increasing
the number of probe packets.
It is difficult to capture rare events (large delay or loss), and they arestill hard to measure.

Conclusions	

4

Parallel Monitoring of Probe FlowsICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

For most measurement applications, multiple paths aremonitored in parallel to measure end-to-end metrics.
e.g., SLA monitoring by Internet Service Providers.

Most of prior works utilize only one probe flow for ameasurement of one path in a parallel path monitoring.
The information concerning a flow can be utilized supplementary
for improving a measurement of another flow.
Flow A
Flow B

Link
Node1
4

3
2

5

Flow C
Flow D
5

Objectives
ICCCN 2019

We have proposed a parallel flow monitoring method for delay [5].
The method achieves accurate measurement by utilizing theobservation results of flows sharing the source/destination.

K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
BackgroundAssumptions
Previous Work
ProposalIn this paper, we propose a parallel flow monitoring method forpacket loss rate.

✓Contributions
1

We extend the delay measurement method to a lossmeasurement.

2

We improve its accuracy by utilizing information of all flows
including flows with different source and destination.

3

We evaluate the effectiveness of the proposed methodthough simulations.

Experiments
Conclusions✒[5] K. Watabe, S. Hirakawa, and K. Nakagawa, “Accurate Delay Measurement for Parallel
Monitoring of Probe Flows,” in Proceedings of 2017 13th International Conference on
Network and Service Management (CNSM 2017), Tokyo, Japan, 2017.

✏✑6

Outline
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

Background
Assumptions and models
Parallel flow monitoring method for delay
The proposed loss monitoring method
Experiments
Conclusions and future works

7

Network Model
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
BackgroundA network considered within the scope of this work isrepresented by a directed graph.
Physical/Virtual Link
RouterAssumptions

Model

Previous Work
ProposalInterface

ExperimentsConclusions

To measure packet delay and loss rate on paths, probe packets
are periodically injected for all or a part of paths.
A delay/loss sample can be obtained by a probe packet.
Though the metric we want to measure is loss rate in wired
packet networks, we utilize delay information to improve an
accuracy of loss rate measurement.
8

ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background

Delay

Sparsity Assumption of Congestion Periods

Delay samples

Propagation delay

Loss samples in a congestion period

Assumptions
Previous WorkA congestion periodProposal
Experiments
Conclusions

An end-to-end delay is consisted of propagation delay andqueueing delay.
Propagation delay can be regarded as a constant.

Most of loss events are caused by buffer overflows in interfaces
placed on links with congestions.
We assume that links with large queueing delay, i.e. links withmany packet loss events, are sparse among all links in anetwork.
9Outline
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

Background
Assumptions and models
Parallel flow monitoring method for delay
The proposed loss monitoring method
Experiments
Conclusions and future works

10Overlap of Virtual Delay Processes
Queueing delay processes within a congestion period that havecommon links frequently overlap.

ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa

χ̂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.

BackgroundPrevious Work
Proposal

Delay

Assumptions

Flow A

Flow A
Flow B

Experiments

TimeConclusions

A congestion periodcaused by Edge 2

A congestion periodcaused by Edge 31324Flow C

5Flow BIf χ̂A (t) and χ̂B (t) in a congestion period tightly overlap,
information of the period can be utilized each other.
To utilize this information, we should discriminate whether
processes overlap.
The determination should be based on samples.

11

Conversion Process
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions

We consider that virtual delay processes overlap if the two flows
satisfy the following conditions:
1The two flows have the same source/destination;

2The interval between the packet injection/receive times of the firstand last samples in a congestion period is smaller than δ;

Samples within the overlap period are converted each other.

Previous WorkConclusions

DelayExperiments

DelayProposal

Delay samples of Flow B(Other flow)

Convert losssamples
Delay samples of Flow A(Target flow)
Packet injection time

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

12Outline
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous WorkProposal
Experiments
Conclusions

Background
Assumptions and models
Parallel flow monitoring method for delay
The proposed loss monitoring method
Experiments
Conclusions and future works

13Extension for Loss Rate Measurements
We extend the method [5] to a loss rate measurement. xxx

ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa

Delay

LA, j : The set of loss samples in jth congestion period of Flow A.

Background

Delay samples of Flow B(Other flow)

Assumptions
Previous Work

Delay

Proposal
Experiments
Conclusions

Unite losssamples

Loss samples

inth congestion period of Flow A

Delay samples of Flow A(Target flow)
Packet injection time
Loss samples
in th congestion period of Flow A,
including united loss samples from Flow B

1

Loss samples LA, j are recorded for all congestion periods.

2

Delay samples are converted each other with method [5].

3Loss samples LA, j are united to LB,k = LA, j ∪ LB,k when delaysamples are converted.

14Extension for Loss Rate Measurements (2)ICCCN 2019

The samples by our method are not uniformly distributed.

K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa

To provide an unbiased estimator of loss rate on each path,samples should be weighted.

Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

The loss rate on the path of Flow A is estimated by the following
estimator with weight w s of a sample s,! !
js∈LA, j

ws,|XA | + |LA ||XA, j ∪ LA, j |where w s =|XA, j ∪ LA, j |for s ∈ LA, j

XA : The set of all delay samples of flow A.
LA : The set of all loss samples of flow A.
XA, j : The set of original delay samples in jth congestion period of Flow A.
XA, j : The set of delay samples in jth congestion period of Flow A, including
converted samples.

LA, j : The set of original loss samples in jth congestion period of Flow A.
LA, j : The set of loss samples in jth congestion period of Flow A, including
united samples.

15

Recursive Conversion
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background

The method in [5] only utilize information of flows that has thesame source/destination with a target probe flows.
By recursively converting samples obtained from each probe
flow, the proposed method utilizes information of all probe flows.

Assumptions
Previous Work

Flow A

1

Flow A
Flow B

41

Proposal
Experiments

Flow B

16Conclusions

Flow D

56

Flow C

5

4

Recursively
convert/unite
samples4235Flow C
Flow D

6

Trees that represent dependency of conversions are generated
for each congestion period.
The proposed method recursively converts/unites samples fromthe leaves to the root of the tree.
16Outline
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

Background
Assumptions and models
Parallel flow monitoring method for delay
The proposed loss monitoring method
Experiments
Conclusions and future works

17Simulation Settings
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
BackgroundWe perform NS-3 simulations to confirm that loss samples ofparallel flows are appropriately united between each other.
"#9.13

"$

13.03

8.18

6.89

"&10.00

"'

2.77

10.45
9.05

"+

Previous Work
Proposal

Conclusions

"%

13.42

Assumptions

Experiments

13.29

17.05

"*Internal link13.85")

6.99

Link capacity: 15.552 Mbps
Queue size: 1024 packets
Queueing policy: Drop-tail"(

External link

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

Probe

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

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 1.0 [s]Exponential distribution with mean 100.0 [s]
74 [Byte]
Periodic arrivals

18

Simulation Settings (2)ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

The parameters common to the privious method [5] are as
follows:
δ = 0.2 : Probe packet intervals.
xth = 0.01 : The threshold to define start/end time of congestion
periods.

r = 0.1 : The tuning parameter in clustering process.

The simulation time is 1005 [s] and we only use the data from5 [s] to 1005 [s].
The simulation is repeated 10 times by changing the phase of
the probe packet injection time.

19Average Loss Rate
The avarage of user loss rate and estimators are calculated.

ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa

The conventional estimator is simply calculated as the ratio of
the number of loss samples to the total number of samples.
0.0025Background
Assumptions

Proposal
Experiments
Conclusions

Loss rate

Previous Work

0.002
0.00150.001

User
Conventional
Proposed(No recursive conversion)
Proposed(Recursive conversion)0.0005
00-30-4

0-82-0Flow ID

3-0

4-08-0The maximum loss rate experienced by stationary user flows
was about 1.7 × 10−3 .
Relatively small loss rate was about 1.2 × 10−4 .

We can confirm that all methods can estimate loss rate withoutbias.

20

Root Mean Squared Errors (RMSE)ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa

We also evaluate Root Mean Squared Errors (RMSE) when theloss rate on end-to-end path are measured.
0.001

Background0.0008Previous Work
ProposalExperiments
Conclusions

RMSE

Assumptions

0.0006

Conventional
Proposed(No recursive conversion)
Proposed(Recursive conversion)

0.00040.000200-30-40-82-0
Flow ID

3-0

4-0

8-0

The proposed method without recursive conversion provides
31.3% reduction of RMSE on average.
The proposed method with recursive conversion achieves 57.5%
reduction.
21

Number of Loss Samples
ICCCN 2019

Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

The number of captured loss events extreamely increases.
The number ofcaptured loss events

K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa

1008060

Conventional
Proposed(No recursive conversion)
Proposed(Recursive conversion)

40
2000-30-4

0-82-0Flow ID

3-0

4-0

8-0

It is impossible for the conventional method to estimate the loss
rate less than 2.0 × 10−4 since the number of the probe packets
par flow is 5000 in the simulation.
However, the proposed method overcomes this fundamental
limitation in accuracy.
22

Outline
ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

BackgroundAssumptions and models
Parallel flow monitoring method for delay
The proposed loss monitoring method
Experiments
Conclusions and future works

23Conlusions and Future WorksICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
Proposal
Experiments
Conclusions

We proposed a loss measurement method that fully utilizes
flows, including flows with different source and destination inthis paper.
Through simulations on ns-3 simulator, we confirmed that theproposed method can reduce estimation errors by 57.5% onaverage.

✓Future Works

As future research, we plan to develop highly accuratedelay/loss tomography using the parallel monitoringtechnique.

✒We also have a plan to implement the proposed method fora real network, and evaluate the effectiveness of themethod.

✏✑24

ICCCN 2019
K. Watabe
N. Murai
S. Hirakawa
K. Nakagawa
Background
Assumptions
Previous Work
ProposalThank you for your kind attention.

Experiments
Conclusions

25