Variable Bit Rate Scheduler

The present invention relates to a variable bit rate scheduler which shapes data before admitting it into an ATM network.

Variable bit rate traffic, such as data from computers, is bursty by nature and requires "shaping" before being admitted into an ATM network. Without the proper "shaping" of the data, the design and management of the network and its components would be very complicated. One method employed to "shape" traffic in ATM networks is to control the rate of the data transmitted on a virtual channel. Virtual paths and virtual channels are mechanisms used to provide for a sequential unidirectional transport of ATM cells. Each ATM cell has a virtual channel indicator field, VCI field, and a virtual path indicator field, VPI field. An ATM cell is assigned virtual channel and virtual path indicator values which together define a virtual channel connection at one end of the connection. Those VCI and VPI values are translated or removed at the destination end of the connection. The cell is not removed or modified until it is removed or translated at the end point of the virtual channel connection. For example, between an ATM switch and physical layer device there may be 10 virtual paths with each virtual path having 128 virtual channels for each the receive and transmit directions. Physically, the coupling could be two light fibres.

In order to control the rate of data transmission on a virtual channel, a method is required which can determine when data should be transmitted on such a channel.

According to the invention there is provided a variable bit rate scheduler for ATM traffic shaping which includes a service rate queue (SRQ) counter for generating a base traffic profile for the control of data transmission on a virtual channel, a virtual channel peak cell rate determinator coupled to said SRQ counter and operative to determine a virtual channel peak cell sub-rate, VC.sub.-- PCR, a leaky bucket having an input for receiving sub-tokens and an output for discharging tokens and means for adding sub-tokens at the virtual channel peak cell rate to the leaky bucket and, when a cell is to be transmitted, removing a number of tokens from the bucket equal to the ratio of a virtual channel sustainable cell rate VC.sub.-- SCR. The virtual channel sustainable cell rate is a fraction of or equal to the virtual channel peak cell rate.

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as other features and advantages thereof, will be best understood by reference to the detailed description which follows, read in conjunction with the accompanying drawings, wherein:

FIG. 1 is a schematic diagram of a leaky bucket algorithm used in the present invention;

FIG. 2 is a diagram showing the relationship between traffic profiles and the sub-blocks used in the VBR scheduler to implement the traffic profiles;

FIG. 3 is a schematic diagram showing the counter system;

FIG. 4 is a schematic diagram showing how the residue value is calculated and carried forward;

FIG. 5 is a schematic diagram showing how the virtual channel prescale counter values are determined from the saturating timestamp counter; and

FIG. 6 is a schematic diagram showing the link list of virtual channels associated with each prescale select register.

The concept of virtual channels and virtual paths are used to create non-physical links between a transmitter and receiver over an intermediate medium such as a pair of optical fibres linking an ATM switch and a Physical Layer Device. In this case the fibre can be considered as being divided up into a number of paths or bands called virtual path connections (VPC) with each virtual path connection further divided up into a number of virtual channel connections. Cells transmitted over such medium are assigned virtual path and virtual channel index numbers which define the destination of the cell. The virtual path designator is used as an area designator with the virtual channel designating a specific location in that area.

Due to the limitation on the rate of transmission permitted for each channel and the bursty nature of the cell transmission it is necessary to control the rate of transmission on a virtual channel. One can establish the following "traffic shaping" rules to obtain rate control over data transmitted on a virtual channel. First one may require the average transmission rate of a virtual channel over time to be T.sub.scr and define the sustainable cell rate of a virtual channel as VC.sub.-- SCR. Second, one may require that no two cells may be transmitted within a time interval T.sub.pcr of each other. The time interval T.sub.pcr corresponds to a Peak Cell Rate of VC.sub.-- PCR. Third, one may require that no virtual channel may burst more than its allowable maximum burst size, VC.sub.-- MBS, at its peak cell rate of VC.sub.-- PCR. Using these rules and referring to FIG. 1 which displays a leaky bucket algorithm one can readily establish the relationship between VC.sub.-- SCR, VC.sub.-- PCR and VC.sub.-- MBS and how these values are applied to traffic shaping rules.

It is clear from FIG. 1 that data can only be transmitted when there is a token present in the leaky bucket 10. If the bucket 10 is empty, tokens can only be removed at the rate of addition, which is VC.sub.-- SCR, the virtual channel sustained or average cell rate. If no data has been transmitted for a while, the bucket 10 fills up to its maximum size. Now tokens can be removed at the rate of VC.sub.-- PCR but only until the bucket empties. This defines the maximum burst size for the virtual channel. After the burst is completed transmission continues at the rate of VC.sub.-- SCR.

A variable bit rate scheduler (VBR) must rely upon a number of base traffic profiles wherein each traffic profile represents a particular rate at which data for a given virtual channel can be transmitted. In addition to base traffic profiles, sub-profiles can be established from traffic information corresponding to each virtual channel as shown in FIG. 2. Service Rate Queue (SRQ) counters (see FIG. 3) are used to generate a base-traffic profile 12. The number of sub-profiles 14 required depends upon the requirements of the variable bit rate scheduler.

Referring to FIG. 3, each SRQ counter 16 is comprised of three counters, namely, a Prescale (PRS) Counter 18, a Peak Cell Rate (PCR) counter 20 and a Saturating Timestamp Counter (STS) counter 22. The PRS counter 18 consists of a L bit divider circuit 24 into which is fed a base clock on line 26. The output of circuit 24 is directed into a Prescale Select register 30 which has a prescale value set by the SRQ Prescale Select circuit 28. The prescale value is used to scale down the output of the circuit 24. Scaled counts from the Prescale Select circuit 30 are counted in a K bit counter 32. The count in K bit counter 32 is fed to a comparator 34. Another input to comparator 34 is from a PCR Rollover Counter 36. When the K bit counter 32 reaches a value equal to the PCR Rollover value on PCR Counter 34 a reset pulse is issued on line 38 by the comparator 34 which resets K bit counter 32 and sends a signal to M bit counter 40 which comprises a Saturating Timestamp (STS) Counter 22 used for token generation and indicating when transmission opportunities occur.

If the virtual channel peak cell rate VC.sub.-- PCR is equal to the SRQ.sub.-- PCR then there is a one-to-one correspondence between the roll over of the PCR Counter 20 and the peak cell rate of the SRQ counter 16. The virtual channel in this case is the same as the base traffic profile 12 as shown in FIG. 2. If, however, VC.sub.-- PCR is 1/2 or 1/4 of the SRQ.sub.-- PCR, every two or four rollovers of the PCR counter 20 would, respectively, correspond to the VC.sub.-- PCR. The virtual channels in this case correspond to sub-traffic profiles of 1/2 and 1/4, respectively, of the base-traffic profile.

Each time the STS counter 22 is accessed to indicate a transmission opportunity or to produce a token, the information required to generate the lower VC.sub.-- PCR is lost. It has been determined that the minimum information required to be saved in order to generate the lower VC.sub.-- PCR is the N least significant bits of the STS Counter 22 where the factor 1/2.sup.N when multiplying the SRQ.sub.-- PCR value produces the lowest VC.sub.-- PCR. A table giving the number of STS counter bits and a corresponding parameter SUB.sub.-- SRQ.sub.-- RATE for sub-traffic profiles 14 is shown in the following table.

If, for example, N is 3 so that the virtual channel SUB.sub.-- SRQ.sub.-- RATE is 1/8th of the base profile rate, then if at the time the M bit counter 40 is serviced there is only 1 bit in the counter, then that bit, which is the residue, is saved. The next time the M counter 40 is accessed there would be 2 bits in the M Counter 40.

In more general terms, referring to FIG. 4, the residue of the STS M bit Counter 40 at the time of a given accessing or servicing is stored in Residue Register 42 and the residue left at the time of next accessing of the STS M bit Counter 40 is added to the previous value stored in the Residue register 42 to provide a value for the first subrate. This process is repeated so as to determine the second, third, etc. subrate. A general virtual channel peak cell rate, VC.sub.-- PCR, is calculated from the following:

Thus, for

N=0, VC.sub.-- PCR=STS

N=1, VC.sub.-- PCR=(STS+Residue ›0!)/2

N=2, VC.sub.-- PCR=(STS+Residue ›1:0!)/4

The variable bit rate scheduler supports only power of 2 subrates for the VC.sub.-- PCR. This eliminates the need for a divider since divide by two can be accomplished simply by shifting logic.

Referring to FIG. 5, there is shown the circuit for detecting a VC.sub.-- PCR event for a given virtual channel. The value in the Residue Register 42 is passed through a selector circuit 44 which selects bits based on the SUB.sub.-- SRQ.sub.-- RATE. The value of selected bits is added to the value in the STS Counter 22 and is then sent to the input of a shift register 45 which shifts the value depending upon the SUB.sub.-- SRQ.sub.-- RATE. For example, if the latter rate is 1/4 then there will be a two bit shift right so that, for example, the binary value xxxx becomes xx. The resulting shifted value is then stored in the sub-STSC Register 46. The latter value determines the VC.sub.-- PCR cell rate. If this value is non-zero then a VC.sub.-- PCR event has occurred and there is an opportunity to transmit a cell on that virtual channel. If there are enough tokens to satisfy the VC.sub.-- SCR rate at which tokens are being added then a cell can be transmitted. Using this algorithm many VC.sub.-- PCR's can be synthesized with a minimal amount of hardware.

To calculate the sustainable cell rate VC.sub.-- SCR from the VC.sub.-- PCR a concept of sub-tokens is used. Tokens define an opportunity to transmit data, and are added to the leaky bucket 10 at the VC.sub.-- SCR rate and can be removed at the VC.sub.-- PCR rate. The process of implementation of the leaky bucket algorithm can be considerably simplified by adding sub-tokens at the VC.sub.-- PCR and removing them based on a Utilization parameter. If one defines a token as follows:

The following table details the relationship between Utilization, the number of sub-tokens required for transmission and the VC.sub.-- SCR as a fraction of the VC.sub.-- PCR.

With the above algorithm VC.sub.-- SCR enforcement can be performed by using addition and subtraction instead of division to synthesize the VC.sub.-- SCR from the VC.sub.-- PCR. The following algorithm is used to perform the VC.sub.-- SCR enforcement.

1. When the sub-STSC register is non-zero for a particular VC, add the value of the sub-STSC register to the bucket. The sub-STSC register value corresponds to sub-tokens.

2. When a cell is to be transmitted subtract the required number of sub-tokens based on the utilization field.

The bucket size can be set to any arbitrary value larger than the utilization field. Tokens will accumulate in the bucket 10 and the size of the bucket will determine the maximum burst size (MBS).

When the peak cell rate counter 20 rolls over the SRQ requires servicing. In the event the SRQ cannot be serviced (this can occur if there are many SRQs in the variable bit rate scheduler) the STS counter 22 contains the number of times the PCR counter 20 rolled over.

Each SRQ has associated with it a link list of virtual channels supported as in FIG. 6. The VBR scheduler services each virtual channel in a SRQ to determine if a cell can be transmitted based on the VC.sub.-- PCR and VC.sub.-- SCR.

The SRQs can be prioritized such that some of the SRQs will always be serviced even if it means interrupting other SRQs. This way constant bit rate (CBR) virtual channels can be attached to the high priority SRQs and the jitter can be kept to a minimum.

Accordingly, while this invention has been described with reference to illustrative embodiments, this description is not intended to be construed in a limiting sense. Various modifications of the illustrative embodiments, as well as other embodiments of the invention, will be apparent to persons skilled in the art upon reference to this description. It is therefore contemplated that the appended claims will cover any such modifications or embodiments as fall within the true scope of the invention.