Increment scheduler

Details Increment scheduler Increment scheduler

1997-06-13

2001-03-27

Olms, Douglas W. (Department: 2732)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S235000, C370S229000

Reexamination Certificate

active

06208652

ABSTRACT:

FIELD OF THE INVENTION
The present invention is related to a scheduler. More specifically, the present invention is related to a scheduler which is composed of a mechanism that selects among a small number of bins (which determines the range of supported rates) and a second mechanism which selects among the sessions within the bins (which determines the precision of supported rates).
BACKGROUND OF THE INVENTION
ATM (asynchronous transfer mode) is used for communications purposes in integrated services digital networks. Through these networks, ATM cells belonging to a multitude of sessions travel to their desired destinations. Due to the potential for sources to transmit more bandwidth to a link than it can sustain, a condition called congestion may occur. To protect sessions from transient overload or belligerent sources, schedulers are used on outgoing links in ATM switches.
Ideally, a scheduler should be able to service every session at its guaranteed rate provided that the sum of the rates guaranteed to the sessions does not exceed the available capacity of the link. To deliver a guaranteed service rate for a session, each session must have its cells identified and stored in a FIFO queue of cells for said session. Ideally, the sessions should receive smooth service. Furthermore, a scheduler must be efficient for either a hardware or a software implementation for high speed operation. In the past, schedulers either could not deliver guarantees, provided them in a rather bursty manner, and/or had high implementation complexity.
The present invention enables schedulers to be designed with low implementation complexity while providing smooth service while being able to support a very large number of rates.
Deficit Round Robin
One scheduler designed to provide fair service among variable sized packets [M. Shreedhar and G. Varghese. “Efficient fair queuing using deficit round robin”, in Proc SIGCOMM'95. Boston, Mass., August 1995], uses a hashing function to assign sessions to buckets. The probability of collisions of multiple sources sharing a bucket eliminates the ability to provide guarantees, and is acknowledged to be “best suited for datagram networks.” Simple round robin provides the same function in ATM networks. If a wide range of rates is desired, the fastest sessions will be serviced in large bursts as in weighted round robin.
Geometric Weighted Groups
One scheduler designed to perform rate control in ATM networks [D. Klausmeier. “Method and apparatus for performing communication rate control using geometric weighted groups.” U.S. Pat. No. 5,561,663. Oct. 1, 1996], uses geometric weighted groups to organize sessions into multiple groups. The mechanism is described using a binary representation of the accumulation rate, where the rate of session i is represented as:
a
i
=
(
a
i0
⁢
x2
0
)
+
(
a
i1
⁢
x2
1
)
+
…
+
(
a
i
⁢
(
m
-
1
)
⁢
x2
m
-
1
)
)
=
∑
j
=
0
m
-
1
⁢
 
⁢
a
ij
⁢
x2
0
⁢
j
wherein a
ij
=0 or 1.
This uses m groups of sessions, with one group per corresponding a
ij
. A session will be entered into every group for which its coefficient is a 1. A credit balance is maintained for each group equal to the number of entries in the group times the weight factor of its position. The weight factor for each session group j is
2
j
when the binary coefficients are used to define the groups. When a group is serviced, the first session on the group's list is served, and sent to the end of its linked list.
While this enables a wide range of rates to be represented with a small number of groups, it can exhibit bursty service, has high memory requirements, and is not ameable for operation as a work conserving scheduler. When a session is scheduled in many groups concurrently, the session may arrive to the head of many of these groups and be serviced from this multitude of groups in immediate succession. This may result in a cell being transmitted for this session in a burst of cells with length equal or greater than the number of bins the session is scheduled in.
Each session must allocate PM=m×log
2
MaxConns bits of memory for maintaining its pointer memory. Where m is the number of groups, and MaxConns is the maximum number of supportable sessions. For a switch requiring 10 cells per second of granularity for an OC-3 link with support for 64 thousand sessions, 32 Bytes are required per session (2 MB of memory for all sessions) to maintain the pointers.
While memory population is an issue that may be addressed with the application of additional money in the form of memory chips, the described mechanism does not adequately address the needs of a work conserving scheduler. In work conserving operation, the scheduler must never stall when a cells exist in the memory awaiting service. A commonly used method of removing sessions from te scheduler when their queues are drained would be expensive to apply to this mechanism, because a session may be enqueued in multiple groups, and is not necessarily at the head of all but the group that served it. The linked lists that are maintained for the groups would have to be made into doubly linked lists to enable a session to be removed from all groups when it becomes idle. Similarly, a session would have to be inserted into every group for which it should be scheduled whenever a cell arrives into an empty queue. This dramatically increases the required memory references and doubles the required pointer memory space, which was already rather large.
One scheduler designed to be hardware efficient [J. L. Rexford, A. G. Greenberg, and F. G. Bonomi. “Hardware-Efficient Fair Queuing Architectures for High-Speed Networks” in Proc IEEE INFOCOM 1996], uses a hierarchical structure to efficiently schedule among sessions. A calendar queue is used to select among the sessions in the rate bins. Each calendar queue consists of multiple FIFOs of sessions, requiring pointer manipulations among the component queues in addition to operations within the FIFOs themselves to select a session for service.
SUMMARY OF THE INVENTION
The present invention pertains to a scheduler for a server for serving ATM cells. The scheduler comprises R rate bins where R is greater than or equal to 2. The scheduler comprises a controller which places a session having a desired rate into a rate bin of the R rate bins.
The present invention pertains to a system for transmitting ATM cells. The system comprises an ATM network along which ATM cells are transmitted. The system comprises S sources where S is greater than or equal to 1 and is an integer. Each source is connected to the network and produces ATM cells for transmission on the network. The system comprises D destinations where D is greater than or equal to 1 and is an integer. Each destination is connected to the network. Each destination receives ATM cells from the network. The system comprises a server connected to the ATM network. Additionally, the system comprises a scheduler which has R different rate bins for holding sessions, where R is an integer greater than or equal to 2. The scheduler schedules service by the server among the R different rate bins, with precision P, where P is an integer and the number of bits assigned for precision. The scheduler is connected to the server.
The present invention pertains to a method for providing service by a server to sessions. The method comprises the steps of receiving a first session having a rate at a scheduler. Next there is the step of placing the first section into a rate bin of R rate bins which has a rate corresponding to the rate of the session. Then there is the step of receiving a second session having a rate at the scheduler. Next there is the step of placing the second session into the rate bin. Next there is the step of providing service by the server to the first session. Then there is the step of determining whether the first session still requires more than a predetermined amount of service from the server if the first session does require more than the predetermi

Affiliated with

Also associated with

Rating

Increment 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 Increment scheduler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Increment scheduler will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2460905