SYSTEM TO SHARE NETWORK BANDWIDTH AMONG COMPETING APPLICATIONS

• US 20120195209A1
• Filed: 02/01/2011
• Published: 08/02/2012
• Est. Priority Date: 02/01/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kumar, Alok, Naik, Uday, Siganporia, Aspi, Jain, Sushant, Raghuraman, Anand
• Granted Patent: US 9,007,898 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/801 Real time traffic
• CPC Class Codes: H04L 47/808 User-type aware
• CPC Class Codes: H04L 47/828 Allocation of resources per group of connections, e.g. per group of users
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

The present invention pertains to the allocation of bandwidth on a global large scale network. Systems and methods are provided to base bandwidth allocation on the predicted bandwidth demands of the network users. In allocating bandwidth, each user is assigned a user weight value, and is to be allocated bandwidth in proportion to that value. In addition, the bandwidth allocation is enforced so as to ensure that bandwidth allocation policies are maintained.

Claims

1. A method of allocating bandwidth over a network, the method comprising:

receiving bandwidth usage information that is representative of a plurality of network users;

classifying the network users, the act of classifying including assigning each network user with one of a plurality of weight values, the assigned weight values being in accordance with a predetermined set of network criteria;

performing operations with a processor to create bandwidth allocations, the bandwidth allocations being based on the bandwidth usage information and the users'"'"' weight values;

transmitting the bandwidth allocations to network devices that correspond to the network users.

2. The method of claim 1, wherein the operations performed with the processor include:

aggregating bandwidth usage information to determine the network'"'"'s total bandwidth demand;

detecting congested links within the network; and

dividing the network'"'"'s available bandwidth between the network users.

3. The method of claim 1, further comprising dividing the bandwidth allocations among the network users.

4. The method of claim 2, further comprising dividing the bandwidth allocations of each network user among the jobs being performed for each network user.

5. The method of claim 3, further comprising dividing the bandwidth allocations of each job among a plurality of tasks associated with each job.

6. The method of claim 1, wherein the bandwidth demand information is based on the peak bandwidth usage of the network users over a predetermined time period.

7. The method of claim 1, further comprising:

determining that all network bandwidth demand is being met;

determining that unused bandwidth is available on the network; and

dividing the unused bandwidth among the network users in proportion to the users'"'"' weight values.

8. The method of claim 1, wherein a portion of network bandwidth remains exempt from the operations to create bandwidth allocations.

9. The method of claim 1, wherein a portion of network transmissions remain exempt from the operations to create bandwidth allocations.

11. The method of claim 9, wherein the bandwidth demand includes bandwidth that is permanently allocated to particular network users.

12. The method of claim 9, wherein the determining of bandwidth demand includes aggregating the bandwidth demand of a plurality of users into a single demand function.

13. The method of claim 9, wherein each network user is associated with a network cluster and wherein the transmitting of the bandwidth demand includes providing the bandwidth demand of a network cluster.

14. The method of claim 9, further comprising dividing the bandwidth of each job among a plurality of tasks.

10. A method of allocating bandwidth over a network, the method comprising:

receiving user weight values for network users;

receiving bandwidth usage information regarding a plurality of jobs running on the network, wherein each job is associated with a given one of the network users and includes one or more tasks to be performed over the network;

determining a bandwidth demand for each network user, wherein the bandwidth demand is based at least in part on the received user weight values;

transmitting the bandwidth demand to a bandwidth allocation module;

receiving, from the bandwidth allocation module, bandwidth allocations; and

dividing bandwidth among the network users and jobs based on the received bandwidth allocations and the bandwidth usage information.

15. A system for allocating bandwidth over a network, the system comprising:

means for classifying network users, wherein the classifying includes assigning to each network user one of a plurality of weight values, the assigned weight value for each respective network user being selected according to at least one network criterion;

means for determining bandwidth demand for each network user;

means for allocating bandwidth among each network user, based at least in part on the user weight values and the determined bandwidth demand; and

means for dividing the allocated bandwidth among each network user.

16. The system of claim 15, wherein the means for allocating bandwidth includes:

means for aggregating bandwidth usage information to determine the network'"'"'s total bandwidth demand; and

means for detecting congested links within the network.