On Generalized Max-Min Rate Allocation and Distributed Convergence Algorithm for Packet Networks
|
Abstract—This paper considers the fundamental problem of bandwidth allocation among flows in a packet-switched network. The classical max-min rate allocation has been widely regarded as a fair rate allocation policy. But, for a flow with a minimum rate requirement and a peak rate constraint, the classical max-min policy no longer suffices to determine rate allocation since it is not capable of supporting either the minimum rate or the peak rate constraint from a flow. In this paper, we generalize the theory of the classical max-min rate allocation with the support of both the minimum rate and peak rate constraints for each flow. Additionally, to achieve generalized max-min rate allocation in a fully distributed packet network, we present a distributed algorithm that uses a feedback-based flow control mechanism. Our design not only offers a fresh perspective on flow marking technique, but also advances the state-of-the-art flow marking technique favored by other researchers. We provide proof that such a distributed algorithm, through asynchronous iterations, will always converge to the generalized max-min rate allocation under any network configuration and any set of link distances. We use simulation results to demonstrate the fast convergence property of the distributed algorithm.
[1] 401 The ATM Forum Technical Committee, Traffic Management Specification, Version 4.0, ATM Forum Contribution, AF-TM 96-0056.00, Apr. 1996.
[2] D. Bertsekas and R. Gallager, Data Networks, chapter 6. Prentice Hall, 1992.
[3] F. Bonomi and K.W. Fendick, The Rate-Based Flow Control Framework for the Available Bit Rate ATM Service IEEE Network Magazine, vol. 9, no. 2, pp. 25-39, Mar./Apr. 1995.
[4] A. Charny, D. Clark, and R. Jain, Congestion Control with Explicit Rate Indication Proc. IEEE Int'l Conf. Comm., pp. 1954-1963, June 1995.
[5] E.M. Gafni, The Integration of Routing and Flow Control for Voice and Data in a Computer Communication Network PhD thesis, Dept. of Electrical Eng. and Computer Science, MIT, Cambridge, Mass., Aug. 1982.
[6] H.P. Hayden, Voice Flow Control in Integrated Packet Networks MS thesis, Dept. of Electrical Eng. and Computer Science, MIT, Cambridge, Mass., June 1981.
[7] NIST Network Simulator,http://w3.antd.nist.gov/Hsntgprd_atm-sim.html , NIST, 2003.
[8] Y.T. Hou, H. Tzeng, S.S. Panwar, and V.P. Kumar, ATM ABR Traffic Control with a Generic Weight-Based Bandwidth Sharing Policy: Theory and a Simple Implementation IEICE Trans. Comm., vol. E81-B, no. 5, pp. 958-972, May 1998.
[9] Y.T. Hou, S.S. Panwar, and H. Tzeng, Available Bit Rate Flow Control for Service Allocation in a Packet Network US Patent #6,515,965, Feb. 2003.
[10] J.M. Jaffe, Bottleneck Flow Control IEEE Trans. Comm., vol. 29, no. 7, pp. 954-962, July 1981.
[11] L. Kalampoukas, A. Varma, and K.K. Ramakrishnan, An Efficient Rate Allocation Algorithm for ATM Networks Providing Max-Min Fairness Proc. Sixth IFIP Int'l Conf. High Performance Networking, pp. 143-154, Sept. 1995.
[12] S. Kalyanaraman, R. Jain, S. Fahmy, R. Goyal, and B. Vandalore, The ERICA Switch Algorithm for ABR Traffic Management in ATM Networks IEEE/ACM Trans. Networking, vol. 8, no. 1, pp. 87-98, Feb. 2000.
[13] Y. Kim, W.K. Tsai, M. Iyer, and J. Ros, Minimum Rate Guarantee without Per-Flow Information Proc. IEEE Int'l Conf. Network Protocols, pp. 155-162, 1999.
[14] J. Mosely, Asynchronous Distributed Flow Control Algorithms PhD thesis, Dept. of Electrical Eng. and Computer Science, MIT, Cambridge, Mass., June 1984.
[15] K.K. Ramakrishnan, R. Jain, and D.-M. Chiu, Congestion Avoidance in Computer Networks with a Connectionless Network Layer Part IV: A Selective Binary Feedback Scheme for General Topologies Methodology DEC-TR-510, Digital Equipment Corp., 1987.
[16] L. Roberts, Enhanced PRCA (Proportional Rate Control Algorithm) ATM Forum Contribution, AF-TM 94-0735R1, Aug. 1994.
[17] K.-Y. Siu and H.-Y. Tzeng, Intelligent Congestion Control for ABR Service in ATM Networks ACM SIGCOMM Computer Comm. Rev., vol. 24, no. 5, pp. 81-106, Oct. 1994.
[18] W.K. Tsai and J. Ros, Maxmin Lambda Allocation for Dense Wavelength-Division-Multiplexing Networks J. Optical Networking, vol. 1, nos. 8/9, pp. 323-337, Aug. 2002.
[19] N. Yin and M.G. Hluchyj, On Closed-Loop Rate Control for ATM Cell Relay Networks Proc. IEEE INFOCOM, pp. 99-108, June 1994.
[20] N. Yin, Max-Min Fairness vs. MCR Guarantee on Bandwidth Allocation for ABR Proc. IEEE ATM Workshop, Aug. 1996.
Index Terms:
Max-min rate allocation, minimum rate, peak rate, centralized algorithm, distributed algorithm, convergence, flow control, packet networks.
Citation:
Y. Thomas Hou, Shivendra S. Panwar, Henry H.-Y. Tzeng, "On Generalized Max-Min Rate Allocation and Distributed Convergence Algorithm for Packet Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 5, pp. 401-416, May 2004, doi:10.1109/TPDS.2004.1278098
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb