article

Distributed iterative optimal resource allocation with concurrent updates of routing and flow control variables

Authors:

Jayakrishnan Nair,

D. ManjunathAuthors Info & Claims

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

Pages 1312 - 1325

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

Published: 01 August 2009 Publication History

Abstract

Consider a set of active elastic sessions over a network. Session traffic is routed at each hop (potentially through multiple network paths) based only on its destination. Each session is associated with a concave increasing utility function of its transfer rate. The transfer rates of all sessions and the routing policy define the operating point of the network.We construct a metric f of the goodness of this operating point. f is an increasing function of the session utilities and a decreasing function of the extent of congestion in the network.We define"good" operating points as those that maximizef, subject to the capacity constraints in the network. This paper presents a distributed, iterative algorithm for adapting the session rates and the routing policy across the network so as to converge asymptotically to the set of "good" operating points. The algorithm updates session rates and routing variables concurrently and is, therefore, amenable to distributed online implementation. The convergence of the concurrent update scheme is proved rigorously.

References

[1]

F. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: Shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, no. 3, pp. 237-252, 1998.

[2]

S. H. Low and D. E. Lapsley, "Optimization flow control--I: Basic algorithm and convergence," IEEE/ACM Trans. Netw., vol. 7, no. 6, pp. 861-874, Dec. 1999.

Digital Library

[3]

K. Kar, S. Sarkar, and L. Tassiulas, "Optimization based rate control for multipath sessions," Inst. for Syst. Res., Univ. of Maryland, Tech. Rep. No. 2001-1, 2001.

[4]

X. Lin and N. B. Shroff, "Utility maximization for communication networks with multi-path routing," IEEE Trans. Automat. Control, vol. 51, no. 5, pp. 766-781, May 2006.

[5]

D. P. Bertsekas and R. G. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice Hall, 1992.

Digital Library

[6]

R. G. Gallager, "A minimum delay routing algorithm using distributed computation," IEEE Trans. Commun., vol. COM-25, no. 1, pp. 73-85, Jan. 1977.

[7]

V. S. Borkar and P. R. Kumar, "Dynamic Cesaro-Wardrop equilibration in networks," IEEE Trans. Automat. Control, vol. 48, no. 3, pp. 382-396, Mar. 2003.

[8]

X. Wang and K. Kar, "Cross-layer rate control for end-to-end proportional fairness in wireless networks with random access," in Proc. MobiHoc' 05, 2005, pp. 157-168.

Digital Library

[9]

F. Paganini, "Congestion control with adaptive multipath routing based on optimization," in Proc. 40th Conf. Inf. Sci. Syst. (CISS 2006), Princeton, NJ, Mar. 2006, pp. 333-338.

[10]

J. Pongsajapan and S. H. Low, "Reverse engineering TCP/IP-like networks using delay-sensitive utility functions," in Proc. IEEE INFOCOM, Anchorage, Alaska, May 2007, pp. 418-426.

[11]

H. Yaiche, R. Mazumdar, and C. Rosenberg, "A game theoretic framework for bandwidth allocation and pricing in broadband networks," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 667-678, Oct. 2000.

Digital Library

[12]

S. H. Low, "Multipath optimization flow control," in Proc. IEEE Int. Conf. Netw., Singapore, Sep. 2000, pp. 39-43.

Digital Library

[13]

D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Upper Saddle River, NJ: Prentice-Hall, 1989.

Digital Library

[14]

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

Digital Library

[15]

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

[16]

L. Georgiadis, M. J. Neely, and L. Tassiulas, Resource Allocation and Cross Layer Control in Wireless Networks. Boston, MA: NOW Publishers, 2006.

Digital Library

[17]

V. S. Borkar, "Stochastic approximation with two timescales," Syst. Control Lett., vol. 29, pp. 291-294, 1997.

Digital Library

[18]

J. Zhang, D. Zheng, and M. Chiang, "The impact of stochastic noisy feedback on distributed network utility maximization," IEEE Trans. Inf. Theory, vol. 54, no. 2, pp. 645-665, Feb. 2008.

Digital Library

[19]

M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms. New York: Wiley, 1993.

[20]

P. Dupuis and A. Nagurney, "Dynamical systems and variational inequalities," Ann. Oper. Res., vol. 55, pp. 9-42, 1993.

[21]

H. K. Khalil, Nonlinear Systems. Englewood Cliffs, NJ: Prentice-Hall, 2002.

[22]

H. J. Kushner and G. G. Yin, Stochastic Approximation and Recursive Algorithms and Applications. New York: Springer, 1997.

[23]

V. S. Borkar, Stochastic Approximation: A Dynamical Systems Viewpoint . New Delhi, India: Hindustan Book Agency and Cambridge, U.K.: Cambridge Univ. Press, 2008.

[24]

W. Rudin, Principles of Mathematical Analysis. New York: Mc-Graw-Hill, 1976.

Cited By

Li SSun WTian N(2019)Resource allocation for multi-class services in multipath networksPerformance Evaluation10.1016/j.peva.2015.06.00192:C(1-23)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.peva.2015.06.001
Li SSun WZhang H(2018)Fair rate allocation for flows in concurrent multipath communicationsTelecommunications Systems10.1007/s11235-013-9855-257:3(271-285)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11235-013-9855-2
Zhang YHe SChen J(2016)Data gathering optimization by dynamic sensing and routing in rechargeable sensor networksIEEE/ACM Transactions on Networking10.1109/TNET.2015.242514624:3(1632-1646)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2425146

Index Terms

Distributed iterative optimal resource allocation with concurrent updates of routing and flow control variables

Recommendations

Optimal multihop routing. An iterative approach to TWDM embedding
LCN '95: Proceedings of the 20th Annual IEEE Conference on Local Computer Networks

This paper introduces the concept of time slot synchronization in time-wave division multiplexed (TWDM) multihop lightwave networks. It is shown that the time slot assignments of the intermediate nodes in a multihop path have significant effect on the ...
Analysis of AntNet routing scheme by using queueing model

We analyzed the AntNet routing scheme's performance by using the network queueing model, and derived the optimal routing strategies to minimize the average time and variance of the end-to-end packet delay. In contrast to existing research, this paper ...
MATE: multipath adaptive traffic engineering

Destination-based forwarding in traditional IP routers has not been able to take full advantage of multiple paths that frequently exist in Internet service provider networks. As a result, the networks may not operate efficiently, especially when the ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 4

August 2009

337 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 August 2009

Revised: 13 May 2008

Received: 23 October 2007

Published in TON Volume 17, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
233
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li SSun WTian N(2019)Resource allocation for multi-class services in multipath networksPerformance Evaluation10.1016/j.peva.2015.06.00192:C(1-23)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.peva.2015.06.001
Li SSun WZhang H(2018)Fair rate allocation for flows in concurrent multipath communicationsTelecommunications Systems10.1007/s11235-013-9855-257:3(271-285)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11235-013-9855-2
Zhang YHe SChen J(2016)Data gathering optimization by dynamic sensing and routing in rechargeable sensor networksIEEE/ACM Transactions on Networking10.1109/TNET.2015.242514624:3(1632-1646)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2425146

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.

Figures

Tables

Media

View Issue’s Table of Contents