Optimal buffer management scheme with dynamic queue length...

Details Optimal buffer management scheme with dynamic queue length... Optimal buffer management scheme with dynamic queue length...

1999-02-12

2002-07-23

Yao, Kwang Bin (Department: 2664)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S395410

Reexamination Certificate

active

06424622

ABSTRACT:

FIELD OF THE INVENTION
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.
BACKGROUND
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, “Architectures for ATM Switching Systems”, 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, “Buffer management in a packet switch,” 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, “Analysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Conditions”, 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, “Dynamic Queue Length Thresholds in a Shared-Memory Packet Switch”, 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.
SUMMARY OF THE PRESENT INVENTION
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 Q
k
(t) at time t and k=1,2 . . . K, with Q
k
(t) fluctuating with incoming traffic load and service bandwidth allocated to output port k, said method comprising:
setting a dynamic threshold T(t) wherein
T
new
(
t
)=max(
Q
k
(
t
)+1,
T
old
) when
Q
(
t
)<&agr;*
B;
T
new
(
t
)=max(
T
old
−1,
T
m
) when
Q
(
t
)>=&agr;*
B;
 wherein Q(t) is a total queue length at time t and 0<&agr;<=1, and
T
m
is a minimum buffer threshold statically set, updating T
new
(t) and accepting a new arr

Affiliated with

Also associated with

Rating

Optimal buffer management scheme with dynamic queue length... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimal buffer management scheme with dynamic queue length..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal buffer management scheme with dynamic queue length... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2844981