This is the post-print version of the following article: Kohei Watabe, Masahiro Terauchi, and Kenji Nakagawa, ``Model-less Approach for an Accurate Packet Loss Simulation,'' in Proceedings of 2020 IEEE International Conference on
Communications (ICC 2020), 2020. The original publication is available at https://doi.org/10.1109/ICC40277.2020.9149066 (DOI: 10.1109/ICC40277.2020.9149066). (c) 2020 IEEE. Personal use of this material is permitted. Permission fromIEEE 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 componentsof this work in other works.

Model-less Approach
for an Accurate Packet Loss Simulation
1st Kohei Watabe

2nd Masahiro Terauchi

3rd Kenji Nakagawa

Graduate School of Engineering,
Nagaoka University of Technology
Nagaoka, Niigata, Japank watabe@vos.nagaokaut.ac.jp

Graduate School of Engineering,
Nagaoka University of Technology
Nagaoka, Niigata, Japan

Graduate School of Engineering,
Nagaoka University of Technology
Nagaoka, Niigata, Japannakagawa@nagaokaut.ac.jp

I. I NTRODUCTION
Network simulation is a fundamental technique to evaluate
Quality of Service (QoS) on networks. Especially for largescale networks, a low-cost evaluation can be achieved by asimulation technique before Internet Service Providers (ISPs)
or other companies actually build their networks. Moreover,
QoS evaluation through network simulations provides helpful
information when we develop emerging applications/protocols
on networks.
When we evaluate QoS of networks through simulations,accurately modeling traffic of real networks is an importantbut difficult task. Many traffic models that reflect various
characteristics of the traffic measured in real networks havebeen proposed by prior works (see [2] and the references
therein). The most fundamental one is a Poisson traffic model.
It was reported that traffic of real networks has various
characteristics, including long-range dependency [3], selfsimilarity [4], periodicity [5], which are different from the
Poisson traffic model. Therefore, we need to choose the best
traffic model from many traffic models, according to a situationthat a simulation reproduces. However, due to the variety ofThis work was partly supported by JSPS KAKENHI Grant Number
JP17K00008 and JP18K18035. An earlier version of this paper was presented
at the 26th IEEE International Conference on Network Protocols (ICNP 2018)
Poster session [1].

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.

…

Abstract—In network evaluation through simulations, accurately modeling traffic of real networks is difficult. Even if
accurate traffic modeling is achieved, it is also difficult toaccurately estimate a rate of rare packet loss events. For accurate
estimations of rare events, Importance Sampling (IS) basedon the change-of-measure technique using traffic models has
been investigated. However, these studies are inapplicable fortraffic traces of real networks since the applicable traffic models
are extremely limited. In this paper, we propose a model-lessapproach to accurately estimate a packet loss rate througha simulation without directly modeling traffic. The change-ofmeasure is achieved based on traffic traces of networks in ourmodel-less approach. We evaluated the applicability of the modelless approach on a G/M/1/K system with a traffic trace of a real
network and confirmed that the model-less approach achieves up
to 145 times accurate than normal a trace-driven Monte Carlo(MC) simulation.
Index Terms—Network Simulation, Packet Loss Rate, Importance Sampling, Rare Event Simulation

Fig. 1. The conventional approach and the model-less approaches for an
accurate estimation with a traffic trace in a real network.

traffic models, it is difficult to select an appropriate trafficmodel and tune its parameters for the traffic of the real network(The double arrows in Fig. 1).
Even if the accurate traffic modeling is achieved, it is alsodifficult to accurately estimate QoS regarding rare events, suchas a packet loss rate in the modern Internet. For emerging
applications with strict performance needs, ITU-T Recommendation Y.1547 [6] defines a QoS class with an upper bound10−5 on a packet loss rate. Packet loss events are rare eventsin networks with such a QoS class, and it is a very difficult
task to estimate the packet loss rate through a simulation.
For accurate estimations of rare events, Importance Sampling (IS) in which a simulation of a network where theevents occur more frequently is performed has been used [7]–[9]. In the IS method for networks, the result of the original
network is obtained by change-of-measure from the resultof the network in the simulation. In most of the studies
regarding the IS method in networks, the change-of-measure isanalytically calculated based on a traffic model (model-based
IS). They are inapplicable for real network traffic since theapplicable traffic models, network topology, etc. are extremely
limited, e.g. Poisson traffic model on a single router, etc. (Thedotted arrows in Fig. 1).
Although there are a few works regarding IS in trace-driven
simulation without traffic models [10], [11] (The triple arrows
in Fig. 1), they require a per-flow packet-level traffic trace inwhich packet arrivals of each flow are recorded. In tracedriven IS, traffic traces of multiple flows that are measured
in a real network is used, and the phases of the flow traffic

traces are shifted in order to cause congestion. Because of its
structure, change-of-measure cannot be obtained analyticallyunless they are uncorrelated in a time-space. Unfortunately,per-flow packet-level traffic traces are hardly disclosed inpublic. Furthermore, since these traces in real networks aredefinitely correlated, trace-driven IS is not suitable for traffic
traces in real networks. In addition, to the best of our knowledge, no study on trace-driven IS has been published after thestudies [10], [11], and there is no prospect of expansion of
trace-driven IS to complicated topologies.
In this paper, we propose a model-less approach to accurately estimate a packet loss rate through a simulation without
directly modeling traffic (The bold arrow in Fig. 1). The
model-less approach provides change-of-measure with a traffic
trace of a network, including real networks. Though traffic ofa simulation actually performed in the model-less approach is
totally different from a traffic trace, an appropriate estimation
can be achieved. Despite the packet loss rate in the original
network to be evaluated naturally does not correspond to thatof the simulation, the estimation result of the loss rate fora traffic trace is obtained by a change-of-measure technique.
Though change-of-measure in the model-less approach isbased on model-based IS, it utilizes a frequency distributionof a discretized traffic trace instead of a traffic model. By
a direct change-of-measure with a traffic trace, we can avoid
the difficulty of model selection (The double arrows in Fig. 1),
the difficulty in analysis, and the restrictions on topology (Thedotted arrows in Fig. 1). The model-less approach has potential
applicability for queueing networks with complex topologies
though we evaluate the model-less approach for a G/M/1/K
as a first step in the development in this paper.
The main contributions of this paper are as follows.
We construct a theoretical framework to derive changeof-measure without direct modeling of network traffic.
Change-of-measure is achieved with a traffic trace ofa network, and there is no assumption regarding trafficcharacteristics.
• We design an algorithm to generate traffic of a simulation
actually performed. By the algorithm, the simulation
traffic in which rare events in a traffic trace frequently
occur is generated from a traffic trace, and an accurate
estimation of a packet loss rate is achieved.
• Through simulations including a traffic trace of a real
network, we confirm the effectiveness of the model-lessapproach on a G/M/1/K system.
•

The remainder of this paper is organized as follows. First,
we summarize related work in Section II, and detail modelbased IS in Section III. Next, we formulate the problem
we tackle in Section IV. Section V explains the model-lessapproach, and Section VI evaluate the proposed method with
Poisson traffic traces and a traffic trace in a real network.
Lastly, in Section VII, we conclude the paper and mention
future directions of the research.

II. R ELATED W ORK
IS has been developed by many researchers in the literatureof rare event simulation (see [12] and references therein).
In the research field of queueing theory, many researchers
have investigated how to achieve an accurate/fast estimationof statistics regarding rare events including buffer overflow
events [13]. IS in queueing networks with complex topologies
have also been tried, and Dupuis et al. investigated buffer
overflows probability in stable open Jackson networks [14].
Mahdipour et al. evaluated the performance of IS in Jackson
networks [8]. Some researchers have tackled optimization
problems of estimation accuracy. Kim et al. proposed a nonparametric adaptive IS using a kernel function estimation
method to explore the optimal condition of a simulation [15].
de Boer et al. also proposed an optimization method basedon cross-entropy, and they confirmed the effectiveness of themethod in Jackson networks [16].
There are a few works that are applicable for traffic traces ofreal networks while many works regarding IS techniques havebeen applied for markovian queueing networks. Paschalidis etal. proposed a trace-driven IS method in which phase ofmultiple traffic traces are synchronized to lead congestion
in a system [10]. By using change-of-measure, the result ina system with synchronized traffic traces are converted toa result in a system where the phase of traffic traces are
randomized. Reference [11] also proposed a simulation technique with a similar idea. However, these studies structurally
inapplicable for systems with correlated flows, and traffic
traces of parallel flows are generally correlated. Additionally,
traffic traces are not always measured as per-flow packet-leveltraces. In the literature of general IS that does not focus
on queueing systems, an IS technique for a system in whichpart of the system is not directly known was proposed [17].
Regrettably, to the best of our knowledge, the studies that
apply the technique to the queueing systems is not reported.
III. M ODEL - BASED IS
In model-based IS, a simulation of a network where thetarget events occur more frequently than the original network
is performed, and the result of the simulation is converted to
the result of the original network. When we estimate a packet
loss rate of a network by model-based IS, we intentionally
increase the traffic intensity of the queueing model that expresses the network in order to cause loss events frequently.
The loss rate of the original network can be obtained by thechange-of-measure technique.
When we estimate the loss rate on a single router with asingle queue, the estimator of model-based IS for the packet
loss rate can be given by}c̃ {∑p(ω̃j )
ˆlIS = 1,(1)
1{j∈ϕ}c̃ j=1p̃(ω̃j )where c̃ and ϕ represent the number of packets in a simulation
and a set {1, 2, . . . , c̃} of packet IDs, respectively. ω̃j denotesa path of a queue length process of the router until arrivalA stochastic functionthat represents a network
A sample pathof an input traffic process

A sample pathof an output traffic process
A sample pathof a packet loss process

Fig. 2. A formulation in the model-less approach.

time sj of jth packet in a simulation. Namely, ω̃j is a sample
path of a queue length process in the period [0, sj ]. p(A)and p̃(A) represent the probability density of an event A in
the original network and the simulation network, respectively.
The part p(ω˜j )/p̃(ω˜j ) of Eq. (1), the ratio of the probability
density of a queue length process in the original network tothat of the simulation network, provides change-of-measure. If
a simulation network corresponds to an original network, i.e.
the condition is not changed, the estimator shown in Eq. (1)is equal to the estimator of a simple Monte-Carlo simulation
since p̃(A) = p(A).
In model-based IS, it is needed that the change-of-measurep(ω˜j )/p̃(ω˜j ) is analytically derived from the traffic model ofthe network. Therefore, the traffic model should be known andprobability density should be analytically solved by using it.
However, as we mentioned above, it is difficult to select/tuning
traffic models according to a traffic trace of a real network, andsimple traffic models that can be analytically treated cannot
represent characteristics of the traffic of the real network.
Consequently, we cannot accurately estimate the packet loss
rate for a network in which packet loss events are rare events,
with model-based IS.
IV. P ROBLEM F ORMULATION
We treat a network as a stochastic function of input/output
traffic in the formulation. Our formulation has high generality
and applicability for traffic in real networks since we do notassume any restriction of input/output traffic characteristics. In
this section, we describe a formulation of a packet loss rateestimation through a simulation (see Fig. 2).
In this paper, we express input and output traffic processesof a network by point processes x(t) and y(t), respectively.
x(t) and∑y(t) are defined as the ∑sum of Dirac delta functions,x(t) = j δ(t−sj ) and y(t) = j δ(t−uj ), where sj and uj
denote arrival and departure time of jth packet, respectively.
Let xt and yt be sample paths of x(t) and y(t) on a period[0, T ], respectively. Additionally,
we also define a packet loss∑
process d(t) as d(t) = j δ(t − vj ), where vj denotes thetime when jth packet losses. Let dt be a sample path of d(t)on a period [0, T ].
Packet loss events stochastically occur depending on asample path xt of an input traffic process. A sample pathyt of an output traffic process and a sample path dt of apacket loss process of a network can be represented by astochastic function f (·) as (yt , dt ) = f (xt ). f (·) is a functionthat expresses the behavior of the network. We assume thatthe value at time t on the sample path dt mainly depends on

the last τ period [t − τ, t) of traffic process, and the value
at time t on dt is approximately independent on xt in the
period [0, t − τ ) for sufficiently large τ . Needless to say, theoutput traffic process y(t) and the packet loss process d(t)are stochastic processes, and there are two sources of therandomness of the two processes: stochastic functions f (·) andan input traffic process x(t). A packet loss rate l is defined by∫Tdt dtl = ∫0T.
xt dt
0We assume that the packet loss rate l is extremely low, and
it is highly dependent on a sample path xt of an input traffic
process. Since the main cause of packet loss events that weassume is a buffer overflow, the dependency of a packet loss
rate on a traffic process is obvious.
The problem we tackle in this paper is a simulation-based
estimation of an average packet loss rate E[ l ] from a measurement of traffic trace xt and a simulation of behavior f (·)
of a network. We assume that behavior f (·) of a network canbe accurately simulated by a simulation. Many packet-level
simulators including ns-3 simulator [18] have been proposedin the literature on network simulations, and these outstanding
simulators achieve accurate reproduction of network behavior.
This assumption means that the following two equations hold:p(yt |xt ) = p̃(yt |xt ),p(dt |xt ) = p̃(dt |xt ),(2)

where p(A|B) and p̃(A|B) denote conditional probability
density that an event A occurs under the condition that an event
B occurs in an original network and a simulation network,
respectively.
Since it is relatively hard to simulate traffic by a trafficmodel, as we mentioned above, we try to utilize a traffic
trace of a real network in a simulation. Of course, it iseasy to perform a trace-driven Monte Carlo (MC) simulation
by directly input the traffic trace into a network simulator,i.e., we can obtain dt by simulating f (xt ). In this paper,
however, we tackle to develop a method in which simulation
traffic x̃t different from a traffic trace xt is simulated as(ỹt , d˜t ) = f (x̃t ), thereby accurately estimating the packet loss
rate. An output traffic process ỹt and a packet loss process d˜tare obtained by the simulation. Though d˜t in the simulationdiffers from dt , the packet loss rate l is appropriately derived
by a change-of-measure technique.
V. M ODEL - LESS A PPROACH
Our goal is to accurately estimate a packet loss rate by
an appropriate change-of-measure through a network simulation. Aiming to achieve the goal, we propose the model-lessapproach whose steps is shown in Fig. 3. In the model-lessapproach, the change-of-measure is achieved based on a traffic
trace xt that is measured in a limited measurement period[0, T ] on a real network. Though traffic in a simulation iscompletely different from a traffic trace xt in a real network,
the packet loss rate should be estimated without bias by theTarget network
Traffic trace
Packet loss process
Inaccurate
due to rare events

Discretized traffic
trace

Packet loss rate
Traffic Generation

Accurate estimation

Discretized traffic
for a simulation

Change-of-measure

where x̃s,τ
denotes a part of the sample path x̃t in the last τtperiod [s − τ, s).
In the model-less approach, in order to achieve empiricalderivation of change-of-measure based on a traffic trace, we
replace x̃t and d˜t by sample paths X̃i and D̃i of discretizedprocesses, respectively. x̃t and d˜t are divided into discrete slots
with interval ∆.
∫ n∆
∫ n∆
d˜t dt.
x̃t dt, D̃i =X̃i =(n−1)∆

Traffic
for a simulation

Packet loss process
in a simulation
Simulation network

Fig. 3. Steps for an accurate estimation in the model-less approach.

change-of-measure. In this section, we will explain a changeof-measure technique that achieves an unbiased and accurate
estimation, and how to generate traffic x̃t in a simulation.
A. Change-of-measure Technique
The model-less approach avoids analytical derivation ofchange-of-measure, and enable an empirical derivation ofchange-of-measure from a traffic trace. In order to achieve
empirical derivation of change-of-measure, we discretize atraffic process and decompose it into patterns. Occurrence
frequency of each traffic pattern is counted, and change-ofmeasure is calculated from a frequency distribution of traffic
patterns.
We design the proposed method to have high versatility byeliminating restrictions (e.g., characteristics of a traffic trace,
network topology, and so on) while acting as an extension of
the conventional model-based IS. Using notations we definedin Section IV, we can rewrite the estimator shown in Eq. (1)of model-based IS as
}
∫
c̃ {
1∑
p(ω̃j )
1 T ˜ p(x̃st ∧ ỹts )1{j∈ϕ}=dsdsc̃ j=1p̃(ω̃j )c̃ 0p̃(x̃st ∧ ỹts )∫1 T ˜ p(x̃st )p(ỹts |x̃st )
=
ds
ds
c̃ 0
p̃(x̃st )p̃(ỹts |x̃st )∫1 T ˜ p(x̃st )
=
ds
ds,
(3)
c̃ 0
p̃(x̃st )where x̃st and ỹts denote sample paths of input and output
traffic processes until time s in a simulation, respectively.
Note that the operator ∧ denotes logical conjunction. The
last equality follows from Eq. (2). The change-of-measure isachieved by the part p(x̃st )/p̃(x̃st ) of Eq. (3). However, when
we derive p(x̃st )/p̃(x̃st ), it is required to analytically calculatep(x̃st )/p̃(x̃st ) assuming traffic model since probability densityp(x̃st ) and p̃(x̃st ) of an event x̃st are defined on a space Rc̃ .
According to the assumption of independence of dt on xt
in [0, t − τ ), we can rewrite Eq. (3) as∫
1 T ˜ p(x̃s,τ
t )
ds
ds,
(4)
c̃ 0
p̃(x̃s,τ
t )(n−1)∆

xt is also discretized as Xi . Similarly, we define X̃in,k ={X̃i }n−k<i≤n as a discretized version of x̃s,τ
t . By definings,τ
X̃in,k as a discretized process, p(x̃s,τt ) and p̃(x̃t ) are also
replaced by P (X̃in,k ) and P̃ (X̃in,k ), respectively. P (A) andP̃ (A) denote probability that an event A occurs in an original
network and a simulation network, respectively. Consequently,
the estimator is rewritten as
1∑
P (X̃in,k )D̃i.
c̃ n=1P̃ (X̃in,k )
T /∆

(5)

The part P (X̃in,k )/P̃ (X̃in,k ) in Eq. (5) corresponds thechange-of-measure, and the probability P (X̃in,k ) and P̃ (X̃in,k )of an event X̃in,k are defined on a space Nk . It is important tolimit a period of the sample path used in change-of-measurein Eq. (4). The limitation enable us to calculate the probability
P (X̃in,k ) and P̃ (X̃in,k ) by counting frequency of a traffic
pattern X̃in,k in Xi and X̃i .
B. Traffic Generation in Simulations
In the model-less approach, traffic patterns that are observedin a traffic trace of an original network are listed, and input
traffic x̃t is generated for a simulation so that the frequency ofall patterns are the same. Traffic patterns referred to here are
Xin,k that is k consecutive slots in a discretized traffic trace
Xi . We define Ω as the set of all traffic patterns appearingin Xi without duplicates. By making the frequency of all
patterns are the same, the frequency of the patterns that cause
loss events increases since we assume that the loss events are
rare. It is not a good policy to break the uniformity of thefrequency of the patterns. If we raise the frequency of specificpatterns, the frequency of the other patterns has to be decreased
thereby being difficult to calculate the probability P (X̃in,k )and P̃ (X̃in,k ) from the low frequency of patterns.
The algorithm to generate input traffic x̃t with the uniform
frequency of all patterns is shown in Algorithm 1. The input
parameters of the algorithm are the following four parameters:
discretized traffic trace Xi , slot interval ∆, the number k ofa consecutive slot in a traffic pattern, and a simulation period
Tsim . The output of the algorithm is discretized traffic X̃i fora simulation. Parameters are initialized on Line 1–3, and thenumber Nsim of slots in discretized traffic X̃i is calculated
in Line 4. Note that ⌈·⌉ denotes a ceiling function. The loop
on Line 5–10 actually generates X̃i . On Line 6, among thetraffic patterns that can be joined to current X̃i , a traffic
pattern having the lowest frequency in simulation traffic X̃iIκ (X̃i ,χ)=1

7:
8:
9:
10:
11:

if χ′ = ∅ then κ ← κ − 1else[χ′ [κ + 1], . . . , χ′ [k]] is joined to X̃ih(χ′ ) ← h(χ′ ) + 1
κ←k−1

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.6

Fig. 4. The sample average of the estimator of the packet loss rate in an
M/M/1/K queueing system.
1.E-09The varianceof the estimators

Algorithm 1 Traffic generation algorithm for simulations
Require: Xi , ∆, k, Tsim
Ensure: X̃i
1: X̃i ← [0], κ ← k − 1
2: for all χ ∈ Ω do
3:h(χ) ← 0
4: Nsim ← ⌈Tsim /∆⌉5: while length of X̃i < Nsim do6:
χ′ ← Randomly sample from arg min h(χ)

Model-less (k=2)
Model-less (k=4)

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

1.E-101.E-11

1.E-12is randomly chosen. h(χ) denotes frequency of a pattern χ inX̃i . Iκ (X̃i , χ) is an indicator function which equals 1 when
the last κ slots of X̃i correspond to the first κ slots of χ and0 otherwise. If there is no χ satisfying the condition of theargument of the minimum, κ is reduced thereby relaxing thecondition that the last κ slots of X̃i correspond to the first κslots of χ (Line 7). When χ′ is not empty, the selected pattern
χ′ is joined to X̃i with an overlap of κ slots (Line 9). Afterthe joining, frequency h(χ) of traffic patterns in X̃i is updated
on Line 10, and κ is initialized on Line 11.
Lastly, the discretized traffic X̃i that is obtained by Algorithm 1 is converted to x̃(t). The value of each time slot of thediscretized traffic X̃i represents the number of arrival packets
in the time slot. Hence, we generate simulation traffic x̃(t) byassuming the arrival time of packets sj is uniformly distributed
in a time slot.
VI. E VALUATIONSIn this paper, in order to evaluate the effectiveness of themodel-less approach, a packet loss rate is estimated in a simple
queueing model by the model-less approach and trace-driven
MC simulations. In the evaluations, we prepared the following
two traffic traces as input traffic: Poisson traffic trace and a
traffic trace of a real network in Widely Integrated Distributed
Environment (WIDE) project [19]. These input traffic are used
as an arrival process of G/M/1/K (i.e., M/M/1/K for Poissontraffic trace). We compare the model-less approach and tracedriven MC simulations in which the traffic trace is directly
input into a G/M/1/K queueing system. Note that the tracedriven MC simulation in the evaluation is not a trace-driven
IS simulation we introduced in the introduction.
A. Poisson Traffic Trace
Firstly, we evaluate the most fundamental case where input
traffic follows the Poisson traffic model. However, the modelless approach does not use the knowledge that the input traffic
follows the Poisson traffic model. By evaluating an M/M/1/K
queueing system where the true value of the packet loss rate

0.0

0.1
0.2
0.3
0.4
0.5
The length of traffic patterns

0.6

Fig. 5. The variance of the estimator of the packet loss rate in an M/M/1/K
queueing system.

is known, we can confirm whether the estimator of the modelless approach has a bias or not.
The parameters of an M/M/1/K queueing system was tuned
so that a true value of the packet loss rate is 10−5 . 10−5 isalso a criterion defined in the most severe QoS class in ITU-T
Recommendation Y.1547 [6]. The arrival rate and the service
rate are set to λ = 329.1 [packet/s] and µ = 1000 [packet/s],
respectively. The queue length K is set to 10 [packet]. We perform simulations 30 times, and the period for each simulationis 2000 [s].
The results of the sample average of the estimators of thepacket loss rate are shown in Fig. 4. The horizontal and thevertical axis represent the length of a traffic pattern k∆ andsample average E[ ˆl ] of the estimators. The black line at 1.0 ×
10−5 represents the true value of the packet loss rate in the
M/M/1/K queueing system. According to the figure, we canconfirm that the model-less approach estimates the packet loss
rate without bias when k∆ ≥ 5 × 10−2 .
Figure 5 shows the variance of the estimators of the modelless approach and the trace-driven MC simulation. The horizontal and the vertical axis represent the length k∆ of a traffic
pattern and variance Var[ ˆl ] of the estimators. The black line
at 4.0 × 10−11 represents not true value but the variance ofthe estimators of the trace-driven MC simulation. According
to the figure, most of the results of the model-less approach
is lower than that of the trace-driven MC simulation when thelength of a traffic pattern k∆ ≥ 5 × 10−2 [s]. Especially, thevariance of the estimators of the model-less approach is about
1/12 of that of the trace-driven MC simulation when k = 4
and k∆ = 5×10−2 [s]. Since the estimators of the model-lessapproach are unbiased for k∆ ≥ 5 × 10−2 [s] in Fig. 4, we
can confirm that the model-less approach provides an accurate
estimator of the packet loss rate.

The sample averageof the estimators

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

0.002
0.00150.001
0.00050
1.0E-05

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

2.5E-05

Fig. 6. The sample average of the estimator of the packet loss rate in a
G/M/1/K queueing system with the traffic trace of the real network.
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

Fig. 7. The variance of the estimator of the packet loss rate in a G/M/1/K
queueing system with the traffic trace of the real network.

B. Traffic Trace of a Real Network
In order to verify the applicability of the model-less approach to traffic traces of real networks, we evaluate themodel-less approach with a traffic trace opened by MAWI
(Measurement and Analysis on the WIDE Internet) Working
Group in WIDE project [19]. The traffic trace we used wasmeasured at samplepoint-F on September 8, 2018, and we
extracted the arrival time of packets from the traffic trace. It
is difficult to analytically derive the true value of the packet
loss rate of a G/M/1/K queueing system with the traffic traceof the real network. For that reason, we tune the service rate of
the G/M/1/K queueing system so that the packet loss rate of
the trace-driven MC simulation is approximately 10−4 , thereby
setting µ = 106 [packet/s] as a service rate. The queue length
K is set to 10 [packet]. We perform simulations 10 times, anda period for each simulation is 100 [s].
The estimation results of the model-less approach and thetrace-driven MC simulation are shown in Figs. 6 and 7.
According to the figures, we can confirm that an unbiased andaccurate estimation is achieved if k and k∆ are sufficiently
large. In particular, the variance of the estimator of themodel-less approach is 1/145 of that of the trace-driven MC
simulation when k = 8 and k∆ = 2.0 × 10−5 [s].
VII. C ONCLUSIONS AND F UTURE W ORKS
In this paper, we proposed the model-less approach toaccurately estimate a packet loss rate through a simulation
without directly modeling traffic. The model-less approachprovides a change-of-measure technique based on model-based
IS with a frequency distribution of discretized traffic patterns.
We evaluated the model-less approach in G/M/1/K with aPoisson traffic trace and the traffic trace in the real network,and confirmed that the model-less approach can achieve an

unbiased and accurate estimation. In the most effective casesin the evaluation, the accuracy of the model-less approach is
145 times accurate than that of the normal trace-driven MC
simulation.
In future works, we will tackle the optimization problem of
the parameters of the model-less approach. The length of thepatterns and the interval of discrete slots should be specified
depending on characteristics of original networks and lengthof traffic traces.
R EFERENCES[1] M. Terauchi, K. Watabe, and K. Nakagawa, “Model-Less Approach of
Network Traffic for Accurate Packet Loss Simulations,” in Proceedingsof the 26th IEEE International Conference on Network Protocols (ICNP
2018) Poster session, Cambridge, UK, 2018, pp. 251–252.
[2] J. Zhang, J. Tang, X. Zhang, W. Ouyang, and D. Wang, “A Survey of
Network Traffic Generation,” in Proceedings of the 3rd International
Conference on Cyberspace Technology (CCT 2015), Beijing, China,
2015.
[3] T. Karagiannis, M. Molle, and M. Faloutsos, “Long-Range Dependence:
Ten Years of Internet Traffic Modeling,” IEEE Internet Computing,vol. 8, no. 5, pp. 57–64, 2004.
[4] K. Park and W. Willinger, Self-Similar Network Traffic and Performance
Evaluation. John Wiley & Sons, 2000.
[5] S. Floyd and V. Jacobson, “The Synchronization of Periodic Routing
Messages,” IEEE/ACM Transactions on Networking, vol. 2, no. 2, pp.
122–136, 2002.
[6] “Network Performance Objectives for IP-based Services,” ITU-T Recommendation Y.1541, 2011.
[7] J. Blanchet and H. Lam, “State-dependent Importance Samplingfor Rare-event Simulation: An Overview and Recent Advances,”
Surveys in Operations Research and Management Science,
vol. 17, no. 1, pp. 38–59, 2012. [Online]. Available:
http://dx.doi.org/10.1016/j.sorms.2011.09.002[8] E. B. Mahdipour, A. M. Rahmani, and S. Setayeshi, “Performance
Evaluation of an Importance Sampling Technique in a Jackson Network,”
International Journal of Systems Science, vol. 45, no. 3, pp. 373–383,
2014.
[9] I. Lokshina, “Study on Estimating Probabilities of Buffer Overflow
in High-speed Communication Networks,” Telecommunication Systems,
vol. 62, no. 2, pp. 289–302, 2016.
[10] I. C. Paschalidis and S. Vassilaras, “Importance Sampling for the Estimation of Buffer Overflow Probabilities via Trace-driven Simulations,”
IEEE/ACM Transactions on Networking, vol. 12, no. 5, pp. 907–919,
2004.
[11] P. E. Heegaard, B. E. Helvik, and R. O. Andreassen, “Application ofRare Event Techniques to Trace Driven Simulation,” in Proceedingsof the Winter Simulation Conference (WSC 2005), Orlando, FL, USA,2005, pp. 509–518.
[12] J. Morio, M. Balesdent, D. Jacquemart, and C. Vergé, “A Survey of Rare
Event Simulation Methods for Static Input-output Models,” Simulation
Modelling Practice and Theory, vol. 49, pp. 287–304, 2014.
[13] D. Miretskiy, Queueing Networks: Rare Events and Fast Simulations,2009. [Online]. Available: http://doc.utwente.nl/68376/[14] P. Dupuis and H. Wang, “Importance Sampling for Jackson Networks,”
Queueing Systems, vol. 62, no. 1-2, pp. 113–157, 2009.
[15] Y. B. Kim, D. S. Roh, and M. Y. Lee, “Nonparametric Adaptive
Importance Sampling for Rare Event Simulation,” in Proceedings ofthe 32nd Conference on Winter Simulation (WSC 2000), Orlando, FL,
USA, 2000, pp. 767–772.
[16] P. T. de Boer, D. P. Kroese, and R. Y. Rubinstein, “A Fast Cross-Entropy
Method for Estimating Buffer Overflows in Queueing Networks,” Management Science, vol. 50, no. 7, pp. 883–895, 2004.
[17] H. Lam, “Efficient importance Sampling Under Partial Information,”in Proceedings of the 2012 Winter Simulation Conference, Berlin,
Germany, 2012, pp. 454–465.
[18] 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, 2008, p. 527.
[19] “WIDE
MAWI
WorkingGroup.”[Online].
Available:
http://mawi.wide.ad.jp/