Egress port scheduling using memory efficient request storage

Details Egress port scheduling using memory efficient request storage Egress port scheduling using memory efficient request storage

1999-07-09

2002-10-08

Kim, Matthew (Department: 2186)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output access regulation

C710S030000, C710S029000, C710S033000, C709S232000, C709S236000

Reexamination Certificate

active

06463484

ABSTRACT:

FIELD
The invention relates generally to an egress port scheduler utilizing an array implementation which supports three scheduling modes.
BACKGROUND OF THE INVENTION
Communications technology is now utilizing digital technology to transmit and integrate voice, video, and data at high speeds over local area and wide area networks. This technology offers a flexible and efficient service, but such high speed networks tend to be susceptible to congestion. Severe congestion can result in data loss which exceeds an acceptable level. However, effective scheduling can prevent congestion from occurring thus maintaining the reliability of the network at high speeds.
Existing schedulers tend to fall into one of two classes:
queue or event based schedulers; and
calendar based schedulers.
The queue or event based scheduler places the service requests into one or more queues. The queue would usually take the form of a first-in-first-out (FIFO) memory or linked list. An event based scheduler requires n queues, where n is the number of priority levels or classes of service. The scheduler determines which queue should be serviced next then picks the next available request from the selected queue. These storage techniques can consume relatively large amounts of memory since the full address of the service requester would need to be stored within the data structure. Furthermore, while requests can be sorted into different queues, once the request is in the queue, the requests must be serviced in the order which they were received, even if this allows one request source to dominate the scheduling activity for a significant period of time.
To alleviate the problem of starvation, where one request source dominates the scheduling activity to the detriment of the other sources, weighted fair queuing was introduced. The principles of weighted fair queuing are described in the papers “Analysis and Simulation of a Fair Queuing Algorithm” by Alan Deters, Sririvasan Keshav, and Scott Shenker(Internetworking: Research and Experience Vol. 1, pp3-26, 1990, John Wiley and Sons) and “A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single Node Case” by Abhay Parekh and Robert Gallager (IEEE/ACY Transactions on Networking, Vol. 2, No. 2, April 1994). The weighted fair queuing system is based on the principle of assigning a timestamp to each incoming packet with respect to a local virtual clock. Packets with a lower timestamp would be processed at a higher priority. This system requires significant mathematical calculations and utilizes FIFO data structures to queue all incoming packet requests.
Subsequently, a more refined and more easily implemented fair queuing system was developed. In their paper “Credit Based Fair Queuing (CBFQ) A simple and feasible scheduling algorithm for packet networks” (B. Bensaou, K. T. Chan, and D. H. K. Tsang; IEEE ATK Workshop Proceedings, Portugal; May 1997) Bensaou, Chan and Tsang introduced a credit based fair queuing system which assigns a number of credits to each tragic source using a leaky bucket approach. However, this system sill requires significant mathematical calculations and utilizes FIFO data structures to queue all incoming packer requests. Furthermore, queue/event based scheduling requires significant amounts of memory to maintain the queues.
Calendar based schedulers insert service requests into lists which are scanned on a periodic basis. While this technique allows events to be scheduled in something other than a first-in-first-out fashion, traversing the list to determine where a new event should be scheduled is time consuming. Furthermore, as in queue/event based scheduling, the lists tend to require significant amounts of memory.
Conventional strict priority traffic schedulers always service the highest priority request first. During periods of high traffic and congestion, starvation of the lower priority requests exists. Also, the conventional leaky bucket type schedulers, although they are able to allocate traffic bandwidth resources between classes of service, bandwidth will often be wasted due to inactivity of a particular class to which the bandwidth has been allocated.
Accordingly, it is an object of the invention to provide an improved method and apparatus for scheduling service requests.
It is a further object of the invention to provide a storage mechanism that is more efficient than a FIFO data structure or a linked list.
SUMMARY OF THE INVENTION
These and other objects of the invention are provided in a new and improved egress port manager having a queue allocate and data block processor, transmit pending arrays and a queue fetch scheduler. The egress port manager accepts service requests from upstream data sources. Each service request contains a destination channel ID, a source channel ID and a priority field. The service requests are stored by the queue allocate and data block processor by setting a bit in a transmit pending array. The transmit pending array consists of a plurality of priority vectors, each having a plurality of multi-bit lines. The position of a set bit in the transmit pending array indicates the port that is requesting service and the priority or class of service of the particular service request.
The egress port manager supports three scheduling algorithms, Strict Priority Scheduling, Weighted Fair Scheduling and Weighted Priority Scheduling. The queue fetch scheduler of the egress port manager implements the scanning, scheduling and frame processing mechanisms. During operation, the vector to be searched is chosen pursuant to the scheduling algorithm that is employed. Once a vector is chosen, the vector is searched one line at a time. Each line of the vector is retrieved and searched using a multi-bit priority encoder. If a set bit is found, the scanner stops, sends a Queue Fetch message and waits for a Data Block to be returned. If the End Of Frame flag is not set in the Data Block header, the scanner sends another Queue Fetch message. If the End Of Frame fag is set, the queue allocate and data block processor clears the corresponding set bit and the scanner returns to searching the transmit pending array.
The progression of the search after a set bit has been found and the frame processed, is determined by the selected scheduling mode. Using Strict Priority Scheduling after processing a frame, the search is restarted within the vector having Priority 0 (the highest priority) and progresses to lower priority vectors only if the higher priority vector is vacant. In his tanner, the highest priority requests are always processed before lower priority requests.
If the Weighted Fair Scheduling mode is implemented on the egress port manager, a credit store is maintained for each priority level. One credit is deducted from the credit store of a particular priority level for each Queue Fetch command sent from that level. When all the vectors have been processed, additional credits are added to all the credit stores. A vector is considered to have been processed if either the credits in the vectors' store are insufficient to process a maximum sized frame or no bits are set in the vector. The amount of credits added is programmable for each priority level thus determining the weighting for each priority level of traffic. A second set of programmable values sets the maximum number of credits which can accumulate for each priority level. After a set bit has been found and the waiting frame has been processed, the search will continue within the current vector if sufficient credits to process a maximum sized frame remain; otherwise the search continues with the next vector which has sufficient credits to process a maximum sized frame.
If the Weighted Priority Scheduling mode is implemented on the egress port manager, it uses the same credit system as weighted Fair Scheduling. After processing a frame, the search does not continue within the present vector but continues with the highest priority vector with sufficient credits to process a maximum sized frame.
Other objects and advantage

Affiliated with

Also associated with

Rating

Egress port scheduling using memory efficient request storage does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Egress port scheduling using memory efficient request storage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Egress port scheduling using memory efficient request storage will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2947992