Adaptive queue-management

• US 8,923,120 B2
• Filed: 12/06/2012
• Issued: 12/30/2014
• Est. Priority Date: 05/17/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Jayakumar, Lenard John Stephan
• Primary Examiner(s): LIU, JUNG
• Application Number:
  US13/706,741
• Publication Number:
  US 20130094358A1
• Time in Patent Office: 754 Days
• Field of Search: 370/203, 370204-215, 370229-240, 370310-337, 370/395.3, 370/395.4, 370/395.41, 370/395.42, 370/395.5, 370/395.52, 370431-457, 370458-463, 370464-497, 370498-529
• US Class Current: 370/230
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/782 Hierarchical allocation of resources, e.g. involving a hierarchy of local and centralised entities
• CPC Class Codes: H04L 47/805 QOS or priority aware

Abstract

In one embodiment, a method includes storing in a QoS-enabled communication system a data structure that has a multi-level hierarchy including a physical level, a logical level, and a class level; receiving a first request for M number of services provided by the QoS-enabled communication system; in response to the first request, modifying an allocation of the logical-level nodes by mapping M class-level nodes to a first one of the logical-level nodes according to a first mapping mode of the data structure; receiving a second request for P services provided by the QoS-enabled communication system, with P being greater than M; and, in response to the second request, modifying an allocation of the logical-level nodes by mapping P class-level nodes to a second one of the logical-level nodes according to a second mapping mode of the data structure.

Claims

1. A method comprising, by one or more computing systems:

storing in a quality-of-service (QoS) -enabled communication system a data structure that has a multi-level hierarchy comprising;

a physical level comprising one or more physical-level nodes, each of the physical-level nodes corresponding to a physical interface for transmitting a bandwidth-limited traffic (BLT) stream of packets;

a logical level comprising one or more logical-level nodes, each of the logical-level nodes comprising a bandwidth-limitation parameter; and

a class level comprising one or more class-level nodes, each of the class-level nodes corresponding to a service provided by the QoS-enabled communication system;

receiving a first request for M number of services provided by the QoS-enabled communication system; and

in response to the first request, modifying an allocation of the logical-level nodes by mapping M class-level nodes to a first one of the logical-level nodes according to a first mapping mode of the data structure.

2. The method of claim 1, further comprising:

receiving a second request for P services provided by the QoS-enabled communication system;

transferring the bandwidth limitation parameter of the first one of the logical-level nodes to a second one of the logical-level nodes, the transfer being in response to the second request; and

resetting the first one of the logical-level nodes.

3. The method of claim 2, further comprising updating a list of logical-level nodes based at least in part on the automatically resetting of the first one of the logical-level nodes, each logical-level node included in the list of logical-level nodes having no corresponding class-level node mapped to it.

4. The method of claim 1, further comprising:

receiving a second request for P services provided by the QoS-enabled communication system;

transferring the bandwidth limitation parameter of a second one of the logical-level nodes to the first one of the logical-level nodes, the transfer being in response to the first request; and

resetting the second one of the logical-level nodes.

5. The method of claim 1, further comprising partitioning the data structure into at least first and second partitions, the first partition storing a first plurality of mappings according the first mapping mode, the second partition storing a second plurality of mappings according to a second mapping mode of the data structure, the second mapping mode being different from the first mapping mode.

6. The method of claim 5, wherein:

the first mapping mode ratio is a 4;

1 ratio of the class-level nodes to the logical-level nodes; and

the second mapping mode ratio is a 8;

1 mapping mode ratio of the class-level nodes to the logical-level nodes.

7. The method of claim 2, wherein:

the first one of the logical-level nodes comprises the second one of the logical-level nodes.

8. The method of claim 1, further comprising:

resetting a logical-level node;

determining the location of the reset logical-level node relative to the end of a range of memory of the data structure; and

in response to the determination, executing one of the following steps;

updating a variable identifying a last used logical-level node; and

adding the reset logical-level node to a list of logical-level nodes, each logical-level node included in the list of logical-level nodes having no corresponding class-level node mapped to it.

9. One or more computer-readable non-transitory storage media embodying software this is operable when executed by one or more computer systems to:

store in a quality-of-service (QoS) -enabled communication system a data structure that has a multi-level hierarchy comprising;

a physical level comprising one or more physical-level nodes, each of the physical-level nodes corresponding to a physical interface for transmitting a bandwidth-limited traffic (BLT) stream of packets;

a logical level comprising one or more logical-level nodes, each of the logical-level nodes comprising a bandwidth-limitation parameter; and

a class level comprising one or more class-level nodes, each of the class-level nodes corresponding to a service provided by the QoS-enabled communication system;

receive a first request for M number of services provided by the QoS-enabled communication system; and

in response to the first request, modify an allocation of the logical-level nodes by mapping M class-level nodes to a first one of the logical-level nodes according to a first mapping mode of the data structure.

10. The media of claim 9, wherein the software is further operable when executed to:

receive a second request for P services provided by the QoS-enabled communication system;

transfer the bandwidth limitation parameter of the first one of the logical-level nodes to a second one of the logical-level nodes, the transfer being in response to the second request; and

reset the first one of the logical-level nodes.

11. The media of claim 10, wherein the software is further operable when executed to update a list of logical-level nodes based at least in part on the automatically resetting of the first one of the logical-level nodes, each logical-level node included in the list of logical-level nodes having no corresponding class-level node mapped to it.

12. The media of claim 9, wherein the software is further operable when executed to:

receive a second request for P services provided by the QoS-enabled communication system;

transfer the bandwidth limitation parameter of a second one of the logical-level nodes to the first one of the logical-level nodes, the transfer being in response to the first request; and

reset the second one of the logical-level nodes.

13. The media of claim 9, wherein the software is further operable when executed to partition the data structure into at least first and second partitions, the first partition storing a first plurality of mappings according the first mapping mode, the second partition storing a second plurality of mappings according to a second mapping mode of the data structure, the second mapping mode being different from the first mapping mode.

14. The media of claim 13, wherein:

the first mapping mode ratio is a 4;

1 ratio of the class-level nodes to the logical-level nodes; and

the second mapping mode ratio is a 8;

1 mapping mode ratio of the class-level nodes to the logical-level nodes.

15. The media of claim 10, wherein:

the first one of the logical-level nodes comprises the second one of the logical-level nodes.

16. The media of claim 9, wherein the software is further operable when executed to:

reset a logical-level node;

determine the location of the reset logical-level node relative to the end of a range of memory of the data structure; and

in response to the determination, execute one of the following steps;

update a variable identifying a last used logical-level node; and

add the reset logical-level node to a list of logical-level nodes, each logical-level node included in the list of logical-level nodes having no corresponding class-level node mapped to it.

17. An apparatus comprising:

one or more communication interfaces;

one or more memory devices containing one or more instructions for execution by one or more processing devices; and

the processing devices, operable when executing the instructions to;

store in a quality-of-service (QoS) -enabled communication system a data structure that has a multi-level hierarchy comprising;

a physical level comprising one or more physical-level nodes, each of the physical-level nodes corresponding to a physical interface for transmitting a bandwidth-limited traffic (BLT) stream of packets;

a logical level comprising one or more logical-level nodes, each of the logical-level nodes comprising a bandwidth-limitation parameter; and

a class level comprising one or more class-level nodes, each of the class-level nodes corresponding to a service provided by the QoS-enabled communication system;

receive a first request for M number of services provided by the QoS-enabled communication system; and

in response to the first request, modify an allocation of the logical-level nodes by mapping M class-level nodes to a first one of the logical-level nodes according to a first mapping mode of the data structure.

18. The apparatus of claim 17, wherein the processing devices are further operable when executing the instructions to:

transfer the bandwidth limitation parameter of the first one of the logical-level nodes to a second one of the logical-level nodes, the transfer being in response to a second request for P services provided by the QoS-enabled communication system; and

reset the first one of the logical-level nodes.

19. The apparatus of claim 18, wherein the processing devices are further operable when executing the instructions to update a list of logical-level nodes based at least in part on the automatically resetting of the first one of the logical-level nodes, each logical-level node included in the list of logical-level nodes having no corresponding class-level node mapped to it.

20. The apparatus of claim 17, wherein the processing devices are further operable when executing the instructions to:

transfer the bandwidth limitation parameter of a second one of the logical-level nodes to the first one of the logical-level nodes, the transfer being in response to the first request; and

reset the second one of the logical-level nodes.