Timestep Stochastic Simulation of Computer Networks using Diffusion Approximation
Timestep Stochastic Simulation of Computer Networks using Diffusion Approximation
Loading...
Files
Publication or External Link
Date
2005-06-23
Authors
Kochut, Andrzej
Advisor
Shankar, A. Udaya
Citation
DRUM DOI
Abstract
Performance evaluation of modern computer networks is
challenging because of their large sizes, high speeds
of communication links, and complex state-dependent
control mechanisms. In particular, TCP congestion
control reacts in a nonlinear fashion to the state of
the network at the time scale of round-trip times,
making analysis intractable. Thus packet-level
simulation is the only widely used method of
performance evaluation.
Although it can be accurate, it is computationally expensive and thus
can be applied only to small networks and low link speeds.
Timestep Stochastic Simulation (TSS) is a novel method for generating
sample paths of computer networks, in increments of time steps rather
than packet transmissions. TSS has a low computation cost independent
of packet rates and provides adequate accuracy for evaluating general
state-dependent control mechanisms. TSS generates the evolution of
the system state S(t) on a sample path in time steps of size delta.
At each step, S(t + delta) is randomly chosen according to S(t) and
the probability distribution Pr[S(t+delta)|S(t)], obtained using the
diffusion approximation. Because packet transmission and reception
events are replaced by time steps, TSS generates sample paths at a
fraction of the cost of packet-level simulation. Because TSS generates
sample paths, it can accurately model state-dependent control mechanisms,
including TCP congestion control, adaptive dynamic routing, and so on.
We have a TSS implementation for general computer networks with
state-dependent control. We have applied this to numerous networks
with TCP and state-dependent UDP flows, and confirmed its accuracy
against packet-level simulation.