Timestep Stochastic Simulation of Computer Networks using Diffusion Approximation

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.