Shared credit round robin queuing

1. Field of the Invention

This invention generally relates to the field of data communication networks. More particularly, the present invention relates to a novel system and method for ensuring bandwidth to different classes of traffic, limiting the classes of traffic to corresponding maximum bandwidths, and dynamically allocating bandwidth to classes needing more than their maximum bandwidth when there exists available bandwidth.

2. Description of Related Art

Most commercial communication networks incorporate network switching devices, such as computer switches or routers, for example, to aggregate streams of data onto a network link and funnel the data traffic to its destination. These switching devices typically employ queuing methodologies to manage the flow of data streams onto the network link. For very high-speed network links, it is important that queuing methodologies be computationally simple so that the switch or router does not become a bottleneck. One such methodology is the Deficit Round Robin (DRR) technique (M. Shreedhar and G. Varghese, Efficient Fair Queuing Using Deficit Round Robin , Washington University, St. Louis, Mo. (Oct. 16, 1995)). DRR was designed to ensure that each class of traffic being transmitted out of a particular network device output port receives a user-selectable percentage of the port's bandwidth.

FIG. 1 illustrates a representative system 100 , employing DRR. As indicated in FIG. 1, a plurality of input streams of packetized data, representing different classes of traffic, flow into the output port 105 of a network switching device. These streams are captured by queues 110 A- 110 M. As packets enter queues 110 A- 110 M, their lengths are stored in a manner that enables the queue servicing algorithm to quickly obtain the length of the packet from the head packet of each queue. The user assigns each of the queues 110 A- 110 M a “quantum” number of bytes, based on the class of traffic of each queue. The ratio of each of the queue's 110 A- 110 M quantum to the total of all quanta represents the fraction of port bandwidth that each queue should receive. For example, queue 110 A may represent a lower class of traffic and may be allocated a quantum of 500 bytes while queue 110 B may represent a higher class and may be allocated a quantum of 1000 bytes. Queue 110 C may represent an even higher class of traffic and may be allocated a quantum of 2000 bytes. If the total of all quanta is 10,000 bytes, then queue 110 A should receive at least 500/10,000, or 5% of the output bandwidth. Likewise, queue 110 B should receive 10% and 110 C 20% of the bandwidth.

DRR incorporates “deficit counters” 120 A- 120 M, which track how many bytes a queue may send. During an initialization stage, deficit counters 120 A- 120 M are initialized to zero. During operation, DRR examines each of the queues 110 A- 110 M in a round-robin fashion (i.e., returning to the first queue 110 A after the final queue 110 M has been observed). If there are no packets in the queue being examined, then that queue is skipped and the next queue is examined. If a queue, for example queue 110 C, has at least one packet to send, then the quantum corresponding to queue 110 C is added to its deficit counter 120 C. DRR then compares the length of the head packet of queue 110 C, with the number of bytes in deficit counter 120 C. If the length is less than or equal to deficit counter 120 C, the packet is dequeued and transmitted while deficit counter 120 C is decremented by the byte length of the packet. DRR then examines queue 110 C again to determined whether there exists another packet in queue 110 C, whose length is less than the number of bytes contained in deficit counter 120 C. If so, the packet is dequeued, transmitted, and deficit counter 120 C decremented.

This process is repeated until there are either no packets in queue 110 C or the length of the packet at the head of queue 110 C is greater than the number of bytes contained in deficit counter 120 C. If there are no packets in queue 110 C, deficit counter 120 C is set to zero and the next queue is examined.

It is to be noted, however, that there are situations in which one queue may need more than its allocated target bandwidth while other queues are dormant. There are other situations where it may be desirable to ensure a predetermined bandwidth to a queue while enabling it to operate at a higher bandwidth if there exists available bandwidth.

What is needed, therefore, is a method and system that ensures bandwidth to different classes of traffic, limits the classes of traffic to a maximum bandwidth, and enables pre-selected classes to use more than their maximum bandwidth when there is bandwidth available.

The accompanying drawings, which are incorporated in and constitute a part of this Specification, illustrate an embodiment of the invention and, together with the description, explain the objects, advantages, and principles of the invention. In the drawings:

FIG. 1 (Prior Art) is a block diagram depicting a conventional queue servicing system.

FIG. 2A is a block diagram depicting a queue servicing system in accordance with a first embodiment of the present invention.

FIGS. 2B-2E are flow diagrams illustrating a queue servicing process in accordance with a first embodiment of the present invention.

FIG. 3A is a block diagram depicting a queue servicing system in accordance with a second embodiment of the present invention.

FIGS. 3B-3E are flow diagrams illustrating a queue servicing process in accordance with a second embodiment of the present invention.

The following detailed description of the present invention refers to the accompanying drawings that illustrate preferred embodiments consistent with this invention. Other embodiments are possible and modifications may be made to the embodiments without departing from the spirit and scope of the invention. Therefore, the following detailed description is not meant to limit the invention. Rather the scope of the invention is defined by the appended claims.

It will be apparent to one of ordinary skill in the art that the present invention as described below may be implemented in many different embodiments of software, firmware, and hardware in the entities illustrated in the figures. The actual software code or specialized control hardware used to implement the present invention is not limiting of the present invention. Thus, the operation and behavior of the present invention will be described without specific reference to the actual software code or specialized hardware components, it being understood that a person of ordinary skill in the art would be able to design software and/or control hardware to implement the embodiments of the present invention based on the description herein.

First Embodiment

FIGS. 2 A and 2 B- 2 E illustrate system 200 and process 250 , respectively, which are constructed and operative in accordance with a first embodiment of the present invention. FIG. 2A is a functional block diagram depicting various components of queue servicing system 200 . FIGS. 2B-2E are flow diagrams illustrating queue servicing process 250 , which comprises initialization routine 250 A, credit update routine 250 B, and packet selection routine 250 C.

As depicted in FIG. 2A, system 200 contains an output section 105 of a network switching device. It will be appreciated that a network switching device may include one or more input sections and one or more output sections. Output section 105 includes selection mechanism 130 , which is configured to select the next packet to be transmitted to output channel 140 from queues 110 A- 110 M. Selection mechanism 130 incorporates “credit counters” 225 A- 225 M, which accumulate a predetermined number of bytes over specific intervals of time (i.e., round time). Because each queue 110 A- 110 M is assigned a target bandwidth, selection mechanism 130 utilizes credit counters 225 A- 225 M to determine, for each of the queues 110 A- 110 M, how many bytes each queue may transmit without exceeding its target bandwidth.

As will be described in detail below, upon the initialization of system 200 , selection mechanism 130 determines a “round time” for each of the queues 110 A- 110 M. Round time is defined as the interval of time necessary to send a “quantum” number of bytes at the corresponding queue target bandwidths.

During the operation of system 200 , selection mechanism 130 adds the quantum number of bytes to the corresponding credit counters 225 A- 225 M during every round time. For example, suppose that quantum is specified as 100 bytes and queue 110 A has a target bandwidth of 1 Mbps. To transmit 100 bytes (800 bits) at 1 Mbps would take a round time of (800/1,000,000) seconds or 800 microseconds. The effect is to credit bytes to queue 110 A at its target bandwidth. As each packet from queue 110 A is transmitted to output channel 140 , credit counter 225 A is decremented by the number of bytes in the packet. Thus, during operation, each of the credit counters 225 A- 225 M keeps track of the number of bytes its corresponding queue may transmit without exceeding its target bandwidth.

Selection mechanism 130 also incorporates borrow enable flags (BEFs) 215 A- 215 M and maximum credit registers 220 A- 220 M for each of the queues 110 A- 110 M. BEFs 215 A- 215 M are initialized to the enabled state if the corresponding queue is allowed to transmit at greater a than its target bandwidth (i.e., by borrowing unused bandwidth). Otherwise, BEFs 215 A- 215 M are initialized to the disabled state. Maximum credit registers 220 A- 220 M are initialized to the maximum number of bytes that each of the queues 110 A- 110 M is allowed to accumulate in its credit counter 225 A- 225 M.

System 200 further comprises shared credit counter 230 A. If any of the credit counters 225 A- 225 M exceed the maximum number of bytes indicated by their respective maximum credit registers 220 A- 220 M, then the bytes that would otherwise be added during round time to credit counters 225 A- 225 M, are donated to shared credit counter 230 A. Shared credit counter 230 A stores these excess bytes so that if any of the queues 110 A- 110 M need to transmit packets but lack the necessary bytes in their respective credit counter 225 A- 225 M, the queues 110 A- 110 M with enabled BEFs 215 A- 215 M may borrow against the bytes stored in shared credit counter 230 A. Shared credit counter 230 A also has an associated maximum shared credit register 230 B, containing a value representing the maximum amount of bytes that shared credit counter 230 A may store. In this manner, the unused output channel 140 bandwidth is allocated to a centralized location (shared credit counter 230 A) to allow queues 110 A- 110 M to borrow against it. As such, all queues 110 A- 110 M may contribute to shared credit counter 230 A but only queues 110 A- 110 M having enabled BEFs 215 A- 215 M may borrow from shared credit counter 230 A.

In addition, system 200 may modify the target bandwidth of queues 110 A- 110 M. If the sum of the target bandwidth of all queues 110 A- 110 M is less than the total output channel 140 bandwidth, then the unallocated bandwidth (i.e., the difference between total output channel 140 bandwidth and the sum of the target bandwidth of all queues 110 A- 110 M) is distributed among the BEF-enabled queues in proportion to their original target bandwidth.

FIG. 2B illustrates queue servicing process 250 , which integrates the various routines comprising the first embodiment. Queue servicing process 250 includes initialization routine 250 A, credit update routine 250 B, and packet selection routine 250 C. Process 250 may be stored in any storage device, such as, for example, a computer system (non-volatile) memory, an optical disk, magnetic tape, or magnetic disk. Furthermore, process 250 may be programmed when the computer system is manufactured or via a computer-readable medium at a later date. Such a medium may include any of the forms listed above with respect to storage devices and may further include, for example, a carrier wave modulated, or otherwise manipulated, to convey instructions that can be read, demodulated/decoded and executed by a computer or network device.

FIG. 2C depicts initialization routine 250 A, which initializes universal parameters (i.e., queue independent parameters) and queue dependent parameters. As indicated in block B 252 , routine 250 A initializes universal parameters, such as, for example, queue index i, output channel 140 bandwidth, quantum, and maximum shared credit register 230 B value.

Upon initializing the universal parameters, routine 250 A, in block B 254 , initializes queue dependent parameters for each queue, indicated by queue index i. As noted above, routine 250 A calculates the round time for queue i. In addition, routine 250 A stores the following queue dependent parameters supplied by the user: queue 110 i target bandwidth, the value in maximum credit register 220 i and BEF 215 i . Furthermore, credit counter 225 i is set to quantum.

In block B 256 , routine 250 A determines whether the queue dependent parameters for all classes have been initialized. If so, routine 250 A progresses to block B 258 . If all the queues 110 A- 110 M have not been initialized, then routine 250 A, in block B 260 , increments queue index i and returns to block B 254 to initialize the queue-dependent parameters for the next queue i+1.

After initializing the queue dependent parameters for all the queues, routine 250 A distributes the unused output channel 140 bandwidth by proportionately adding the unused or excess bandwidth to each of the queues 110 A- 110 M. Specifically, in block B 258 , routine 250 A calculates the excess output channel 140 bandwidth (i.e., excess bandwidth=output channel bandwidth−sum of all queue target bandwidths). In block B 262 , routine 250 A calculates the bandwidth sum of all the queues having enabled BEFs 215 A- 215 M (i.e., total BEF enabled bandwidth=Σ BEF enabled queue bandwidths). In block B 264 , routine 250 A distributes the excess bandwidth by adding a proportionate share of the excess bandwidth to the queue bandwidth (i.e., queue bandwidth i=queue bandwidth i+(excess bandwidth/total BEF enabled bandwidth)×queue bandwidth i). In block B 266 , routine 250 A re-calculates the round time for each of the BEF-enabled queues.

FIG. 2D depicts the update credit routine 250 B, which increments credit counter 225 i for each queue i. After initialization routine 250 A has been completed, routine 250 B is executed separately and continuously for each queue i.

As indicated in block B 260 , queue index i is initialized. In block B 261 , routine 250 B waits for the passage of round time i. After waiting for round time i, routine 250 B, in block B 262 , updates the corresponding credit counter 225 i by adding the quantum number of bytes to counter 225 i.

In block B 264 , routine 250 B determines if credit counter 225 i exceeds its maximum value contained in the corresponding maximum credit register 220 i . If not, routine 250 B returns to block B 261 , where it waits for the passage of round time i to commence another round of incrementing credit counter 225 i . If routine 250 B determines that credit counter 225 i does exceed its maximum value in maximum credit register 220 A- 220 M then, in block B 270 , routine 250 B donates the excess bytes to shared credit counter 230 A and advances to block B 272 .

In block B 272 , routine 250 B determines whether share credit counter 230 A exceeds its maximum value, as contained in maximum shared credit register 230 B. If not, then routine 250 B returns to block B 261 , where it waits for the passage of round time i to commence another round of incrementing credit counter 225 i . If routine 250 B determines that share credit counter 230 A does exceed its maximum value, routine 250 B truncates the value share credit counter 230 A to the maximum value and returns to block B 261 to repeat the process.

As such, each of the copies of routine 250 B (i.e., one copy for each queue i) updates the credit counters 225 A- 225 M by adding quantum bytes to the credit counters 225 A- 225 M every round time and then checking to see whether credit counters 225 A- 225 M exceed their maximum credit thresholds 220 A- 220 M. If credit counters 225 A- 225 M exceed their maximum credit threshold, then the excess bytes are donated to the shared credit counter 230 A, so that any of the queues 110 A- 110 M could use them. In addition, routine 250 B checks to see whether donating the excess bytes causes the shared credit counter 230 A to exceed its maximum. If it does, the number of bytes in shared credit 230 A are truncated to its maximum value.

FIG. 2E illustrates packet selection routine 250 C, which selects the packets to be transmitted for each queue i. After initialization routine 250 A has been completed, one copy of routine 250 C is executed continuously.

As indicated in block B 280 , queue index i is initialized. In block B 282 , process 250 C determines, for queue i, whether the byte length of the packet at the head of queue i is less than or equal to the number of bytes in the corresponding credit counter 225 i . If so, then in block B 284 , routine 250 C transmits and dequeues the packet and, in block B 286 , routine 250 C decrements the corresponding credit counter 225 i by the byte length of the transmitted packet. In block B 288 , queue index i is incremented, and in block B 290 , routine 250 C determines whether queue index i exceeds the number of queues. If it does, routine 250 C returns to block B 280 to repeat the process. If queue index i does not exceed the number of queues, routine 250 C points to the next queue i+1.

Returning to block B 282 , if the byte length of the packet is not less than or equal to the number of bytes in the respective credit counter 225 i , then routine 250 C advances to block B 292 , where it determines whether the corresponding BEF 215 i is enabled. If so, then routine 250 C advances to block B 294 . If the corresponding BEF 215 i is not enabled, routine 250 C returns to blocks B 288 and B 290 , to point to the next queue i+1.

After determining that BEF 215 i is enabled, routine 250 C determines, in block B 294 , whether the length of the packet is less than or equal to the sum of the bytes contained in the corresponding credit counter 225 i and shared credit counter 230 A. If not, then routine 250 C returns to blocks B 288 and B 290 , to point to the next queue i+1. If the length of the packet is less than or equal to the sum of the bytes contained in the corresponding credit counter 225 i and shared credit counter 230 A, then routine 250 C progresses to block B 296 , where the packet is transmitted and dequeued. In block B 298 , the shared credit counter 230 A is decremented by the difference between the byte length of the transmitted packet and the number of bytes stored in credit counter 225 i and credit counter 225 i is then set to 0. Routine 250 C then returns to blocks B 288 and B 290 to point to the next queue i+1.

As such, routine 250 C selects the queues 110 A- 110 M that will transmit packets by examining the head packet lengths to determine if there are enough bytes in the corresponding credit counters 225 A- 225 M to justify transmission. If there are enough bytes, a packet from queue i is transmitted and the credit counter 225 i is decremented. If there are not enough bytes in credit counter 225 i , the bytes required to justify transmission may be borrowed from shared credit counter 230 , which is then is decremented accordingly. In this manner routine 250 C, provides the option of limiting any queue to a single target bandwidth while allowing other queues to borrow unused bandwidth.

Second Embodiment

FIGS. 3A and 3B illustrate system 300 and process 350 , respectively, which are constructed and operative in accordance with a second embodiment of the present invention. FIG. 3A is a functional block diagram depicting various components of queue servicing system 300 , including, inter alia, credit-up counters 320 A- 320 M associated with each queue 110 A- 110 M. FIG. 2B illustrates queue servicing process 350 , which integrates the various routines comprising the second embodiment. Queue servicing process 350 includes initialization routine 350 A, credit update routine 350 B, and packet selection routine 350 C. As stated above with respect to the first embodiment, process 350 may be stored in any storage device and may be programmed when the computer system is manufactured or via a computer-readable medium at a later date.

As depicted in FIG. 3A, selection mechanism 130 implements credit-up counters 320 A- 320 M, which correspond to each of the queues 110 A- 110 M. In addition to the queue target bandwidth, system 300 includes a queue upper bandwidth limit, which may never be exceeded. Associated with each queue upper bandwidth limit is a quantum-up value, which specifies the number of bytes that are added to credit-up counters 320 A- 320 M at the rate of the queue upper bandwidths during round time. Quantum-up is the number of bytes, which may be transmitted during round time at the upper bandwidth rate. For example, if an upper bandwidth of a particular queue is 2 Mbps and its round time is 800 microseconds, quantum-up would be 200 bytes (i.e., 0.000800×2,000,000=1600 bits =200 bytes).

FIG. 3C depicts the first component of process 350 , initialization routine 350 A. Much like routine 250 A of the first embodiment, routine 350 A initializes the universal parameters and the queue dependent parameters. However, routine 350 A takes into account the upper queue bandwidths and the credit-up counters 320 A- 320 M.

As indicated in block B 352 , routine 350 A initializes universal parameters, such as output channel 140 bandwidth, quantum, and maximum shared credit register 230 B value, as well as queue index i.

Upon initializing the universal parameters, routine 350 A, in block B 354 , initializes queue dependent parameters for each queue i. The queue dependent parameters supplied by the user include queue i bandwidth, BEF 215 i , upper queue i bandwidths, and the maximum values in credit register 220 i . Credit counter 225 i and credit-up counter 320 i are set to quantum. In addition, routine 350 B calculates the round time for queue i and quantum-up.

In block B 356 , routine 350 A determines whether the queue dependent parameters for all queues 110 A- 110 M have been initialized. If so, routine 350 A progresses to block B 358 . If all the queues 110 A- 110 M have not been initialized, then routine 350 , in block B 360 , increments queue index i and returns to block B 354 to initialize the queue dependent parameters for the next queue i+1.

Similar to routine 250 A of the first embodiment, routine 350 A distributes the unused output channel 140 bandwidth by proportionately adding the unused or excess bandwidth to each of the queues 110 A- 110 M, after initializing the queue dependent parameters for all the queues 110 A- 110 M. For example, in block B 358 , routine 350 A calculates the excess output channel 140 bandwidth (i.e., excess bandwidth=output channel bandwidth−sum of all queue target bandwidths). In block B 362 , routine 350 A calculates the bandwidth sum of all the queues having enabled BEFs 215 A- 215 M (i.e., total BEF enabled bandwidth=Σ BEF enabled queue bandwidths). In block B 364 , routine 350 A distributes the excess bandwidth by adding a proportionate share of the excess bandwidth to the queue bandwidth (i.e., queue bandwidth i=queue bandwidth i+(excess bandwidth/total BEF enabled bandwidth)×queue bandwidth i). In block B 366 , routine 350 A recalculates the round time for each of the BEF-enabled queues.

FIG. 3D depicts increment credit routine 350 B, which updates the credit counters 225 A- 225 M for each queue i. After initialization routine 250 A has been completed, routine 350 B is executed separately and continuously for each queue i.

As indicated in block B 360 , queue index i is initialized. In block B 361 , process 350 B waits for the passage of round time i. In block B 362 , process 350 B adds the quantum number of bytes to credit counter 225 i and adds the quantum-up number of bytes to credit-up counter 320 i. In block B 363 , routine 350 B determines whether the credit-up counter 320 i exceeds the maximum value contained in the corresponding maximum credit register 220 i . If not, routine 350 B advances to block B 364 . If credit-up counter 320 i does exceed the maximum value in maximum credit register 220 i , routine 350 B advances to block B 365 where credit-up counter 320 i is set to the value contained in maximum credit register 220 i.

In block B 364 , routine 350 B determines whether credit counter 225 i exceeds the value contained in the corresponding maximum credit register 220 i . If not, routine 350 B returns to block B 361 , where it waits for the passage of round time i to commence another round of incrementing credit counter 225 i . If routine 250 B determines that credit counter 225 i does exceed the maximum value in maximum credit register 220 A- 220 M then, in block B 270 , routine 250 B donates the excess bytes to shared credit counter 230 A and advances to block B 372 .

In block B 372 , routine 350 B determines whether shared credit counter 230 A exceeds the value in maximum shared credit register 230 B. If not, then routine 350 B returns to block B 361 wait for another round time. If routine 350 B determines that shared credit counter 230 A does exceed the value in maximum shared credit register 230 B, routine 350 B truncates the value to the maximum shared credit value and returns to block B 361 to wait another round time.

As such, routine 350 B updates credit-up counters 320 A- 320 M by adding quantum-up bytes every round time and never allowing them to exceed the value in the corresponding maximum credit registers 220 A- 220 M. In addition, much like routine 250 B of the first embodiment, routine 350 B updates the credit counters 225 A- 225 M by adding quantum bytes to the credit counters 225 A- 225 M every round time and checking to see whether the added bytes exceed the value in the corresponding maximum credit registers 220 A- 220 M. If the added bytes do exceed the maximum credit threshold, then the excess bytes are donated to the shared credit counter 230 A, so that any of the BEF enabled queues 110 A- 110 M can use them. Moreover, routine 350 B checks to see whether donating the excess bytes causes the shared credit counter 230 A to exceed its maximum. If it does, the number of bytes in shared credit 230 A is truncated to its maximum value, as included in maximum shared credit register 230 B.

FIG. 3E illustrates packet selection routine 350 C, which selects packets to be transmitted on channel 140 . After initialization routine 350 A has been completed, a single copy of routine 350 B is executed continuously to serve all queues i.

As indicated in block B 380 , queue index i is initialized to 0. In block B 382 , routine 350 C determines, whether the byte length of the head packet in queue i is less than or equal to the corresponding credit-up counter 320 i . If not, then no packet may be sent and, routine 350 C proceeds to block B 388 to advance to the next queue i+1. If the byte length of the head packet in queue i is less than or equal to the corresponding credit-up counter 320 i , then in block B 384 , routine 350 C checks whether the byte length of the head packet less than or equal to the corresponding credit counter 225 i . If so, routine 350 C proceeds to block B 386 where the packet is transmitted and dequeued and credit counter 225 i and credit-up counter 320 i are each decremented by the length of the packet.

Routine 350 C then enters into block B 388 , to proceed to the next queue i+1 to be selected. In block B 388 the queue index i is incremented and, in block B 390 , routine 350 C determines whether queue index i is greater than or equal to the number of queues. If so, process 350 C proceeds to block B 380 where queue index i starts again at 0 . If queue index i is not greater than or equal to the number of queues, process 350 C proceeds to block B 382 to operate on the next queue i+1 to be selected.

Returning to block B 384 , if the byte length of the packet is not less than or equal to the number of bytes in the corresponding credit counter B 225 i , then routine 350 C advances to block B 392 , where it determines whether the corresponding BEF 215 i is enabled. If so, then routine 350 C advances to block B 394 . If the corresponding BEF 215 i is not enabled, routine 350 C returns to blocks B 388 and B 390 , to point to the next queue i+1 to be selected.

After determining that the corresponding BEF 215 i is enabled, routine 350 C, in block B 394 , determines if the length of the packet is less than or equal to the sum of the bytes contained in the corresponding credit counter 225 i and shared credit counter 230 A. If not, then routine 350 C returns to blocks B 388 and B 390 , to point to the next queue i+1 to be selected. If the length of the packet is less than or equal to the sum of the bytes contained in the corresponding credit counter 225 i and shared credit counter 230 A, then routine 350 C progresses to block B 396 .

In block B 396 , the packet is transmitted and dequeued. Then credit-up counter 320 i is decremented by the packet length, shared credit counter 230 A is decremented by packet length minus the value of credit counter 225 i , and credit counter 225 i is decremented to zero. Finally, routine 396 C proceeds to blocks B 388 and B 390 to point to the next queue i+1 to be selected.

In this manner, routine 350 C selects packets from queues 110 A- 110 M to be transmitted by examining the packet length to determine if there are enough bytes in the credit counters 225 A- 225 M and credit-up counters 320 A- 320 M to transmit the packets included therein. If there are enough bytes, the packets in the queues 110 A- 110 M are transmitted and the credit counters 225 A- 225 M are decremented. Credits may only be borrowed from shared credit counter 230 A if BEF is enabled and there are enough bytes in credit up counters 320 A- 320 M. Each queue is guaranteed to be able to transmit packets at least its target bandwidth rate, because its credit counter B 225 i is receiving bytes at that rate. If BEF is enabled, a queue may borrow unused bandwidth up to the upper bandwidth limit. A queue may not exceed its upper bandwidth limit because its credit-up counter, which is incremented at the upper bandwidth rate, is not allowed to borrow.

The foregoing description of the preferred embodiments provides an illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible consistent with the above teachings or may be acquired from practice of the invention. Thus, it is noted that the scope of the invention is defined by the claims and their equivalents.