SHARING BANDWIDTH AMONG MULTIPLE USERS OF NETWORK APPLICATIONS

• US 20120195324A1
• Filed: 02/02/2012
• 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: Raghuraman, Anand, Kumar, Alok, Naik, Uday, Siganporia, Aspi, Jain, Sushant
• Granted Patent: US 9,559,956 B2
• Time in Patent Office: Days
• US Class Current: 370/431
• CPC Class Codes: H04L 47/00 Traffic control in data switching networks arrangements for detecting or preventing errors in the information received H04L1/00
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames

Abstract

A system and method are provided that allocate bandwidth on a global large scale network. Bandwidth allocation is based on the predicted bandwidth demands of the network users. Each user may be assigned one of a plurality of different values that determines the amount of bandwidth allocated to that user. In instances where an application runs on behalf of a plurality of remote clients, a system and method is provided that allows for the allocation of bandwidth based each individual remote client.

Claims

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

receiving, on a network, a request for a shared-service application to run on a host device on behalf of a plurality of remote clients;

receiving an estimation of network traffic associated with running the shared-service application for each remote client;

classifying the plurality of remote clients, based at least in part on the received estimation, as either being in a first classification or a second classification;

transmitting classifications of the plurality of remote clients to the host device; and

allocating bandwidth for the shared-service application, wherein remote clients classified with the first classification are allocated bandwidth individually, and wherein the remote clients classified with the second classification are provided bandwidth as part of a group.

2. The method of claim 1, wherein classifying the plurality of remote clients includes:

determining whether the estimated network traffic for each remote client is below a predetermined threshold;

classifying all remote clients having estimated network traffic that is not below the predetermined threshold with the first classification; and

classifying all remote clients having estimated network traffic that is below the predetermined threshold with the second classification.

3. The method of claim 1, wherein classifying the plurality of remote clients includes:

aggregating the network traffic associated with each of the remote clients to create a network traffic total;

selecting at least some of the plurality of remote clients in an order of descending network traffic;

upon selecting each remote client, aggregating the network traffic for all selected remote clients;

stopping the selection of remote clients when the selected remote clients have an aggregated network traffic that is above a predetermined fraction of the network traffic total;

classifying all selected remote clients with the first classification; and

classifying all remote clients that have not been selected with the second classification.

4. The method of claim 1, wherein allocating bandwidth includes providing bandwidth for each remote client having the first classification based at least in part on one of a plurality of weight values associated with each of the remote clients.

5. The method of claim 1, further comprising:

receiving bandwidth usage information for a plurality of applications running on behalf of a plurality of clients, including the shared-service application running on behalf of the plurality of remote clients;

aggregating bandwidth usage information to determine a total bandwidth demand;

detecting congested links within the network; and

dividing the network'"'"'s available bandwidth between the plurality of applications based, at least in part, on a weight value associated with the remote clients.

6. The method of claim 5, wherein the bandwidth demand information is based on peak bandwidth usage of the plurality of applications over a predetermined time period.

7. The method of claim 5, 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 plurality of clients in proportion to the client'"'"'s weight values.

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

9. The method of claim 5, wherein a subset of the clients receive a permanent allocation of bandwidth.

10. A network device for allocating bandwidth over a network, the device comprising:

a memory; and

a processor coupled to the memory, the processor configured to execute instructions to;

receive a request for a shared-service application to run on a host device on behalf of a plurality of remote clients;

receive an estimation of network traffic associated with running the shared-service application for each remote client;

classify the remote plurality of clients, based at least in part on the received estimation, as either being in a first classification or a second classification

transmit classifications of the plurality of remote clients to the host device; and

allocate bandwidth for the shared-service application, wherein remote clients classified with the first classification are allocated bandwidth individually, and wherein the remote clients classified with the second classification are provided bandwidth as part of a group.

11. The device of claim 10, wherein the processor is further configured to execute instruction to:

determine whether each of the remote client'"'"'s estimated network traffic is below a predetermined threshold;

classify all remote clients having estimated network traffic that is not below the predetermined threshold with the first classification; and

classify all remote clients having estimated network traffic that is below the predetermined threshold with the second classification.

12. The device of claim 10, wherein the processor is further configured to execute instructions to:

aggregate the network traffic associated with each of the remote clients to create a network traffic total;

select at least some of the remote clients in an order of descending network traffic;

upon selecting each remote client, aggregate the network traffic for all selected remote clients;

stop the selection of remote clients when the selected remote clients have an aggregated network traffic that is above a predetermined fraction of the network traffic total;

classify all selected remote clients with the first classification; and

classify all remote clients that have not been selected with the second classification.

13. The device of claim 10 wherein instructions to allocate bandwidth includes providing bandwidth for remote clients having the first classification based, at least in part, on one of a plurality of weight values associated with each of the remote clients.

14. A network device for running an application over a network, the network device comprising:

a memory; and

a processor coupled to the memory, the processor being configured to execute instructions to;

receive a request for a shared-service application to run on behalf of a plurality of remote clients;

estimate the network traffic associated with running the shared-service application for each remote client;

transmit, to a second network device, the estimated network traffic;

receive an indication of whether each remote client is in a first classification or a second classification;

enforce an individual bandwidth policy for each remote client in the first classification; and

enforce a group bandwidth policy for all remote clients in the second classification.

15. The device of claim 14, wherein the instructions to enforce the individual bandwidth policy and the group bandwidth policy include instructions to:

create a separate token bucket for each remote client in the first classification; and

create a single token bucket for all remote clients in the second classification.

16. The device of claim 14, wherein the processor is further configured to execute instructions to transmit, to the second network device, a weight value for each remote client, the weight value being related to a network criterion.

17. The device of claim 16, wherein the individual bandwidth policy for each remote client is based, at least in part, on the weight value of the remote client.

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

receiving, on a network, a request for a shared-service application to run on a host device on behalf of a plurality of remote clients;

classifying at least a subset of the remote clients, the act of classifying including assigning the subset of the remote clients with one of a plurality of weight values, the assigned weight values being in accordance with a predetermined set of network criteria; and

allocating bandwidth for the shared-service application, wherein the subset of remote clients are each allocated bandwidth based on their assigned weight values.

19. The method of claim 18, further comprising:

determining that network bandwidth demand is being met;

determining that unused bandwidth is available on the network; and

dividing the unused bandwidth among the subset of remote clients in proportion to the remote client'"'"'s weight values.

20. The method of claim 18, wherein allocating bandwidth includes permanently allocating a predetermined amount of bandwidth to specific remote clients.