research-article

Public Access

Achieving Low-Delay and Fast-Convergence in Stochastic Network Optimization: A Nesterovian Approach

Author:

Jia LiuAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 44, Issue 1

Pages 221 - 234

https://doi.org/10.1145/2964791.2901474

Published: 14 June 2016 Publication History

Abstract

Due to the rapid growth of mobile data demands, there have been significant interests in stochastic resource control and optimization for wireless networks. Although significant advances have been made in stochastic network optimization theory, to date, most of the existing approaches are plagued by either slow convergence or unsatisfactory delay performances. To address these challenges, in this paper, we develop a new stochastic network optimization framework inspired by the Nesterov accelerated gradient method. We show that our proposed Nesterovian approach offers utility-optimality, fast-convergence, and significant delay reduction in stochastic network optimization. Our contributions in this paper are three-fold: i) we propose a Nesterovian joint congestion control and routing/scheduling framework for both single-hop and multi-hop wireless networks; ii) we establish the utility optimality and queueing stability of the proposed Nesterovian method, and analytically characterize its delay reduction and convergence speed; and iii) we show that the proposed Nesterovian approach offers a three-way performance control between utility-optimality, delay, and convergence.

References

[1]

X. Lin and N. B. Shroff, "The impact of imperfect scheduling on cross-layer congestion control in wireless networks," IEEE/ACM Trans. Netw., vol. 14, no. 2, pp. 302--315, Apr. 2006.

Digital Library

[2]

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

Digital Library

[3]

M. J. Neely, E. Modiano, and C.-P. Li, "Faireness and optimal stochastic control for heterogeneous networks," IEEE/ACM Trans. Netw., vol. 16, no. 2, pp. 396--409, Apr. 2008.

Digital Library

[4]

A. Eryilmaz and R. Srikant, "Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control," IEEE/ACM Trans. Netw., vol. 15, no. 6, pp. 1333--1344, Dec. 2007.

Digital Library

[5]

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

Digital Library

[6]

X. Lin, N. B. Shroff, and R. Srikant, "A tutorial on cross-layer optimization in wireless networks," IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1452--1463, Aug. 2006.

Digital Library

[7]

M. J. Neely, "Super-fast delay tradeoffs for utility optimal fair scheduling in wireless networks," IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1489--1501, Aug. 2006.

Digital Library

[8]

L. Huang and M. J. Neely, "Delay reduction via lagrange multipliers in stochastic network optimization," IEEE Trans. Autom. Control, vol. 56, no. 4, pp. 842--857, Apr. 2011.

[9]

L. Huang, X. Liu, and X. Hao, "The power of online learning in stochastic network optimization," in Proc. ACM Sigmetrics, Austin, TX, Jun.16--20, 2014, pp. 153--165.

Digital Library

[10]

M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, 3rd ed. New York, NY: John Wiley & Sons Inc., 2006.

Digital Library

[11]

J. Liu, C. H. Xia, N. B. Shroff, and H. D. Sherali, "Distributed cross-layer optimization in wireless networks: A second-order approach," in Proc. IEEE INFOCOM, Turin, Italy, Apr. 14--19, 2013.

[12]

J. Liu, N. B. Shroff, C. H. Xia, and H. D. Sherali, "Joint congestion control and routing optimization: An efficient second-order distributed approach," IEEE/ACM Trans. Netw., 2015, accepted, to appear.

[13]

Y. Nesterov, "A method of solving a convex programming problem with convergence rate O(1/k²)," Soviet Math. Doklady, vol. 27, no. 2, pp. 372 -- 376, 1983.

[14]

----, Introductory Lectures on Convex Programming. Boston/Dordrecht/London: Kluwer Academic Publishers, 2004.

[15]

J. Liu, A. Eryilmaz, N. B. Shroff, and E. S. Bentley, "Heavy-ball: A new approach to tame delay and convergence in wireless network optimization," in Proc. IEEE INFOCOM, 2016.

[16]

R. J. Gibbens and F. P. Kelly, "Resource pricing and the evolution of congestion control," Automatica, vol. 35, pp. 1969--1985, 1999.

Digital Library

[17]

S. Kunniyur and R. Srikant, "Analysis and design of an adaptive virtual queue algorithm for active queue management," in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001, pp. 123--134.

Digital Library

[18]

A. Laksmikantha, C. Beck, and R. Srikant, "Robustness of real and virtual queue-based active queue management schemes," IEEE/ACM Trans. Netw., vol. 13, no. 1, pp. 81--93, Feb. 2005.

Digital Library

[19]

E. Athanasopoulou, L. Bui, T. Ji, R. Srikant, and A. Stolyar, "Back-pressure-based packet-by-packet adaptive routing in communication networks," IEEE/ACM Trans. Netw., vol. 21, no. 1, pp. 244--257, Feb. 2013.

Digital Library

[20]

N. Walton, "Concave switching in single and multihop networks," in Proc. ACM Sigmetrics, Austin, TX, Jun. 11--14, 2014, pp. 139 -- 151.

Digital Library

[21]

\BIBentryALTinterwordspacingM. Bramson, B. D'Auria, and N. Walton, "Proportional switching in FIFO networks." {Online}. Available: http://arxiv.org/abs/1412.4390\BIBentrySTDinterwordspacing

[22]

\BIBentryALTinterwordspacingZ. A. Zhu and L. Orecchia, "Linear coupling: An ultimate unification of gradient and mirror descent," MIT CSAIL, Tech. Rep., January 2015. {Online}. Available: http://arxiv.org/pdf/1407.1537v4.pdf\BIBentrySTDinterwordspacing

[23]

\BIBentryALTinterwordspacingW. Su, S. Boyd, and E. J. Candes, "A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights," Journal of Machine Learning Research, 2015, accepted, to appear. {Online}. Available: http://arxiv.org/abs/1503.01243\BIBentrySTDinterwordspacing

[24]

\BIBentryALTinterwordspacingS. Bubeck, Y. T. Lee, and M. Singh, "A geometric alternative to Nesterov's accelerated gradient descent," June 2015. {Online}. Available: http://arxiv.org/abs/1506.08187\BIBentrySTDinterwordspacing

[25]

B. T. Polyak, "Some methods of speeding up the convergence of iteration methods," USSR Computational Mathematics and Mathematical Physics, vol. 4, no. 5, pp. 1--17, 1964.

[26]

----, Introduction to Optimization. New York, NY: Optimization Software, Inc., May 1987.

[27]

E. Ghadimi, I. Shames, and M. Johansson, "Multi-step gradient methods for networked optimization," IEEE Trans. Signal Process., vol. 61, no. 21, pp. 5417--5429, Nov. 2013.

Digital Library

[28]

P. Ochs, T. Brox, and T. Pock, "iPiasco: Inertial proximal algorithm for strongly convex optimization," Journal of Mathematical Imaging and Vision (JMIV), 2015.

Digital Library

[29]

D. Jakovetic, J. M. F. Xavier, and J. M. F. Moura, "Convergence rates of distributed nesterov-like gradient methods on random networks," IEEE Trans. Signal Process., vol. 62, no. 4, pp. 868 -- 882, Feb. 2014.

Digital Library

[30]

A. Eryilmaz, R. Srikant, and J. R. Perkins, "Stable scheduling policies for fading wireless channels," IEEE/ACM Trans. Netw., vol. 13, no. 2, pp. 411--424, Apr. 2005.

Digital Library

[31]

X. Lin and N. B. Shroff, "Joint rate control and scheduling in multihop wireless networks," in Proc. IEEE CDC, Atlantis, Paradise Island, Bahamas, Dec. 2006, pp. 1484--1489.

[32]

R. A. Horn and C. R. Johnson, Matrix Analysis.\hskip 1em plus 0.5em minus 0.4em\relax New York, NY: Cambridge University Press, 1990.

Digital Library

[33]

S. P. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability, 2nd ed.\hskip 1em plus 0.5em minus 0.4em\relax Cambridge, UK: Cambridge University Press, 2009.

Digital Library

[34]

M. J. Neely, E. Modiano, and C. E. Rohrs, "Power allocation and routing in multibeam satellites with time-varying channels," IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 138--152, Feb. 2003.

Digital Library

[35]

L. Jiang and J. Walrand, "A distributed CSMA algorithm for throughput and utility maximization in wireless networks," IEEE/ACM Trans. Netw., vol. 18, no. 3, pp. 960--972, Jun. 2010.

Digital Library

[36]

J. Ni, B. Tan, and R. Srikant, "Q-CSMA: Queue-length-based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks," IEEE/ACM Trans. Netw., vol. 20, no. 3, pp. 825--836, Jun. 2012.

Digital Library

Cited By

Dong YZhang HLi JYu FGuo SLeung V(2022)An Online Zero-Forcing Precoder for Weighted Sum-Rate Maximization in Green CoMP SystemsIEEE Transactions on Wireless Communications10.1109/TWC.2022.315977921:9(7566-7581)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1109/TWC.2022.3159779
Guo DNakhleh KHou IKompella SKam C(2022)A Theory of Second-Order Wireless Network Optimization and Its Application on AoIIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796686(999-1008)Online publication date: 2-May-2022
https://dl.acm.org/doi/10.1109/INFOCOM48880.2022.9796686
Dong YZhang HLi JYu FGuo SLeung V(2022)An Online Throughput Maximization Algorithm for Green Coordinated Multi-Point SystemsICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP43922.2022.9746775(5383-5387)Online publication date: 23-May-2022
https://doi.org/10.1109/ICASSP43922.2022.9746775
Show More Cited By

Index Terms

Achieving Low-Delay and Fast-Convergence in Stochastic Network Optimization: A Nesterovian Approach
1. Networks
  1. Network algorithms
    1. Control path algorithms
      1. Network control algorithms
      2. Network resources allocation
  2. Network performance evaluation
    1. Network performance modeling

Recommendations

Achieving Low-Delay and Fast-Convergence in Stochastic Network Optimization: A Nesterovian Approach
SIGMETRICS '16: Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science

Due to the rapid growth of mobile data demands, there have been significant interests in stochastic resource control and optimization for wireless networks. Although significant advances have been made in stochastic network optimization theory, to date, ...
Dynamic Control Policy for Delay Guarantees in Multi-hop Wireless Networks

This paper considers the dynamic control of stochastic networks for the guaranteed delay with network utility maximization in multi-hop wireless networks. On contrary to single hop case, the delay is difficult to predict in multi-hop scenarios due to ...
Delay-sensitive routing in multi-rate MANETs

A mobile ad hoc network (MANET) is a collection of mobile hosts, which can communicate by the aid of intermediate mobile hosts without utilizing a fixed infrastructure and centralized administration. Many MANET standards, such as 802.11a, 802.11b, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 44, Issue 1

Performance evaluation review

June 2016

409 pages

ISSN:0163-5999

DOI:10.1145/2964791

Editors:
Derek Eager
University of Saskatchewan
,
Carey Williamson
University of Calgary

Issue’s Table of Contents

SIGMETRICS '16: Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science
June 2016
434 pages
ISBN:9781450342667
DOI:10.1145/2896377
General Chairs:
Sara Alouf
Inria, France
,
Alain Jean-Marie
Inria, France
,
Program Chairs:
Nidhi Hegde
Bell Labs, France
,
Alexandre Proutière
KTH, Sweden

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2016

Published in SIGMETRICS Volume 44, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
686
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)10

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dong YZhang HLi JYu FGuo SLeung V(2022)An Online Zero-Forcing Precoder for Weighted Sum-Rate Maximization in Green CoMP SystemsIEEE Transactions on Wireless Communications10.1109/TWC.2022.315977921:9(7566-7581)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1109/TWC.2022.3159779
Guo DNakhleh KHou IKompella SKam C(2022)A Theory of Second-Order Wireless Network Optimization and Its Application on AoIIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796686(999-1008)Online publication date: 2-May-2022
https://dl.acm.org/doi/10.1109/INFOCOM48880.2022.9796686
Dong YZhang HLi JYu FGuo SLeung V(2022)An Online Throughput Maximization Algorithm for Green Coordinated Multi-Point SystemsICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP43922.2022.9746775(5383-5387)Online publication date: 23-May-2022
https://doi.org/10.1109/ICASSP43922.2022.9746775
Wu ZChen XXu CYang S(2020)Nesterov Accelerated Gradient-based Algorithm for the Allocation Problem of NFV Service2020 International Conference on Networking and Network Applications (NaNA)10.1109/NaNA51271.2020.00044(213-220)Online publication date: Dec-2020
https://doi.org/10.1109/NaNA51271.2020.00044
Huang LChen MLiu Y(2018)Learning-Aided Stochastic Network Optimization With State PredictionIEEE/ACM Transactions on Networking10.1109/TNET.2018.285459326:4(1810-1820)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2854593
Huang LChen MLiu Y(2018)Learning-Aided Stochastic Network Optimization With State PredictionIEEE/ACM Transactions on Networking10.1109/TNET.2018.285459326:4(1810-1820)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2854593
Wang SShroff N(2017)Towards Fast-Convergence, Low-Delay and Low-Complexity Network OptimizationProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31544921:2(1-32)Online publication date: 19-Dec-2017
https://dl.acm.org/doi/10.1145/3154492
Huang LChen MLiu Y(2017)Learning-aided Stochastic Network Optimization with Imperfect State PredictionProceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/3084041.3084054(1-10)Online publication date: 10-Jul-2017
https://dl.acm.org/doi/10.1145/3084041.3084054

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents