Earliest deadline first communications cell scheduler and scheduling method for transmitting earliest deadline cells first

• US 6,028,843 A
• Filed: 03/25/1997
• Issued: 02/22/2000
• Est. Priority Date: 03/25/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rajan, Rajendran, Firoiu, Victor, Peris, Vinod Gerard John, Delp, Gary Scott, Poulter, David Richard, Shaffer, John Handley, Leichty, Philip Lynn, Guerin, Roch A.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US08/823,155
• Time in Patent Office: 1,064 Days
• Field of Search: 370/233, 370/395, 370/396, 370/401, 370/466, 370/468, 370/471, 370/474, 370/235
• US Class Current: 370/235
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5675 Timeslot assignment, e.g. TDMA
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus are provided for scheduling the transmission of cells of a plurality of data streams in a communications network. An earliest deadline first (EDF) scheduler is provided for scheduling the transmission of cells of a plurality of data streams in a communications network to ensure that the connection or data stream with the earliest deadline is transmitted first. Each of the multiple data streams has a delay bound or deadline. Data of each data stream is enqueued to a corresponding data cell queue. A timing wheel time slot based on an identified target transmission time for each data cell queue is calculated utilizing an addition of a maximum delay value. A move forward timing mechanism includes a scan forward feature to identify a succession of virtual connection or data stream cell queues for transmission. A multiple tier cell scheduler is provided that includes at least two scheduling timing wheels. The priority of a first timing wheel is higher than the priority of a second timing wheel. The priority of the second timing wheel is higher than the priority of an optional third timing wheel. The third timing wheel includes a best effort operational mode. The relative rates between data streams are maintained, while the absolute rates of the data streams are increased or decreased in the lowest priority wheel.

Claims

1. A method for scheduling the transmission of cells of a plurality of data streams in a communications network comprising the steps of:

enqueuing data of each data stream to a corresponding data cell queue;

calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream;

responsive to each said calculated next target transmission time, calculating a time slot in a timing wheel utilizing an addition of a maximum delay value, setting an active indication for said identified timing wheel time slot and storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot;

selecting a next data cell queue for transmission by checking for said active indication in a current timing wheel time slot;

responsive to identifying said active indication, processing a first data cell queue for transmission and rescheduling said data cell queue;

moving to a next time timing wheel time slot by checking for an entry from said current timing wheel time slot;

responsive to identifying said entry, processing said identified entry from said current timing wheel time slot and returning to checking for a next entry from said current timing wheel time slot;

responsive to identifying an empty time slot, comparing a current time value with said current timing wheel time slot,

responsive to a current time value less than or equal to said current timing wheel time slot, scanning forward a predefined range, checking for said active indication in any time slot within said predefined range.

2. A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 includes the steps of processing a first identified entry from a first timing wheel time slot in said range and returning to checking for a next entry from said current timing wheel time slot.

3. A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 includes the steps of responsive to identifying said current time value greater than said current timing wheel slot, moving to a next timing wheel time slot and returning to checking for said active indication for said current time slot.

4. A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 wherein the step of calculating said target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream includes the steps of maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and utilizing a calculation algorithm represented by:

New timestamp=MAX(old timestamp+sustained interval, current time-burst limit).

5. A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 4 wherein the step of calculating said time slot in said timing wheel utilizing an addition of a maximum delay value includes utilizing a calculation algorithm represented by:

New time slot=MAX(timestamp+sustained interval, current time+peak interval)+max delay.

6. A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 wherein said step of enqueuing data of each data stream to said corresponding data cell queue includes the steps of enqueuing data of each said data stream to at least one logical channel descriptor for each said data stream.

7. A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 6 wherein said steps of calculating said target transmission time and calculating said time slot in a timing slot are performed for each logical channel descriptor for each said data stream.

8. Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network comprising:

memory means for storing a corresponding data cell queue enqueued data of each data stream;

means for calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream;

means responsive to said next target transmission time calculating means, for calculating a time slot in a timing wheel utilizing an addition of a maximum delay value, means for storing an active indication for said identified timing wheel time slot and means for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot;

means for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot;

means, responsive to identifying said active indication, for processing a first data cell queue for transmission and for rescheduling said data cell queue;

means for moving to a next time timing wheel time slot including means for checking for an entry from said current timing wheel time slot;

means, responsive to said entry checking means, for processing an identified entry from said current timing wheel time slot and for checking for a next entry from said current timing wheel time slot;

means, responsive to an empty time slot identified by said entry checking means, for comparing a current time value with said current timing wheel time slot,

means, responsive to an identified current time value less than or equal to said current timing wheel time slot, for scanning forward a predefined range, checking for said active indication in any time slot within said predefined range.

9. Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 8 further includes means for processing a first identified entry from a first timing wheel time slot in said range and for checking for a next entry from said current timing wheel time slot.

10. Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 8 further includes means, responsive to identifying said current time value greater than said current timing wheel slot, for moving to a next timing wheel time slot and for checking for said active indication for said current time slot.

11. Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 8 further includes a last active bucket responsive to a calculated next target transmission time beyond said timing wheel time slots.

12. An earliest deadline first (EDF) scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network comprising:

memory means for storing a corresponding data cell queue for each of the plurality of data streams;

means for storing predetermined logical channel control parameter values for each data cell queue, said predetermined logical channel control parameter values including has a delay bound value;

timing wheel means for storing an array of pointers to said data cell queues and for storing an occupancy bit map of timing wheel time slots;

means for calculating a target transmission time and for calculating a timing wheel time slot for each data cell queue, said timing wheel time slot calculating means utilizing an addition of said delay bound value; and

timing means for moving forward on said timing wheel time slots to identify a succession of data stream cell queues for transmission,

said timing means including means for checking for an entry from said current timing wheel time slot;

means, responsive to said entry checking means, for processing an identified entry from said current timing wheel time slot and for checking for a next entry from said current timing wheel time slot;

means, responsive to an empty time slot identified by said entry checking means, for comparing a current time value with said current timing wheel time slot, and

means, responsive to an identified current time value less than or equal to said current timing wheel time slot, for scanning forward a predefined range, and for checking for said active indication in any time slot within said predefined range.

13. An earliest deadline first (EDF) scheduler for scheduling the transmission of cells and frames of a plurality of data streams in a communications network as recited in claim 12 wherein said timing means further includes means for processing a first identified entry from a first timing wheel time slot in said range and for checking for a next entry from said current timing wheel time slot.

14. An earliest deadline first (EDF) scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 12 wherein said timing means further includes means, responsive to identifying said current time value greater than said current timing wheel slot, for moving to a next timing wheel time slot and for checking for said active indication for said current time slot.

15. An earliest deadline first (EDF) scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 12 further includes a last active bucket responsive to a calculated next target transmission time beyond said timing wheel time slots.

16. A communications network comprising:

at least one communication system including a network interface;

a cell scheduler included with said network interface;

said cell scheduler including memory means for storing a corresponding data cell queue of enqueued data of each data stream;

means for calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream;

means responsive to said next target transmission time calculating means, for calculating a time slot in a timing wheel utilizing an addition of a maximum delay value, means for storing an active indication for said identified timing wheel time slot and means for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot;

means for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot;

means, responsive to identifying said active indication, for processing a first data cell queue for transmission and for rescheduling said data cell queue;

means for moving to a next time timing wheel time slot including means for checking for an entry from said current timing wheel time slot;

means, responsive to said entry checking means, for processing an identified entry from said current timing wheel time slot and for checking for a next entry from said current timing wheel time slot;

means, responsive to an empty time slot identified by said entry checking means, for comparing a current time value with said current timing wheel time slot,

means, responsive to an identified current time value less than or equal to said current timing wheel time slot, for scanning forward a predefined range, checking for said active indication in any time slot within said predefined range.

17. A communications network as recited in claim 16 further including an internal network routing system including at least one said cell scheduler.

18. A computer program product for use in a data communications network having a cell scheduler for scheduling the transmission of cells of a plurality of data streams in said communications network, the computer program product comprising:

a record medium;

means, recorded on said recording medium, for storing a corresponding data cell queue for each of the plurality of data streams;

means, recorded on said recording medium, for storing predetermined logical channel control parameter values for each data cell queue, said predetermined logical channel control parameter values including has a delay bound value;

timing wheel means, recorded on said recording medium, for storing an array of pointers to said data cell queues and for storing an occupancy bit map of timing wheel time slots;

means, recorded on said recording medium, for calculating a target transmission time and for calculating a timing wheel time slot for each data cell queue, said timing wheel time slot calculating means utilizing an addition of said delay bound value; and

timing means, recorded on said recording medium, for moving forward on said timing wheel time slots identify a succession of data stream cell queues for transmission,

said timing means including means for checking for an entry from said current timing wheel time slot;

means, responsive to said entry checking means, for processing an identified entry from said current timing wheel time slot and for checking for a next entry from said current timing wheel time slot;

means, responsive to an empty time slot identified by said entry checking means, for comparing a current time value with said current timing wheel time slot, and

means, responsive to an identified current time value less than or equal to said current timing wheel time slot, for scanning forward a predefined range, and for checking for said active indication in any time slot within said predefined range.

19. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network comprising:

memory means for storing a corresponding data cell queue for each of the plurality of data streams;

means for storing predetermined logical channel control parameter values for each data cell queue,

means for calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream;

means responsive to each said calculated next target transmission time, for selecting a higher priority timing wheel, or a lower priority timing wheel, means for calculating a timing wheel time slot in said selected timing wheel, means for setting an active indication for said identified timing wheel time slot and means for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot;

means for selecting a next data cell queue for transmission including means for identifying scheduling opportunities on said timing wheel and means, responsive to identified scheduling opportunities, for moving entries from said lower priority timing wheel to said higher priority timing wheel.

20. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 19 wherein said higher priority timing wheel includes a higher priority leaky bucket timing wheel and wherein said lower priority timing wheel includes a lower priority earliest deadline first timing wheel.

21. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 19 wherein said higher priority timing wheel includes a higher priority earliest deadline first timing wheel and wherein said lower priority timing wheel includes a lower priority best effort timing wheel.

22. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 19 wherein said higher priority timing wheel includes a higher priority leaky bucket timing wheel and wherein said lower priority timing wheel includes a lower priority best effort timing wheel.

23. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 19 further include a middle priority timing wheel.

24. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 23 wherein said higher priority timing wheel includes a higher priority leaky bucket timing wheel, said middle priority timing wheel includes a earliest deadline first middle priority timing wheel, and said lower priority timing wheel includes a lower priority best effort timing wheel.

25. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 24 further include means for defining scheduling opportunities on at least one of said higher priority leaky bucket timing wheel and said middle priority earliest deadline first timing wheel utilizing a predefined pseudo data cell queue;

and wherein said means for calculating said target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream includes said predefined pseudo data cell queue, and said identified target transmission time for said predefined pseudo data cell queue defining scheduling opportunities of multiple lower priority best effort timing wheel time slots.

26. A multiple tier cell scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 24 wherein said means for selecting a next data cell queue for transmission includes means for checking for said active indication in a current timing wheel time slot of said higher priority leaky bucket timing wheel;

means, responsive to an absence of said active indication in said current frame, for reading a next frame and means for moving an entry from said lower priority best effort timing wheel to at least one of said higher priority leaky bucket timing wheel and said middle priority earliest deadline first timing wheel.