Systems and methods for grouping of bandwidth allocations

• US 20040042399A1
• Filed: 08/29/2002
• Published: 03/04/2004
• Est. Priority Date: 08/29/2002
• Status: Active Grant

• Current Assignee: World Wide Packets, Inc. (Ciena Corporation)
• Original Assignee: World Wide Packets, Inc. (Ciena Corporation)
• Inventors: Bly, Keith Michael, Johnson, C. Stuart
• Granted Patent: US 7,277,389 B2
• Time in Patent Office: Days
• US Class Current: 370/230.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/39 Credit based
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A data traffic shaping system, comprises a plurality of burst groups, each burst group having a burst group credit allocation mechanism configured to earn credit over time; a shaping engine configured to manage incoming entries of traffic and to assign each incoming entry of traffic to a selected queue of the burst group depending on the characteristics of the entry; a plurality of queues, respective queues belonging to respective burst groups; and a bandwidth allocation table including locations identifying a queue and an amount of bandwidth credit to allocate to that queue, the shaping engine being configured to traverse the locations, to determine the bandwidth earned by the queues, such credit only being made available to the queue if its assigned burst group has at least that much credit available at that instant in time, and to process an entry in that queue only if the queue has earned a predetermined minimum amount of credit, relative to the current entry on the queue in question.

Claims

1. A data traffic shaping system, comprising:

a plurality of burst groups, each burst group having a burst group credit allocation mechanism configured to earn credit over time;

a shaping engine configured to classify incoming entries of traffic and to assign an incoming entry of traffic to a selected queue of one of the burst groups depending on characteristics of the entry;

a plurality of queues, respective queues belonging to respective burst groups; and

a bandwidth allocation table including locations identifying a queue and an amount of bandwidth credit to allocate to that queue, the shaping engine being configured to traverse the locations, to determine the bandwidth earned by the queues, and to process an entry in that queue only if both the queue and the burst group with which the queue is associated have respectively earned a predetermined minimum amount of credit.

2. A data traffic shaping system in accordance with claim 1 wherein a queue is associated with multiple burst groups and wherein an entry in that queue is processed only if both the queue and at least one of the burst groups with which the queue is associated have respectively earned a predetermined minimum amount of credit.

4. A data traffic shaping system in accordance with claim 1 wherein the burst groups earn credit more often than the queues earn credit.

5. A data traffic shaping system in accordance with claim 4 wherein respective burst groups earn credit in lower amounts, each time they are updated, than the queues.

6. A data traffic shaping system in accordance with claim 1 wherein the queues respectively have an upper bound on the amount of credit they can accumulate.

7. A data traffic shaping system in accordance with claim 1 wherein the order in which queues earn credit in the bandwidth allocation table is reconfigurable on the fly while traffic entries are being processed.

8. A data traffic shaping system in accordance with claim 1 wherein the credit amounts for respective queues in the bandwidth allocation table is reconfigurable while traffic entries are being processed.

9. A data traffic shaping system in accordance with claim 1 wherein queues are sequenced in the bandwidth allocation table such that a queue that is listed twice in the table, including at the end of the table, to take advantage of any unused credit.

10. A data traffic shaping system in accordance with claim 1 wherein each queue is defined by a linked list.

3. A data traffic shaping system in accordance with claim 3 wherein the bandwidth allocation table is traversed at a fixed rate.

11. A method for shaping traffic from a plurality of data streams, the method comprising:

providing a plurality of FIFO queues;

assigning each queue to a burst group;

assigning traffic to the queues depending on the characteristics of the traffic; and

controlling traffic flow out of the queues using a bandwidth allocation table and a burst group credit allocation mechanism.

12. A method for shaping traffic in accordance with claim 11 and further comprising defining the queues, at least in part, using linked lists.

13. A method for shaping traffic in accordance with claim 11 wherein controlling traffic flow comprises using timed division multiplexing to allocate credit to individual queues.

14. A method for shaping traffic in accordance with claim 13 wherein burst groups are allocated credit over time at a steady rate.

15. A method for shaping traffic in accordance with claim 14 wherein an amount of traffic is permitted to flow out of a queue when the queue has earned a predetermined amount of credit and wherein the burst group with which that queue has been assigned has also earned at least the predetermined amount of credit.

16. A method for shaping data traffic, comprising:

providing a plurality of queues;

assigning the queues to burst groups, each burst group earning bandwidth over time;

classifying incoming entries of traffic and assigning an incoming entry of traffic to a selected queue of a selected burst group depending on characteristic of the entry;

providing a memory including locations identifying a queue and the amount of bandwidth credit to allocate to that queue;

allocating bandwidth to each of the queues using timed division multiplexing by traversing the memory locations in a repeating order to determine the bandwidth allocatable to each of the queues; and

releasing an entry from a queue when the queue has earned a predetermined amount of credit provided that the burst group to which the queue is assigned has also earned a predetermined amount of bandwidth.

17. A method for shaping data traffic in accordance with claim 16 and further comprising assigning a queue to multiple burst groups, and wherein an entry in that queue is released only if both the queue and at least one of the burst groups with which the queue is associated have earned a predetermined minimum amount of bandwidth.

18. A method for shaping data traffic in accordance with claim 16 wherein the memory locations are traversed at a constant rate.

19. A method for shaping data traffic in accordance with claim 16 wherein the burst groups earn bandwidth more often than the queues earn bandwidth.

20. A method for shaping data traffic in accordance with claim 19 wherein respective burst groups earn bandwidth in lower amounts, each time they are updated, than the queues.

21. A method for shaping data traffic in accordance with claim 16 wherein the queues respectively have an upper bound on the amount of bandwidth they can accumulate.

22. A method for shaping data traffic in accordance with claim 16 wherein the order in which queues earn bandwidth is reconfigurable while traffic entries are being processed.

23. A method for shaping data traffic in accordance with claim 16 wherein the bandwidth amounts for respective queues in the memory locations are reconfigurable while traffic entries are being processed.

24. A method for shaping data traffic in accordance with claim 16 wherein queues are sequenced in the memory locations such that a queue that is listed twice in the sequence, including at the end of the sequence, to take advantage of any unused credit.

25. A method for shaping data traffic in accordance with claim 16 wherein each queue is defined by a linked list.