This is the post-print version of the following article: Masahiro Terauchi, Kohei Watabe, and Kenji Nakagawa, ``Model-Less Approach of Network Traffic for Accurate Packet Loss Simulations,'' in Proceedings of the 26th IEEE International
Conference on Network Protocols (ICNP 2018) Poster session, 2018. The original publication is available at https://doi.org/10.1109/ICNP.2018.00038 (DOI: 10.1109/ICNP.2018.00038). (c) 2018 IEEE. Personal use of this material is permitted.
Permission from IEEE 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 components of this work in other works.

Model-less Approach of Network Trafficfor Accurate Packet Loss Simulations
1st Masahiro Terauchi

2nd Kohei Watabe

3rd Kenji Nakagawa

Graduate School of Engineering
Nagaoka University of Technology
Nagaoka, Niigata, Japanm terauchi@kashiwa.nagaokaut.ac.jp

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, Japannakagawa@nagaokaut.ac.jp

I. I NTRODUCTION
When we evaluate Quality of Service (QoS) of networks
through simulations, accurately modeling traffic of real networks is important and also difficult task. Many traffic models
that reflect various characteristics have been proposed by priori
works (see [1] and the references therein). However, it isdifficult to select an appropriate traffic model and tune its
parameters for real network traffic (The double arrows inFig. 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 accurate
estimations of rare events, Importance Sampling (IS) in which
a simulation on a condition where the events occur more
frequently is performed and the result for the original condition
is obtained by the change-of-measure [2]. In the most ofresearches regarding IS in networks, the change-of-measureis analytically calculated based on the traffic model. They areinapplicable for real network traffic since the applicable trafficmodels, topology etc. are extremely limited, e.g. Poisson trafficmodel on a single router etc. (Dotted arrows in Fig. 1).
Though there are a few researches regarding IS in tracedriven simulations without traffic models [3], [4] (Triplearrows in Fig. 1), they cannot be applied for traffic composedof a single flow or correlated flows since they randomize
phases of traces. In addition, to the best of our knowledge,
This work was partly supported by JSPS KAKENHI Grant Number
JP17K00008 and JP18K18035.

Traffic in realnetworks

Trace-driven simulation
Only for non-correlated and large
Direct change-of-measure number of traces on a single router.
in Model-less approach

Difficulty in model selection
and parameter tuning.

Trace-driven ISIS simulation(not trace-driven)…

Poisson model

IS for Poisson

FBM model

Difficulty in analysis, andrestrictions on topology, etc.

Trace based model…

Abstract—It is important to accurately model network traffic
when we evaluate Quality of Service (QoS) of networks throughsimulations. However, for traffic in real networks, it is a toughtask to select an appropriate traffic model and tune its parameters. 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. In this paper, wepropose a model-less approach to accurately estimate a packet
loss rate through a simulation without directly modeling traffic
including real network traffic. We also show the effectiveness of
the approach in a simple queueing system as a first step in ourdevelopment.
Index Terms—Network, Simulation, Importance sampling,
Packet loss rate, QoS estimation

Fig. 1. The model-less approach and the conventional simulations.

no research on trace-driven IS has been published after theresearches [3], [4], 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, including real network traffic (Thebold arrow in Fig. 1). In the model-less approach, a simulation with Poisson traffic model is performed, irrespectiveof the characteristics of traffic on a network to be evaluated.
Naturally, despite the packet loss rate in the network to beevaluated does not correspond to the packet loss rate of thesimulation, the estimation result of the loss rate for arbitrary
traffic is obtained by a change-of-measure technique based on
the model-based IS with a frequency distribution of descritizedtraffic trace.
II. N OTATIONIn this paper, we express the packet loss rate l = {li }i∈N as
a probability function l = f (x(t), y(t)) of the input and output
traffic x(t) = {xi (t)}i∈N and y(t) = {yi (t)}i∈N , where idenotes flow ID. xi∑(t), yi (t) and di (t) are∑respectively defined
as pointprocesses
δ(t−T),
In{i,j}j=1
j=1 δ(t−TOut{i,j} )∑andδ(t−T),
whereT
Loss{i,j}
In{i,j} , TOut{i,j} andj=1
TLoss{i,j} ({i, j} ∈ N2 ) are the times when the jth packet in
the ith flow inputs, outputs, and losses, respectively. Note that
δ(t) is Dirac delta function. In addition, let xi,T and yi,T be thepaths {xi (t)}0≦t≦T and {yi (t)}0≦t≦T on [0, T ], respectively.
III. M ODEL BASED ISWhen IS estimates a loss rate on a single router into whicha single flow streams, the change-of-measure is performedOur goal is to accurately estimate a packet loss rate
through a simulation by the change-of-measure based on traffic
trace of x(t) and y(t) in a real network without assuming
any traffic model. To accomplish this goal, we rewritethe∫∞estimator of model-based IS as ˆlIS = (1/c̃1 ) 0 d1 (t) ·p(x1,t ∩ y1,t )/p̃(x1,t ∩ y1,t )dt using the notation shown inSection II, where A ∩ B is a event that paths A and B
occurs simultaneously. There is no way to strictly obtainp(x1,t ∩ y1,t )/p̃(x1,t ∩ y1,t ) except to analytically calculate
assuming a traffic model like model based IS.
In the model-less approach, in order to obtain the changeof-measure from traffic trace of xi (t) and∫ yi (t), we discretizen∆
xi (t) and yi (t) into ∆ as Xi (n) = (n−1)∆ xi (t)dt and∫ n∆
Yi (n) = (n−1)∆ yi (t)dt (n ∈ N). In addition, di (t) in a sim∫ n∆ulation is similarly discretized as D̃i (n) = (n−1)∆ di (t)dt.
Using these descritized traffic, we estimate the packet loss
rate byˆli = 1c̃i∞∑N =1D̃i (N )P (X N,k ∩ Y N,k ),P̃ (X N,k ∩ Y N,k )(1)

where P (A) and P̃ (A) denote the probabilities that event A
occurs in the traffic trace and the simulation, respectively.
X N,k = {Xi,N,k }i∈N and Y N,k = {Yi,N,k }i∈N are discritizedversion of x and y, respectively. Xi,N,k and Yi,N,k aredefined as {Xi (n)}N −k<n≦N and {Yi (n)}N −k<n≦N , respectively. k is a parameter and we assume that the effect of{Xi (n)}n≤N −k and {Yi (n)}n≤N −k on packet losses at time
N is negligible. When we assume a single router and a single
flow, in the limit as ∆ → 0 and k → N , our estimator
converges to that of model based IS.
Our approach can estimate a packet loss rate without therestrictions of the conventional IS. Because of the discretization, P (X N,k ∩ Y N,k ) directly obtained from arbitrary traffic
trace of x(t) without modeling the traffic. In our method,
we perform a simulation using the simple Poisson trafficmodel irrespective of the traffic trace. Therefore, it is easy
to analytically obtain P̃ (X N,k ∩ Y N,k ). By expressing theestimator by input and output traffic instead of a queue length
process, (1) is applicable for multiple flows on a network withcomplicated topology.
V. E XPERIMENTS
As a first step in the development, we investigate the casewhen the packet loss rate of an MMPP/M/1/K system isestimated from an M/M/1/K simulation. MMPP of the arrival

3.0 × 10−5
2.5 × 10−5
2.0 × 10−5
1.5 × 10−5
1.0 × 10−5
5.0 × 10−6
0.0
10−8
10−9
Var[ˆl1 ]IV. M ODEL - LESS A PPROACH

E[ˆl1 ]

based on probability density of a path ωTIn{1,j} of the queue
length process on [0, TIn{1,j} ] [2]. Assuming that probability
density of an event A in the original condition and themodified condition is p(A) and p̃(A), the estimator of IS isˆlIS = (1/c̃1 ) ∑c̃1 {1{j∈ϕ } ·p(ωT)/p̃(ωTIn{1,j} )}, where
1In{1,j}j=1c̃1 and ϕ1 denote the number of packets and the set of IDs oflost packets. The change-of-measure p(ωTIn{1,j} )/p̃(ωTIn{1,j} )is analytically derived from a traffic model in model-based IS.

Theoretical Value
Model-less Approach

Model-less Approach
Trace Driven

10−1010−1110−12 −51010−410−310−210−1
Packet Loss Rate of Simulation NetworkFig. 2. Comparison between the estimators of the model-less approach andthe trace-driven simulation.

process in the original system has 2-states with traffic intensity
100 [packet/s] and 339 [packet/s]. The transition rate of eachstate is 1 times per second. For both of the original systemand the simulation, the mean service time is 0.001 [s] and thequeue size is 10 [packet]. The simulation time is 2000 [s],∆ = 0.025 [s], and k = 2. In these systems, since thepacket arrivals and a service time are independent, it is assumed that P (Y1,N,k |X1,N,k )/P̃ (Y1,N,k |X1,N,k ) = 1. Therefore, the change-of-measure can be expressed as P (X1,N,k ∩Y1,N,k )/P̃ (X1,N,k ∩ Y1,N,k ) = P (X1,N,k )/P̃ (X1,N,k ).
By changing the loss rate in the simulation through thetraffic intensity, we performed the simulation 30 times foreach loss rate. Then the average of the estimator with 95%
confidence intervals and the variance of the estimator werecalculated. The result is compared with the trace-driven simulation in Fig. 2. According to the figure, we can find the regionin which the model-less approach can estimate the packet loss
rate of the original system. Additionally, we can confirm thatthe variances of the estimators are about 1/3 in the region,
compared with the estimator by the trace-driven simulation.
VI. C ONCLUSIONS AND F UTURE D IRECTIONS
We proposed the model-less approach to accurately estimatea packet loss rate through simulation with traffic trace without
traffic models. Though our approach is applicable to arbitrary
trace on arbitrary network with a complicated topology, weonly confirmed its effectiveness on a single router with asingle flow in this paper. We will verify the applicability ofour approach to the various trace on various networks in ourfuture works.
R EFERENCES[1] J. Zhang et al., “A Survey of Network Traffic Generation,” in Proc. ofCCT 2015.
[2] N. Kobayasahi et al., “On-line Estimation by Importance Sampling for
the Tail Probability of FIFO Queue Length,” in Proc. of RESIM 2014.
[3] I. C. Paschalidis et al., “Importance Sampling for the Estimation ofBuffer Overflow Probabilities via Trace-driven Simulations,” IEEE/ACM
Transactions on Networking, vol. 12, no. 5, 2004.
[4] P. E. Heegaard et al., “Application of Rare Event Techniques to Trace
Driven Simulation,” in Proc. of WSC 2005.