Network adiabatic theorem: an efficient randomized protocol for contention resolution

ABSTRACT

The popularity of Aloha-like algorithms for resolution of contention between multiple entities accessing common resources is due to their extreme simplicity and distributed nature. Example applications of such algorithms include Ethernet and recently emerging wireless multi-access networks. Despite a long and exciting history of more than four decades, the question of designing an algorithm that is essentially as simple and distributed as Aloha while being efficient has remained unresolved.

In this paper, we resolve this question successfully for a network of queues where contention is modeled through independent-set constraints over the network graph. The work by Tassiulas and Ephremides (1992) suggests that an algorithm that schedules queues so that the summation of `weight' of scheduled queues is maximized, subject to constraints, is efficient. However, implementing such an algorithm using Aloha-like mechanism has remained a mystery. We design such an algorithm building upon a Metropolis-Hastings sampling mechanism along with selection of `weight' as an appropriate function of the queue-size. The key ingredient in establishing the efficiency of the algorithm is a novel adiabatic-like theorem for the underlying queueing network, which may be of general interest in the context of dynamical systems.

REFERENCES

• 1: N. Abramson and F. Kuo (Editors). The aloha system. Computer-Communication Networks, 1973.
• 2: D.J. Aldous, Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels, IEEE Transactions on Information Theory, v.33 n.2, p.219-223, March 1987 [doi>10.1109/TIT.1987.1057295]
• 3: Charles Bordenave , David McDonald , Alexandre Proutiere, Performance of random medium access control, an asymptotic approach, Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 02-06, 2008, Annapolis, MD, USA
• 4: M. Born and V. A. Fock. Beweis des adiabatensatzes. Zeitschrift für Physik a Hadrons and Nuclei, 51(3--4):165--180, 1928.
• 5: J. G. Dai. Stability of fluid and stochastic processing networks. Miscellanea Publication, (9), 1999.
• 6: A. Ephremides and B. Hajek. Information theory and communication networks: an unconsummated union. IEEE Transactions on Information Theory, 44(6):2416--2432, 1998.
• 7: A. Eryilmaz, A. Ozdaglar, D. Shah, and E. Modiano. Distributed cross-layer algorithms for the optimal control of multi-hop wireless networks. submitted to IEEE/ACM Transactions on Networking, 2008.
• 8: S. Foss and Takis Konstantopoulos. An overview of some stochastic stability methods. Journal of Operations Research, Society of Japan, 47(4), 2004.
• 9: R. K. Getoor. Transience and recurrence of markov processes. In AzÖma, J. and Yor, M., editors, Séminaire de Probabilités XIV, pages 397--409, 1979.
• 10: L. A. Goldberg , M. Jerrum , S. Kannan , M. S. Paterson, A Bound on the Capacity of Backoff and Acknowledgement-based Protocols, University of Warwick, Coventry, UK, 2000
• 11: Leslie Ann Goldberg. Design and analysis of contention-resolution protocols, epsrc research grant gr/l60982. http://www.csc.liv.ac.uk/ leslie/contention.html, Last updated, Oct. 2002.
• 12: Albert G. Greenberg , Philippe Flajolet , Richard E. Ladner, Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, Journal of the ACM (JACM), v.34 n.2, p.289-325, April 1987 [doi>10.1145/23005.23006]
• 13: D. J. Griffiths. Introduction to Quantum Mechanics. Pearson Prentice Hall, 2005.
• 14: P. Gupta and A. L. Stolyar. Optimal throughput allocation in general random-access networks. In Proceedings of 40th Annual Conf. Inf. Sci. Systems, IEEE, Princeton, NJ, pages 1254--1259, 2006.
• 15: Johan Håstad , Tom Leighton , Brian Rogoff, Analysis of Backoff Protocols for Mulitiple AccessChannels, SIAM Journal on Computing, v.25 n.4, p.740-774, Aug. 1996 [doi>10.1137/S0097539792233828]
• 16: L. Jiang and J. Walrand. A distributed csma algorithm for throughput and utility maximization in wireless networks. In Proceedings of 46th Allerton Conference on Communication, Control, and Computing, Urbana-Champaign, IL, 2008.
• 17: J.Liu and A. L. Stolyar. Distributed queue length based algorithms for optimal end-to-end throughput allocation and stability in multi-hop random access networks. In Proceedings of 45th Allerton Conference on Communication, Control, and Computing, Urbana-Champaign, IL, 2007.
• 18: F. P. Kelly. Stochastic models of computer communication systems. J. R. Statist. Soc B, 47(3):379--395, 1985.
• 19: F.P. Kelly and I.M. MacPhee. The number of packets transmitted by collision detect random access schemes. The Annals of Probability, 15(4):1557--1568, 1987.
• 20: I.M. MacPhee. On optimal strategies in stochastic decision processes, d. phil. thesis, university of cambridge, 1989.
• 21: P. Marbach. Distributed scheduling and active queue management in wireless networks. In Proceedings of IEEE INFOCOM, Minisymposium, 2007.
• 22: P. Marbach, A. Eryilmaz, and A. Ozdaglar. Achievable rate region of csma schedulers in wireless networks with primary interference constraints. In Proceedings of IEEE Conference on Decision and Control, 2007.
• 23: Sean Meyn , Richard L. Tweedie, Markov Chains and Stochastic Stability, Cambridge University Press, New York, NY, 2009
• 24: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 25: Microsoft research lab. self organizing neighborhood wireless mesh networks. http://research.microsoft.com/mesh/.
• 26: Sujay Sanghavi , Loc Bui , R. Srikant, Distributed link scheduling with constant overhead, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 27: D. Shah and D. J. Wischik. Optimal scheduling algorithm for input queued switch. In Proceeding of IEEE INFOCOM, 2006.
• 28: D. Shah and D. J. Wischik. Heavy traffic analysis of optimal scheduling algorithms for switched networks. Submitted, 2007.
• 29: Srinivas Shakkottai , R. Srikant, Network optimization and control, Foundations and Trends® in Networking, v.2 n.3, p.271-379, January 2007 [doi>10.1561/1300000007]
• 30: A. L. Stolyar. Dynamic distributed scheduling in random access bnetworks. Journal of Applied Probabability, 45(2):297--313, 2008.
• 31: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37:1936--1948, 1992.
• 32: B.S. Tsybakov and N. B. Likhanov. Upper bound on the capacity of a random multiple-access system. Problemy Peredachi Informatsii, 23(3):64--78, 1987.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication; Distributed networks

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes; Queueing theory

General Terms:
Algorithms, Design, Performance

Keywords:
aloha, markov chain, mixing time, wireless multi-access