LAPLUS An Efficient, Effective and Stable Switch Algorithm for Flow Control of the Availabl
- 格式：pdf
- 大小：2.82 MB
- 文档页数：9
LAPLUS : An Efficient, Effective and Stable Switch Algorithm for Flow Control of the Available Bit Rate ATM Service
Sharat Prasad1 Broadband Network Lab, Samsung Telecommunications America, Richardson, TX 75081
1. 1. Introduction
The ATM Forum has defined the Available Bit Rate (ABR) service for applications that require from the network, in addition to an optional minimum bandwidth, an amount of bandwidth that is difficult to specify precisely. The ABR service dynamically varies the bandwidth allowed to an application based on both the needs of the application and the congestion state of the network. The members of the ATM Forum have reached an agreement to employ the rate-based closed-loop feedback flow control for supporting the ABR service. The Forum has specified [1] the behavior required of end-stations and switches to be compliant with the ABR service. In this paper we focus our attention on the algorithm a switch may use to manage congestion, maximize the utilization of resources and to meet the QOS guarantees applicable to ABR connections. There are two applicable guarantees - a fair access to the available bandwidth and a specified low Cell Loss Ratio (CLR). There are several possible fairness criteria [2]. Two we will use here are the Max-Min [3] and the MCR-plus-equal-share criteria. The simple distributed algorithm [3] for Max-Min fair rate allocation, and many others reported in the literature [4, 5, 12], require the current rate of each flow to be stored. This calls for a large amount of high-speed memory in the switches. Some variations of the simple distributed algorithm update the rate allocation each time a forward RM cell arrives. Others recompute the allocation periodically. Both the update and the recomputation require time proportional to the square of the number of flows making the simple distributed algorithm
Kamran Kiasaleh and Poras Balsara Dept of Elect. Engg., University of Texas at Dallas, P.O.Box 830688, Richardson, TX 75083
impractical. On the positive side, the algorithm quickly converges to the Max-Min fair allocation. At the other end of the spectrum are algorithms which rely on approximations to reduce the computation time and memory size [6 – 9, 13]. Network configurations can be constructed which make algorithms of this class converge to unfair rate allocation [10]. In the middle are clever implementations of the basic algorithm, which require significantly smaller amount of memory and enable efficient computation of the rate allocation [11]. All algorithms that recompute the allocation periodically are prone to problems that arise from the period being too short or too long. A long period makes an algorithm less responsive. A short period, when low speed flows are present, leads to errors in the measurement of traffic load on a link. If a short period is used for measuring the available bandwidth, an unstable control results [16]. All switch algorithms for flow controlling the ABR ATM service have to deal with growth of switch queues during transients. Techniques for containing the queue growth include requiring source end-stations to delay rate increases but to affect rate reductions immediately upon being notified [11, 12], setting aside a fraction of the link bandwidth [7-9, 13], etc. Both the techniques lower link bandwidth utilization. Delaying rate increases limits low utilization to periods of transients. But delaying rate increases requires mechanisms in the source endstation which have not been specified by the ATM Forum. In this paper we present the algorithm named LAPLUS. LAPLUS approximates the bottleneck rate of a link as the LArgest among flow rates PLUs the Surplus bandwidth divided by the number of flows with the largest rate. This estimate, when bound below at a suitable value enables links to succeed in determining their bottleneck rates in the order of their bottleneck levels. While rates of flows differ greatly from their respective MCR-plus-fair-share values, this approximation causes flows to change their rates by amounts that have correbe imprecise. When rates of flows satisfy a lock condition, the LAPLUS estimates the correct bottleneck rate. The algorithm is naturally able to take Peak Cell Rates of flows into account. The algorithm only requires constant-time processing and two flags per flow to be stored while ensuring MCR-plus-equal-share rate allocation in the steady state. It solves in a novel way the problem of selecting a control or measurement interval. It uses nested measurement intervals. High rate flows are controlled using inner (therefor short) intervals to keep utilization high and to contain queue growth. Outer (therefor long) intervals are used to control low rate flows
Sharat Prasad1 Broadband Network Lab, Samsung Telecommunications America, Richardson, TX 75081
1. 1. Introduction
The ATM Forum has defined the Available Bit Rate (ABR) service for applications that require from the network, in addition to an optional minimum bandwidth, an amount of bandwidth that is difficult to specify precisely. The ABR service dynamically varies the bandwidth allowed to an application based on both the needs of the application and the congestion state of the network. The members of the ATM Forum have reached an agreement to employ the rate-based closed-loop feedback flow control for supporting the ABR service. The Forum has specified [1] the behavior required of end-stations and switches to be compliant with the ABR service. In this paper we focus our attention on the algorithm a switch may use to manage congestion, maximize the utilization of resources and to meet the QOS guarantees applicable to ABR connections. There are two applicable guarantees - a fair access to the available bandwidth and a specified low Cell Loss Ratio (CLR). There are several possible fairness criteria [2]. Two we will use here are the Max-Min [3] and the MCR-plus-equal-share criteria. The simple distributed algorithm [3] for Max-Min fair rate allocation, and many others reported in the literature [4, 5, 12], require the current rate of each flow to be stored. This calls for a large amount of high-speed memory in the switches. Some variations of the simple distributed algorithm update the rate allocation each time a forward RM cell arrives. Others recompute the allocation periodically. Both the update and the recomputation require time proportional to the square of the number of flows making the simple distributed algorithm
Kamran Kiasaleh and Poras Balsara Dept of Elect. Engg., University of Texas at Dallas, P.O.Box 830688, Richardson, TX 75083
impractical. On the positive side, the algorithm quickly converges to the Max-Min fair allocation. At the other end of the spectrum are algorithms which rely on approximations to reduce the computation time and memory size [6 – 9, 13]. Network configurations can be constructed which make algorithms of this class converge to unfair rate allocation [10]. In the middle are clever implementations of the basic algorithm, which require significantly smaller amount of memory and enable efficient computation of the rate allocation [11]. All algorithms that recompute the allocation periodically are prone to problems that arise from the period being too short or too long. A long period makes an algorithm less responsive. A short period, when low speed flows are present, leads to errors in the measurement of traffic load on a link. If a short period is used for measuring the available bandwidth, an unstable control results [16]. All switch algorithms for flow controlling the ABR ATM service have to deal with growth of switch queues during transients. Techniques for containing the queue growth include requiring source end-stations to delay rate increases but to affect rate reductions immediately upon being notified [11, 12], setting aside a fraction of the link bandwidth [7-9, 13], etc. Both the techniques lower link bandwidth utilization. Delaying rate increases limits low utilization to periods of transients. But delaying rate increases requires mechanisms in the source endstation which have not been specified by the ATM Forum. In this paper we present the algorithm named LAPLUS. LAPLUS approximates the bottleneck rate of a link as the LArgest among flow rates PLUs the Surplus bandwidth divided by the number of flows with the largest rate. This estimate, when bound below at a suitable value enables links to succeed in determining their bottleneck rates in the order of their bottleneck levels. While rates of flows differ greatly from their respective MCR-plus-fair-share values, this approximation causes flows to change their rates by amounts that have correbe imprecise. When rates of flows satisfy a lock condition, the LAPLUS estimates the correct bottleneck rate. The algorithm is naturally able to take Peak Cell Rates of flows into account. The algorithm only requires constant-time processing and two flags per flow to be stored while ensuring MCR-plus-equal-share rate allocation in the steady state. It solves in a novel way the problem of selecting a control or measurement interval. It uses nested measurement intervals. High rate flows are controlled using inner (therefor short) intervals to keep utilization high and to contain queue growth. Outer (therefor long) intervals are used to control low rate flows
