Versatile scheduler for ATM switches

Details Versatile scheduler for ATM switches Versatile scheduler for ATM switches

1998-11-24

2003-07-15

Kizou, Hassan (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S412000

Reexamination Certificate

active

06594264

ABSTRACT:

I. BACKGROUND OF THE INVENTION
The present invention relates generally to network management, and more specifically to scheduling messages for Asynchronous Transfer Mode (ATM) networks.
As ATM technology becomes increasingly popular for Broadband ISDN, it must be able to support traffic having different Quality of Service (QoS) requirements, and this requires priority control in scheduling the transmission of cells in ATM messages. Thus, optimal use of network resources without sacrificing QoS requires that the ATM switches use proper scheduling disciplines to mediate the departure of ATM cells and discard cells on a priority basis. These priority-based scheduling disciplines fall into one of three main categories: delay-based, loss-based, or delay-and-loss-based.
In the delay-based category, the Head-Of-Line (HOL) discipline offers stringent delay guarantees for real-time cells but at the expense of increased buffering delays for non-real-time cells. Several disciplines attempt to control the performance tradeoff between real-time and non-real-time cells. The Minimum Laxity Threshold (MLT) and Earliest Due Date (EDD) disciplines manage the performance trade-off from the time perspective. The MLT discipline grants higher priority to real-time cells only when the minimum laxity (defined as the amount of time until the earliest deadline of a queued real-time cell expires) has not exceeded threshold L. The EDD discipline allows a real-time cell to precede non-real-time cells arriving not prior to slot time D.
The Queue Length Threshold (QLT) and Threshold Based Priority (TBP) disciplines manage the performance trade-off from a space perspective. The QLT discipline concedes ERON, precedence to real-time cells only when the number of queued non-real-time cells does not exceed a threshold T. The TBP discipline, on the other hand, allows real-time cells to take precedence when the number of queued real-time cells exceeds a threshold L.
These delay-based disciplines retain adequate QoS for real-time cells while offering the best possible service to non-real-time cells. The success of these disciplines hinges on the effective determination of the thresholds L, D, or T.
In the loss-based category, the Complete Buffer Partitioning discipline divides the queue into two regions dedicated to loss-sensitive and loss-insensitive cells, respectively. This discipline is prone to queue wastage, however, because no queue sharing takes place.
The Nested Threshold Cell Discarding (NTCD) (or partial buffer sharing) discipline allows loss-insensitive cells to share the queue until the queue occupancy reaches a threshold T. The NTCD discipline results in poor space utilization, however, when the loss-sensitive traffic load is low.
To alleviate the problem, the Push-Out buffer sharing (PO) discipline allows newly-arriving loss-sensitive cells to push out loss-insensitive cells if the queue is full. However, the PO discipline does not offer any adjustment of the Cell Loss Ratio (CLR) for any traffic class.
In a Threshold Push-Out (TPO) discipline, a loss-sensitive cell observing a full queue upon arrival can push out a loss-insensitive cell if the number of loss-insensitive cells exceeds a threshold T. In a P
ow
Push-Out(P
ow
PO) discipline, a newly-arriving loss-sensitive cell observing a fall queue can push out a loss-insensitive cell with probability P
ow
.
To consider both delay and loss requirements in the delay-and-loss-based category, the Nested Threshold Cell Discarding with Multiple Buffers (NTCD-MB) discipline allows real-time cells to enter one smaller queue employing NTCD and allows loss-sensitive cells to enter another larger queue. Loss-sensitive cells are served only when there is no real-time cell in the smaller-size queue. This discipline offers stringent delay and loss guarantees for real-time cells and loss-sensitive cells, respectively, but wastes space because of two independent queues.
The Head-of-Line with Push-Out (HLPO) discipline uses HOL and PO disciplines for real-time cells and loss-sensitive cells, respectively. The HLPO discipline, however, does not provide any adjustment of the Cell Delay (CD) and CLR for any traffic class.
II. SUMMARY OF THE INVENTION
To provide an improved scheduling discipline, a scheduling method consistent with this invention comprises: (1) determining whether a message queue is full; (2) determining whether a newly-arriving cell is a high priority cell if the message queue is full; (3) placing the newly-arriving cell into the message queue before a predetermined number of low-priority cells in the queue if the newly-arriving cell is a high-delay-priority cell and if the queue is not full; and (4) placing the newly-arriving cell into the queue in the place of a selected low-priority cell in the queue if the queue is full, the newly-arriving cell is a high-loss-priority cell, and the selected low-loss-priority cell is located beyond a predetermined location in the queue.
A message scheduler consistent with this invention comprises a message queue and a processor for controlling the entry of cells into the queue. The processor includes (1) means for determining whether the message queue is full; (2) means for determining whether a newly-arriving cell is a high priority cell if the message queue is full; (3) means for placing the newly-arriving cell into the message queue before a predetermined number of low-priority cells in the queue if the newly-arriving cell is a high-delay-priority cell and if the queue is not full; and (4) means for placing the newly-arriving cell into the queue in the place of a selected low-priority cell in the queue if the queue is full, the newly-arriving cell is a high-loss-priority cell, and the selected low-loss-priority cell is located beyond a predetermined location in the queue.
Both the foregoing general description and the following detailed description are exemplary and explanatory only and do not restrict the invention claimed. The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate some systems and methods consistent with the invention and, together with the description, explain the principles of the invention.


REFERENCES:
patent: 5541912 (1996-07-01), Choudhury et al.
patent: 5555264 (1996-09-01), Sallberg et al.
patent: 5757771 (1998-05-01), Li et al.
patent: 5809021 (1998-09-01), Diaz et al.
patent: 6269079 (2001-07-01), Marin et al.
Enrique J Hernandez-Valencia and Flavio G Bonomi; Simulation of a Simple Loss/Delay Priority Scheme for Shared Memory ATM Fabrics; IEEE, 1993, pp. 1389-1394 vol. 3.*
Jen M. Hah and Maria C. Yuang; “A Delay and Loss Versatile Scheduling Discipline in ATM Switches;” Mar. 29-Apr. 2, 1998; IEEE Infocom '98, The Conference on Computer Communications, vol. 2; pp. 939-946.
S.T. Liang and M.C. Yuang; “Performance Analysis of Earliest-Due-Date Scheduling Discipline for ATM Switches;” International Journal of Modelling and Simulation, vol. 17, No. 4, 1997; pp. 1-15.
Duan-Shin Lee and Bhaskar Sengupta; “Queueing Analysis of a Threshold Based Priority Scheme for ATM Networks,” IEEE/ACM Transactions on Networking, vol. 1, No. 6, Dec. 1993; pp. 709-717.
Ren Chipalkatti, James F. Kurose, and Don Towsley; “Scheduling Policies for Real-Time and Non-Real-Time Traffic in a Statistical Multiplexer,” IEEE 1989; pp. 774-783.
Parviz Yegani, Marwan Krunz, and Herman Hughes; “Congestion Control Schemes in Prioritized ATM Networks,” IEEE 1994; pp. 1169-1172.
Joseph Y. Huh; “Resource Allocation for Broadband Networks;” IEEE 1988; pp. 1598-1608.
Arthur Y. M. Lin and John A. Silvester; “Priority Queueing Strategies and Buffer Allocation Protocols for Traffic Control at an ATM Integrated Broadband Switching System;” IEEE 1991; pp. 1524-1536.
S. Suri, D. Tipper, and G. Meempat; “A Comparative Evaluation of Space Priority Strategies in ATM Networks;” IEEE 1994; pp. 516-523.
Jen M. Hah and Maria C. Yuang; “Estimation-Based Call Admission Control with Delay and Loss Guarantees in ATM Networks.”
H. Jonathan Chao and I. Hakan Pekcan; “Queue Management with Mu

Affiliated with

Also associated with

Rating

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

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3046339