TranSim: Accelerating simulation of large-scale IP networks through preserving network invariants

Abstract

In this paper, we propose a fast simulation framework, TranSim, that expedites simulation by reducing the rate of generating packet-events. In the framework, we transform an IP network into an alternate network that generates a smaller number of packet-events, conduct simulation in the "transformed" network, and extrapolate simulation results for the original network from those obtained in the "transformed" network. We formally prove that, as long as the network invariant - the bandwidth-delay product - is preserved, the network dynamics, such as the queue dynamics and the packet dropping probability at each link, and TCP dynamics, such as the congestion window, RTTs, and rate dynamics, are also preserved in the course of network transformation. We implement TranSim in ns-2, and carry out a simulation study to evaluate it against packet-level simulation, with respect to the capability of capturing transient, packet-level network dynamics, the reduction in the execution time and memory usage, and the discrepancy in the network throughput. The simulation results indicate maximally two orders of magnitude improvement in the execution time, and the performance improvement becomes more prominent as the network size increases (in terms of the number of nodes, the number of flows. the complexity of topology, and link capacity) or as the degree of downsizing increases. The memory usage incurred in TranSim is comparable to that in packet-level simulation. The error discrepancy between TranSim and packet-level simulation, on the other hand, is between 1% and 10% in a wide variety of network topologies, inclusive of randomly generated topologies, traffic loads with different AQM strategies, different combination of operating systems and hardware systems. (C) 2008 Elsevier B.V. All rights reserved.