Mixed queue scheduler

Details Mixed queue scheduler Mixed queue scheduler

1999-09-24

2004-04-27

Kizou, Hassan (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S429000

Reexamination Certificate

active

06728253

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to an improved method and system for managing communications networks. In particular, the present invention relates to a method and system for scheduling the arrival rate of data packets among a plurality of data queues. More particularly, the present invention relates to a method and system for allocating bandwidth between memory queues and corresponding output queues having differing service rates. Still more particularly, the present invention provides a selection mechanism by which output queue threshold criteria are compared with current output queue occupancy data to service one among a plurality of data queues during each of a repeating time interval, such that queue underflow and overflow are minimized.
2. Description of the Related Art
In switch design it is necessary to schedule traffic to multiple data ports which may have different output flow rates. In this context, a “data port” may be referred to interchangeably as a “data queue”. Similarly, and consistent with conventional queueing theory terminology, the “output flow rate” of a queue may be referred to as the “service rate” of the queue in question. All data in memory exists in fixed cell sizes. Each cell resides within a particular memory queue, and is labeled with a designator that identifies a given output port as its destination. At each time step, a scheduler may either declare a pause (do nothing to any cells) or choose exactly one memory queue, extract the first cell from that queue, and move that cell into the output queue of the same label, as illustrated in FIG.
1
.
Furthermore, at each time step some irregular but constant fraction of a cell is taken from each output queue. The irregular function reflects the asynchronous nature of the scheduler and the external media into which output ports feed. To avoid underflow, a fundamental and obviously necessary assumption is that the sum of the output fractions must be less than or equal to one.
To further clarify the scheduler problem, it should be noted that the configuration depicted in
FIG. 1
is susceptible to two constraints which must be addressed. The first is underflow which, as the term is utilized herein, refers to a queue that, once started, becomes empty even when data designated for that port is currently available within memory buffers
106
. Underflow occurs in the scheme depicted in
FIG. 1
when scheduler
102
has begun scheduling a memory queue but then fails to allocate input data from memory buffers
106
to one of output queues
104
at a rate sufficient to compensate for the output flow rate, or queue bandwidth of one of the queues. The problems caused by underflow include degradation in Quality of Service (QoS) guarantees and increased network congestion.
Whereas underflow results in data queues being permitted by scheduler
102
to become empty, overflow results when, in trying to build up an excessive surplus in an output queue, scheduler
102
allocates input data to one of queues
104
at a rate faster than the queue's respective service bandwidth (output flow rate), the queue's occupancy will rise until an unacceptable overflow condition occurs. Like underflow, overflow results in degraded network efficiency and predictability and in increased congestion.
From the foregoing, it can be appreciated that a need exists for a method and system for scheduling the data arrival rate from a single source link to multiple data queues such that the minimum level of occupancy within each of the queues in maximized. Implementation of such a method and system would prevent overflow and underflow from occurring, thereby enhancing the efficiency and reliability of telecommunications networks.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide an improved method and system for managing communications networks.
It is another object of the invention to provide a method and system for scheduling the arrival rate of data packets among a plurality of data queues.
It is a further object of the present invention to provide a method and system for allocating bandwidth of a single source link among a plurality of output queues having differing service rates.
It is still another object of the present invention to provide a selection mechanism by which queue threshold criteria are compared with current queue occupancy data to increment one among a plurality of data queues during each of a repeating time interval, such that queue underflow and overflow are minimized.
The above and other objects are achieved as is now described. A method and system are disclosed for allocating data input bandwidth from a source link to a plurality of N data queues each having a variable occupancy value, Q
i
(t), and a constant decrement rate, D
i
, where i designated the i
th
queue among the N queues. First, a threshold occupancy value, T, is designated for the N queues. During each time step of a repeating time interval, &Dgr;t, the occupancy value, Q
i
, is compared with T. In response to each and every of said N data queues having occupancy values exceeding T, pausing data transmission from the source link to the N data queues, such that overflow within the data queues is prevented. In response to at least one of the N data queues having an occupancy value less than or equal to T, selecting one among the N data queues to be incremented, and incrementing the selected data queue, such that underflow of the selected queue is prevented. In the context of scheduling one cell per time step, the value of T is one. Furthermore, the method of the present invention guarantees that output port occupancy shall never, in that context, exceed two cells.


REFERENCES:
patent: 4845710 (1989-07-01), Nakamura et al.
patent: 4970720 (1990-11-01), Esaki
patent: 5193090 (1993-03-01), Filipiak et al.
patent: 5268900 (1993-12-01), Hluchyj et al.
patent: 5375208 (1994-12-01), Pitot
patent: 5640389 (1997-06-01), Masaki et al.
patent: 5689500 (1997-11-01), Chiussi et al.
patent: 5689508 (1997-11-01), Lyles
patent: 5706288 (1998-01-01), Radhakrishnan et al.
patent: 5710909 (1998-01-01), Brown et al.
patent: 5712851 (1998-01-01), Nguyen et al.
patent: 5734650 (1998-03-01), Hayter et al.
patent: 5757771 (1998-05-01), Li et al.
patent: 5771234 (1998-06-01), Wu et al.
patent: 5790522 (1998-08-01), Fichou et al.
patent: 5796719 (1998-08-01), Peris et al.
patent: 6035333 (2000-03-01), Jeffries et al.
patent: 6182176 (2001-01-01), Ziegler et al.
patent: 6377546 (2002-04-01), Guerin et al.

Affiliated with

Also associated with

Rating

Mixed queue scheduler does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Mixed queue scheduler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mixed queue scheduler will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3257808