Snapshot Simulation of Internet Traffic: Fast and Accurate for Heavy-tailed Flows

Simulations involving processes at very different time scales can be so slow to converge that starting in one state and waiting for a representative sample of the state space to be explored is not feasible. Under these circumstances we need to find a different way to explore a representative range of states in order to obtain valid results in a reasonable time. Internet traffic is an example of this situation. This is due to the fact that it is made up of clearly identifiable flows and a significant proportion of overall bytes occur in long-lived flows, whose overall duration will in many cases be longer than can be simulated. In this paper we develop a method which constructs a “randomly selected state” of Internet traffic from scratch – snapshot simulation. The technique is applied to a realistic model of Internet traffic and is used to confirm theoretical results for the number of active flows in a router which adopts either Fair Queueing or Shortest Job First as its queueing discipline. Snapshot simulations are also compared to conventional simulations of the same systems and it is shown that although convergence to the same results appears to be occurring, satisfactory accuracy cannot be obtained in a reasonable time by the conventional simulations. Simulation of a practical high-performance queue discipline, SJF-n, in which only the largest n flows at any time are de-prioritized, is also simulated and shown to give good performance for quite low n.