Feedback output queuing system, apparatus, and method

• US 7,158,480 B1
• Filed: 02/20/2002
• Issued: 01/02/2007
• Est. Priority Date: 07/30/2001
• Status: Expired due to Fees

• Current Assignee: Avaya Holdings Ltd (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Holtey, Thomas O., Haversat, Eric, Firoiu, Victor
• Primary Examiner(s): Kizou; Hassan
• Assistant Examiner(s): ADHAMI, MOHAMMAD SAJID
• Application Number:
  US10/079,923
• Time in Patent Office: 1,777 Days
• Field of Search: 370/232, 370/235, 370/412, 370/413
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• 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/506 Backpressure

Abstract

A feedback output queuing system, apparatus, and method controls the rate at which packets are forwarded from the ingress ports to a particular output queue over the switching/routing fabric based upon the level of congestion at the output queue. The output queue is monitored and the level of congestion at the output queue is determined based upon a predetermined congestion determination mechanism. An ingress forwarding scheme is determined based upon the level of congestion at the output queue. Information is forwarded from the ingress ports to the output queue based upon the ingress forwarding scheme.

Claims

1. A feedback output queuing method comprising:

determining a level of congestion at an output queue of a network device;

determining an ingress queue drop probability for an ingress queue associated with an ingress port of the network device based upon the level of congestion at the output queue; and

dropping packets at the ingress port of the network device according to the ingress drop probability to reduce congestion at the output queues,

wherein determining an ingress queue drop probability based upon the level of congestion at the output queue comprises;

determining thresholds T and h;

determining a number of ingress drop probability levels n, where;

$n=\lceil <br><br>{\log }_{\frac{1-T}{1-h}}<br><br>\left(1/N\right)\rceil <br><br>;<br><br>$

and

determining an ingress drop probability S_n for each ingress drop probability level n, where;

$\mathrm{sn}=1-{\left(\frac{1-T}{1-h}\right)}^n.$

2. The method of claim 1, wherein determining the level of congestion at the output queue comprises:

collecting congestion information for the output queue;

computing a running time average of the output queue size; and

deriving a drop probability for the output queue based upon the running time average of the output queue size.

3. The method of claim 1, wherein determining the level of congestion at the output queue comprises:

monitoring an input data rate to the output queue; and

monitoring an output data rate from the output queue.

4. The method of claim 1, wherein determining an ingress queue drop probability comprises:

determining a forwarding rate for forwarding information to the output queue based upon the level of congestion at the output queue.

5. The method of claim 1, wherein determining an ingress queue drop probability for the ingress queue associated with the ingress port of the network device comprises:

maintaining a step number for the output queue, the step number indicating an ingress drop probability level having a corresponding ingress drop probability;

initializing the step number for the output queue to a predetermined initial step number;

setting the ingress drop probability for the input queue equal to an ingress drop probability corresponding to the initial step number;

monitoring changes in the level of congestion at the output queue;

incrementing the step number for the output queue and setting the ingress drop probability for the input queue equal to an ingress drop probability corresponding to the incremented step number, if the level of congestion at the output queue is greater than a first predetermined threshold; and

decrementing the step number for the output queue and setting the ingress drop probability for the input queue equal to an ingress drop probability corresponding to the decremented step number, if the level of congestion at the output queue is less than a second predetermined threshold.

6. The method of claim 5, wherein the step number for the output queue is maintained at an ingress port.

7. The method of claim 5, wherein the step number for the output queue is maintained at the output queue.

8. The method of claim 1, wherein determining an ingress queue drop probability based upon the level of congestion at the output queue comprises:

determining that the level of congestion at the output queue has increased; and

increasing the ingress queue drop probability.

9. The method of claim 1, wherein determining the ingress queue drop probability based upon the level of congestion at the output queue comprises:

determining that the level of congestion at the output queue has decreased; and

decreasing the ingress queue drop probability.

10. The method of claim 4, wherein determining a forwarding rate for forwarding information to the output queue based upon the level of congestion at the output queue comprises:

determining that the level of congestion at the output queue has increased; and

decreasing the forwarding rate.

11. The method of claim 4, wherein determining a forwarding rate for forwarding information to the output queue based upon the level of congestion at the output queue comprises:

determining that the level of congestion at the output queue has decreased; and

increasing the forwarding rate.

12. A feedback output queuing system comprising:

egress logic operably coupled to maintain an output queue of a network device and to determine a level of congestion at the output queue; and

ingress logic operably coupled to control the rate at which information is forwarded to the output queue using an ingress forwarding scheme that is based upon the level of congestion at the output queue;

wherein the ingress logic is also coupled to an ingress queue of the network device for controlling an ingress queue drop rate based upon the level of congestion at the output queue; and

wherein the ingress logic is operably coupled to drop information at an ingress queue when the information is destined for the output queue at an ingress drop probability that is determined by;

determining thresholds T and h;

determining a number of ingress drop probability levels n, where;

$n=\lceil <br><br>{\log }_{\frac{1-T}{1-h}}<br><br>\left(1/N\right)\rceil <br><br>;<br><br>$

and

determining an ingress drop probability Sn for each ingress drop probability level n, where

$\mathrm{sn}=1-{\left(\frac{1-T}{1-h}\right)}^n.$

13. The system of claim 12, wherein the egress logic is operably coupled to determine the level of congestion at the output queue by collecting congestion information for the output queue, computing a running time average of the output queue size, and deriving a drop probability for the output queue based upon the running time average of the output queue size, the drop probability indicating the level of congestion at the output queue.

14. The system of claim 12, wherein the egress logic is operably coupled to determine the level of congestion at the output queue by monitoring an input data rate to the output queue and monitoring an output data rate from the output queue.

15. The system of claim 12, wherein the ingress logic is operably coupled to determine the ingress forwarding scheme based upon output queue congestion information provided by the egress logic.

16. The system of claim 12, wherein the egress logic is operably coupled to determine the ingress forwarding scheme and provide the ingress forwarding scheme to the ingress logic.

17. The system of claim 12, wherein the ingress drop probability is determined based upon the level of congestion at the output queue.

18. The system of claim 12, wherein the ingress logic is operably coupled to forward information to the output queue at a forwarding rate that is determined based upon the level of congestion at the output queue.

19. The system of claim 17, wherein the ingress drop probability is determined by maintaining a step number for the output queue, the step number indicating an ingress drop probability level having a corresponding ingress drop probability;

initializing the step number for the output queue to a predetermined initial step number;

setting the ingress drop probability for the input queue equal to an ingress drop probability corresponding to the initial step number;

monitoring changes in the level of congestion at the output queue;

incrementing the step number for the output queue and setting the ingress drop probability for the input queue equal to an ingress drop probability corresponding to the incremented step number, if the level of congestion at the output queue is greater than a first predetermined threshold; and

decrementing the step number for the output queue and setting the ingress drop probability for the input queue equal to an ingress drop probability corresponding to the decremented step number, if the level of congestion at the output queue is less than a second predetermined threshold.

20. The system of claim 19, wherein the step number for the output queue is maintained by the ingress logic.

21. The system of claim 19, wherein the step number for the output queue is maintained by the egress logic.

22. The system of claim 17, wherein the ingress drop probability is increased when the level of congestion at the output queue increases.

23. The system of claim 17, wherein the ingress drop probability is decreased when the level of congestion at the output queue decreases.

24. The system of claim 18, wherein the forwarding rate is decreased when the level of congestion at the output queue increases.

25. The system of claim 18, wherein the forwarding rate is increased when the level of congestion at the output queue decreases.