Unified algorithm for frame scheduling and buffer management in differentiated services networks

• US 6,990,529 B2
• Filed: 02/22/2001
• Issued: 01/24/2006
• Est. Priority Date: 02/24/2000
• Status: Expired due to Term

• Current Assignee: Synaptics Incorporated
• Original Assignee: Zarlink Semiconductor Inc. (Microchip Technology Incorporated)
• Inventors: Wang, Linghsiao, Yang, Brian, Barrack, Craig I.
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US09/792,152
• Publication Number:
  US 20010051992A1
• Time in Patent Office: 1,797 Days
• Field of Search: 709/226, 709/233, 709/235, 709/232, 709/224, 709/223
• US Class Current: 709/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A frame forwarding and discard architecture in a Differentiated Services network environment. The architecture comprises a discard logic for discarding a frame from a stream of incoming frames of the network environment in accordance with a discard algorithm, the frame being discarded if a predetermined congestion level in the network environment has been reached, and a predetermined backlog limit of a queue associated with the frame, has been reached. Scheduling logic is also provided for scheduling the order in which to transmit one or more enqueued frames of the network environment.

Claims

1. A method for guaranteeing different packet delays for different packet classes, wherein each packet class having a corresponding priority class, input queue having a queue length and a delay bound, comprising:

receiving a packet for forwarding to an output port, the packet having a packet class determining the sum of the product of queue lengths and delay bounds for all classes;

determining the product of the queue length and delay bound for the packet'"'"'s class; and

discarding the packet when the sum of the product of queue lengths and delay bounds for all classes exceeds a predetermined congestion plane and when the product of the queue length and delay bound for the packet'"'"'s class exceeds a bandwidth allocated for the packet'"'"'s class.

2. The method of claim 1, further comprising:

forwarding the packet to a queue to an input queue for the packet class when the product of the queue length and delay bound for the packet'"'"'s class exceeds the bandwidth allocated for the packet'"'"'s class and when the sum of the product of queue lengths and delay bounds for all classes is less than the predetermined congestion plane.

3. The method of claim 2, further comprising:

scheduling the packet to be forwarded to the output port from the input queue prior to the delay bound for the packet'"'"'s class expires.

4. The method of claim 1, further comprising:

forwarding the packet to a queue to an input queue for the packet class when the product of the queue length and delay bound for the packet'"'"'s class is less than the bandwidth allocated forte packet'"'"'s class and when the sum of the product of queue lengths and delay bounds for all classes is exceeds the predetermined congestion plane.

5. The method of claim 4, further comprising:

scheduling the packet to be forwarded to the output port from the input queue prior to the delay bound forte packet'"'"'s class expires.

6. The method of claim 1, wherein the predetermined congestion plane is defined as the sum of the product of the delay bound of each class divided by the delay bound of the highest priority class times the queue length for the class is one of less than or equal to a predetermined value.

7. The method of claim 6, wherein the predetermined value is the product of the speed of the output port times the delay bound of the highest priority class.

8. A weighted random early drop method, comprising:

forwarding all inbound low drop packets and discarding a first fixed percentage of inbound high drop packets when the sum of products of the queue length for each class times the delay bound for the class divided by the delay bound for the highest priority class exceeds a first predetermined threshold; and

discarding a second percentage of inbound low drop packets and a third percentage of inbound high priority packets when the sum of products of the queue length for each class times the delay bound for the class divided by the delay bound for the highest priority class exceeds a second predetermined threshold;

wherein the first predetermined threshold is lower than the second predetermined threshold.

9. The method of claim 8, further comprising:

discarding all inbound low drop and all inbound high priority packets when the sum of products of the queue length for each class times the delay bound for the class divided by the delay bound for the highest priority class exceeds a third predetermined threshold;

wherein the second predetermined threshold is lower than the third predetermined threshold.

10. A method for routing packets received from an input stream to a port, the input stream having n classes where n is an integer greater than 1, and the port having a bandwidth, comprising:

receiving a packet belonging to a class i, where i is an integer between 1 and n;

calculating the sum of λ

_iQ_i for i equals 1 to i equals n, where λ

_i is the ratio of the delay bound for the class i, δ

_i, divided by the delay bound of the highest priority class δ

₁, and Q_i is the current queue size for the class i forwarding a packet that exceeds for a class exceeding its allocated queue length defined as the product of the allocated bandwidth for the class r_i and the delay bound for the class, δ

_i, when the sum of λ

_iQ_i is less than a predetermined threshold value.

11. The method of claim 10, wherein the predetermined threshold value is the product of the port speed and the delay bound of the highest priority class, δ

₁.

12. The method of claim 10, wherein the predetermined threshold value is less than the product of the port speed and the delay bound of the highest priority class, δ

₁.

13. A method for dynamically adjusting queue sizes for n queues, where n is an integer greater than 1, each queue corresponding to a class C_i, where i is an integer between 1 and n, the class having a priority based on a delay bound δ

_i, comprising;

allocating each class a bandwidth, r_i;

allocating each class an allocated queue size determined by the product of the class bandwidth and the class delay bound, r_iδ

_i;

determining a congestion plane as a sum of the products for i equals 1 to n of a priority factor, λ

_i, the priority factor based on the delay bound of the class δ

_i divided by the delay bound of the highest priority class δ

₁ and a current queue length Q_i, wherein the sum λ

_iQ_i for i equals 1 to n is one equal to a predetermined threshold;

increasing the queue size for a class i when a packet is received for class i when the increase of queue size does not exceed the congestion plane.

14. The method of claim 13 wherein the predetermined threshold is the product of a port speed of an output port connected to the n queues and the delay bound of the highest priority class, δ

_i.

15. The method of claim 13, further comprising:

decreasing a queue size Q_i for a queue that is larger than its allocated queue size r_iδ

_i when a packet is received for a higher priority class and the sum λ

_iQ_i for i equals 1 to n is one greater than the predetermined threshold.

16. An apparatus for guaranteeing different packet delays for different packet classes, wherein each packet class having a corresponding priority class, input queue having a queue length and a delay bound, comprising:

means adapted for receiving a packet for forwarding to an output port, the packet having a packet class

means adapted for determining the sum of the product of queue lengths and delay bounds for all classes;

means adapted for determining the product of the queue length and delay bound for the packet'"'"'s class; and

means adapted for discarding the packet when the sum of the product of queue lengths and delay bounds for all classes exceeds a predetermined congestion plane and when the product of the queue length and delay bound for the packet'"'"'s class exceeds a bandwidth allocated for the packet'"'"'s class.

17. The apparatus of claim 16, further comprising:

means adapted for forwarding the packet to a queue to an input queue for the packet class when the product of the queue length and delay bound for the packet'"'"'s class exceeds the bandwidth allocated for the packet'"'"'s class and when the sum of the product of queue lengths and delay bounds for all classes is less than the predetermined congestion plane.

18. The apparatus of claim 16, further comprising:

scheduling the packet to be forwarded to the output port from the input queue prior to the delay bound for the packet'"'"'s class expires.

19. The apparatus of claim 16, further comprising:

means adapted for forwarding the packet to a queue to an input queue for the packet class when the product of the queue length and delay bound for the packet'"'"'s class is less than the bandwidth allocated for the packet'"'"'s class and when the sum of the product of queue lengths and delay bounds for all classes is exceeds the predetermined congestion plane.

20. The apparatus of claim 19, further comprising:

means adapted for scheduling the packet to be forwarded to the output port from the input queue prior to the delay bound for the packet'"'"'s class expires.

21. The apparatus of claim 19, wherein the predetermined congestion plane is defined as the sum of the product of the delay bound of each class divided by the delay bound of the highest priority class times the queue length for the class is one of less than or equal to a predetermined value.

22. The apparatus of claim 21, wherein the predetermined value is the product of the speed of the output port times the delay bound of the highest priority class.

23. An apparatus configured to perform a weighted random early drop method, comprising:

means adapted for forwarding all inbound low drop packets and discarding a first fixed percentage of inbound high drop packets when the sum of products of the queue length for each class times the delay bound for the class divided by the delay bound for the highest priority class exceeds a flint predetermined threshold; and

means adapted for discarding a second percentage of inbound low drop packets and a third percentage of inbound high priority packets when the sum of products of the queue length for each class times the delay bound for the class divided by the delay bound for the highest priority class exceeds a second predetermined threshold;

wherein the first predetermined threshold is lower than the second predetermined threshold.

24. The apparatus of claim 23, further comprising:

means adapted for discarding all inbound low drop and all inbound high priority packets when the sum of products of the queue length for each class times the delay bound for the class divided by the delay bound for the highest priority class exceeds a third predetermined threshold;

wherein the second predetermined threshold is lower than the third predetermined threshold.

25. An apparatus for guaranteeing different packet delays for n different packet classes, wherein n is an integer greater than 1, comprising:

n input queues, each of the n input queues is assigned to a corresponding packet class;

discard logic adapted to receiving a packet for forwarding to an output port, the packet belonging to a class i, that is one of the n packet classes;

the discard logic being suitably adapted for determining the sum of the product of queue lengths and delay bounds for all classes;

the discard logic being suitably adapted for determining the product of the queue length and delay bound for the packet'"'"'s class; and

the discard logic configured for discarding the packet when the sum of the product of queue lengths and delay bounds for all classes exceeds a predetermined congestion plane and when the product of the queue length and delay bound for the packet'"'"'s class exceeds a bandwidth allocated for the packet'"'"'s class.

26. The method of claim 25, further comprising:

the discard logic configured for forwarding the packet to a queue to an input queue for the packet class when the product of the queue length and delay bound for the packet'"'"'s class exceeds the bandwidth allocated for the packet'"'"'s class and when the sum of the product of queue lengths and delay bounds for all classes is less than the predetermined congestion plane.

27. The apparatus of claim 26, further comprising:

scheduling logic operative to scheduling the packet to be forwarded to the output port from the input queue prior to the delay bound for the packet'"'"'s class expires.

28. The apparatus of claim 27, further comprising:

a multiplexer having n inputs and one output, the n inputs coupled to the n input queues and the output connected to an output port;

wherein the scheduling logic is operative to control the multiplexer for forwarding a packet from one of the n input queues to the output port.

29. The apparatus of claim 25, further comprising:

the discard logic configured for forwarding the packet to a queue to an input queue for the packet class when the product of the queue length and delay bound for the packet'"'"'s class is less than the bandwidth allocated for the packet'"'"'s class and when the sum of the product of queue lengths and delay bounds for all classes is exceeds the predetermined congestion plane.

30. The apparatus of claim 29, further comprising:

scheduling logic for scheduling the packet to be forwarded to the output port from the input queue prior to the delay bound for the packet'"'"'s class expires.