Hierarchical virtual queuing

• US 20080159135A1
• Filed: 12/29/2006
• Published: 07/03/2008
• Est. Priority Date: 12/29/2006
• Status: Active Grant

• Current Assignee: Ellacoya Networks, Inc. (NetScout Systems Incorporated)
• Original Assignee: Ellacoya Networks, Inc. (NetScout Systems Incorporated)
• Inventors: Caram, Bruce E.
• Granted Patent: US 7,826,358 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints

Abstract

A system and method of providing high speed, prioritized delivery of data packets over broadband communications networks that avoids inducing unwanted latency in data packet transmission. The system employs a hierarchical, real-time, weighted token bucket prioritization scheme that provides for fair sharing of the available network bandwidth. At least one token bucket is employed at each level of the hierarchy to meter data flows providing service applications included in multiple subscribers'"'"' service plans. Each token bucket passes, discards, or marks as being eligible for subsequent discarding data packets contained in the data flows using an algorithm that takes into account the priority of the data packets, including strict high, strict medium, and strict low priorities corresponding to strict priority levels that cannot be overridden. The algorithm also takes into account weighted priorities of at least a subset of the low priority data packets. The priority levels of these low priority data packets are weighted to provide for fair sharing of the available network bandwidth among the low priority data flows, and to assure that none of the low priority data flows is starved of service.

Claims

1. A method of controlling a plurality of data flows for subsequent transmission over a network, comprising the steps of:

receiving, at a control mechanism, said plurality of data flows, said control mechanism being implemented as a plurality of token buckets arranged in a hierarchy having a plurality of levels, each level of the hierarchy including at least one of said plurality of token buckets;

in a first metering step, metering, by at least one first token bucket included in a first level of the hierarchy, said plurality of data flows to assure fair sharing of a predetermined aggregate transmission bandwidth among the respective data flows; and

in a second metering step, metering, by at least one second token bucket included in a second level of the hierarchy, said plurality of data flows to assure that said data flows conform to said predetermined aggregate transmission bandwidth.

2. The method of claim 1 wherein said second metering step includes metering said plurality of data flows to enforce a specified maximum data packet transmission rate.

3. The method of claim 1 wherein said first metering step includes metering said plurality of data flows to enforce at least one of a maximum data packet transmission rate, an intermediate data packet transmission rate, a minimum data packet transmission rate, and a fair data packet transmission rate.

4. The method of claim 3:

wherein said plurality of data flows comprises at least one first data flow including a plurality of high priority data packets, at least one second data flow including a plurality of medium priority data packets, and at least one third data flow including a plurality of low priority data packets, said plurality of low priority data packets including a first sub-plurality of low priority data packets and at least one second sub-plurality of low priority data packets; and

wherein said first metering step includes enforcing said maximum data packet transmission rate upon said plurality of high priority data packets, enforcing said intermediate data packet transmission rate upon said plurality of medium priority data packets, enforcing said minimum data packet transmission rate upon said first sub-plurality of low priority data packets, and enforcing said fair data packet transmission rate upon said second sub-plurality of low priority data packets.

5. The method of claim 4 including the steps of:

determining a size of at least one of said high priority data packets included in said received first data flow, said medium priority data packets included in said received second data flow, and said low priority data packets included in said received third data flow;

determining whether said at least one first token bucket included in said first level of the hierarchy contains at least a required number of credits corresponding to said determined size of said at least one data packet included in said received data flow; and

performing one of passing said at least one data packet, dropping said at least one data packet, and marking said at least one data packet as being eligible for dropping, based upon whether said at least one first token bucket contains less than the required number of credits.

6. The method of claim 4 including the steps of:

determining whether said at least one first token bucket included in said first level of the hierarchy contains no credits or a determined negative number of credits; and

in the event said at least one first token bucket contains no credits or said determined negative number of credits, performing one of dropping said plurality of low priority data packets, and marking said plurality of low priority data packets as being eligible for dropping.

7. The method of claim 4 including the steps of:

determining whether said at least one first token bucket included in said first level of the hierarchy contains more than a first predetermined negative number of credits; and

in the event said at least one first token bucket contains more than said first predetermined negative number of credits, performing one of dropping said plurality of low priority data packets and said plurality of medium priority data packets, and marking said plurality of low priority data packets and said plurality of medium priority data packets as being eligible for dropping.

8. The method of claim 7 including the steps of:

determining whether said at least one first token bucket included in said first level of the hierarchy contains more than a second predetermined negative number of credits, said second predetermined negative number of credits being greater than said first predetermined negative number of credits; and

in the event said at least one first token bucket contains more than said second predetermined negative number of credits, performing one of dropping said plurality of low priority data packets, said plurality of medium priority data packets, and said plurality of high priority data packets, and marking said plurality of low priority data packets, said plurality of medium priority data packets, and said plurality of high priority data packets as being eligible for dropping.

9. The method of claim 4 including the steps of:

determining a size of said low priority data packets included in said received third data flow;

determining whether said at least one first token bucket included in said first level of the hierarchy contains at least a required number of credits corresponding to said determined size of said low priority data packets included in said received third data flow; and

wherein said first metering step includes, in the event said at least one first token bucket contains less than the required number of credits, enforcing said fair data packet transmission rate upon said second sub-plurality of low priority data packets using a weighted prioritization technique.

10. The method of claim 9 wherein at least one of said at least one first token bucket and said at least one second token bucket has an associated weight and an associated accumulated weight,

said method including the steps of:

determining, by said at least one of said at least one first token bucket and said at least one second token bucket, whether a rate limiting condition exists with respect to said low priority data packets included in said received third data flow;

in the event said rate limiting condition exists, adding, by said at least one of said at least one first token bucket and said at least one second token bucket, said associated weight to said associated accumulated weight; and

in the event said associated accumulated weight is greater than or equal to a predetermined maximum accumulated weight, performing said weighted prioritization technique including promoting every “

n^th”

low priority data packet included in said received third data flow to a next higher priority level, “

n”

being an integer having a determined value based upon the weight associated with said at least one of said at least one first token bucket and said at least one second token bucket.

11. A network switch, comprising:

a control mechanism, said control mechanism being implemented as a plurality of token buckets arranged in a hierarchy having a plurality of levels, each level of the hierarchy including at least one of said plurality of token buckets,

wherein said control mechanism is configured;

to receive a plurality of data flows;

to meter, by at least one first token bucket included in a first level of the hierarchy, said plurality of data flows to assure fair sharing of a predetermined aggregate transmission bandwidth among the respective data flows; and

to meter, by at least one second token bucket included in a second level of the hierarchy, said plurality of data flows to assure that said data flows conform to said predetermined aggregate transmission bandwidth.

12. The network switch of claim 11 wherein said at least one second token bucket included in said second level of the hierarchy is configured to meter said plurality of data flows to enforce a specified maximum data packet transmission rate.

13. The network switch of claim 11 wherein said at least one first token bucket included in said first level of the hierarchy is configured to meter said plurality of data flows to enforce at least one of a maximum data packet transmission rate, an intermediate data packet transmission rate, a minimum data packet transmission rate, and a fair data packet transmission rate.

14. The network switch of claim 13:

wherein said plurality of data flows comprises at least one first data flow including a plurality of high priority data packets, at least one second data flow including a plurality of medium priority data packets, and at least one third data flow including a plurality of low priority data packets, said plurality of low priority data packets including a first sub-plurality of low priority data packets and at least one second sub-plurality of low priority data packets; and

wherein said at least one first token bucket included in said first level of the hierarchy is configured to enforce said maximum data packet transmission rate upon said plurality of high priority data packets, to enforce said intermediate data packet transmission rate upon said plurality of medium priority data packets, to enforce said minimum data packet transmission rate upon said first sub-plurality of low priority data packets, and to enforce said fair data packet transmission rate upon said second sub-plurality of low priority data packets.

15. The network switch of claim 14 wherein said control mechanism is configured:

to determine a size of at least one of said high priority data packets included in said received first data flow, said medium priority data packets included in said received second data flow, and said low priority data packets included in said received third data flow;

to determine whether said at least one first token bucket included in said first level of the hierarchy contains at least a required number of credits corresponding to said determined size of said at least one data packet included in said received data flow; and

to perform one of passing said at least one data packet, dropping said at least one data packet, and marking said at least one data packet as being eligible for dropping, based upon whether said at least one first token bucket contains less than the required number of credits.

16. The network switch of claim 14 wherein said control mechanism is configured:

to determine whether said at least one first token bucket included in said first level of the hierarchy contains no credits or a determined negative number of credits; and

in the event said at least one first token bucket contains no credits or said determined negative number of credits, to perform one of dropping said plurality of low priority data packets, and marking said plurality of low priority data packets as being eligible for dropping.

17. The network switch of claim 14 wherein said control mechanism is configured:

to determining whether said at least one first token bucket included in said first level of the hierarchy contains more than a first predetermined negative number of credits; and

in the event said at least one first token bucket contains more than said first predetermined negative number of credits, to perform one of dropping said plurality of low priority data packets and said plurality of medium priority data packets, and marking said plurality of low priority data packets and said plurality of medium priority data packets as being eligible for dropping.

18. The network switch of claim 17 wherein said control mechanism is configured:

to determining whether said at least one first token bucket included in said first level of the hierarchy contains more than a second predetermined negative number of credits, said second predetermined negative number of credits being greater than said first predetermined negative number of credits; and

in the event said at least one first token bucket contains more than said second predetermined negative number of credits, to perform one of dropping said plurality of low priority data packets, said plurality of medium priority data packets, and said plurality of high priority data packets, and marking said plurality of low priority data packets, said plurality of medium priority data packets, and said plurality of high priority data packets as being eligible for dropping.

19. The network switch of claim 14 wherein said control mechanism is configured:

to determine a size of said low priority data packets included in said received third data flow; and

to determine whether said at least one first token bucket included in said first level of the hierarchy contains at least a required number of credits corresponding to said determined size of said low priority data packets included in said received third data flow; and

wherein said at least one first token bucket included in said first level of the hierarchy is configured, in the event said at least one first token bucket contains less than the required number of credits, to enforce said fair data packet transmission rate upon said second sub-plurality of low priority data packets using a weighted prioritization technique.

20. The network switch of claim 19 wherein at least one of said at least one first token bucket and said at least one second token bucket has an associated weight and an associated accumulated weight, and

wherein said control mechanism is configured:

to determine whether a rate limiting condition exists with respect to said low priority data packets included in said received third data flow;

in the event said rate limiting condition exists, to add said associated weight to said associated accumulated weight; and

in the event said associated accumulated weight is greater than or equal to a predetermined maximum accumulated weight, to perform said weighted prioritization technique including promoting every “

n^th”

low priority data packet included in said received third data flow to a next higher priority level, “

n”

being an integer having a determined value based upon the weight associated with said at least one of said at least one first token bucket and said at least one second token bucket.