Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-02-09
2002-10-22
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395420, C370S412000, C370S465000
Reexamination Certificate
active
06470016
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to communication networks, and, more particularly, to servicing output queues dynamically according to bandwidth allocation in a frame environment.
BACKGROUND OF THE INVENTION
In today's information age, communication networks are used to transport vast amounts of information. As more and more information is carried over these communication networks, the various communication devices within the communication network, such as routers and switches, are called upon to process increasing amounts of data traffic. Often times, this data traffic includes data having different priority levels, and specifically different bandwidth requirements. Therefore, the various communication devices within the communication network must schedule data transmission opportunities for the data based upon, among other things, the relative bandwidth requirements of the data.
One well-known scheduling discipline is commonly referred to as Weighted Round Robin (WRR) scheduling. In WRR scheduling, each priority level is assigned a relative weight, and transmission opportunities are allocated for each priority level based upon the relative weights of the priority levels, using a round-robin technique to cycle between the priority levels.
Another well-known scheduling discipline is commonly referred to as Weighted Fair Queuing (WFQ) scheduling. In WFQ scheduling, transmission opportunities are allocated to the priority levels by computing a finishing time for each data transmission and scheduling data transmissions based on the computed finishing times. In WFQ scheduling, any unused bandwidth from one priority level is automatically reallocated to the other priority levels.
WRR scheduling and WFQ scheduling work well, and are relatively easy to implement, when the communication network uses fixed-length data transmissions (for example, in a cell-based communication network). However, scheduling data transmission opportunities in a frame-based communication network is more complex due to the variability of frame sizes. This variability of frame sizes can result in incorrect bandwidth allocation when WRR scheduling is used, and makes it difficult to compute finishing times when WFQ scheduling is used.
Thus, a need has remained for a scheduling discipline that is easy to implement in a frame-based communication network and is capable of dynamically reallocating any unused bandwidth from one logical communication channel to the other logical communication channels.
SUMMARY OF THE INVENTION
In accordance with one aspect of the invention, an adaptive weighted round robin scheduling technique schedules variable-length frame transmissions from a plurality of output queues having different transmission priorities by first allocating, for each queue, a number of bandwidth segments for a bandwidth cycle and a number of transmission opportunities for a round robin cycle, and then processing the queues consecutively in a round-robin fashion, beginning with a highest priority queue, until none of the queues has any bandwidth remaining. More specifically, during each iteration of a round robin cycle, a queue is permitted to transmit a frame if the queue has at least one remaining transmission opportunity, the queue has a frame ready for transmission, and the queue has at least one remaining bandwidth segment, and furthermore the number of transmission opportunities for the queue is decremented by at least one. Upon transmitting a frame, the number of bandwidth segments for the queue is decreased by the number of bandwidth segments in the frame. If a queue has no frame ready for transmission, then the queue may be either penalized, in which case the number of bandwidth segments for the queue is reduced, or forced to forfeit its bandwidth segments, in which case any remaining bandwidth segments are reallocated to other queues and the number of bandwidth segments and the number of transmission opportunities for the queue are set to zero.
REFERENCES:
patent: 6018527 (2000-01-01), Yin et al.
patent: 6061330 (2000-05-01), Johansson
patent: 6134217 (2000-10-01), Stiliadis et al.
patent: 6188698 (2001-02-01), Galand et al.
patent: 6246687 (2001-06-01), Siu
patent: 6304552 (2001-10-01), Chapman et al.
Kalkunte Mohan
Mangin Jim
Bromberg & Sunstein LLP
Nortel Networks Limited
Olms Douglas
Sa Phirin
LandOfFree
Servicing output queues dynamically according to bandwidth... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Servicing output queues dynamically according to bandwidth..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Servicing output queues dynamically according to bandwidth... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2927644