Communications cell scheduler and scheduling method for providing proportional use of network bandwith

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:
• 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.

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:
• 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.

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:
• 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.