More Web Proxy on the site http://driver.im/

article

Distributed link scheduling with constant overhead

Authors:

Sujay Sanghavi,

R. SrikantAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 5

Pages 1467 - 1480

https://doi.org/10.1109/TNET.2009.2013621

Published: 01 October 2009 Publication History

Abstract

This paper proposes a new class of simple, distributed algorithms for scheduling in multihop wireless networks under the primary interference model. The class is parameterized by integers k ≥ 1. We show that algorithm kof our class achieves k/(k + 2) of the capacity region, for every k ≥ 1. The algorithms have small and constant worst-case overheads. In particular, algorithm k generates a new schedule using a) time less than 4k + 2 round-trip times between neighboring nodes in the network and b) at most three control transmissions by any given node for any k. The control signals are explicitly specified and face the same interference effects as normal data transmissions. Our class of distributed wireless scheduling algorithms are the first ones guaranteed to achieve any fixed fraction of the capacity region while using small and constant overheads that do not scale with network size. The parameter k explicitly captures the tradeoff between control overhead and throughput performance and provides a tuning-knob protocol designers can use to harness this tradeoff in practice.

References

[1]

X. Lin and S. Rasool, "Constant-time distributed scheduling policies for ad hoc wireless networks," in Proc. IEEE Conf. Decision Control, San Diego, CA, Dec. 2006, pp. 1258-1263.

[2]

A. Gupta, X. Lin, and R. Srikant, "Low-complexity distributed scheduling algorithms for wireless networks," in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 1631-1639.

[3]

C. Joo and N. Shroff, "Performance of random access scheduling schemes in multi-hop wireless networks," in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 19-27.

[4]

B. Hajek and G. Sasaki, "Link scheduling in polynomial time," IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 910-917, Sep. 1988.

Digital Library

[5]

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, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.

[6]

N. McKeown, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 1996, vol. 1, pp. 296-302.

Digital Library

[7]

L. Tassiulas, "Linear complexity algorithms for maximum throughput in radio networks and input queued switches," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 1998, vol. 2, pp. 533-539.

[8]

P. Giaccone, B. Prabhakar, and D. Shah, "Towards simple, high-performance schedulers for high-aggregate bandwidth switches," in Proc. IEEE INFOCOM, New York, NY, Jun. 2002, vol. 3, pp. 1160-1169.

[9]

T. Weller and B. Hajek, "Scheduling non uniform traffic in a packet switching system with small propagation delay," IEEE/ACM Trans. Netw., vol. 5, no. 6, pp. 813-823, Dec. 1997.

Digital Library

[10]

J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, vol. 2, pp. 556-564.

[11]

X. Lin and N. Shroff, "The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, vol. 3, pp. 1804-1814.

[12]

S. Sarkar and K. Kar, "Achieving 2/3 throughput approximation with sequential maximal scheduling under primary interference constraints," in Proc. Allerton Conf. Commun., Control Comput., Monticello, IL, Sep. 2006, pp. 729-740.

[13]

E. Modiano, D. Shah, and G. Zussman, "Maximizing throughput in wireless networks via gossiping," ACM SIGMETRICS Perf. Evaluation Rev., vol. 34, no. 1, pp. 27-38, Jun. 2006.

Digital Library

[14]

A. Brzezinski, G. Zussman, and E. Modiano, "Enabling distributed throughput maximization in wireless mesh networks: A partitioning approach," in Proc. ACM MOBICOM, Los Angeles, CA, Sep. 2006, pp. 26-37.

Digital Library

[15]

A. Eryilmaz, A. Ozdaglar, and E. Modiano, "Polynomial complexity algorithms for full utilization of multi-hop wireless networks," in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 499-507.

Digital Library

[16]

Y. Yi, G. de Veciana, and S. Shakkottai, "Learning contention patterns and adapting to load/topology changes in a MAC scheduling algorithm," in Proc. WiMesh, 2006, pp. 23-32.

[17]

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 Conf. Decision Control, Dec. 2005, pp. 5342-5347.

[18]

P. Chaporkar, K. Kar, and S. Sarkar, "Achieving queue length stability through maximal scheduling in wireless networks," in Proc. Inf. Theory Appl. Workshop, Feb. 2006.

[19]

X. Wu, R. Srikant, and J. Perkins, "Queue length stability of maximal greedy schedules in wireless networks," in Proc. Inf. Theory Appl. Workshop, Feb. 2006.

[20]

S. Ray and S. Sarkar, "Arbitrary throughput versus complexity trade-offs in wireless networks using graph partitioning," in Proc. Inf. Theory Appl. Workshop, Jan. 2007.

[21]

M. Neely, E. Modiano, and C. Rohrs, "Dynamic power allocation and routing for time varying wireless networks," IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89-103, Jan. 2005.

Digital Library

[22]

D. Shah and D. Wischik, "Optimal scheduling algorithms for input-queued switches," in Proc. IEEE INFOCOM, Barcelona, Spain, Apr. 2006.

[23]

H. N. Gabow, "Data structures for weighted matching and nearest common ancestors with linking," in Proc. ACM-SIAM Symp. Discrete Algorithms (SODA), San Francisco, CA, 1990, pp. 434-443.

Digital Library

[24]

A. Stolyar, "Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm," Queueing Syst., vol. 50, no. 4, pp. 401-457, Aug. 2005.

Digital Library

[25]

A. Eryilmaz and R. Srikant, "Fair resource allocation in wireless networks using queue-length based scheduling and congestion control," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 1794-1803.

[26]

A. Eryilmaz and R. Srikant, "Joint congestion control, routing and MAC for stability and fairness in wireless networks," in IEEE J. Sel. Areas Commun., Aug. 2006, vol. 24, no. 8, pp. 1514-1524.

Digital Library

[27]

M. Neely, E. Modiano, and C. Li, "Fairness and optimal stochastic control for heterogeneous networks," in Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 1723-1734.

[28]

X. Lin and N. Shroff, "Joint rate control and scheduling in multihop wireless networks," in Proc. IEEE Conf. Decision Control, Paradise Island, Bahamas, Dec. 2004, pp. 1484-1489.

[29]

S. Pettie and P. Sanders, "A simpler linear time 2/3-ε approximation for maximum weight matching," Inf. Process. Lett., vol. 91, no. 6, pp. 271-276, 2004.

Digital Library

Cited By

Nguyen QModiano EJi BChiasserini CWu JSubramaniam S(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
https://dl.acm.org/doi/10.1145/3565287.3610258
Jawad SAl-Ali MJasim A(2022)Adaptive CSMA scheduling algorithm for queuing delay enhancement and energy optimizationAd Hoc Networks10.1016/j.adhoc.2022.102908134:COnline publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.adhoc.2022.102908
Gupta MRao AVisotsky EGhosh AAndrews J(2020)Learning Link Schedules in Self-Backhauled Millimeter Wave Cellular NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2020.301895519:12(8024-8038)Online publication date: 9-Dec-2020
https://dl.acm.org/doi/10.1109/TWC.2020.3018955
Show More Cited By

Recommendations

Distributed link scheduling with constant overhead
SIGMETRICS '07: Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

This paper proposes a new class of simple, distributed algorithms for scheduling in wireless networks. The algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. The class is parameterized by integers k\...
Distributed link scheduling with constant overhead
SIGMETRICS '07 Conference Proceedings

This paper proposes a new class of simple, distributed algorithms for scheduling in wireless networks. The algorithms generate new schedules in a distributed manner via simple local changes to existing schedules. The class is parameterized by integers k\...
Multi-channel Busy-tone Multiple Access for Scalable Wireless Mesh Network
AINAW '07: Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops - Volume 02

This paper proposes a multi-channel medium access control (MAC) protocol for wireless mesh networks (WMNs) by using busy tones to prevent data packet collisions at data channels. Multi-channel MAC schemes can achieve higher network throughput than ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 5

October 2009

339 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 October 2009

Revised: 06 September 2008

Received: 13 January 2008

Published in TON Volume 17, Issue 5

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
223
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nguyen QModiano EJi BChiasserini CWu JSubramaniam S(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
https://dl.acm.org/doi/10.1145/3565287.3610258
Jawad SAl-Ali MJasim A(2022)Adaptive CSMA scheduling algorithm for queuing delay enhancement and energy optimizationAd Hoc Networks10.1016/j.adhoc.2022.102908134:COnline publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1016/j.adhoc.2022.102908
Gupta MRao AVisotsky EGhosh AAndrews J(2020)Learning Link Schedules in Self-Backhauled Millimeter Wave Cellular NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2020.301895519:12(8024-8038)Online publication date: 9-Dec-2020
https://dl.acm.org/doi/10.1109/TWC.2020.3018955
Sinha AModiano E(2018)Optimal Control for Generalized Network-Flow ProblemsIEEE/ACM Transactions on Networking10.1109/TNET.2017.278384626:1(506-519)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1109/TNET.2017.2783846
Sinha APaschos GLi CModiano E(2017)Throughput-Optimal Multihop Broadcast on Directed Acyclic Wireless NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2016.258290725:1(377-391)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TNET.2016.2582907
Zheng XCai ZLi JGao H(2017)A Study on Application-Aware Scheduling in Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2016.261352916:7(1787-1801)Online publication date: 2-Jun-2017
https://dl.acm.org/doi/10.1109/TMC.2016.2613529
Facchi NGringoli FMalone DPatras P(2017)ImolaComputer Communications10.1016/j.comcom.2016.12.015105:C(157-168)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.comcom.2016.12.015
Kim DOh SLim J(2017)Multi-channel-based scheduling for overlay inband device-to-device communicationsWireless Networks10.1007/s11276-016-1306-z23:8(2587-2600)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s11276-016-1306-z
Markakis MModiano ETsitsiklis JMarkakis MModiano ETsitsiklis J(2016)Delay Stability of Back-Pressure Policies in the Presence of Heavy-Tailed TrafficIEEE/ACM Transactions on Networking10.1109/TNET.2015.244810724:4(2046-2059)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2448107
Joo CLin XRyu JShroff N(2016)Distributed greedy approximation to maximum weighted independent set for scheduling with fading channelsIEEE/ACM Transactions on Networking10.1109/TNET.2015.241786124:3(1476-1488)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2417861
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents