Charles Bordenave
ABSTRACT
Random Medium-Access-Control (MAC) 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 paper we provide a general and accurate method to analyze networks where interfering users share a resource using random MAC algorithms. We show that this method 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 apply this analysis to solve two open problems: (a) We 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. (b) We outline how to apply the analysis to predict the performance of adaptive MAC algorithms, such as the exponential back-off algorithm, in a system where saturated users interact through interference. In general, our analysis may be used to quantify how far from optimality the simple MAC algorithms used in LANs today are, and to determine if more complicated (e.g. queue-based) algorithms proposed in the literature could provide significant improvement in performance.
- V. Anantharam. The stability region of the finite-user slotted Aloha protocol. IEEE Trans. on Information Theory, 37:535--540, 1991.Google Scholar
Cross Ref
- F. Baccelli and P. Bremaud. Elements of Queueing Theory, 2dn edition. Springer-verlag, 2003.Google ScholarCross Ref
- G. Bianchi. Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 18(3):535--547, 2000. Google ScholarDigital Library
- T. Bonald, S. Borst, N. Hegde, and A. Proutiere. Wireless data performance in multi-cell scenarios. In Proceedings of ACM Sigmetrics, 2004. Google ScholarDigital Library
- C. Bordenave, D. McDonald, and A. Proutiere. Random multi-access algorithms: A mean field analysis. In Proceedings of Allerton conference, 2005.Google Scholar
- C. Bordenave, D. McDonald, and A. Proutiere. A particle system in interaction with a rapidly varying environment: Mean field limits and applications. to appear in NHM, available at http://arxiv.org/abs/math/0701363, 2007.Google Scholar
- S. Borst, M. Jonckheere, and L. Leskela. Stability of parallel queueing systems with coupled rates. Journal of Discrete Event Dynamic Systems, 2007. Google ScholarDigital Library
- M. Durvy and P. Thiran. Packing approach to compare slotted and non-slotted medium access control. In Proc. of IEEE Infocom, 2006.Google ScholarCross Ref
- F. Kelly. Loss networks. Annals of Applied Probability, 1:319--378, 1991.Google ScholarCross Ref
- F. P. Kelly. Reversibility and Stochastic Networks. Wiley, Chichester, 1979.Google Scholar
- L. Kleinrock. Queueing Systems, volume 2. Wiley, 1976.Google Scholar
- W. Luo and A. Ephremides. Stability of n interacting queues in random-access systems. IEEE trans. on Information Theory, 45(5):1579--1587, 1999. Google ScholarDigital Library
- P. Nain. Analysis of a two-node Aloha network with infinite capacity buffers. In Proc. of the Int. Seminar on Computer Networking and Performance Evaluation, 1985.Google Scholar
- L. Roberts. Aloha packet system with and without slot and capture. ASS Note 8, ARPA, Stanford Res. Inst., 1972.Google Scholar
- T. Saadawi and A. Ephremides. Analysis, stability and optimization of slotted Aloha with a finite number of buffered users. IEEE Transactions on Automatic Control, 26:680--689, 1981.Google ScholarCross Ref
- S. Sanghavi, L. Bui, and R. Srikant. Distributed link scheduling with constant overhead. In Proceedings of ACM Sigmetrics, 2007. Google ScholarDigital Library
- W. Szpankowski. Stability conditions for some multiqueue distributed systems: Buffered random access systems. Advances in Applied Probability, 26:498--515, 1994.Google ScholarCross Ref
- L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. on Automatic Control, 37:1936--1949, 1992.Google ScholarCross Ref
- B. Tsybakov and W. Mikhailov. Ergodicity of slotted Aloha system. Probl. Peredachii Infor., 15:73--87, 1979.Google Scholar
Index Terms
- Performance of random medium access control, an asymptotic approach
Recommendations
Performance of random medium access control, an asymptotic approach
SIGMETRICS '08Random Medium-Access-Control (MAC) 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 ...
On the Performance of Distributed Polling Service-based Medium Access Control
Part 2It has been shown in the literature that many MAC protocols for wireless networks have a considerable control overhead, which limits their achievable throughput and delay performance. In this paper, we study the problem of improving the efficiency of ...
Channel-aware distributed medium access control
In this paper, we solve a fundamental problem: how to use distributed random access to achieve the performance of centralized schedulers. We consider wireless networks with arbitrary topologies and spatial traffic distributions, where users can receive ...
Comments