The present invention relates to a buffer management scheme for ATM switches. Specifically, the present invention provides an optimal buffer management scheme for ATM switches using dynamic queue lengths. The present invention is embodied in an ATM switch that uses a dynamic queue threshold and a method of dynamically setting a common threshold for queues in an ATM switch.
Conventionally, ATM switch architectures used buffering to accommodate cells whose service has been delayed due to contention for bandwidth or temporary congestion within the switch. Literature. See E. W. Zegura, xe2x80x9cArchitectures for ATM Switching Systemsxe2x80x9d, IEEE Communications Magazine, pp. 28-37, February, 1993. Among these architectures, the shared buffer memory switches are preferred because of they utilize buffers more efficiently. By sharing the buffer, e.g., among all output ports, and taking advantage of the statistical multiplexing on input traffic, shared buffer ATM switches are able to achieve the same cell delay and loss performance with a smaller buffer size per port. Such a buffer size reduction effect is even more significant when the traffic is bursty and traffic load is uneven.
In an ATM switch, the buffer memory is usually shared at several different levels. For example, the buffer can be logically partitioned and shared by different service classes, i.e., CBR, VBR, ABR, UBR, etc. As mentioned above, the buffer can be shared among queues corresponding to different output ports. If per-VC queuing is adopted, the buffer can be shared among queues corresponding to different VCs.
However, the shared-memory switches without buffer management procedures do not perform well under overload conditions. See M. I. Irland, xe2x80x9cBuffer management in a packet switch,xe2x80x9d IEEE Trans. Commun., vol. COM-26, pp. 328-337, March 1978. A key problem is fairness among the various output ports. The statistical sharing of the buffer memory introduces the possibility that a small group of output ports consume most of the memory. Such an excessive use memory by some ports prevent cells destined for less utilized ports from gaining their fair share of memory. In a worst case scenario even access is prevented.
One conventional solution to such problem is setting restrictions on the amount of buffering a port can use. That is, each queue has a threshold of the maximum amount of memory it can access as well as a minimum amount guaranteed for itself.
Different threshold-setting methods have been proposed and analyzed in literature. See F. Kamoun and L. Kleinrock, xe2x80x9cAnalysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Conditionsxe2x80x9d, IEEE Trans. Commun., Vol.Com-28, No. 7, pp. 992-1003, July, 1980. There are generally two techniques of setting queue thresholds.
One technique is called static threshold (ST). In this method, buffer thresholds are pre-set for each queue, by the network management system (NMS). An arriving cell is accepted only if the corresponding queue length is less than the given threshold value. The ST method is simple to implement and only requires the corresponding queue counters and a comparator. In choosing the static thresholds for different queues, the NMS is required to know the characteristics and the statistics of the traffic. The traffic arriving at the queues are required to be in line with their descriptions. Therefore, the ST method is more appropriate for traffic at class level, i.e., CBR, VBR and UBR, in which the traffic is more predictable for the whole class although they may fluctuate substantially with respect to different port queues and individual connections within the class.
Another technique is called dynamic threshold (DT). In this method, buffer thresholds are dynamically adjusted according to the changing traffic load. The DT technique allows the overloading traffic to get access to memory as long as its queue has not exceeded its fair share of the memory, i.e., the dynamic threshold. Therefore, a good dynamic threshold method should improve the overall switch bandwidth utilization while ensuring fair sharing of buffer memory among different queues. In general, DT schemes require more processing power and are more appropriate for buffer management at port or VC level. In these levels traffic load variation may fluctuate substantially (although mostly lasting in a shorter time span) among different queues. The relative short time scale with respect to the traffic load variation at port and VC level requires any DT scheme to be simple for implementation practice.
For the above two schemes, performances in various traffic conditions have been compared through a comprehensive simulation study. See Choudhury and Hahne in A. K. Choudhury and E. L. Hahne, xe2x80x9cDynamic Queue Length Thresholds in a Shared-Memory Packet Switchxe2x80x9d, IEEE/ACM Trans. Networking, Vol. 6, No., pp. 130-140, April, 1998. In particular, they have proposed a simple and elegant DT scheme that ensures the fair sharing of buffer memory with a certain amount of buffer being unallocated. However, in this scheme the buffer memory utilization is low when only a small number of queues are overloaded.
In order to overcome the problems in conventional methods it is an object of the present invention to provide an ATM switch that uses a dynamic queue threshold scheme that enables efficient utilization of available memory regardless of the numbers of overloaded queues.
Another objective of the present invention is to provide a hierarchical buffer management scheme using ST and DT algorithms. A further object is to provide a new dynamic queue threshold algorithm, which improves buffer utilization. In order to accomplish the objects of the present invention there is provided An ATM switch using a dynamic queue threshold scheme, said ATM switch comprising K output port queues and a buffer of B cells sharing said K output port queues, wherein a common threshold is dynamically set for the K output port queues, the common threshold being changed to a new value from an old value when a new cell arrives at any of said K output queues, said new value being a maximum of a length of said any of said K output queues plus one and said old value when total queue length is less than a preset value times B and, said new value being a maximum of a said old value minus one and a statically set minimum buffer threshold when total queue length is greater than or equal to a preset value times B, wherein said preset value is greater than 0.
Preferably the length of each of said K output queues fluctuates based on variations in an incoming traffic load and a service bandwidth allocated to said each of said K output queues.
Preferably, a new cell is accepted to a specific queue when a length of said specific queue is less than the new value and total queue length is less than B.
Preferably, the statically set minimum buffer threshold is equal to zero by default. Preferably, a small amount of buffer B is allocated for some predetermined operations.
Preferably, buffer memory is allocated to VCs within said each of said K output queues, further using the dynamic queue threshold scheme.
Preferably, the dynamic queue threshold scheme is applied to multiple levels of dynamic buffers.
Another aspect of the present invention is a method of dynamically setting a common threshold T(t) for K queues in an ATM switch comprising said K queues, a buffer of B cells shared by said K queues, each of said K queues having a queue length of Qk(t) at time t and k=1,2 . . . K, with Qk(t) fluctuating with incoming traffic load and service bandwidth allocated to output port k, said method comprising:
setting a dynamic threshold T(t) wherein
Tnew(t)=max(Qk(t)+1, Told) when Q(t) less than xcex1*B;
Tnew(t)=max(Toldxe2x88x921, Tm) when Q(t) greater than =xcex1*B;
xe2x80x83wherein Q(t) is a total queue length at time t and 0 less than xcex1 less than =1, and
Tm is a minimum buffer threshold statically set, updating Tnew(t) and accepting a new arriving cell at output port k at time t if Qk(t) less than Tnew(t) and Q(t) less than B, otherwise blocking said new arriving cell. Yet another aspect of the present invention is a method of dynamically setting a common threshold T(t) for K queues in an ATM switch comprising said K queues, a buffer of B cells shared by said K queues, each of said K queues having a queue length of Qk(t) at time t and k=1,2 . . . K, and l=1, 2, . . . Lk with Qk(t) fluctuating with incoming traffic load and service bandwidth allocated to output port k, each queue comprising Lk VCs and each VC queue of port K has a queue of length Qkl(t) said method comprising:
setting a dynamic threshold TP(t) for each output queue wherein
TPnew(t)=max(Qk(t)+1, TPold) when Q(t) less than xcex1*B;
TPnew(t)=max(TPoldxe2x88x921, Tm) when Q(t) greater than =xcex1*B;
xe2x80x83setting a dynamic threshold TVk(t) for each VC assigned to queue k wherein
TVknew(t)=max(Qkl(t)+1, TVkold) when Q(t) less than xcex2*TP(t);
TVknew(t)=max(TVkoldxe2x88x921, Tm) when Q(t) greater than =xcex2*TP(t);
xe2x80x83wherein Qk(t) is a total queue length for kth queue at time t and 0 less than xcex1 less than =1, 0 less than xcex2 less than =1 and Tm is a minimum buffer threshold statically set, updating TP(t) and TVk(t) and accepting a new arriving cell at output port k at time t if Qk(t) less than TP(t) and Qkl(t) less than TVk(t) and Q(t) less than B, otherwise blocking said new arriving cell.