Method and apparatus for forwarding packets from a plurality of contending queues to an output

• US 6,067,301 A
• Filed: 05/29/1998
• Issued: 05/23/2000
• Est. Priority Date: 05/29/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Aatresh, Deepak J.
• Primary Examiner(s): COLAIANNI, MICHAEL
• Assistant Examiner(s): COLAIANNI, MICHAEL
• Application Number:
  US09/087,064
• Time in Patent Office: 725 Days
• Field of Search: 370/412, 370/413, 370/414-418, 370/468, 370/461
• US Class Current: 370/418
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04L 47/762 triggered by the network

Abstract

A method and apparatus for forwarding packets from contending queues of a multiport switch to an output of a finite bandwidth involve first prioritizing the contending queues into different priorities that relate to priorities of the packets that are being forwarded in the network. Bandwidth of the output is then allocated among the prioritized contending queues and the bandwidth of the output is consumed by the queued packets according to the allocated proportions. Any unconsumed bandwidth is distributed to the queues on a priority basis such that the highest priority queue is offered the unconsumed bandwidth first and lower priority queues are offered the remaining unconsumed bandwidth in priority order. An advantage of the invention is that queues are not starved of bandwidth by higher priority queues and unconsumed bandwidth is not wasted when there are not enough packets to consume an allocated portion of the output bandwidth. The method is adjustable during normal network operations through a programming interface to provide a specified quality of service.

Claims

1. A method for forwarding packets from a plurality of contending queues to an output having a finite bandwidth comprising the steps of:

prioritizing each queue of said plurality of queues with a priority that is fixed relative to the other queues of said plurality of queues, thereby defining a fixed prioritization range that includes a highest priority queue and a lowest priority queue;

allocating a share of said bandwidth of said output to each of said queues;

consuming at least a portion of said bandwidth of said output with packets from said queues according to said allocated shares, leaving an unconsumed portion when at least one of said queues does not exhaust the allocated share of said at least one queue; and

distributing one hundred percent of said unconsumed portion of said bandwidth to said queues on a fixed priority basis, wherein one hundred percent of said unconsumed portion of said bandwidth is offered first to said highest priority queue and then any remaining portion of said unconsumed portion of said bandwidth is offered to lower priority queues, on a queue by queue basis, according to said fixed prioritization range until all of said bandwidth is consumed or until there are no more queued packets.

2. The method of claim 1 wherein said step of prioritizing said plurality of queues includes a step of prioritizing each of said queues with a different priority relative to the other queues of said queues.

3. The method of claim 2 further comprising a step of prioritizing said packets into a prioritization range that directly relates to said prioritization range of said queues.

4. The method of claim 2 wherein said step of consuming said bandwidth includes a step of forwarding said packets to an output port of a multiport switch.

5. The method of claim 1 wherein said step of allocating shares of said bandwidth includes the step of utilizing a programming interface to set register values, in circuitry, that correspond to said allocated shares of said bandwidth.

6. The method of claim 5 wherein said step of consuming bandwidth includes steps of:

changing a clock counter value in relation to a system clock; and

comparing said clock counter value to said register values to control bandwidth consumption.

7. The method of claim 6 wherein said step of comparing includes a step of inputting said counter value and one of said register values into a comparator circuit.

8. An application-specific integrated circuit (ASIC) having a plurality of queues related to packets contending for the same output, where said output has a bandwidth capacity comprising:

means for identifying a fixed priority order among said plurality of queues wherein one queue has a highest priority among said queues and a different queue has a lowest priority among said queues;

means for allocating a percentage of said bandwidth capacity of said output to each of said queues;

means, formed in circuitry that is specific to said queue management, for forwarding packets to said output according to said allocated percentages; and

means, formed in circuitry that is specific to queue management, for distributing one hundred percent of any unused bandwidth capacity to said plurality of queues according to said fixed priority order such that said queue with said highest priority is first offered one hundred percent of said unused bandwidth capacity and then lower priority queues are offered one hundred percent of any remaining unused bandwidth, one queue at a time, according to said fixed priority order from highest priority to lowest priority until all of said bandwidth capacity is distributed or until no packets remain for forwarding.

9. The ASIC of claim 8 wherein said means for allocating is formed in circuitry that is specific to said queue management.

10. The ASIC of claim 8 wherein said means for allocating includes run-time programmable registers that are set to register values that define time intervals.

11. The ASIC of claim 10 wherein said means for forwarding includes a clock counter that generates counter values.

12. The ASIC of claim 11 wherein said means for forwarding packets includes a plurality of comparators, wherein each comparator has a first input for receiving one of said counter values and a second input for receiving one of said register values.

13. The ASIC of claim 8 wherein said ASIC is part of a multiport switch having input ports for receiving packets, output ports for transmitting packets, and a switch fabric for directing packets from said input ports to said output ports.

14. The ASIC of claim 13 wherein said ASIC is connected to memory that stores packets in said multiport switch that have already been forwarded through said switch fabric.

15. A method of forwarding contending variable-length packets from an output buffer to an output port of a multiport switch comprising steps of:

prioritizing output queues that store information representative of said contending variable-length packets such that each output queue has a different fixed priority relative to the other of said output queues;

allocating bandwidth of said output port among said prioritized output queues such that said prioritized output queues have allocated shares of said bandwidth;

forwarding, from said output buffer to said output port, contending variable-length packets represented by said information stored within said prioritized output queues according to said bandwidth allocations;

monitoring said forwarding of said contending variable-length packets to detect bandwidth allocations in excess of bandwidth consumed by said contending variable-length packets;

offering one hundred percent of any excess bandwidth allocations that are detected by said monitoring to a highest priority output queue of said prioritized output queues that includes a variable-length packet to be forwarded to said output port of said multiport switch; and

offering any remaining portions of said excess bandwidth allocations to lower priority output queues on a queue-by-queue basis until all of said remaining portions of said excess bandwidth allocations are consumed, said remaining portions of said excess bandwidth allocations being offered to said prioritized output queues in priority order from highest priority to lowest priority.

16. The method of claim 15 wherein said step of storing includes steps of:

prioritizing said contending variable-length packets; and

storing said prioritized contending variable-length packets in similarly prioritized queues of said prioritized output queues.

17. The method of claim 15 wherein said step of allocating bandwidth includes a step of setting register values that represent time intervals in an application specific integrated circuit on a queue specific basis while said multiport switch is forwarding packets.

18. The method of claim 17 further comprising a step of utilizing a programming interface to override said step of offering excess bandwidth allocations to said highest priority output queue, thereby distributing bandwidth on a pure priority basis.

19. The method of claim 15 further including a step of adjusting a queue specific time interval in order to change a packet latency characteristic of said multiport switch.

20. A method for forwarding packets from a plurality of contending queues to an output having a finite bandwidth comprising the steps of:

prioritizing said plurality of queues such that each of said queues has a priority relative to the other queues of said plurality of queues, thereby defining a prioritization range that includes a highest priority queue and a lowest priority queue;

allocating a share of said bandwidth of said output to each of said queues, said step of allocating including a step of utilizing a programming interface to set register values, in circuitry, that correspond to said allocated shares of said bandwidth;

consuming at least a portion of said bandwidth of said output with packets from said queues according to said allocated shares, leaving an unconsumed portion when at least one of said queues does not exhaust the allocated share of said at least one queue, said step of consuming including steps of changing a clock counter value in relation to a system clock and comparing said clock counter value to said register values to control bandwidth consumption; and

distributing said unconsumed portion of said bandwidth to said queues according to said prioritization range.

21. The method of claim 20 wherein said step of prioritizing said plurality of queues includes a step of prioritizing each of said queues with a different priority relative to the other queues of said queues.

22. The method of claim 21 further comprising a step of prioritizing said packets into a prioritization range that directly relates to said prioritization range of said queues.

23. The method of claim 21 wherein said step of distributing said unconsumed portion of said bandwidth includes steps of:

offering said unconsumed portion to said highest priority queue before any other of said queues; and

offering said unconsumed portion to said lowest priority queue only after said unconsumed portion has been offered to higher priority queues of said queues.

24. The method of claim 23 wherein said step of consuming said bandwidth includes a step of forwarding said packets to an output port of a multiport switch.

25. The method of claim 20 wherein said step of comparing includes a step of inputting said counter value and one of said register values into a comparator circuit.

26. An application-specific integrated circuit (ASIC) having a plurality of queues related to packets contending for the same output, where said output has a bandwidth capacity comprising:

means for identifying a priority order among said plurality of queues wherein one queue has a highest priority among said queues and a different queue has a lowest priority among said queues;

means for allocating a percentage of said bandwidth capacity of said output to each of said queues, said means for allocating including run-time programmable registers that are set to register values that define time intervals;

means, formed in circuitry that is specific to said queue management, for forwarding packets to said output according to said allocated percentages; and

means, formed in circuitry that is specific to queue management, for distributing unused bandwidth capacity to said plurality of queues in priority order from said queue with said highest priority to said queue with said lowest priority.

27. The ASIC of claim 26 wherein said means for allocating is formed in circuitry that is specific to said queue management.

28. The ASIC of claim 26 wherein said means for forwarding includes a clock counter that generates counter values.

29. The ASIC of claim 28 wherein said means for forwarding packets includes a plurality of comparators, wherein each comparator has a first input for receiving one of said counter values and a second input for receiving one of said register values.

30. The ASIC of claim 26 wherein said ASIC is part of a multiport switch having input ports for receiving packets, output ports for transmitting packets, and a switch fabric for directing packets from said input ports to said output ports.

31. The ASIC of claim 30 wherein said ASIC is connected to memory that stores packets in said multiport switch that have already been forwarded through said switch fabric.

32. A method of forwarding contending variable-length packets from output queues to an output port of a multiport switch comprising steps of:

prioritizing said output queues such that each output queue has a different priority relative to the other of said contending queues;

storing said contending variable-length packets in output queues of said prioritized output queues;

allocating bandwidth of said output port among said prioritized output queues such that said prioritized output queues have allocated shares of said bandwidth, including setting register values that represent time intervals in an application specific integrated circuit on a queue specific basis while said multiport switch is forwarding packets;

forwarding contending variable-length packets from said prioritized output queues to said output ports according to said bandwidth allocations;

monitoring said forwarding of contending variable-length packets to detect bandwidth allocations in excess of bandwidth consumed by said contending variable-length packets in said prioritized output queues; and

offering excess bandwidth allocations that are detected by said monitoring to a highest priority output queue of said prioritized output queues that has a variable-length packet to be forwarded to said output port of said multiport switch.

33. The method of claim 32 wherein said step of storing includes steps of:

prioritizing said contending variable-length packets; and

storing said prioritized contending variable-length packets in similarly prioritized queues of said prioritized output queues.

34. The method of claim 32 further comprising a step of utilizing a programming interface to override said step of offering excess bandwidth allocations to said highest priority output queue, thereby distributing bandwidth on a pure priority basis.

35. The method of claim 32 further including a step of adjusting a queue specific time interval in order to change a packet latency characteristic of said multiport switch.