BANDWIDTH ALLOCATION METHOD AND APPARATUS

• US 20100085874A1
• Filed: 03/24/2009
• Published: 04/08/2010
• Est. Priority Date: 10/05/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Contextream Ltd.
• Inventors: NOY, Ariel, Kaempfer, Gideon
• Granted Patent: US 8,000,235 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/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/805 QOS or priority aware

Abstract

System for bandwidth assignment to manage congestion over a network bottleneck, comprises a regulation point being set up downstream of the bottleneck in the network to manage congestion in data packets arriving from various sources via the bottleneck. For each of the sources, a priority level assigner assigns priority levels to respective data packets. A token bucket assigns tokens at a limiting rate to the prioritized data packets, the tokens allowing passage of packets to which they are assigned. The token bucket is a multi-priority token bucket, meaning it has at least two thresholds corresponding to the priority levels assigned to the packets. The token bucket only assigns a token to an arriving packet having a respective priority level if there are sufficient tokens currently in the bucket to reach the threshold corresponding to the packet'"'"'s priority level.

Claims

1. System for bandwidth assignment to manage congestion over a network bottleneck, the system comprising a regulation point being set up downstream of said bottleneck in said network to manage congestion in data packets arriving from at least two sources via said bottleneck, the system comprising, for each of said at least two sources, a priority level assigner for assigning priority levels to respective data packets, and at least one token bucket for assigning tokens at a limiting rate to said prioritized data packets, said tokens allowing passage of packets to which they are assigned, said token bucket being a multi-priority token bucket having at least two thresholds corresponding to priority levels assignable to packets, and said token bucket assigning a token to an arriving packet having a respective priority level if there are sufficient tokens currently in said bucket to reach a one of said thresholds corresponding to said respective priority level.

2. The system of claim 1, wherein said at least one priority token buckets are arranged to define a bandwidth, and a bandwidth defined by said token buckets is lower than a maximum rate allowed by a corresponding network locality.

3. The system of claim 1, wherein said thresholds respectively define minimal numbers of tokens required within the token bucket for a packet of a corresponding priority to be eligible for token consumption.

4. The system of claim 1, wherein each threshold corresponds to a single priority level.

5. The system of claim 1, the network comprising a hierarchy of bottlenecks, the system comprising a hierarchy of multi-priority token buckets for said hierarchy of bottlenecks.

6. The system of claim 5, wherein the hierarchy of token buckets is placed downstream of said hierarchy of bottlenecks.

7. The system of claim 1, wherein said at least one token bucket is configured to supply a quantity of tokens, the quantity being selected to underuse said bottleneck by a margin, said margin being dynamically variable.

8. The system of claim 1, wherein said bottleneck comprises a network access link, including an Internet access link.

9. The system of claim 1, wherein said bottleneck comprises any one of the group consisting of:

a link between an Optical Line Termination (OLT) point and a network service provider network;

a digital subscriber line access multiplexer (DSLAM) link and a network service provider network;

a broadband remote access server (BRAS) link and a network service provider;

a cable modem termination system (CMTS) and a network service provider;

a serving GPRS (general packet radio service) support node (SGSN) and a network service provider;

an LTE (long term evolution) compatible link and a network service provider; and

a wireless access link.

10. System for bandwidth assignment to manage congestion over a network bottleneck, the system comprising a regulation point being set up downstream of said bottleneck in said network to manage congestion in data packets arriving from upstream in said network, the apparatus comprising a limiter for allowing packets to pass up to a threshold, said threshold being lower than a maximum rate of said congestion point.

11. A token bucket limiter for congestion management over a network bottleneck, the bucket limiter comprising:

an input unit for receiving packets of a given source with assigned priority levels;

a rate limiter for inserting tokens at a given rate;

a thresholder for providing thresholds associated with priority levels, said thresholds defining numbers of tokens to be present before packets below said associated priority are eligible for token assignment; and

a token assigner for assigning tokens to arriving packets according to a respective priority level and associated threshold to allow passage of said packets.

12. A method of congestion management for a plurality of sources sending data packets over a network bottleneck, the method comprising;

setting an overall bandwidth over said bottleneck, said bandwidth not exceeding a physical maximum bandwidth defined by said bottleneck;

assigning said bandwidth between said sources as per source bandwidth allocations;

assigning priority levels to packets for each source; and

for each source assigning highest priority packets in precedence to said per source bandwidth allocation.

13. The method of claim 12, wherein said overall bandwidth set over said bottleneck is less than said maximum physical bandwidth by a variable margin.

14. The method of claim 13, further comprising dynamically varying said margin.

15. The method of claim 14 wherein said dynamically varying said margin comprises probing cycles carried out at predetermined or dynamically adjusted intervals, each cycle comprising increasing the margin if no high priority packets are being dropped and as long it is detected that the incoming traffic rate remains equal to the network capacity but otherwise decreasing the margin from the actual network capacity.