Flexible multilevel output traffic control

• US 20030231593A1
• Filed: 05/16/2003
• Published: 12/18/2003
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Anderson, Eric, Aybay, Gunes, Morrison, Mike, Bauman, James
• Granted Patent: US 7,474,668 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/21 using leaky-bucket
• 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/2483 involving identification of individual flows
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A two stage rate shaping and scheduling system and method is implemented to control the flow of traffic to at least one output interface. The system and method involves initially queuing incoming packets into type-specific queues and applying individual rate shaping rules to each queue. A first stage arbitration is performed to determine how traffic is queued from the type-specific queues to interface-specific queues. Packets that win arbitration and pass the applied rate shaping rules are queued in interface-specific queues. Rate shaping rules are applied to the interface-specific queues. The interface-specific queues are further distinguished by priority and priority-specific and interface-specific rate shaping rules are applied to each queue. A second stage arbitration is performed to determine how different priority traffic that is targeting the same output interface is dequeued in response to interface-specific requests.

Claims

1. A method for controlling the flow of packets through at least one output interface comprising:

queuing packets into type-specific queues;

applying per-type rate shaping rules to said type-specific queues;

queuing packets, from the type-specific queues that pass said applied per-type rate shaping rules, into interface-specific queues;

applying per-interface rate shaping rules to said interface-specific queues; and

dequeuing packets, from the interface-specific queues that pass said applied per-interface rate shaping rules, from said interface-specific queues to at least one output interface in response to interface-specific requests.

2. The method of claim 1 further including:

establishing priority-specific subqueues, which have different priority levels, within said interface-specific queues;

queuing packets to particular priority-specific subqueues of said interface-specific queues; and

applying per-priority and per-interface rate shaping rules to said priority-specific subqueues.

3. The method of claim 2 wherein dequeuing packets from said interface-specific queues in response to interface-specific requests further includes arbitrating among said priority-specific subqueues.

4. The method of claim 2 wherein applying per-interface rate shaping rules includes scaling, by a common multiple, refresh rates of credit buckets that are associated with said priority-specific subqueues that have a pending packet but do not have a passing credit value when no priority-specific subqueues have both a pending packet and a passing credit value.

5. The method of claim 2 wherein queuing packets into said interface-specific queues includes arbitrating among multiple type-specific queues that target the same priority-specific subqueue.

6. The method of claim 1 wherein queuing packets into said interface-specific queues includes writing queue identifiers of said type-specific queues into said interface-specific queues to identify packets in said interface-specific queues.

7. The method of claim 6 wherein queuing packets into said type-specific queues includes writing at least the payload of said packets into a separate packet buffer and wherein dequeuing packets from said interface-specific queues includes reading at least the payload of said packets from said separate packet buffer.

8. The method of claim 1 wherein queuing packets into said type-specific queues includes writing at least the payload of said packets into a separate packet buffer and wherein dequeuing packets from said interface-specific queues includes reading at least the payload of said packets from said separate packet buffer.

9. The method of claim 8 wherein applying said per-type rate shaping rules to said type-specific queues further includes deducting an assumed length value from a credit bucket value to determine a new credit bucket value if a type-specific queue passes an applied rate shaping rule and a packet is queued into an interface-specific queues.

10. The method of claim 9 further including correcting for the difference between said assumed length value and an actual length value after a packet is fetched from said separate packet buffer.

11. The method of claim 9 further including establishing said assumed length value as an average of the actual packet length of packets that were queued in respective type-specific queues.

12. The method of claim 1 further including:

associating a scaling factor with a first one of said interface-specific queues; and

scaling, by said scaling factor, per-type rate shaping rules that are applied to the type-specific queues that target said first interface-specific queue.

13. The method of claim 12 further including adjusting the scaling factor that is associated with said first interface-specific queue in response to packet depth of said first interface-specific queue.

14. A system for controlling the flow of packets through at least one output interface comprising:

a queue manager configured to receive packets that have been classified, to direct said packets to a packet buffer, and to dispatch packets from said packet buffer to at least one output interface in response to interface-specific requests;

a plurality of type-specific queues;

a type-specific shaping and scheduling engine operationally associated with said plurality of type-specific queues; and

an interface-specific shaping and scheduling engine operationally associated with said type-specific shaping and scheduling engine, said interface-specific shaping and scheduling engine including a plurality of interface-specific queues;

said type-specific shaping and scheduling engine being configured to apply per-type rate shaping rules to said type-specific queues and to queue packets, from type-specific queues that pass said applied per-type rate shaping rules, into said interface-specific queues of said interface-specific shaping and scheduling engine;

said interface-specific shaping and scheduling engine being configured to apply per-interface rate shaping rules to said interface-specific queues and to dequeue packets, from interface-specific queues that pass said applied per-interface rate shaping rules, from said interface-specific queues to said at least one output interface in response to interface-specific requests.

15. The system of claim 14 wherein said interface-specific queues are divided into priority-specific subqueues that have different priority levels and wherein packets are queued to particular priority-specific subqueues, said interface-specific shaping and scheduling engine being further configured to apply per-priority and per-interface rate shaping rules to said priority-specific subqueues.

16. The system of claim 15 wherein said interface-specific shaping and scheduling engine is further configured to arbitrate among different priority-specific subqueues.

17. The system of claim 15 wherein said interface-specific shaping and scheduling engine is further configured to scale, by a common multiple, refresh rates of credit buckets that are associated with priority-specific subqueues that have a pending packet but do not have a passing credit value when no priority-specific subqueues have both a pending packet and a passing credit value.

18. The system of claim 15 wherein said type-specific shaping and scheduling engine is further configured to arbitrate among multiple type-specific queues that target the same priority-specific subqueues.

19. The system of claim 14 wherein queuing packets into said interface-specific queues includes writing queue identifiers of said type-specific queues into said interface-specific queues to identify packets in said interface-specific queues.

20. The system of claim 14 wherein said queue manager is further configured to write at least the payload of said packets into said packet buffer and wherein dequeuing packets from said interface-specific queues includes reading at least the payload of said packets from said packet buffer.

21. The system of claim 20 wherein said packet buffer is an off-chip packet buffer.

22. The system of claim 14 wherein applying said per-type rate shaping rules to said type-specific queues further includes deducting an assumed length value from a credit bucket value to determine a new credit bucket value if a type-specific queue passes an applied rate shaping rule and a packet is queued into an interface-specific queue.

23. The system of claim 22 further including correcting for the difference between said assumed length value and an actual length value after a packet is fetched from said packet buffer.

24. The system of claim 22 wherein said assumed length value is established as a running average of the actual length of packets that were queued in respective type-specific queues.

25. The system of claim 14 wherein a scaling factor is associated with a first interface-specific queue and the rate shaping rules that are applied to the type-specific queues that target said first interface-specific queue are scaled by the scaling factor that is associated with said first interface-specific queue.

26. The system of claim 25 wherein the scaling factor that is associated with said first interface-specific queue is adjusted in response to the depth of the first interface-specific queue.

27. A method for rate shaping a flow of packets comprising:

establishing an assumed length value;

providing a credit value that is related to a queue and a flow of packets;

performing a rate shaping check on said queue; and

deducting said assumed length value from said credit value if said queue passes said rate shaping check and a first packet, from said flow of packets, is forwarded from said queue.

28. The method of claim 27 further including:

obtaining an actual length value from said first packet; and

correcting said credit value to account for any difference between said assumed length value and said actual length value after said actual length value is obtained.

29. The method of claim 28 wherein correcting said credit value includes finding the difference between said assumed length value and said actual length value and adding the difference to said credit value.

30. The method of claim 29 further including establishing said assumed length value as a running average of the actual length of packets from said flow of packets.

31. The method of claim 27 further including:

receiving said first packet at a queue manager;

queuing an identifier of said first packet in a type-specific queue;

storing said packet in a packet buffer;

obtaining an actual length value from said first packet when said first packet is dispatched from said packet buffer; and

correcting said credit value to account for any difference between said assumed length value and said actual length value after said actual length value is obtained.

32. A method for rate shaping a flow of packets comprising:

establishing a plurality of subqueues that all target the same interface, said interface having a total available bandwidth;

allocating a portion of said total available bandwidth to each of said subqueues by setting credit refresh rates for subqueue-specific credit buckets;

queuing packets into said plurality of subqueues;

distributing bandwidth to said plurality of subqueues according to said bandwidth allocations;

identifying unused bandwidth related to said interface; and

allocating said unused bandwidth to subqueues, which have consumed their allocated portion of the total available bandwidth but still have queued packets, by increasing the credit refresh rate by a common multiple for all of the subqueues that have consumed their allocated portion of the total available bandwidth but still have queued packets;

wherein said allocation of unused bandwidth preserves the relative relationships of bandwidth allocations among the subqueues that have consumed their allocated portion of the total available bandwidth but still have queued packets.

33. The method of claim 32 wherein increasing the credit refresh rate by a common multiple includes multiplying, by a common value, the refresh rate for all of the subqueues that have consumed their allocated portion of the total available bandwidth but still have packets.

34. The method of claim 32 wherein unused bandwidth related to said interface is identified when none of said plurality of subqueues have both a queued packet and a passing credit value.