Time-based scheduler architecture and method for ATM networks
AssigneeNEC USA, Inc.
InventorsRuixue Fan, Brian L. Mark, Gopalakrishan Ramamurthy, Alexander T. Ishii
Life of this patent
Estimating the term…
Abstract
A flexible and scalable architecture and method that implements dynamic rate control scheduling in an ATM switch. The scheduler shapes a large number of streams according to rate values computed dynamically based on switch congestion information. To handle a large range of bit rates, a plurality of timewheels are employed with different time granularities. The streams are assigned dynamically to the timewheels based on computed rate values. The shaper architecture and method support priority levels for arbitrating among streams which are simultaneously eligible to transmit.
Claims30
An apparatus for scheduling stream queues serving cells in an ATM switch comprising:
- a cell memory connected to a queue manager unit that stores ATM cells organized into stream queues;
- and
- a control memory connected to a scheduler unit and the queue manager that stores queue information;
- wherein the scheduler unit selects a stream queue to be serviced, based on the queue information in the control memory, and comprises a timewheel scheduling memory that stores stream queue identifiers in a series of time-bins;
- and
- wherein the queue manager controls the receipt and transmission of ATM cells based on the congestion of the ATM switch and on the queue information in the control memory.
A method for scheduling stream queues containing cells in an ATM switch comprising the steps of:
- (a) calculating a scheduling rate value for each stream;
- (b) calculating a timestamp value for each stream queue based on its scheduling rate value;
- (c) scheduling each stream queue by assigning a stream queue identifier to a first timewheel scheduling memory time-bin based on its timestamp value;
- (d) transferring a list of stream queue identifiers from a time-bin on the timewheel to a ready list when a current time value equals the time-bin value;
- (e) choosing a first stream queue identifier from the ready list;
- and
- (f) transmitting a first cell in the stream queue corresponding to the chosen stream queue identifier;
- wherein the timestamp value and current time value cycle.
A method for scheduling stream queues containing cells in an ATM switch comprising the steps of:
- (a) calculating a scheduling rate value for each stream;
- (b) calculating a timestamp value for each stream queue based on its scheduling rate value;
- (c) assigning one of at least two priority levels to each stream queue, wherein the priority levels are assigned different values from high to low;
- (d) scheduling each stream queue by assigning a stream queue identifier to a timewheel scheduling memory time-bin based on its timestamp value and its priority level;
- (e) at each priority level, transferring a list of stream queue identifiers from a time-bin on the timewheel to a ready list when a current time value equals the time-bin value;
- (f) choosing a first stream queue identifier from the highest priority non-empty ready list;
- and
- (g) transmitting a first cell in the stream queue corresponding to the chosen stream queue identifier;
- wherein the timestamp value and current time value cycle.
A method of scheduling a stream composed of a sequence of cells to successively transmit each cell towards a downstream side, comprising the steps of:
- calculating, on the basis of a dynamic rate on the downstream side, a scheduling timestamp representative of timing at which each cell of the stream is to be scheduled;
- and
- deciding a shaping timestamp of each cell on the basis of the scheduling timestamp
- wherein the calculating step comprises the step of:
- calculating the scheduling timestamp with reference to UPC (Usage Parameter Control) parameters.
A method of scheduling a stream composed of a sequence of cells to successively transmit each cell towards a downstream side, comprising the steps of:
- calculating a scheduling timestamp on the basis of a peak cell rate (PCR) of the stream, a sustainable cell rate (SCR), a burst threshold (TH), and a dynamic rate;
- and controlling a cell rate without congestion on the basis of the scheduling timestamp calculated
- wherein the calculating step comprises the step of:
- calculating the scheduling timestamp with reference to UPC (Usage Parameter Control) parameters.
A scheduler for use in scheduling a stream composed of a sequence of cells to successively transmit each cell towards a downstream side, comprising:
- calculating means for calculating a scheduling timestamp with reference to a dynamic rate computed on congestion on the downstream side to specify scheduling time at which each cell of the stream is to be scheduled;
- and
- deciding means for deciding output timing of each cell in the shaped manner on the basis of the scheduling timestamp and the current time
- wherein the calculating means calculates the scheduling timestamp with reference to a peak cell rate (PCR) of the stream along with the dynamic rate.
A scheduler for use in scheduling a stream composed of a sequence of cells to successively transmit each cell towards a downstream side, comprising:
- calculating means for calculating a scheduling timestamp with reference to a dynamic rate computed on congestion on the downstream side to specify scheduling time at which each cell of the stream is to be scheduled;
- and
- deciding means for deciding output timing of each cell in the shaped manner on the basis of the scheduling timestamp and the current time
- wherein the calculating means comprises:
- first means for calculating, on arrival of each cell in the stream, a first timestamp of each cell on the basis of the dynamic rate of the stream, a peak cell rate (PCR) of the stream, and a current time.
A scheduler for use in scheduling a stream composed of a sequence of cells to successively transmit each cell towards a downstream side, comprising:
- calculating means for calculating a scheduling timestamp with reference to a dynamic rate computed on congestion on the downstream side to specify scheduling time at which each cell of the stream is to be scheduled;
- and
- deciding means for deciding output timing of each cell in the shaped manner on the basis of the scheduling timestamp and the current time
- wherein the deciding means is operable to decide the shaping timestamp on cell departure;
- and
- the calculating means comprises:
- first means for calculating a first timestamp on the basis of a timestamp assigned to a preceding one of the cells in the stream, the dynamic rate of the stream, and a peak cell rate (PCR) of the stream, to obtain the scheduling timestamp with reference to the first timestamp.
Dependencies are inferred from the claim text.