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

• US 20010051992A1
• Filed: 02/22/2001
• Published: 12/13/2001
• Est. Priority Date: 02/24/2000
• Status: Active Grant

• Current Assignee: Synaptics Incorporated
• Original Assignee: Zarlink Semiconductor Inc. (Microchip Technology Incorporated)
• Inventors: Wang, Linghsiao, Yang, Brian, Barrack, Craig I.
• Granted Patent: US 6,990,529 B2
• Time in Patent Office: Days
• US Class Current: 709/207
• 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 of frame scheduling and discard in a Differentiated Services network environment, comprising the steps of:

discarding a frame of an incoming stream of frames with a discard logic which operates in accordance with a discard algorithm; and

scheduling with a scheduling logic the order in which to transmit one or more enqueued frames of the network environment.

2. A method of frame scheduling and discard in a Differentiated Services network environment, comprising the steps of:

discarding a frame of an incoming stream of frames with a discard logic which operates in accordance with a discard algorithm, if,

a predetermined congestion level in the network environment has been reached, and

a predetermined backlog limit of a queue associated with said frame, has been reached, and

scheduling with a scheduling logic the order in which to transmit one or more enqueued frames of the network environment.

3. The method of

claim 2

, wherein said frame in the step of discarding is associated with a unique class of frames, and which said unique class of frames are further associated with said queue of the networking environment.

4. The method of

claim 2

, wherein said queue in the step of discarding is controlled in accordance with a maximum delay limit and a minimum bandwidth limit.

5. The method of

claim 2

, wherein the network environment contains a plurality of queues which are classified in accordance with respective queue classes, which said plurality of queue classes range from a lowest transmission priority class to a highest transmission priority class.

6. The method of

claim 5

, wherein said lowest transmission priority class has a maximum delay value which is greater than said maximum delay value of said highest transmission priority class.

7. The method of

claim 2

, wherein the step of scheduling comprises a step of calculating a slackness time in order to determine the order of transmitting said one or more enqueued frames.

8. The method of

claim 7

, wherein a smaller said slackness time corresponds to a higher transmission priority.

9. The method of

claim 7

, wherein each of said one or more enqueued frames is associated with a time stamp, and said slackness time of a select one of said one or more enqueued frames is defined as the difference in time that said select one of said one or more enqueued frames has been enqueued and a maximum delay time associated with said respective queue.

10. The method of

claim 7

, wherein if a first slackness time of a lower priority queue equals a second slackness time of a higher priority queue, a frame of said higher priority queue will be scheduled, in the step of scheduling, for transmission first.

11. The method of

claim 2

, wherein a select frame of said one or more enqueued frames is scheduled for transmission, in the step of scheduling, when said select frame reaches a head-of-line position in its respective queue.

12. The method of

claim 2

, wherein said frame is discarded, in the step of discarding, in accordance with a plurality of predetermined congestion levels.

13. The method of

claim 12

, wherein when a highest congestion level of said plurality of predetermined congestion levels is reached, all of the frames associated with said queue which has reached said predetermined backlog limit are discarded.

14. The method of

claim 13

, wherein when said predetermined congestion level is reached, and said predetermined congestion level is lower than said highest congestion level, some of the frames associated with said queue which has reached said predetermined backlog limit are discarded.

15. A frame scheduling and discard architecture in a Differentiated Services network environment, comprising:

discard logic for discarding select ones of a stream of incoming frames of the network environment in accordance with a discard algorithm; and

scheduling logic for scheduling the order in which to transmit one or more enqueued frames of the network environment.

16. A frame scheduling and discard architecture in a Differentiated Services network environment, comprising:

discard logic for discarding a frame from a stream of incoming frames in accordance with a discard algorithm, said 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 said frame, has been reached, and

scheduling logic for scheduling the order in which to transmit one or more enqueued frames of the network environment.

17. The architecture of

claim 16

, wherein said frame is associated with a unique class of frames, and which said unique class of frames are further associated with said queue of the networking environment.

18. The architecture of

claim 16

, wherein said queue is controlled in accordance with a maximum delay limit and a minimum bandwidth limit.

19. The architecture of

claim 16

, wherein the network environment contains a plurality of queues which are classified in accordance with respective queue classes, which said plurality of queue classes range from a lowest transmission priority class to a highest transmission priority class.

20. The architecture of

claim 19

, wherein said lowest transmission priority class has a maximum delay value which is greater than said maximum delay value of said highest transmission priority class.

21. The architecture of

claim 16

, wherein a slackness time is calculated inorder to determine the order of transmitting said one or more enqueued frames.

22. The architecture of

claim 21

, wherein a smaller said slackness time corresponds to a higher transmission priority.

23. The architecture of

claim 21

, wherein each of said one or more enqueued frames is associated with a time stamp, and said slackness time of a select one of said one or more enqueued frames is defined as the difference in time that said select one of said one or more enqueued frames has been enqueued and a maximum delay time associated with said respective queue.

24. The architecture of

claim 21

, wherein if a first slackness time of a lower priority queue equals a second slackness time of a higher priority queue, a frame of said higher priority queue will be scheduled for transmission first.

25. The architecture of

claim 16

, wherein a select frame of said one or more enqueued frames is scheduled for transmission when said select frame reaches a head-of-line position in its respective queue.

26. The architecture of

claim 16

, wherein said frame is discarded in accordance with a plurality of predetermined congestion levels.

27. The architecture of

claim 26

, wherein when a highest congestion level of said plurality of predetermined congestion levels is reached, all of the frames associated with said queue which has reached said predetermined backlog limit are discarded.

28. The architecture of

claim 27

, wherein when said predetermined congestion level is reached, and said predetermined congestion level is lower than said highest congestion level, some of the frames associated with said queue which has reached said predetermined backlog limit are discarded.