Leaky bucket type traffic shaper and bandwidth controller

• US 20030123390A1
• Filed: 02/22/2002
• Published: 07/03/2003
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Moriwaki, Norihiko, Takase, Masayuki, Wada, Mitsuhiro, Kozaki, Takahiko, Kasahara, Hiroaki
• Granted Patent: US 7,023,799 B2
• Time in Patent Office: Days
• US Class Current: 370/230.1
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 47/22 Traffic shaping

Abstract

A traffic shaper comprises a bandwidth controller 40 having a plurality of leaky bucket units 41-1 to 41-n prepared in correspondence with buffer memories 20-1 to 20-n, and an output queue designation unit 43 for specifying a buffer memory from which a packet is to be read out. Each of the leaky bucket units 41 has a level counter 416 for decrementing the count value at a predetermined rate, and a level increaser 411 to 417 for increasing the count value of the level counter by a value proportional to the product of the length of a transmitted packet and a unitary increment value which is variable depend on the current count value of the level counter.

Claims

1. A traffic shaper for transferring variable-length packets received from a plurality of input ports to one output port while guaranteeing preliminarily designated minimum bandwidths, comprising:

a plurality of buffer memories for temporarily storing the variable-length packets received from said input ports;

a bandwidth controller for specifying a buffer memory from which a packet is to be read out; and

a read controller for reading out a variable-length packet from a buffer memory specified by said bandwidth controller and transmitting the packet to said output port,

said bandwidth controller comprising;

a plurality of leaky bucket units prepared in correspondence with said buffer memories;

a plurality of level deviation detectors each for outputting a numerical value indicative of a difference between a level count value output from each of said leaky bucket units and a threshold corresponding to the preliminarily designated minimum guaranteed bandwidth; and

an output queue designation unit for specifying a buffer memory from which a packet is to be read out on the basis of the difference values output from said level deviation detectors, and

each of said leaky bucket units comprising;

a level counter for decrementing the count value at a predetermined rate; and

level raising means for increasing the count value of said level counter, in response to reading out of a packet from a corresponding buffer memory by said read controller, by a value proportional to the length of said packet.

2. The traffic shaper according to claim 1, wherein when the level count value output from each of said leaky bucket units becomes equal to or smaller than said threshold, each of said level deviation detectors outputs zero as said difference value, and

said output queue designation unit has a register for indicating a packet storage status in each of said buffer memories, validates output values from the level deviation detectors corresponding to the buffer memories, each of which is storing at least one packet to be read out, indicated by said register among the validated difference values, and selects one minimum value.

3. The traffic shaper according to claim 2, wherein said output queue designation unit includes means for selecting one minimum value in a round-robin manner when a plurality of difference values having the same minimum values exist in said validated difference values.

4. The traffic shaper according to claim 1, wherein each of said leaky bucket units includes means for supplying a variable unitary increment value to said level raising means, said variable unitary increment value being changed step by step according to the current level count value of said level counter, and

said level raising means increases the count value of said level counter in accordance with the product of said variable unitary increment value and said packet length.

5. The traffic shaper according to claim 1, wherein each of said leaky bucket units includes an increment value table for indicating unitary increment values corresponding to a plurality of level zones defined within the range of the level count values of said level counter, and

said level raising means increases the count value of said level counter in accordance with the product of said packet-length and a unitary increment value read out from said increment value table according to the current level count value of said level counter.

6. The traffic shaper according to claim 5, wherein each of said plurality of leaky bucket units selectively uses one of increment value tables having different definitions of level zones in accordance with the preliminarily designated minimum guaranteed bandwidth value.

7. The traffic shaper according to claim 4, wherein the unitary increment value supplied to said level raising means increases step by step as the level count value of said level counter decreases.

8. A traffic shaper for temporarily storing variable-length packets received from a plurality of input ports in buffer memories corresponding to the input ports, reading out the packets stored in the buffer memories, and transferring the packets to one output port while guaranteeing minimum bandwidths within maximum allowable bandwidths preliminarily designated for each of the buffer memories, comprising:

a bandwidth controller for specifying a buffer memory from which a packet is to be read out, having

a plurality of leaky bucket units prepared in correspondence with said buffer memories, and

an output queue designation unit for specifying a buffer memory from which a packet is to be read out, among buffer memories of which level count value is equal to or smaller than a first threshold corresponding to the preliminarily designated maximum allowable bandwidth, on the basis of difference values each indicating the difference between a level count value output from each of said leaky bucket units and a second threshold corresponding to the preliminarily designated minimum guaranteed bandwidth, and

each of said leaky bucket units having;

a level counter for decrementing the count value at a predetermined rate; and

level raising means for increasing the count value of said level counter, in response to reading out of a packet from a corresponding buffer memory, by a value proportional to the length of said packet.

9. The traffic shaper according to claim 8, wherein said output queue designation unit comprises:

a plurality of level deviation detectors each for outputting a difference value between the level count value output from one of said leaky bucket units and said second threshold; and

a buffer selector for specifying a buffer memory from which a packet is to be read out on the basis of the difference values output from said level deviation detectors,

each of said level deviation detectors outputs zero as said difference value when the level count value output from the leaky bucket units becomes equal to or smaller than said second threshold, and

said buffer selector validates difference values output from level deviation detectors corresponding to buffer memories each of which is storing at least one packet to be read out, and selects one minimum value among the validated difference values.

10. The traffic shaper according to claim 9, wherein said buffer selector selects one minimum value in a round-robin manner when a plurality of same minimum values exist in said validated difference values.

11. The traffic shaper according to claim 8, wherein each of said leaky bucket units includes means for supplying a variable unitary increment value, which increases step by step as the level count value of said level counter decreases, to said level raising means, and

said level raising means increases the count value of said level counter in accordance with the product of said variable unitary increment value and said packet length.

12. The traffic shaper according to claim 8, wherein each of said plurality of leaky bucket units includes an increment value table for indicating different unitary increment values corresponding to a plurality of level zones defined within the range of the level count values of said level counter, and

said level raising means increases the count value of said level counter in accordance with the product of said packet length and a unitary increment value corresponding to the current level count value of said level counter in said increment value table.

13. The traffic shaper according to claim 12, wherein each of said plurality of leaky bucket units selectively uses one of increment value tables having different definitions of level zones in accordance with the preliminarily designated minimum guaranteed bandwidths.

14. A bandwidth controller for reading out variable-length packets from a plurality of buffer memories while guaranteeing a minimum bandwidth preliminarily designated for each buffer memory, comprising:

a plurality of leaky bucket units prepared in correspondence with said buffer memories;

an output queue designation unit for specifying a buffer memory from which a packet is to be read out, on the basis of difference values each indicating the difference between a level count value output from one of said leaky bucket units and a threshold corresponding to a minimum guaranteed bandwidth preliminarily designated for each buffer memory; and

a read controller for reading out one variable-length packet from a buffer memory specified by said output queue designation unit,

each of said leaky bucket units having;

a level counter for decrementing the count value at a predetermined rate; and

level raising means for increasing the count value of said level counter, in response to reading out of a packet from a corresponding buffer memory, by a value proportional to the length of said packet, and

said level raising means for increasing the count value of said level counter in accordance with the product of a variable unitary increment value and a packet length, said variable unitary increment value increasing step by step as the level count value of said level counter decreases.

15. The bandwidth controller according to claim 14, wherein each of said leaky bucket units has an increment value table for indicating unitary increment values corresponding to a plurality of level zones defined within the range of the level count values of said level counter, the threshold corresponding to the minimum guaranteed band width designated for the buffer memory being positioned almost in the center of one of said level zones, and wherein

said level raising means increases the count value of said level counter in accordance with the product of said packet length and a unitary increment value corresponding to the current level count value of said level counter in said table.

16. A traffic shaper for transferring variable-length packets received from a plurality of input ports to one output port while guaranteeing preliminarily designated minimum bandwidths, comprising:

a plurality of buffer memories for temporarily storing the variable-length packets received from said input ports;

a bandwidth controller for specifying a buffer memory from which a packet is to be read out; and

a read controller for reading out one variable-length packet from the buffer memory specified by said bandwidth controller and transmitting the packet to said output port,

wherein said bandwidth controller includes means for assigning an unoccupied bandwidth in said output port to each of said buffer memories in accordance with a rate of the minimum bandwidth designated to each of said buffer memories, and

said read control means reads out packets from each of said buffer memories in a transmission rate equal to or higher than the minimum guaranteed bandwidth in response to the assigning of said unoccupied bandwidth from said bandwidth controller.