Pushing mean field asymptotics to the limits
The stability and performance of random medium access control
(joint work with Charles Bordenave and David McDonald)
Distributed
scheduling algorithms have played an increasingly important role in the
development of wired and wireless Local Area Networks (LANs) and yet
the performance of even the simplest of these algorithms, such as
slotted-ALOHA, are still not clearly understood. In this talk, we
present a generic method to analyze the performance of large networks
where
interfering users share a resource using distributed scheduling schemes.
The method relies on studying the mean field limiting behavior of the
system. We show that it is asymptotically exact when the number of
users grows large, and explain why it also provides extremely accurate
performance estimates even for small systems.
We
push the method to its limits and show how it can be applied to address
the stability region of non-adaptive ALOHA-like systems. Specifically,
we consider a fixed number of buffered users receiving packets from
independent exogenous processes and accessing the resource using
ALOHA-like algorithms. We provide an explicit expression to approximate
the stability region of this system, and prove its accuracy.