Communications cell scheduler and scheduling method for providing proportional use of network bandwith
First Claim
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;
including 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;
space="preserve" listing-type="equation">New timestamp=MAX(old timestamp+sustained interval, current time-burst limit);
responsive to each said calculated next target transmission time, calculating a timing wheel time slot in a timing wheel, 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 of said timing wheel;
responsive to identifying said active indication, processing a first data cell queue for transmission and rescheduling said data cell queue;
moving to a next timing wheel time slot by checking for an active indication in a current frame of active indicators corresponding to timing wheel time slots of said timing wheel; and
responsive to identifying said active indication in said current frame, moving to a first active timing wheel time slot in said current frame.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus are provided for scheduling the transmission of cells of a plurality of data streams in a communications network. A best effort scheduler is provided for scheduling the transmission of cells of a plurality of data streams in a communications network. The best effort scheduler includes a best effort operational mode and can include more than one timing wheel. When the best effort scheduler includes more than one timing wheel, then the priority of the best effort timing wheel is lower than the priority of the other timing wheel or wheels. Data of each data stream is enqueued to a corresponding data cell queue. A target next transmission time for each data cell queue is calculated utilizing predetermined logical channel descriptor parameters. A lower priority or a higher priority timing wheel is selected and a timing wheel time slot is calculated based on an identified target transmission time for each active data cell queue. An active indication is set for the identified timing wheel time slot and an entry is stored to point to the corresponding data cell queue for the identified timing wheel time slot. The relative rates between data streams are maintained, while the absolute rates of the data streams are increased or decreased in the low priority wheel. Scheduling opportunities can be defined utilizing a predefined pseudo data cell queue. Then the calculation of the target transmission time for each data cell queue includes the predefined pseudo data cell queue, and the identified target transmission time for the predefined pseudo data cell queue defines scheduling opportunities of multiple timing wheel time slots.
155 Citations
21 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;
including 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;
space="preserve" listing-type="equation">New timestamp=MAX(old timestamp+sustained interval, current time-burst limit);responsive to each said calculated next target transmission time, calculating a timing wheel time slot in a timing wheel, 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 of said timing wheel; responsive to identifying said active indication, processing a first data cell queue for transmission and rescheduling said data cell queue; moving to a next timing wheel time slot by checking for an active indication in a current frame of active indicators corresponding to timing wheel time slots of said timing wheel; and responsive to identifying said active indication in said current frame, moving to a first active timing wheel time slot in said current frame. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network comprising:
-
means for enqueuing data of each data stream to a corresponding 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;
said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by;
space="preserve" listing-type="equation">New timestamp=MAX(old timestamp+sustained interval, current time-burst limit);means responsive to each said calculated next target transmission time, means for calculating a timing wheel time slot in a 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 checking for said active indication in a current timing wheel time slot of said first timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of active indications corresponding to timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame. - View Dependent Claims (13, 14, 15, 16)
-
-
17. 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; means, recorded on said recording medium, for calculating a next target transmission time for each data cell queue;
said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by;
space="preserve" listing-type="equation">New timestamp=MAX(old timestamp+sustained interval, current time-burst limit);means, recorded on said recording medium, for calculating a timing wheel time slot in a timing wheel, for setting an active indication for said identified timing wheel time slot, and for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; means, recorded on said recording medium, for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot of said timing wheel;
means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue;
means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of timing wheel time slots of said timing wheel; and
means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame. - View Dependent Claims (18, 19, 20)
-
-
21. A best effort 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;
said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by;
space="preserve" listing-type="equation">New timestamp=MAX(old timestamp+sustained interval, current time-burst limit);means responsive to each said calculated next target transmission time, for calculating a timing wheel time slot in a 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 checking for said active indication in a current timing wheel time slot of said first timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of active indications corresponding to timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame.
-
Specification