Patent Publication Number: US-6904045-B1

Title: Method and apparatus for guaranteeing data transfer rates and delays in asynchronous transfer mode networks using pivot sessions

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application is related to U.S. patent application Ser. No. 60/137,542, filed Jun. 4, 1999. This application is also related to commonly assigned U.S. patent application Ser. No. 09/247,742, filed Feb. 9, 1999; U.S. patent application Ser. No. 09/247,779, filed Feb. 9, 1999; and U.S. patent application Ser. No. 09/432,976, filed Nov. 3, 1999. 

   COPYRIGHT NOTICE 
   A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. 
   BACKGROUND OF THE INVENTION 
   The present invention relates to Asynchronous Transfer Mode (ATM) networks, and in particular to a method and apparatus to compute and sort the timestamps in a system for scheduling packets in Asynchronous Transfer Mode networks for guaranteeing data transfer rates to data sources and data transfer delays from data sources to destinations. 
   In ATM systems and networks, an important objective is to minimize the complexity involved in the implementation of per-Virtual-Connection (per-VC) schedulers, and to minimize the cost differential of systems including such schedulers with respect to systems using less sophisticated scheduling. More particularly, the minimization of the implementation cost of per-VC schedulers which achieve near-optimal delay and fairness properties in approximating the Generalized Processor Sharing (GPS) policy is a central issue in next-generation ATM switches. 
   Among GPS-related scheduling disciplines, the class of Packet-by-packet Rate-Proportional Servers (P-RPS) has optimal delay properties. Several well-known scheduling algorithms, such as Packet-by-packet Generalized Processor Sharing (P-GPS), Virtual Clock, Frame-based Fair Queuing (FFQ), and Starting-Potential Fair Queuing (SPFQ), are P-RPS. They differ in the specific function used as system potential, interchangeably referred to as virtual time, which tracks the amount of work that is done by the server and is used to compute, for each cell in the system, a timestamp or finishing potential which specifies when the cell should be transmitted relative to other cells. 
   While the delay bounds guaranteed by a scheduler are generally accepted as the single measure of interest to characterize its delay properties, two distinct measures of fairness are used. 
   The Service Fairness Index (SFI), introduced by Golestani as described in S. J. Golestani, “A Self-Clocked Fair Queuing Scheme for Broadband Applications”, PROCEEDINGS OF INFOCOM 94, pp. 636-646, April 1994; captures the distance of the scheduler from the ideal fairness of GPS in distributing service to connections that are simultaneously backlogged. The Worst-case Fairness Index (WFI), defined by Bennett and Zhang in J. C. R. Bennett and H. Zhang, “Hierarchical Packet Fair Queuing Algorithms”, PROCEEDINGS OF SIGCOMM 96, pp. 143-156, Aug. 1996; measures the maximum amount of time that a backlogged connection may have to wait between two consecutive services. Schedulers with minimal WFI are called worst-case-fair schedulers. The achievement of worst-case-fairness is rather desirable, since the distribution of service to competing connections in a scheduler with small WFI is much less bursty than in a scheduler with large WFI. 
   With P-RPS schedulers, worst-case fairness is achieved by using the Smallest Eligible Finishing potential First (SEFF) cell-selection policy. With the SEFF policy, the scheduler grants the next service to the cell having the minimum timestamp among those which satisfy the eligibility condition, i.e., those cells whose starting potentials are not greater than the current value of system potential. For each connection, the eligibility condition needs to be verified only for the cell at the head of the corresponding queue, since this is the cell with the minimum starting potential among all cells in that queue. Depending on the specific P-RPS, the resulting scheduler may be work-conserving (P-GPS and SPFQ) or non-work-conserving (Virtual Clock and FFQ). 
   Any P-RPS scheduler using the SEFF selection policy achieves optimal delay bounds, is worst-case fair, and has an SFI very close to the theoretical lower bound in packet-by-packet servers. Because of their near-optimal delay and fairness properties, worst-case-fair P-RPS schedulers have gained popularity, and considerable attention has been devoted to simplifying their implementation. Four factors contribute to the total implementation cost of a worst-case-fair P-RPS. One factor is the complexity of maintaining the system-potential function, and is scheduler-specific. For a scheduler supporting V connections, this complexity is O(V) in P-GPS, O(log V) in SPFQ, and O( 1 ) in Virtual Clock and FFQ. The other three contributions, which are common to all worst-case-fair P-RPS, are (i) the complexity of identifying the eligible cells, (ii) the cost of handling and storing the timestamps, and (iii) the complexity of sorting the timestamps of the eligible cells in order to select the one with the minimum timestamp for the next service. 
   The complexity of implementing the SEFF policy is a considerable burden when the scheduler&#39;s implementation is based on conventional priority queues, since a worst-case of O(V) cells may become eligible at the same time. To solve this problem, Bennett et al. have introduced, in J. C. R. Bennett, D. C. Stephens, and H. Zhang, “High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks”, PROCEEDINGS OF ICNP 97, pp. 7-14, October 1997; a simplified scheduling structure, referred to as the discrete-rate scheduler, which can be used when the system is only required to support a relatively small discrete set of guaranteed service rates at any time, an assumption that is certainly realistic in most, if not all, ATM switches. 
   In the discrete-rate scheduler, backlogged connections with the same service rate are grouped together in a rate First-In-First-Out (FIFO) queue, and scheduling is performed only among the connections at the head of each rate FIFO queue. Thus, the number of connections for which the eligibility condition must be checked and the number of timestamps to be sorted at every timeslot is greatly reduced, to be equal to the number of supported rates. In addition, the complexity of implementing the SEFF policy is considerably decreased. In the case of a worst-case-fair P-RPS, this discrete-rate approach only introduces a negligible degradation in delay bounds, and conserves both the minimal WFI and the excellent SFI of the same P-RPS implemented with conventional priority queue. In order to implement a scheduler with near-optimal delay bounds, the discrete-rate approach requires that the scheduler under consideration be worst-case fair. However, the total implementation cost of the resulting discrete-rate scheduler is not only dramatically lower than that of worst-case-fair schedulers implemented with conventional priority queues, but is even competitive with the cost of non-worst-case-fair schedulers implemented with other known techniques. The competitive cost, together with the achievement of worst-case fairness, explains the recent popularity of the discrete-rate approach for the implementation of P-RPS schedulers. 
   The discrete-rate scheduler described in J. C. R. Bennett, D. C. Stephens, and H. Zhang, “High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks”, PROCEEDINGS OF ICNP 97, pp. 7-14, October 1997; although constitutes an important improvement in reducing the implementation complexity of worst-case-fair P-RPS schedulers, still requires computing and storing a timestamp for each connection, which is a significant contribution to the cost of the scheduler. For convenience as described herein, the scheduling architecture presented in J. C. R. Bennett, D. C. Stephens, and H. Zhang, “High Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks”, PROCEEDINGS OF ICNP 97, pp. 7-14, October 1997; is referred to as the discrete-rate scheduler with per-connection timestamps. 
   To further reduce implementation complexity, in F. M. Chiussi and A. Francini, “Implementing Fair Queuing in ATM Switches: The Discrete-Rate Approach”, PROCEEDINGS OF INFOCOM 98, pp. 272-281, March 1998; a discrete-rate scheduler is presented which does not require the computation and storage of a timestamp per connection and only maintains a single timestamp per rate. This no-per-connection-timestamp scheduler still achieves near-optimal delay bounds and is worst-case fair. However, the price paid for the elimination of the per-connection timestamps is that the SFI is compromised. 
   Another variation of the discrete-rate scheduler, presented in F. M. Chiussi and A. Francini, “A Low-Cost Architecture for the Implementation of Worst-Case-Fair Schedulers in ATM Switches”, PROCEEDINGS OF GLOBECOM 98, November 1998; does not require a whole timestamp per connection, but only uses a single bit per connection, plus one timestamp per rate FIFO queue. The single-bit-timestamp scheduler achieves near-optimal delay bounds, and fairness indices (both SFI and WFI) that are identical to those of the discrete-rate scheduler with per-connection timestamps. 
   Such discrete-rate schedulers and their implementations are further described in commonly assigned U.S. patent application Ser. No. 09/247,742, filed Feb. 9, 1999; U.S. patent application Ser. No. 09/247,779, filed Feb. 9, 1999; and U.S. patent application Ser. No. 09/432,976, filed Nov. 3, 1999, each of which are incorporated herein by reference. 
   SUMMARY OF THE INVENTION 
   It is an object of the present invention to provide a technique to further reduce the implementation complexity of worst-case-fair P-RPS schedulers in ATM systems while retaining near-optimal delay and fairness properties. An apparatus and method implementing a No-Per-Connection-Timestamp Discrete-Rate Scheduler with Pivot Session are described herein which do not strictly require the computation and storage of any scheduling-related information per connection, not even a single bit, but only maintain one variable service rate and one timestamp per rate FIFO queue. In a first embodiment, the implementation of the pivot-session-based scheduler does not make use of per-connection scheduling information, and further embodiments maintain a single scheduling-related bit per connection. The disclosed scheduler achieves near-optimal delay bounds, and fairness indices (both SFI and WFI) that are almost identical to those of the discrete-rate scheduler with per-connection timestamps. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  illustrates a first embodiment of the disclosed scheduler; 
       FIGS. 2A-2B  illustrate flowcharts of the operation of the first embodiment of  FIG. 1 ; 
       FIG. 3  illustrates a second embodiment of the disclosed scheduler; 
       FIGS. 4A-4B  illustrate flowcharts of the operation of the second embodiment of  FIG. 3 ; 
       FIG. 5  illustrates a third embodiment of the disclosed scheduler; and 
       FIGS. 6A-6B  illustrate flowcharts of the operation of the third embodiment of FIG.  5 . 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   The present invention relates to a technique for reducing the implementation complexity of a worst-case-fair GPS-related scheduler in ATM systems. 
   Referring to  FIGS. 1-6B , the apparatus and method of use implement, in one or more embodiments, a No-Per-Connection-Timestamp Discrete-Rate Scheduler with Pivot Session, which arbitrates the distribution of service to competing connections using a special backlogged session, referred to as the pivot session, in each backlogged rate FIFO queue. As used herein, rate FIFO queues are interchangeably referred to as macro-sessions. 
   In order to overcome the unfairness of the no-per-connection-Timestamp discrete-rate schedulers of the prior art, the scheduler  10  with pivot session maintains variable macro-session rates. An improper updating mechanism for the macro-session rates would easily compromise the delay bounds and fairness indices of the scheduler. The basic condition to avoid such a degradation of performance requires that the virtual timestamp of a backlogged session i; that is, the timestamp of the corresponding macro-session I at the time session i reaches the head of the rate FIFO queue, be sufficiently close to the system potential at the time the session is queued at the tail of the macro-session. In order for the difference between the virtual timestamp and the system potential to be strictly bounded, the service rate of the macro-session must be frozen for a sufficiently long period of time. It is straightforward, at this point, to identify a complete cycle of services within the macro-session as a candidate for the updating period of the macro-session rate: if B I (m k ) sessions are backlogged in macro-session I at timeslot m k  when R I (m k )=B I (m k )·r I  is determined, then the next update of R I  occurs at timeslot m k+1 , just after the last of the B I (m k ) sessions has been serviced and the timestamp of macro-session I has increased exactly by 1/ r I . In this way, the virtual timestamps of all the sessions that are backlogged in macro-session I at timeslot m k  are fully defined at timeslot m k , and the differences between the timestamps of all the sessions that become backlogged between m k  and m k+1  and the system potential P(m k ) are easy to bound as well. 
   Using the pivot session to detect the boundaries of service cycles in the respective rate FIFO queues, the no-per-connection-timestamp discrete-rate scheduler  10  not only retains near-optimal delay bounds and WFI, but additionally achieves excellent SFI, due to the continuous adaptation of the service rates guaranteed to the macro-sessions, which avoids unfair redistribution of leftover bandwidth. 
   In a first embodiment shown in  FIG. 1 , the no-per-connection-timestamp discrete-rate scheduler  10  using pivot sessions has a server  12  simultaneously supporting only a fixed number N of guaranteed service rates  14 - 18  at any given time, and connections with the same service rate r I  are queued, when backlogged, in the same rate FIFO queue I of queues  20 - 24 . Each rate FIFO queue I is implemented as a linked list of connections, such as connections  26 - 28 , referred to as virtual connections VC I,a , VC I,b , . . . , VC I,i  in  FIG. 1 , with a pointer HEAD(I) to the first connection in the list and a pointer TAIL(I) to the last connection in the list, such as HEAD(I)  30  and TAIL(I)  32  of the first rate FIFO queue  20  shown in FIG.  1 . 
   When a connection becomes backlogged, it is queued at the tail of the corresponding rate queue. When a rate queue is granted a service, the connection that is currently at its head is de-queued, and if still backlogged, queued back at the tail. In the embodiment of  FIG. 1 , the scheduler  10  does not use any per-connection scheduling information, but only maintains a timestamp F I , a queue length B I , a variable service rate R I , and a service counter M I , for each rate FIFO queue I. 
   The scheduler  10  grants service to the macro-sessions  34 - 38  according to the values of their timestamps. At timeslot m, the scheduler searches for the macro-session timestamp F s(m)  which has the minimum value among the timestamps of currently backlogged macro-session, in which a macro-session is backlogged when it has at least one connection queued, and satisfies the eligibility condition for processing by the SEFF selector  40  according to the SEFF cell-selection policy: 
         F     S   ⁡     (   m   )         =       min     1   ≤   l   ≤   N       ⁢     {         F   I     ⁢           ⁢   such   ⁢           ⁢   that   ⁢           ⁢     F   I       ≤       P   ⁡     (   m   )       +     1     R   I           }           
 
   A flowchart describing the operation of the scheduler for maintaining the timestamps and the variable service rates of the macro-sessions is shown in  FIGS. 2A-2B . 
   Generally, according to the disclosed method, at timeslot m, when a new cell of connection i is received, the cell is queued into the corresponding cell queue. If connection i was previously idle, its corresponding rate FIFO queue I is identified. The queue length B I  of the rate queue is incremented and then, if the rate FIFO queue was also idle (in which case session i becomes the pivot session of macro-session I, such as pivot session  28  in FIG.  1 ), its service rate R I  is set equal to the service rate r I  of the connection, and the macro-session timestamp is computed as follows: 
         F   I     =       P   ⁡     (   m   )       +     2     R   I             
 
   Then, the scheduler sets the service counter M I  equal to the macro-session queue length B I . 
   If macro-session I was not idle, connection i is simply appended to the tail of the corresponding rate FIFO queue, and the macro-session queue length is incremented. If, instead, connection i was already backlogged before receiving the new cell, no operation is required on the macro-session variables. 
   At timeslot n, when a connection i is selected for service, it is de-queued from the corresponding macro-session I and its head-of-the-queue cell is transferred to the transmitter. If connection i becomes idle after being serviced, the scheduler decrements the queue length B I  of macro-session I, otherwise it queues connection i back to the tail of rate queue I. Then, the scheduler decrements the service counter M I  of macro-session I. If the service counter M I  becomes equal to zero (that is, connection i was the pivot of macro-session I) and macro-session I remains backlogged, the scheduler updates the macro-session service rate:
 
 R   I   =B   I ( n )· r   I 
 
and sets the service counter in such a way that the connection that is currently at the tail of the rate FIFO queue becomes the new pivot of macro-session I:
 
 M   I   =B   I ( n )
 
   Finally, the scheduler updates the timestamp of macro-session I: 
         F   I     =       max   ⁡     (       P   ⁡     (   n   )       ,     F   I       )       +     1     R   I             
 
and the system potential P according to the algorithm adopted for its maintenance.
 
   Referring to  FIGS. 2A-2B , in operation, the method determines in step  44  if there are any new data packets. If not, the method then determines in step  46  if there are any backlogged connections. If not, the method loops back to step  44 . Otherwise, after step  46 , the method performs step  74 . 
   If, in step  44 , there are new data packets, the method selects one data packet in step  48 , identifies its connection in step  50 , stores the data packet in a respective connection queue in step  52 , and increments the queue length (QL) of the connection in step  54 . The method then determines in step  56  if the queue length of the connection is equal to 1. If not, the method performs step  74 . Otherwise, the method proceeds to step  58  to increment the number of backlogged connections, and identifies the rate queue (RQ) of the connection in step  60 . The connection is then stored in the identified rate queue in step  62 , and the length of the rate queue is incremented in step  64 . The method then determines if the length of the rate queue is equal to 1 in step  66 . If not, the method proceeds to step  74 . 
   Otherwise, in step  66 , if the rate queue length is equal to 1, the method proceeds to step  68  to set the service counter of the rate queue equal to the length of the rate queue. The method then sets the service rate of the rate queue in step  70 , sets the timestamp of the rate queue in step  72 , and proceeds to step  74  in FIG.  2 B. 
   In step  74 , the method determines if the transmitter in front of the output interface of the ATM system is available (that is, if the transmitter is currently not dispatching a cell through the output interface). If the transmitter is not available, the method loops back to step  44 . Otherwise, if the transmitter is available, the method proceeds to step  76  to determine if the last serviced connection is available (that is, if the last connection for which a cell was dispatched through the output interface is still waiting for its status to be updated to reflect the just completed transmission). If not, the method then selects a new connection to serve from one of the rate queues in step  78 , sends a data packet from the connection to the transmitter in step  80 , and loops back to step  44 . 
   If the last serviced connection is available in step  76 , the method proceeds to remove the connection from the rate queue in step  82 , decrements the queue length of the connection in step  84 , and determines in step  86  if the queue length of the connection is equal to zero. If not, the method stores the connection in the rate queue in step  88  and decrements the service counter of the rate queue in step  90 . Otherwise, in step  86 , if the queue length is equal to zero, the method decrements the number of backlogged connections in step  92 , and decrements the length of the rate queue in step  94 , and then determines in step  96  if there are any backlogged connections. If so, the method proceeds to step  90 ; otherwise, the method loops back to step  44 . 
   After performing step  90 , the method determines in step  98  if the service counter of the rate queue is equal to zero. If not, the method updates the timestamp of the rate queue in step  100 , updates the system potential in step  102 , and loops back to step  78 . 
   Otherwise, in step  98 , if the service counter is equal to zero, the method determines in step  104  if the length of the rate queue is equal to zero. If so, the method proceeds to step  100 . Otherwise, the method updates the service rate of the rate queue in step  106 , sets the service counter of the rate queue in step  108 , and then proceeds to step  100 . 
   In  FIG. 3 , the basic structure of a second embodiment  110  of the no-per-connection-timestamp discrete-rate scheduler with pivot session is illustrated which makes use of a single bit per connection (the pivot bit). Compared to the structure of the scheduler  10  of  FIG. 1 , per-connection bits  112 ,  114  associated with each VC in  FIG. 3  replace the per-macro-session service counters  116 , shown in FIG.  1 . The operation of the scheduler in this second embodiment  110  is shown in the flowchart of  FIGS. 4A-4B . 
   Generally, instead of being implicitly identified by the value of the service counter M I , the pivot session of macro-session I, such as pivot session  28 , is explicitly marked with a specific value of the connection bit  114 , labeled b VC,I , which, for example in  FIG. 3 , has the value of  1  to mark the pivot session  28 . 
   Referring to  FIGS. 4A-4B , in operation, the second embodiment of  FIG. 3  performs the method by determining in step  118  if there are any new data packets. If not, the method then determines in step  120  if there are any backlogged connections. If not, the method loops back to step  118 . Otherwise, after step  120 , the method performs step  148 . 
   If, in step  122 , there are new data packets available, the method selects one data packet in step  122 , identifies its connection in step  124 , stores data packets in a respective connection queue in step  126 , and increments the queue length (QL) of the connection in step  128 . The method then determines in step  130  if the queue length of the connection is equal to 1. If not, the method performs step  148 . Otherwise, the method proceeds to step  132  to increment the number of backlogged connections, and identifies the rate queue (RQ) of the connection in step  134 . 
   The method then determines in step  136  if the length of the rate queue is equal to zero. If not, the method performs step  138  to store the connection in the rate queue. Otherwise, after step  136 , the method proceeds to step  140  to set the pivot bit of the connection, and then sets the service rate of the rate queue in step  142  and the timestamp of the rate queue in step  144 . 
   After step  144 , the connection is stored in the identified rate queue in step  138 . After step  138 , the length of the rate queue is incremented in step  146 , and the method proceeds to step  148 . 
   In step  148 , the method determines if the transmitter in front of the output interface of the ATM system is available. If not, the method loops back to step  118 . Otherwise, if the transmitter is available, the method proceeds to step  150  to determine if the serviced connection is available. If not, the method then selects a connection to serve from one of the rate queues in step  152 , sends the data packet from the connection to the transmitter in step  154 , and loops back to step  118 . 
   If the last serviced connection is available in step  150 , the method proceeds to remove the connection from the rate queue in step  156 , decrements the queue length of the connection in step  158 , saves the pivot bit of the connection in step  160 , resets the pivot bit of the connection in step  162 , and then determines in step  164  if the queue length of the connection is equal to zero. If not, the method stores the connection in the rate queue in step  166  and proceeds to step  168 . Otherwise, in step  164 , if the queue length is equal to zero, the method decrements the number of backlogged connections in step  170  and the length of the rate queue in step  172 , and then determines in step  174  if there are any backlogged connections. If so, the method proceeds to step  168 ; otherwise, the method loops back to step  118 . 
   At step  168 , the method determines if the saved pivot bit is set. If not, the method updates the timestamp of the rate queue in step  176 , updates the system potential in step  178 , and loops back to step  152 . 
   Otherwise, in step  168 , if the saved pivot bit is set, the method determines in step  180  if the length of the rate queue is equal to zero. If so, the method proceeds to step  176 . Otherwise, the method updates the service rate of the rate queue in step  182 , sets the pivot bit of the connection at the rate queue tail in step  184 , and then proceeds to step  176 . 
     FIG. 5  shows the basic structure of a third embodiment  190  of the scheduler, which also makes use of per-connection bits. In this case, similar to the single-bit-timestamp discrete-rate scheduler described in F. M. Chiussi and A. Francini, “A Low-Cost Architecture for the Implementation of Worst-Case-Fair Schedulers in ATM Switches”, PROCEEDINGS OF GLOBECOM 98, November 1998; each macro-session I is equipped with a rate-queue bit b RQ,I , which may be stored, for example, as a bit  192  associated with the pointer HEAD of each respective rate FIFO queue, such as HEAD( 1 )  30  of queue  20 . According to the flowchart of  FIGS. 6A-6B , the pivot session is now identified as the last session i in the queue whose connection bit b VC,i  has a value equal to the rate queue bit b RQ,I . Compared to the embodiment  110  of FIGS.  3  and  4 A- 4 B, this third embodiment  190  reduces the number of accesses to connection entries that are necessary at every timeslot to mark the pivot session of the rate FIFO queue. 
   Referring to  FIGS. 6A-6B , the third embodiment  190  of  FIG. 5  operates according to the method having the steps of determining in step  194  if there are any new data packets. If not, the method then determines in step  196  if there are any backlogged connections. If not, the method loops back to step  194 . Otherwise, after step  196 , the method performs step  226 . 
   If, in step  194 , there are new data packets, the method selects one data packet in step  198 , identifies its connection in step  200 , stores data packets in a respective connection queue in step  202 , and increments the queue length (QL) of the connection in step  204 . The method then determines in step  206  if the queue length of the connection is equal to 1. If not, the method performs step  226 . Otherwise, the method proceeds to step  228  to increment the number of backlogged connections, and identifies the rate queue (RQ) of the connection in step  210 . 
   The method then determines in step  212  if the length of the rate queue is equal to zero. If not, the method performs step  214  to set the connection bit to be b VC =˜b RQ , where ˜b RQ  is the complement of b RQ , and proceeds to step  216 . Otherwise, after step  212 , the method proceeds to step  218  to set the rate queue bit to be b RQ =b VC , and then sets the service rate of the rate queue in step  220  and the timestamp of the rate queue in step  222 . Step  216  is then performed. 
   In step  216 , the connection is stored in the identified rate queue. After step  216 , the length of the rate queue is incremented in step  224 , and the method proceeds to step  226 . 
   In step  226 , the method determines if the transmitter in front of the output interface of the ATM system is available. If not, the method loops back to step  194 . If, instead, the transmitter is available, the method proceeds to step  228  to determine if the serviced connection is available. If not, the method then selects the connection from the rate queue in step  230 , sends the data packet from the connection to the transmitter in step  232 , and loops back to step  194 . 
   If the serviced connection is available in step  228 , the method proceeds to remove the connection from the rate queue in step  234 , decrements the queue length of the connection in step  236 , and then determines in step  238  if the queue length of the connection is equal to zero. If not, the method proceeds to step  240 . Otherwise, in step  238 , if the queue length is equal to zero, the method decrements the number of backlogged connections in step  242 , and decrements the length of the rate queue in step  244 . 
   Step  240  is then performed, in which the method determines if the rate queue is empty. If not, then the method reads the bit b VC,HEAD  from the head of the rate queue in step  246 , and the method determines if b VC,HEAD =b RQ  in step  248 . If so, the method proceeds to step  250  to update the system potential. Otherwise, the method performs step  252  to update the service rate of the rate queue, and then sets the rate queue bit b RQ =b VC,HEAD  and proceeds to step  250 . 
   In step  240 , if the rate queue is empty, then the method sets the service rate of the rate queue in step  256 , and determines in step  258  if there are any backlogged connections. If so, the method proceeds to step  250 ; otherwise, the method loops back to step  194 . 
   After step  250 , the method updates the timestamp of the rate queue in step  260 , and determines in step  262  if the queue length of the served connection is equal to zero. If so, the method loops back to step  230 ; otherwise, the method determines if the rate queue is empty in step  264 . If the rate queue is empty, then the method sets the rate queue bit in step  266  to be b RQ =b VC , and stores the served connection in the rate queue in step  268 . Otherwise, if the rate queue is not empty in step  264 , the method sets the connection bit to be b VC =˜b RQ  in step  270 , and proceeds to step  268 . After step  268  is performed, the method loops back to step  230 . 
   As described herein, the delay bounds and fairness indices (both SFI and WFI) of the no-per-connection-timestamp scheduler with pivot session are almost identical to the ones of the discrete-rate scheduler with per-connection timestamps. More precisely, the worst-case delay experienced by a (b i , r i )-leaky-bucket-constrained connection i is bounded as: 
         D   i     ≤         b   i     +   3       r   i           
 
   For the same connection, the Cell Worst-case-Fairness Index (C-WFI) is equal to two cells. The Service Fairness Index, for two connections i and j having reserved service rates r i  and r j , is bounded as: 
         F     i   ,   j       ≤     max   ⁡     (         3     r   i       +     1     r   j         ,           ⁢       3     r   j       +     1     r   i           )           
 
   The disclosed schedulers and methods have been described by way of the preferred embodiments. However, numerous modifications and substitutions may be made without departing from the spirit of the invention. Accordingly, the invention has been described by way of illustration rather than limitation.