US5745490A — Variable bit rate scheduler

Claim 1

Independent Claim 126 words

A variable bit rate scheduler for ATM traffic shaping, comprising: (a) a service rate queue (SRQ) counter for generating a base traffic profile for the control of data transmission on a virtual channel; (b) a virtual channel peak cell rate determinator coupled to said SRQ counter and operative to determine a virtual channel peak cell sub-rate, VC -- PCR; (c) a leaky bucket having an input for receiving sub-tokens and an output for discharging sub-tokens; and (d) 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 sub-tokens from the bucket equal to the ratio of the virtual channel peak cell rate to a virtual channel sustainable cell rate.

Claim 2

Dependent Claim 126 words

A variable bit rate scheduler for ATM traffic shaping, comprising: (a) a service rate queue (SRQ) counter for generating a base traffic profile for the control of data transmission on a virtual channel; (b) a virtual channel peak cell rate determinator coupled to said SRQ counter and operative to determine a virtual channel peak cell sub-rate, VC -- PCR; (c) a leaky bucket having an input for receiving sub-tokens and an output for discharging sub-tokens; and (d) 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 sub-tokens from the bucket equal to the ratio of the virtual channel peak cell rate to a virtual channel sustainable cell rate.

Claim 3

Dependent Claim 111 words

A scheduler according to claim 1, wherein said SRQ counter includes (a) a prescale (PRS) counter which divides down a base clock for low rate traffic profiles by a prescale value set by a host in a SRQ prescale select register; (b) a peak cell rate (PCR) counter coupled to an output of said PRS counter having a peak cell rate rollover register which rolls over upon reaching a peak cell rate value set by an external host, resets the PCR counter and issues an output rollover count; and (c) a saturating timestamp (STS) counter coupled to an output of said PCR counter which accumulates rollover counts from said PCR counter.

Claim 4

Dependent Claim 74 words

A scheduler according to claim 2, including means for storing a parameter corresponding to a SUB -- SRQ -- RATE for each virtual channel (VC) in a service rate queue (SRQ) and equal to the integer value N where the SUB -- SRQ -- RATE is equal to the SRQ -- RATE divided by 2 N and wherein the VC -- PCR is equal to the SRQ -- PCR divided by 2 N .

Claim 5

Dependent Claim 55 words

A scheduler according to claim 3, including means for adding the least significant N bits in said STS counter to a residue value obtained from a residue register and storing the resultant new residue value in the residue register wherein the least significant N bits is determined at the time of servicing said STS counter.

Claim 6

Dependent Claim 119 words

A scheduler according to claim 4, including a residue register and a selector circuit coupled to an output of said residue register operative to store a register value from said residue register and to select bit "N" from the value so stored, an adder coupled to an output of each of said selector circuit and said STS Counter operative to add the N least significant bits from said STS Counter and the select bit from said bit selector, a shift register coupled to an output of said adder operative to store the bits from said adder and shifting the bits stored by the number of bits corresponding to the value of N for each SUB -- SRQ -- RATE.

Claim 7

Dependent Claim 16 words

A scheduler according to claim 3, wherein the bucket size is larger than the UTILIZATION parameter.

Claim 8

Dependent Claim 41 words

A scheduler according to claim 3, wherein sub-tokens are added to the bucket at the virtual channel peak cell rate and, when a cell is to be transmitted, a number of sub-tokens equal to the UTILIZATION are removed from the bucket.

Claim 9

Dependent Claim 21 words

A scheduler according to claim 3, wherein the maximum burst size is equal to the bucket size divided by the UTILIZATION.

Claim 10

Dependent Claim 170 words

A variable bit rate scheduler for ATM traffic shaping, comprising: (a) a plurality of service rate queue (SRQ) counters for generating a base traffic profiles for the control of data transmission on a plurality of virtual channels; (b) a plurality of virtual channel peak cell rate determinators coupled to respective ones of said SRQ counters and operative to determine virtual channel peak cell sub-rates, VC -- PCR; (c) a plurality of leaky buckets having an input for receiving sub-tokens and an output for discharging sub-tokens; and (d) means for adding sub-tokens to each of said leaky buckets at a corresponding virtual channel peak cell rate and, when a cell is to be transmitted, removing a number of sub-tokens from an associated one of said buckets equal to the ratio of the virtual channel peak cell rate to a virtual channel sustainable cell rate, wherein each virtual channel in each SRQ is serviced to determine if a cell can be transmitted based upon the VC -- PCR and VC -- SCR.

Claim 11

Dependent Claim 170 words

A variable bit rate scheduler for ATM traffic shaping, comprising: (a) a plurality of service rate queue (SRQ) counters for generating a base traffic profiles for the control of data transmission on a plurality of virtual channels; (b) a plurality of virtual channel peak cell rate determinators coupled to respective ones of said SRQ counters and operative to determine virtual channel peak cell sub-rates, VC -- PCR; (c) a plurality of leaky buckets having an input for receiving sub-tokens and an output for discharging sub-tokens; and (d) means for adding sub-tokens to each of said leaky buckets at a corresponding virtual channel peak cell rate and, when a cell is to be transmitted, removing a number of sub-tokens from an associated one of said buckets equal to the ratio of the virtual channel peak cell rate to a virtual channel sustainable cell rate, wherein each virtual channel in each SRQ is serviced to determine if a cell can be transmitted based upon the VC -- PCR and VC -- SCR.

Claim 12

Dependent Claim 16 words

A scheduler according to claim 9, wherein selected SRQ's are serviced in priority to other SRQs.

Claim 13

Independent Claim 172 words

A method of scheduling traffic in an ATM network, comprising: (a) generating a base traffic profile for the control of data transmission on a service rate queue (SRQ); (b) generating a peak cell rate PCR for the SRQ; (c) establishing SUB-SRQ-RATEs for each virtual channel associated with the SRQ which are a fraction of or equal to the SRQ; (d) generating a VC -- PCR for each virtual channel which is the same fraction of the SRQ -- PCR as is the SUB -- SRQ -- RATE to the SRQ; (e) establishing each virtual channel sustainable cell rate, VC -- SCR, as equal to VC -- PCR divided by a UTILIZATION parameter value which is an integer greater than or equal to unity; (f) adding sub-tokens at the VC -- PCR to a leaky bucket and, when a cell is to be transmitted, removing a number of sub-tokens from the bucket equal to the UTILIZATION parameter, the removal of the UTILIZATION number of sub-tokens corresponding to an opportunity to transmit a cell.

Claim 14

Independent Claim 172 words

A method of scheduling traffic in an ATM network, comprising: (a) generating a base traffic profile for the control of data transmission on a service rate queue (SRQ); (b) generating a peak cell rate PCR for the SRQ; (c) establishing SUB-SRQ-RATEs for each virtual channel associated with the SRQ which are a fraction of or equal to the SRQ; (d) generating a VC -- PCR for each virtual channel which is the same fraction of the SRQ -- PCR as is the SUB -- SRQ -- RATE to the SRQ; (e) establishing each virtual channel sustainable cell rate, VC -- SCR, as equal to VC -- PCR divided by a UTILIZATION parameter value which is an integer greater than or equal to unity; (f) adding sub-tokens at the VC -- PCR to a leaky bucket and, when a cell is to be transmitted, removing a number of sub-tokens from the bucket equal to the UTILIZATION parameter, the removal of the UTILIZATION number of sub-tokens corresponding to an opportunity to transmit a cell.

Claim 15

Dependent Claim 83 words

A method according to claim 11, wherein the step of generating a base traffic profile includes dividing down a base clock by a divider set in a SRQ Prescale Select register by an external host, and the step of generating a peak cell rate includes rolling over a counter which counts the divided down base clock once the counts equal a rollover value stored in a PCR rollover register by the external host and counting the number of rollovers in an STS Counter.

Claim 16

Dependent Claim 146 words

A method according to claim 12, wherein the step of generating a VC -- PCR includes, in response to servicing the STS Counter, establishing a residue value in a residue register by adding the N least significant bits from the STS Counter to the bits in a residue register corresponding to a previous residue value to establish a new residue value in the residue register, transmitting the new residue value to a selector circuit and selecting bits based on the SUB -- SRQ -- RATE, adding in an adder circuit the bits selected in the selector circuit to the N least significant bits from the STS Counter, shifting the bits from the adder circuit in a shift register a number of bits equal to the exponent N of a divider 2 N by which the SRQ -- PCR is divided to obtain the VC -- PCR.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-04-27	2001-10-27	2002-04-28	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-04-27	2005-10-27	2006-04-28	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-04-27	2009-10-27	2010-04-28	$7700.00	Window Closed / Lapsed

Variable bit rate scheduler

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag