Fair share egress queuing scheme for data networks

• US 6,504,818 B1
• Filed: 12/03/1998
• Issued: 01/07/2003
• Est. Priority Date: 12/03/1998
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Levine, Ronald M
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): NGUYEN, VAN KIM T
• Application Number:
  US09/204,258
• Time in Patent Office: 1,496 Days
• Field of Search: 370/222-229, 370/230-231, 370/395.21, 370/395.41, 370/236.1, 370/412, 370/415, 370/419, 370/420, 370/235
• US Class Current: 370/229
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

A method of controlling congestion in data networks wherein data is received by an egress port and buffered in a local buffer associated with a source of the element. For each data element received, the egress port determines whether a global threshold is exceeded and, if so, requests all data sources to reduce their rate of data delivery to the egress port. Similarly, the egress port determines whether a local threshold is exceeded and, if so, requests the one source associated with the local buffer to reduce the data delivery rate to the egress port. Optionally, if the data delivery rate of the one source falls below a predetermined minimum rate, the one source may refuse the request. In response, the egress port requests other data sources to reduce their rate of data delivery to the egress port.

Claims

1. A method of controlling congestion in data networks, comprising the steps of:

receiving a data element from the network,

buffering the data element in one of a plurality of local buffers, the one local buffer associated with a source of the element,

determining whether a total amount of data in the local buffers exceeds a global threshold and, when the global threshold is exceeded, requesting all sources to reduce a rate at which the sources deliver data elements to the network, and

determining whether an amount of data in the local buffer associated with the source of the data element exceeds a local threshold and, when the local threshold is exceeded, requesting the source of the data element to reduce the rate at which the source delivers data elements to the network.

2. The method of claim 1, further comprising a step of, when neither the global threshold nor the local threshold is exceeded, requesting the source of the data element to increase the rate at which it delivers data elements to the network.

3. The method of claim 1, further comprising the steps of, subsequent to the step of requesting the source of the data element to reduce the rate at which it delivers data elements to the network, determining whether the source denied the request and, when the source denied the request, requesting other sources to reduce the rate at which they deliver data elements to the network.

4. The method of claim 1, wherein the receiving step occurs at an egress port of the data network.

5. The method of claim 1, wherein the data elements are frames of data routed by a frame relay network.

6. The method of claim 1, wherein the data elements are packets of data routed by a packet relay network.

7. The method of claim 1, wherein the data elements are cells of data routed by a cell relay network.

8. The method of claim 1, further comprising the steps of:

receiving a request at a source,

determining what kind of request was received,

when the request was a request to decrease the source'"'"'s rate of delivery of data elements to the network, determining whether a current rate of delivery exceeds a predetermined minimum threshold, and

when the current rate does not exceed the predetermined minimum threshold, denying the request.

9. An egress port of a data network, comprising:

a processor,

a memory in communication with the processor, providing a data buffer divided into a plurality of local buffers,

a communication interface in communication with the processor and the memory, the interface receiving data elements from the data network,

wherein the processor;

identifies a source of the data element,

causes the communication interface to store the data element in a local buffer associated with the source,

determines whether an amount of data held in the buffer exceeds a global threshold and, if so, requests all sources in the data network to reduce rates at which the sources deliver data elements to the network, and

determines whether an amount of data stored in the local buffer associated with the issuing source exceeds a local threshold and, if so, requests the issuing source via the interface to reduce the rate at which the issuing source delivers data elements to the network.

10. The egress port of claim 9, wherein when neither the global threshold nor the local threshold are exceeded, the processor requests the issuing source via the interface to increase the rate at which it delivers data elements to the network.

11. The egress port of claim 9, wherein the processor, after it requests the issuing source of the data element to reduce the rate at which it delivers data elements to the network, determines whether the issuing source denied the request and, when the source denied the request, the processor requests other sources to reduce the rate at which the other sources deliver data elements to the network.

12. The egress port of claim 9, wherein the data elements are frames of data routed by a frame relay network.

13. The egress port of claim 9, wherein the data elements are packets of data routed by a packet relay network.

14. The egress port of claim 9, wherein the data elements are cells of data routed by a cell relay network.

15. A method of controlling congestion in data networks, comprising the steps of:

receiving a data element from the network,

buffering the data element in a local buffer associated with a source of the element, determining whether an amount of data in the local buffers exceeds a global threshold and,

when the global threshold is exceeded, requesting all sources to reduce a rate at which the sources deliver data elements to the network,

subsequent to the requesting step, determining whether the source denied the request and, when the source denies the request, requesting other sources to reduce the rate at which the other sources deliver data elements to the network.