Title :
Time scale analysis and scalability issues for explicit rate allocation in ATM networks
Author :
Charny, Anna ; Ramakrishnan, K.K. ; Lauck, Anthony
Author_Institution :
Digital Equipment Corp., Littleton, MA, USA
fDate :
8/1/1996 12:00:00 AM
Abstract :
End-to-end rate based congestion management has been extensively studied for control of computer communication networks. We examine some of the properties of end-to-end rate based algorithms for congestion management using explicit rate feedback, to achieve maxmin fair rate allocation in the network. We formulate a requirement on a switch´s local rate allocation computation sufficient to ensure convergence of the distributed algorithm to the global maxmin fair rate allocation. We provide an upper bound on the convergence time when the switch algorithm satisfies this requirement. We propose a requirement of feasibility of the transmission rates, maintaining which results in oscillation-free operation of the algorithm while maintaining small queues at the switches. Feasibility implies that the capacity of any of the resources is not exceeded at any time. We suggest a source policy to ensure feasibility of transmission rates, the essence of which is to delay a rate increase by a certain time, while decreasing the transmission rate immediately upon receiving the appropriate feedback. Finally, we seek ways of improving scalability of the computation of maxmin fair rates in the presence of a large number of flows. We suggest using a discrete set of rates, which as we show, reduces the computational complexity and the state requirement at the switches
Keywords :
asynchronous transfer mode; computational complexity; computer network management; convergence of numerical methods; distributed algorithms; feedback; queueing theory; telecommunication congestion control; ATM networks; computational complexity reduction; computer communication networks; congestion management; convergence time; distributed algorithm convergence; explicit rate allocation; explicit rate feedback; global maxmin fair rate allocation; local rate allocation; oscillation-free operation; queues; rate based algorithms; scalability; source policy; state requirement; switch algorithm; time scale analysis; transmission rates feasibility; upper bound; Communication networks; Communication switching; Communication system control; Computer network management; Computer networks; Convergence; Distributed computing; Feedback; Scalability; Switches;
Journal_Title :
Networking, IEEE/ACM Transactions on