Timestepped Stochastic Simulation of 802.11 WLANs

Abstract

Performance evaluation of computer networks is primarily done using packet-level simulation because analytical methods typically cannot adequately capture the combination of state-dependent control mechanisms (such as TCP congestion control) and stochastic behavior exhibited by networks. However, packet-level simulation becomes prohibitively expensive as link speeds, workloads, and network size increase. Timestepped Stochastic Simulation (TSS) overcomes scalability problems of packet-level simulation by generating a sample path of the system state S(t) at time t=d,2d,... rather than at each packet transmission. In each timestep [t,t+d], the distribution Pr[S(t+d)|S(t)] is obtained analytically, and S(t+d) is sampled from it. This dissertation presents TSS for shared links, specifically, 802.11 WLAN links. Our method computes sample paths of instantaneous goodput N_i(t) for all stations "i" in a WLAN over timesteps of length "d". For accurate modeling of higher layer protocols, "d" should be lesser than their control timescales (e.g., TCP's round-trip time). At typical values of "d" (e.g, 50ms), N_i(t)'s are correlated across timesteps (e.g., a station with high contention window has low goodput for several timesteps) as well as across stations (since they share the same media). To model these correlations, we obtain, jointly with the N_i(t)'s, sample paths of the WLAN's state, which consists of a contention window and a backoff counter at each station. Comparisons with packet level simulations show that TSS is accurate and provides up to two orders of magnitude improvement in simulation runtime.