skip to main content
article

Scalability of wireless networks

Published: 01 April 2007 Publication History

Abstract

This paper investigates the existence of scalable protocols that can achieve the capacity limit of c/√N per source-destination pair in a large wireless network of N nodes when the buffer space of each node does not grow with the size of the network N. It is shown that there is no end-to-end protocol capable of carrying out the limiting throughput of c/√N with nodes that have constant buffer space. In other words, this limit is achievable only with devices whose buffers grow with the size of the network. On the other hand, the paper establishes that there exists a protocol which realizes a slightly smaller throughput of c/√N log N when devices have constant buffer space. Furthermore, it is shown that the required buffer space can be very small, capable of storing just a few packets. This is particularly important for wireless sensor networks where devices have limited resources. Finally, from a mathematical perspective, the paper furthers our understanding of the difficult problem of analyzing large queueing networks with finite buffers for which, in general, no explicit solutions are available.

References

[1]
{1} P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
[2]
{2} A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Throughput-delay trade-off in wireless networks," in Proc. IEEE INFOCOM 2004, Hong Kong, Mar. 2004, pp. 464-475.
[3]
{3} A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Optimal throughput-delay scaling in wireless networks--Part I: The fluid model," IEEE Trans. Inf. Theory, vol. 52, no. 6, pp. 2568-2592, Jun. 2006.
[4]
{4} A. El Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Optimal throughput-delay scaling in wireless networks--Part II: Constant-size packets," IEEE Trans. Inf. Theory, vol. 52, no. 11, pp. 5111-5116, Nov. 2006.
[5]
{5} M. Franceschetti, O. Dousse, D. Tse, and P. Thiran, "On the throughput capacity of random wireless networks." Preprint.
[6]
{6} S. Kulkarni and P. Viswanath, "A deternimistic approach to throughput scaling in wireless networks," IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1041-1049, Jun. 2004.
[7]
{7} P. R. Kumar and L.-L. Xie, "A network information theory for wireless communications: Scaling laws and optimal operation," IEEE Trans. Inf. Theory, vol. 50, no. 5, pp. 748-767, May 2004.
[8]
{8} O. Leveque and E. Telatar, "Information theoretic upper bounds on the capacity of ad hoc networks," IEEE Trans. Inf. Theory, vol. 51, no. 3, pp. 858-865, Mar. 2005.
[9]
{9} A. Jovičič, P. Viswanath, and S. Kulkarni, "Upper bounds to transport capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 50, no. 11, pp. 2555-2565, Nov. 2004.
[10]
{10} G. Barrenechea, B. Beferull-Lozano, and M. Vetterli, "Lattice sensor networks: Capacity limits, optimal routing and robustness to failures," in Proc. Conf. Information Processing In Sensor Networks (IPSN), Berkeley, CA, Apr. 2004.
[11]
{11} R. M. Loynes, "The stability of a queue with non-independent inter-arrival and service times," Proc. Cambr. Phil., Soc., vol. 58, pp. 497-520, 1962.
[12]
{12} F. Kelly, Reversibility and Stochastic Networks. New York: Wiley, 1979.
[13]
{13} D. Bertsekas and R. Gallager, Data Networks, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 1992.
[14]
{14} P. Jelenković, P. Momčilović, and M. Squillante, "Buffer scalability of wireless networks," presented at the IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
[15]
{15} T. Liggett, Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Berlin, Germany: Springer-Verlag, 1999.
[16]
{16} M. Karol, S. J. Golestani, and D. Lee, "Prevention of deadlocks and livelocks in lossless backpressured packet networks," IEEE/ACM Trans. Netw., vol. 11, no. 6, pp. 923-934, Dec. 2003.
[17]
{17} F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, and Hypercubes. San Mateo, CA: Morgan Kaufmann, 1992.
[18]
{18} J. Herdtner and E. Chong, "Throughput-storage tradeoff in ad hoc networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, vol. 4, pp. 2536-2542.
[19]
{19} M. Grossglauser and D. Tse, "Mobility increases the capacity of ad hoc wireless networks," IEEE/ACM Trans. Netw., vol. 10, no. 4, pp. 477-486, Aug. 2002.
[20]
{20} M. Neely and E. Modiano, "Capacity and delay tradeoffs for ad hoc mobile networks," IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1917-1937, Jun. 2005.
[21]
{21} P. Robert, Stochastic Networks and Queues. Berlin, Germany: Springer, 2003.
[22]
{22} X. Chao, M. Miyazawa, and M. Pinedo, Queueing Networks: Customers, Signals, and Product Form Solutions. Chichester, U.K.: Wiley, 1999.

Cited By

View all
  • (2023)Learning to Schedule in Non-Stationary Wireless Networks With Unknown StatisticsProceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3565287.3610258(181-190)Online publication date: 23-Oct-2023
  • (2021)Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput LimitJournal of the ACM10.1145/344821368:3(1-30)Online publication date: 25-May-2021
  • (2015)Data rate, path length and network contention trade-off in IEEE 802.11s mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.08.02691:C(225-243)Online publication date: 14-Nov-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 2
April 2007
232 pages

Publisher

IEEE Press

Publication History

Published: 01 April 2007
Published in TON Volume 15, Issue 2

Author Tags

  1. ad hoc wireless networks
  2. finite-buffer queueing networks
  3. large-scale networks
  4. local cooperation
  5. scaling laws
  6. wireless sensor networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Learning to Schedule in Non-Stationary Wireless Networks With Unknown StatisticsProceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3565287.3610258(181-190)Online publication date: 23-Oct-2023
  • (2021)Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput LimitJournal of the ACM10.1145/344821368:3(1-30)Online publication date: 25-May-2021
  • (2015)Data rate, path length and network contention trade-off in IEEE 802.11s mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.08.02691:C(225-243)Online publication date: 14-Nov-2015
  • (2011)Tandem queueing networks with neighbor blocking and back-offsQueueing Systems: Theory and Applications10.1007/s11134-011-9239-968:3-4(321-331)Online publication date: 1-Aug-2011
  • (2011)Linear loss networksQueueing Systems: Theory and Applications10.1007/s11134-011-9230-568:2(111-131)Online publication date: 1-Jun-2011
  • (2008)On throughput in stochastic linear loss networksACM SIGMETRICS Performance Evaluation Review10.1145/1453175.145320536:2(125-127)Online publication date: 31-Aug-2008
  • (2008)Revisiting stochastic loss networksACM SIGMETRICS Performance Evaluation Review10.1145/1384529.137550336:1(407-418)Online publication date: 2-Jun-2008
  • (2008)Revisiting stochastic loss networksProceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems10.1145/1375457.1375503(407-418)Online publication date: 2-Jun-2008
  • (2008)On throughput in linear wireless networksProceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing10.1145/1374618.1374646(199-208)Online publication date: 26-May-2008
  • (2008)Engineering of Software-Intensive SystemsSoftware-Intensive Systems and New Computing Paradigms10.1007/978-3-540-89437-7_1(1-44)Online publication date: 14-Nov-2008
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media