Wireless Multi-hop Networks Beyond Capacity

Wireless multi-hop local area networks use in general scheduling schemes that assume the network capacity to be known. Indeed in most of the throughput-optimal algorithms the sources are assumed to send at a rate within the capacity region. However, measurements made on real deployments show that the network capacity is usually difficult to characterize and also time-varying. It is therefore important to understand how the network behaves when the sources attempt to transmit at a rate above capacity. Toward this goal, we show 3-phase regime in the effect of the input rate lambda on the end-to-end throughput mu of a multi-hop network. First, when lambda is smaller than a threshold lambda(1), mu is an increasing function of lambda. Second, when lambda is larger than another threshold lambda(2) > lambda(1), mu is independent of lambda. Third, when lambda(1) < lambda < lambda(2), mu decreases with lambda. To understand this phenomenon, we capture the relation between the end-to-end throughput and the queue stability with a mathematical model that allows us to explain and derive the exact values of the transition points lambda(i). We then validate experimentally our simulation results with measurements on a testbed composed of five wireless routers.