Packet scheduling methods and apparatus

• US 6,560,230 B1
• Filed: 05/21/1999
• Issued: 05/06/2003
• Est. Priority Date: 02/01/1999
• Status: Expired due to Term

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Redback Networks Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Li, Renwei, Terry, Paul, Kwong, Peter Wai-Tong, Westfall, Ronald Leonard
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): LEVITAN, DMITRY
• Application Number:
  US09/316,930
• Time in Patent Office: 1,446 Days
• Field of Search: 370/395.21, 370/395.4, 370/395.42, 370/413, 370/415, 370/417
• US Class Current: 370/395.42
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/3065 for real time traffic
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling

Abstract

Providing different levels of quality of service for different data flows being transported over a data link requires a very fast way to schedule individual packets for forwarding on the data link. The invention provides scheduling methods which give preference to higher priority packets while treating lower priority packets fairly. The methods can provide shorter latencies for higher priority packets than can many prior scheduling methods. The methods and apparatus of the invention are readily adaptable for use with scheduling rules provided in the form of hierarchical policy trees.

Claims

1. A method for scheduling transmission of data packets on a data link, the method comprising:

a) receiving data packets, each data packet belonging to one of a plurality of classes, the classes having priorities, and assigning each data packet to one of a plurality of queues, each queue capable of accommodating at least one data packet;

b) from a group comprising data packets in the plurality of queues selecting an eligible group of data packets, the eligible group comprising data packets which satisfy an eligibility criterion;

c) determining whether data packets in the eligible group all belong to one or more classes having the same priority or belong to two or more classes having different priorities;

d) if the data packets in the eligible group belong to two or more classes having different priorities, selecting one data packet for transmission on the data link by applying a selection criterion to an eligible sub-group, the eligible sub-group containing those one or more data packets which are in the eligible group and belong to one or more classes having a highest priority;

e) if the data packets in the eligible group all belong to classes having the same priority, selecting one data packet for transmission on the data link by applying a selection criterion to all data packets in the eligible group, wherein the selection criterion comprises a first to finish selection criterion wherein the first to finish selection criterion comprises selecting a packet having a smallest finish time F where F is given by;

$F_i=S_i+\frac{L_i}{p_{i-}<br><br>R}$

where S_i is a start time for the packet, L_i is a length of the packet, R is a data rate of the data link, and p_i is a proportion of the capacity of the data link to which the packet is entitled wherein p_i=Q_i/N where Q_i is a proportion of the capacity of the data link to which a leaf node with which the packet is associated is entitled and N is a number of active queues at the leaf node; and

,

f) forwarding the selected packet.

2. The method of claim 1, wherein each queue is associated with a single class and receives only packets classified in the single class.

3. The method of claim 1, wherein each class has one of two priorities.

4. The method of claim 1 comprising maintaining a virtual time value wherein selecting packets which satisfy the eligibility criterion comprises selecting packets having a start time less than or equal to the virtual time value.

5. The method of claim 4 comprising updating the virtual time value after each time a packet is forwarded.

6. The method of claim 5, wherein the updated virtual time value, V_i, is given by:

$V_i=V_{i-1}+\frac{L_i}{R}$

where V<sub>i−

1</sub> is a previous virtual time value, L_i is a length of the forwarded packet and R is a data rate of the link on which the packet is forwarded.

7. A method for scheduling transmission of data packets on a data link, the method comprising:

a) providing a plurality of scheduling engines interlinked to form a hierarchical tree, the hierarchical tree including at least a parent scheduling engine and a plurality of child scheduling engines linked to the parent scheduling engine, each of the child scheduling engines adapted to select and hold a data packet for eventual selection by the parent scheduling engine, the data packets each belonging to one of a plurality of classes, the classes each having a priority;

b) in the parent scheduling engine selecting one data packet from among the data packets being held by the child scheduling engines;

i) selecting an eligible group of data packets, the eligible group consisting of fewer than all of the data packets being held by the child scheduling engines and then selecting the one data packet from among data packets in the eligible group;

ii) if there are any high priority data packets being held by any of the child scheduling engines, selecting one high priority data packet by applying a selection criterion to high priority data packets held by the child scheduling engines;

iii) if there are no high priority data packets held by any of the child scheduling engines but there are low priority data packets held by one or more of the child scheduling engines, selecting one low priority data packet by applying a selection criterion to low priority data packets being held by the child scheduling engines.

8. The method of claim 7, wherein selecting the eligible group comprises selecting data packets being held by the child scheduling engines which have a finish time less than a virtual time value for the parent scheduling engine.

9. The method of claim 8 comprising updating the virtual time value each time a packet is passed on by the parent scheduling engine.

10. The method of claim 9, wherein the updated virtual time value, V_i, is given by:

$V_i=V_{i-1}+\frac{L_i}{R}$

where V<sub>i−

1</sub> is a previous virtual time value, L_i is a length of the packet passed on and R is a data rate of the link on which the packet is forwarded.

11. The method of claim 7, wherein the selection criterion is a first to finish selection criterion.

12. The method of claim 7 comprising, whenever a data packet belonging to a high priority class becomes available for selection by a child scheduling engine and a data packet already selected and being held by that child scheduling engine belongs to a lower priority class, making the data packet belonging to the high priority class available for selection by the parent scheduling engine in place of the already selected data packet.

13. The method of claim 7, wherein the hierarchical tree comprises a plurality of leaf nodes, one or more queues are associated with each leaf node, the one or more queues associated with one leaf node receive only data packets belonging to a class having a high priority and the one or more queues associated with another leaf node receive only data packets belonging to a class having a lower priority.

14. The method of claim 7 comprising passing a value representing a priority of a class to which the selected packet belongs to the parent scheduling engine.

15. The method of claim 7, wherein the selection criterion is a first to finish selection criterion.

16. A method for scheduling transmission of data packets on a data link, the method comprising:

a) providing a plurality of schedulers interlinked to forrn a hierarchical tree, the hierarchical tree including a first scheduler adapted to select data packets from among data packets selected by one or more child schedulers, the first scheduler having a parent scheduler adapted to select data packets from a group of one or more data packets including a data packet selected by the first scheduler each child scheduler adapted to select data packets from data packets at heads of one or more queues, each queue capable of receiving one or more data packets, the data packets each belonging to a class, each class having one of two or more priorities;

b) in the first scheduler;

i) providing locations for holding one data packet from each of a plurality of different priorities, and, if any of the locations is vacant and the eligible group includes one or more data packets belonging to classes having the same priority as a priority corresponding to the vacant location, selecting from the eligible group one data packet belonging to a class having the same priority as the priority corresponding to the vacant location;

ii) from a group comprising data packets selected by the child schedulers, selecting an eligible group of data packets, the eligible group comprising data packets eligible for transmission according to an eligibility criterion;

iii) if the data packets in the eligible group do not all belong to classes having the same priority, selecting one data packet from the eligible group by applying a selection criterion to an eligible sub-group, the eligible sub-group containing those one or more data packets which are in the eligible group and belong to classes having a priority higher than or equal to a priority of every other class of packet in the eligible group;

iv) if the data packets in the eligible group all belong to classes having the same priority, selecting one data packet by applying a selection criterion to all data packets in the eligible group; and

,

v) making the selected data packet available for forwarding by the parent scheduler.

17. The method of claim 16, wherein the eligibility criterion selects packets having a finish time smaller than or equal to a virtual time of the first scheduler.

18. The method of claim 16, wherein the eligibility criterion selects packets having a start time smaller than or equal to a virtual time of the first scheduler.

19. The method of claim 17, wherein the selection criterion comprises a first to finish selection criterion.

20. The method of claim 19, wherein the first to finish selection criterion comprises selecting a packet having a smallest finish time F where F is given by:

$F_i=S_i+\frac{L_i}{p_{i-}<br><br>R}$

where S_i is a start time for the packet, L_i is a length of the packet, R is a data rate associated with the first scheduler, and p_i is a proportion of the data rate to which the child scheduler is entitled.

21. Apparatus for scheduling transmission of data packets on a data link, the apparatus comprising:

a) a memory capable of holding a plurality of data packets queued in a plurality of queues;

b) means for keeping a start time, a finish time and a priority for a packet at a head of each of the queues;

c) a scheduling engine adapted to select one packet from a plurality of packets at the heads of the queues, the scheduling engine comprising;

i) a counter for maintaining a virtual time for the scheduling engine;

ii) means for comparing the start time for each packet to the virtual time for the scheduling engine to select an eligible group of packets;

iii) means for comparing the priorities of packets in the eligible group of packets and eliminating from the eligible group packets having a priority lower than a priority for another packet in the eligible group; and

,

iv) means for selecting one packet from the eligible group having an earliest finish time.

22. The apparatus of claim 21 comprising a plurality of scheduling engines linked to form a hierarchical tree, the hierarchical tree comprising one or more parent scheduling engines each linked to one or more child scheduling engines, each parent scheduling engine comprising

i) a counter for maintaining a virtual time for the parent scheduling engine;

ii) means for comparing the start time for each packet held by a child scheduling engine linked to the parent scheduling engine to the virtual time for the parent scheduling engine to select an eligible group of packets;

iii) means for comparing the priorities of packets in the eligible group of packets and eliminating from the eligible group packets having a priority lower than a priority for another packet in the eligible group; and

,

iv) means for selecting one packet from the eligible group having an earliest finish time.

26. The apparatus of claim 21, wherein the eligible group of packets includes packets having a start time less than or equal to the virtual time.

27. The apparatus of claim 26, wherein the scheduling engine comprises means for updating the virtual time maintained by the counter after each time a packet is forwarded.

28. The apparatus of claim 27, wherein the updated virtual time, V_i, is given by:

$V_i=V_{i-1}+\frac{L_i}{R}$

where V<sub>i−

1</sub> is a previous virtual time, L_i is a length of the forwarded packet and R is a data rate of the data link on which the packet is forwarded.

23. Apparatus for scheduling the transmission of data packets on a data link, the apparatus comprising a plurality of scheduling engines linked to form a hierarchical tree, the hierarchical tree comprising one or more parent scheduling engines each linked to one or more child scheduling engines, the one or more parent scheduling engines comprising:

i) a counter for maintaining a virtual time for the parent scheduling engine;

ii) means for comparing the start time for each packet held by a child scheduling engine linked to the parent scheduling engine to the virtual time for the parent scheduling engine to select an eligible group of packets; and

,

iv) means for selecting one packet having a first priority from the eligible group; and

,

v) means for selecting another packet having a second priority different from the first priority from the eligible group.

29. The apparatus of claim 23, wherein the eligible group of packets includes packets having a start time less than or equal to the virtual time.

30. The apparatus of claim 29, wherein the one or more parent scheduling engines comprises means for updating the virtual time maintained by the counter after each time a packet is forwarded.

31. The apparatus of claim 30, wherein the updated virtual time, V_i, is given by:

$V_i=V_{i-1}+\frac{L_i}{R}$

where V<sub>i−

1</sub> is a previous virtual time, L_i is a length of the forwarded packet and R is a data rate of the data link on which the packet is forwarded.

24. A method for scheduling transmission of data packets on a data link, the method comprising:

a) providing a plurality of scheduling engines interlinked to form a hierarchical tree, the hierarchical tree including at least a parent scheduling engine and a plurality of child scheduling engines linked to the parent scheduling engine, each of the child scheduling engines adapted to select and hold a data packet for eventual selection by the parent scheduling engine, the data packets each belonging to one of a plurality of classes, the classes each having a priority;

b) in the parent scheduling engine;

i) if any of the child scheduling engines are holding any data packets classified as having a first priority and the parent scheduling engine is not already holding a first priority data packet, selecting one of the first priority data packets by applying a selection criterion to first priority data packets held by the child scheduling engines; and

,

ii) if any of the child scheduling engines are holding any data packets classified as having a second priority and the parent scheduling engine is not already holding a second priority data packet, selecting one of the second priority data packets by applying a selection criterion to second priority data packets held by the child scheduling engines.

32. The method of claim 24, wherein the selection criterion is based on a first to finish criterion.

33. The method of claim 32, wherein the first to finish selection criterion comprises selecting a packet having a smallest finish time F where F is given by:

$F_i=S_i+\frac{L_i}{p_{i-}<br><br>R}$

where S_i is a start time for the packet, L_i is a length of the packet, R is a data rate associated with the first scheduler, and p_i is a proportion of the data rate to which the child scheduler is entitled.

34. The method of claim 24, wherein the selection criterion is based on a start criterion.

25. A method for scheduling transmission of data packets on a data link, the method comprising:

a) providing a plurality of schedulers interlinked to form a hierarchical tree, the hierarchical tree including a first scheduler adapted to select data packets from among data packets selected by one or more child schedulers, the first scheduler having a parent scheduler adapted to select data packets from a group of one or more data packets including a data packet selected by the first scheduler, each child scheduler adapted to select data packets from data packets at heads of one or more queues, each queue capable of receiving one or more data packets, the data packets each belonging to a class, each class having one of two or more priorities;

b) in the first scheduler;

i) providing a plurality of locations each able to hold one data packet, each of the locations corresponding to a different one of the two or more priorities;

ii) whenever one or more of the locations is vacant, selecting an eligible group of data packets from a group comprising data packets selected by the child schedulers, the eligible group comprising data packets eligible for transmission according to an eligibility criterion; and

,

iii) for each of the vacant locations for which the eligible group comprises one or more packets belonging to a class having a priority equal to the priority of the vacant location, selecting one data packet from the eligible group by applying a selection criterion to an eligible subgroup, the eligible sub-group containing those one or more data packets which are in the eligible group and belong to classes having a priority equal to the priority of the vacant location; and

,

iv) holding the selected data packets available for forwarding by the parent scheduler.

35. The method of claim 25, wherein the eligible group of packets includes packets having a start time less than or equal to a virtual time associated with the first scheduler.

36. The method of claim 35, wherein in the first scheduler, updating the virtual time after each time a packet is forwarded out from the data link.

37. The method of claim 36, wherein the updated virtual time, V_i, is given by:

$V_i=V_{i-1}+\frac{L_i}{R}$

where V<sub>i−

1</sub> is a previous virtual time, L_i is a length of the forwarded packet and R is a data rate of the data link on which the packet is forwarded.