Maximizing throughput in wireless networks via gossiping

ABSTRACT

A major challenge in the design of wireless networks is the need for distributed scheduling algorithms that will efficiently share the common spectrum. Recently, a few distributed algorithms for networks in which a node can converse with at most a single neighbor at a time have been presented. These algorithms guarantee 50% of the maximum possible throughput. We present the first distributed scheduling framework that guarantees maximum throughput. It is based on a combination of a distributed matching algorithm and an algorithm that compares and merges successive matching solutions. The comparison can be done by a deterministic algorithm or by randomized gossip algorithms. In the latter case, the comparison may be inaccurate. Yet, we show that if the matching and gossip algorithms satisfy simple conditions related to their performance and to the inaccuracy of the comparison (respectively), the framework attains the desired throughput.It is shown that the complexities of our algorithms, that achieve nearly 100% throughput, are comparable to those of the algorithms that achieve 50% throughput. Finally, we discuss extensions to general interference models. Even for such models, the framework provides a simple distributed throughput optimal algorithm.

References

1. M. Bayati, D. Shah, and M. Sharma. Maximum weight matching via maxproduct algorithm. In Proc. IEEE ISIT'05, Sep. 2005.
2. D. Bertsekas and J. Tsitsiklis. Parallel and distributed computation: numerical methods. MIT/LIDS Tech. Report, 2003.
3. R. Bhatia, A. Segall, and G. Zussman. Analysis of bandwidth allocation algorithms for wireless personal area networks. To appear in ACM/Springer Wireless Networks (WINET), 12, 2006.
4. S. Boyd, A. Ghosh, B. Prabbakar, and D. Shah. Gossip algorithms: design, analysis and applications. In Proc. IEEE INFOCOM'05, March 2005.
5. P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through maximal scheduling in wireless networks. In Proc. 43rd Allerton Conf. on Commun., Control, and Comp., September 2005.
6. L. Chen, S. H. Low, M. Chiang, and J. C. Doyle. Optimal cross-layer congestion control, routing and scheduling design in ad hoc wireless networks. In Proc. IEEE INFOCOM'06, April 2006.
7. S. Deb, D. Shah, and S. Shakkottai. Fast incremental algorithm for repetitive optimization: an application to switch scheduling. In Proc. CISS, March 2006.
8. A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. 2nd edition, Springer, 1998.
9. P. Giaccone, B. Prabhakar, and D. Shah. Randomized scheduling algorithms for high-aggregate bandwidth switches. IEEE J. Sel. Areas Commun., 21(4):546--559, May 2003.
10. B. Hajek and G. Sasaki. Link scheduling in polynomial time. IEEE Trans. Inf. Theory, 34(5):910--917, September 1988.
11. J.-H. Hoepman. Simple distributed weighted matchings. eprint cs.DC/0410047, October 2004.
12. A. Israeli and A. Itai. A fast randomized parallel algorithm for maximal matching. Inform. Process. Lett., 22(2):77--80, January 1986.
13. K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu. Impact of interference on multi-hop wireless network performance. ACM/Springer Wireless Networks, 11(4):471--487, July 2005.
14. K. M. Jung and D. Shah. Fast gossip via non-reversible random walk. In Proc. IEEE ITW'06, March 2006.
15. R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In Proc. IEEE FOCS'00, November 2000.
16. E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976.
17. X. Lin and N.B. Shroff. The impact of imperfect scheduling on cross-layer rate control in wireless networks. In Proc. IEEE INFOCOM'05, March 2005.
18. N. McKeown, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. In Proc. IEEE INFOCOM'96, March 1996.
19. D. Mosk-Aoyama and D. Shah. Computing separable functions via gossip. Available at www.arxiv.org:cs.NI/0504029, Feb. 2006.
20. M. Neely, E. Modiano, and C. Rohrs. Dynamic power allocation and routing for time-varying wireless networks. IEEE J. Sel. Areas Commun., 23(1):89--103, January 2005.
21. D. Peleg, Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
22. L. Tassiulas. Linear complexity algorithms for maximum throughput in radio networks and input queued switches. In Proc. IEEE INFOCOM'98, April 1998.
23. L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control, 37(12):1936--1948, December 1992.
24. L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless ad hoc networks. IEEE J. Sel. Areas Commun., 23(1):163--173, January 2005.
25. M. Wattenhofer and R. Wattenhofer. Distributed weighted matching. In Proc. DISC'04, LNCS 3221:335--348, Springer, October 2004.
26. X. Wu and R. Srikant. Regulated maximal matching: a distributed scheduling algorithm for multi-hop wireless networks with node-exclusive spectrum sharing. In Proc. IEEE CDC-ECC'05, December 2005.
27. G. Zussman and A. Segall. Capacity assignment in bluetooth scatternets - optimal and heuristic algorithms. ACM/Kluwer Mobile Networks and Applications (MONET), 9(1):49--61, February 2004.

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic reasoning algorithms

      • Markov-chain Monte Carlo methods

      • Sequential Monte Carlo methods

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks