Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Model-less Approach
for an Accurate Packet Loss
Simulation
Kohei Watabe
Masahiro Terauchi
Kenji Nakagawa
Graduate School ofNagaoka University of Technology
1Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Introduction• Accurate network simulation is a fundamental technique to evaluate
Quality of Service (QoS).
• Importance Sampling (IS) has been used for accurate estimations ofrare events.
• In IS simulation, a simulation of a network where the events occurmore frequently is performed.
• Conventional IS simulation require the traffic model of the targetnetwork.

• IS simulations are inapplicable for real network traffic due todifficulty of traffic modelling.
• Objectives• We propose a model-less approach to accurately estimate a packet
loss rate of real traffic through a simulation without directly modelingtraffic.
2

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Model-based IS• A simulation of a network where packet loss occur more frequently
than the original network is performed.
• The result of the simulation is converted to the result of the original
network.
Original network

Traffic

Normal estimator

Inaccurate due torare loss events
Tuned traffic

Packet arrivals

andandSimulation network

IS estimator for original network

Packet loss

Conversion by change-of-measurewith traffic model: A set of ID of loss packets: The number of arrival packets in original/simulation networks: Probability density of queue length process
before packet arrival in original/simulation networks.

3

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

IS Simulations for Real Networks• In conventional approach, real traffic is modeled and IS
simulation with its model are performed.
• There are a few works regarding IS in trace-driven simulation
without traffic models.
• These approaches have the following problems, and ourapproach overcome them.
Trace-driven simulation
Difficulty to obtain a per-flow packet-level trace.
It is not applicable to correlated flows.

Traffic trace inreal networks

Difficulty in model selection
and parameter tuning.

Direct change-of-measure
in model-less approach
Trace-driven IS
Accurate rare event simulation…

Poisson model
FBM model
Trace based model

IS for Poisson
Difficulty in analysis, andrestrictions on topology, etc.

…

4Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Model-less Approach• Overview of the proposed method is as follows.
Original network
Real traffic
trace

Packet loss
process
Inaccurate

Discretizedtraffic trace

Packet loss rate
Traffic Generation
Discretized traffic
for a simulation
Traffic
for a simulation

Accurate
Change-of-measure
Packet loss
process
in a simulation
Simulation network

5Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Change-of-measure Technique• The model-less approach enable an empirical derivation of changeof-measure from a traffic trace.
• Change-of-measure is calculated from a frequency distribution oftraffic patterns.
secCount patterns

slots

The numberof packets…
Pattern A

Original network

Pattern A
Pattern B

1
1

Pattern B…

Estimator

Packet loss
Simulation network
Pattern A
Pattern B

32

…

6

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Traffic Generation in Simulations• Traffic patterns that are observed in a traffic trace of an original
network are listed, and input traffic is generated for a simulation sothat the frequency of all patterns are the same.

Patterns intraffic trace

Currentstatus

Pattern A

1

Pattern B

0

Pattern C

1

Pattern D

1

Pattern D
What is thenext value?
Pattern A

Pattern B
1

Pattern C
7

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Evaluations• In order to evaluate the effectiveness of the model-less approach, apacket loss rate is estimated in a simple queueing model by themodel-less approach and trace-driven MC simulations.
• Traffic traces• Poisson traffic trace• A traffic trace of a real network (WIDE project)• Evaluated network system• G/M/1/K

Poissonor real traffic
G/M/1/K

Estimateloss rate• Parameters• Arrival rate: 329.1 [packet/s]• Service rate:• 1000 [packet/s] (Poisson)• 10000 [packet/s] (Real trace)• The queue length K: 10 [packet]• Simulation time:• 1000 [s] (Poisson)• 100 [s] (Real trace)• Iteration:• 30 times (Poisson)• 10 times (Real trace)

8

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Poisson Traffic Trace - Bias
• The average of the estimators of the packet loss rate are calculated.
• We can confirm that the model-less approach estimates the packet
loss rate without bias when.

The sample averageof the estimators

0.00005

Model-less (k=2)
Model-less (k=3)
Model-less (k=4)
True value

0.00004
0.000030.000020.00001
0
0.0

0.1
0.2
0.3
0.4
0.5
The length of traffic patterns

0.69Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Poisson Traffic Trace - Variance• The variance of the estimators of the model-less approach and thetrace-driven MC simulation is calculated.
• Most of the results of the model-less approach is lower than that of
the trace-driven MC simulation when.
• The lowest variance of the model-less approach is about 1/12.

The varianceof the estimators

1.E-09Model-less (k=2)
Model-less (k=4)

Model-less (k=3)
Trace-driven MC

1.E-101.E-11

1.E-12
0.0

0.1
0.2
0.3
0.4
0.5
The length of traffic patterns

0.610

NagaokaNagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Traffic Trace of a Real Network - Bias• The average of the estimators of the packet loss rate are calculated.
• We can confirm that an unbiased estimation is achieved if
are sufficiently large.
The sample averageof the estimators

0.00250.002
0.00150.001

andModel-less (k=2)
Model-less (k=3)
Model-less (k=4)
Model-less (k=5)
Trace-driven MC

0.000501.0E-05

1.5E-05
2.0E-05
The length of traffic patterns

2.5E-05
11NagaokaNagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Traffic Trace of a Real Network - Variance• The variance of the estimators of the model-less approach and thetrace-driven MC simulation is calculated.
• We can confirm that an accurate estimation is achieved for unbiased
estimator.
• The lowest variance of the model-less approach is about 1/145.

The varianceof the estimators

1.E-06
1.E-08Model-less (k=2)
Model-less (k=4)
Trace-driven MC

Model-less (k=3)
Model-less (k=5)

1.E-101.E-12
1.E-14
1.0E-05

1.5E-05
2.0E-05
The length of traffic patterns

2.5E-05
12Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

Conclusions and Future Works• Conclusion• In this paper, we proposed the model-less approach to accurately
estimate a packet loss rate through a simulation without directlymodeling traffic.
• The model-less approach provides a change-of-measure techniquebased on model-based IS with a frequency distribution of discretizedtraffic patterns.
• In the most effective cases in the evaluation, the accuracy of themodel-less approach is 145 times accurate than that of the normal
trace-driven MC simulation.

• Future works• The optimization problem of the parameters.
• Evaluations in complex topology.

13

Nagaoka
NagaokaUniv.
Univ.ofofTech.
Tech.- -ComNets
ComNetsLab.
Lab.

• Thank you for your kind attention.

14