Method and apparatus for per traffic flow buffer management

• US 6,535,484 B1
• Filed: 01/24/2000
• Issued: 03/18/2003
• Est. Priority Date: 05/15/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Klausmeier, Daniel E., Hughes, David A.
• Primary Examiner(s): RAO, SEEMA SRINIVAS
• Application Number:
  US09/490,548
• Time in Patent Office: 1,149 Days
• Field of Search: 370/229-234, 370/252, 370/253, 370/389, 370/392, 370/395-397, 370/400, 370/409, 370/412, 370/415, 370/416, 370/395.2, 370/395.21, 711/130, 711/147, 711/150, 711/151, 711/153, 711/163, 711/165, 711/166, 711/170-173
• US Class Current: 370/230
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5682 Threshold; Watermark
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of managing oversubscription of a common buffer resource shared by a number of traffic flows in a cell switching network in response to the utilization of the common buffer resource. A buffer utilization threshold is established for each of the traffic flows. As new cells arrive, the global usage of the buffer resource is monitored. As the buffer utilization increases, the thresholds for each of the traffic flows are dynamically adjusted based upon the global usage of the buffer. Aggressive buffer allocations are scaled back when necessary, thereby leaving space for traffic flows which are relatively empty. In one embodiment, the thresholds are coded in mantissa and exponent form so that the scaling is accomplished by adjusting the exponent value.

Claims

1. A method comprising:

establishing, for each of a plurality of processes sharing a common buffer resource, corresponding buffer utilization thresholds, each of said buffer utilization thresholds representing a predetermined maximum amount of said common buffer resource that the corresponding process may use; and

dynamically adjusting a first buffer utilization threshold corresponding to a first process of said plurality of processes according to the usage of said common buffer resource by all of said plurality of processes.

2. A buffer management process for a cell switching communications network having a first node, said first node having a common buffer being shared by a plurality of network connections including a first connection, the process comprising:

receiving a first cell at said first node, said first cell being associated with said first connection;

determining a buffer count for said common buffer, said buffer count representing a current utilization of said common buffer by said plurality of connections;

establishing a first connection threshold for said first connection according to a predetermined maximum amount of said common buffer that said first connection may use and said buffer count; and

determining whether said first cell will be accommodated in said common buffer using said first connection threshold.

3. A buffer management system for congestion prevention in a cell switching communications network comprising a plurality of logical connections, the buffer management system comprising:

a first node receiving network traffic transmitted over said plurality of logical connections, said first node having a common buffer shared by said plurality of logical connections and further having a buffer control device, said buffer control device monitoring the usage of said common buffer by said plurality of logical connections and dynamically scaling a buffer utilization threshold according to a predetermined maximum amount of said common buffer that a corresponding first one of said plurality of logical connections may use and said usage.

4. A node for a cell switching communications network, the node comprising:

a lookup table stored in a memory, said lookup table comprising buffer threshold scaling factors to be used to determine whether or not to admit a cell of a first of a plurality of traffic flows transmitted within said cell switching communications network to a common buffer shared by said plurality of traffic flows, said buffer threshold scaling factors arranged according to a predetermined maximum amount of the common buffer that the first of said plurality of traffic flows may use and the total usage of the common buffer by all of the plurality of traffic flows.

5. An apparatus, comprising:

means for establishing, for each of a plurality of processes sharing a common buffer resource, corresponding buffer utilization thresholds, each of said buffer utilization thresholds representing a predetermined maximum amount of said common buffer resource that the corresponding process may use; and

means for dynamically adjusting a first buffer utilization threshold corresponding to a first process of said plurality of processes according to the usage of said common buffer resource by all of said plurality of processes.

6. The apparatus of claim 5, wherein the means for dynamically adjusting comprises means for scaling said first buffer utilization threshold by a first scaling factor determined according to said usage of said common buffer resource.

7. The apparatus of claim 5, further comprising means for representing said buffer utilization threshold.

8. An apparatus, comprising:

means for receiving a first cell at a first node, said first cell being associated with a first connection;

means for determining a buffer count for a common buffer, said buffer count representing a current utilization of said common buffer by a plurality of network connections;

means for establishing a first connection threshold for said first connection according to a predetermined maximum amount of said common buffer that said first connection may use and said buffer count; and

means for determining whether said first cell will be accommodated in said common buffer using said first connection threshold.

9. The apparatus of claim 8, wherein the means for establishing the first connection threshold comprises:

means for establishing an initial connection threshold corresponding to said predetermined maximum amount of said common buffer that said first connection may use; and

means for dynamically adjusting said initial connection threshold according to said buffer count, said dynamic adjusting producing a first scaled threshold.

10. The apparatus of claim 9, wherein the means for determining whether said first cell will be accommodate comprises:

means for establishing a connection cell count, the connection cell count indicating the number of cells associated with the first connection stored in said common buffer;

means for comparing said connection cell count to said first scaled threshold, and wherein the apparatus further comprises means for denying admittance of said first cell to said common buffer if said connection cell count exceeds said first scaled threshold.