Buffer management scheme employing dynamic thresholds

Details Buffer management scheme employing dynamic thresholds Buffer management scheme employing dynamic thresholds

2000-08-11

2004-09-07

Nguyen, Steven (Department: 2665)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S252000, C370S235000, C709S229000, C709S234000

Reexamination Certificate

active

06788697

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to buffer management and, more particularly, to an improved buffer management scheme employing dynamic thresholds.
BACKGROUND OF THE INVENTION
Switch architectures use buffering mechanisms to accommodate packets whose service has been delayed due to contention for bandwidth or temporary congestion within the switch. Shared buffer memory switches are popular for their efficient buffer utilization. By sharing the buffer, for instance, among all output ports, and taking advantage of the statistical multiplexing on input traffic, shared-memory switches are able to achieve the same packet delay and loss performance with a smaller pool of buffers per port when compared with switches of other types. Such a reduction in buffer size is even more significant for bursty traffic and non-uniform traffic load at the switch ports. Thus, shared-memory switches have become very popular, since they can achieve a given loss probability requirement with the smallest amount of total memory.
However, as is well known, management and control of such a shared resource is a challenging task because of the conflicting objectives of maximizing buffer utilization and increasing the degree of statistical multiplexing, on one hand, and providing heterogeneous loss requirements and isolation to connections admitted into the system, on the other hand. Shared-memory switches without good buffer management procedures may not perform well under overload conditions, especially in regard to fairness. The statistical sharing of the buffer memory introduces the possibility of a small group of output ports hogging most of the memory, preventing packets destined for less utilized ports from gaining their fair shares of memory or even blocked completely.
One conventional solution to the above-stated problems is to set some restrictions on the amount of buffering a port can use (e.g., each queue has a threshold for the maximum number of buffers it can access, each queue is guaranteed a minimum number of buffers, etc.) A number of threshold-setting methods have been proposed for buffer management. These methods can be broadly categorized as static threshold methods (e.g., see G. J. Foschini, and B. Gopinath, “Sharing Memory Optimally,”
IEEE Trans. Communications
, Vol. 3, March, 1983, pp. 352-360; F. Kamoun and L. Kleinrock, “Analysis of Shared Finite Storage in a Computer Network ode Environment under General Traffic Conditions,”
IEEE Trans. Communications
, Vol. 28, July, 1980, pp. 992-1003; and G. Latouche, “Exponential Servers Sharing a Finite Storage: Comparison of Space Allocation Policies,”
IEEE Trans. Communications
, Vol. 28, June, 1980, pp. 992-1003), and dynamic threshold methods (e.g., see A. K. Choudhury and E. L. Hahne, “Dynamic Queue Length Thresholds in a Shared Memory ATM Switch,”
Proc. IEEE INFOCOM
′ 96, Vol. 2, March, 1996, pp. 679-687; and R. Fan, A. Ishii, B. Mark, G. Ramamurthy, and Q. Ren, “An Optimal Buffer Management Scheme with Dynamic Thresholds,”
Proc. IEEE GLOBECOM
′ 99, December, 1999, pp. 631-637).
In a static threshold method, each queue is only allowed to grow up to a maximum length which is statically defined. Arriving packets destined to a queue whose length is equal to their threshold are discarded. With different settings of thresholds, the static threshold method varies from complete sharing (e.g., the individual threshold is set to full buffer capacity to achieve maximal utilization but no fairness among different ports) to complete partitioning (e.g., buffer capacity is completely partitioned to ensure fairness among different ports but could lead to least usage efficiency). Usually a good static threshold scheme has to take a good compromise between efficiency and fairness of buffer sharing. If the sum of the thresholds is close or equal to the total buffer size, static thresholding becomes very restrictive in the use of the available buffers, and results in low buffer utilization (the special case where the sum of the thresholds adds up to the total buffer size is referred to as complete partitioning). On the other hand, if the sum of the thresholds is much larger than the total buffer size, sharing is achieved, but the scheme does not provide minimum allocations and suffers from potential starvation. A variation of this scheme, referred to as static thresholding with minimum allocations, divides the total buffer space in two portions and implements complete partitioning in one of them to guarantee a minimum allocation. Still, however, because of the static nature of the scheme, the tradeoff between sharing and isolation that can be achieved may not be optimal.
In a dynamic threshold method, buffer thresholds are dynamically adjusted according to the changing traffic load. A dynamic threshold method intends to allow congested queues to gain access to buffers not utilized by lightly loaded queues as long as their queues do not exceed their fair share of the memory (i.e., the dynamic threshold). Therefore, a good dynamic threshold scheme should improve the overall switch buffer utilization while ensuring fair sharing of buffer memory among different queues. In general, dynamic threshold schemes require more processing and are more appropriate for buffer management of queues where traffic load may fluctuate substantially (although only lasting for a short time span).
Despite the above-described benefits of both static threshold methods and dynamic threshold methods, merely using an efficient and fair buffer allocation scheme in a shared-memory architecture, without appropriate queue management, does not necessarily lead to improved performance. That is, some form of active queue management is needed even for routers that use efficient dynamic buffer allocation mechanisms. This is because dynamic buffer allocation algorithms by themselves do nothing to control the overall queue size of individual queues (i.e., there is no direct control on the lengths of the individual queues). For example, while dynamic buffer allocation mechanisms can allocate buffer memory efficiently and fairly among output ports, fair buffer allocation does not necessarily result in efficient and fair buffer usage, particularly for transmission control protocol (TCP) (e.g., see V. Jacobson, “Congestion Avoidance and Control,”
Proc. ACM SIGCOMM
′ 88, 1988, pp. 314-329; and W. Stevens, “TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms,”
IETF RFC
2001, January, 1997). Thus, active queue management is needed to control the overall queue sizes so that arriving bursts can be accommodated without dropping packets unnecessarily (e.g., see B. Braden et al., “Recommendation on Queue Management and Congestion Avoidance in the Internet,”
IETF RFC
2309, April, 1998; and S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance,”
IEEE/ACM Trans. Networking
, Vol. 1, No. 4, August, 1993, pp. 397-413).
The basic idea behind active queue management schemes such as, for example, random early detection (RED), is to detect incipient congestion early and to convey congestion notification to the end-systems, allowing them to reduce their transmission rates before queue overflow and sustained packet loss occur. In addition, active queue management can be used to control the queue sizes for each individual port so that they do not experience unnecessarily high delays.
In the basic RED scheme, as well as in improvements thereto such as described in the above-referenced related U.S. patent application Ser. No. 09/455,445, filed Dec. 6, 1999, a queue length average is maintained and used, along with a number of queue thresholds, to detect congestion. If congestion is detected, incoming packets are dropped (or marked, e.g., see S. Floyd, “TCP and Explicit Congestion Notification”,
ACM Computer Communication Review
, Vol. 24, No. 5, October, 1994, pp. 10-23) in a random probabilistic manner where the probability is a function of recent buffer fill history. The objective is to provide a m

Affiliated with

Also associated with

Rating

Buffer management scheme employing dynamic thresholds does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3252670