METHOD FOR JOINT SERVICE PLACEMENT AND SERVICE ROUTING IN A DISTRIBUTED CLOUD

1 . A method for distributing an application in a distributed cloud computing system including a plurality of clients with demand and a plurality of data centers, comprising:

determining a plurality of sets of candidate clients from the plurality of clients corresponding to a select plurality of data centers, the plurality of data centers comprising the select plurality of data centers;

determining a cost of providing service and a capacity capability for each of at least a portion of the select plurality of data centers; and

selecting a data center from the select plurality of datacenters to provide service to the plurality of clients based on the determined costs of providing service and the capacity capabilities.

2 . The method of claim 1 , further comprising updating the demand of the plurality of clients based upon the demand satisfied by the selected data center.

3 . The method of claim 2 , further comprising:

determining that the updated demand of a first client is 0;

removing the first client from a set of clients with demand; and

removing the first client from the plurality of sets of candidate clients.

4 . The method of claim 1 , further comprising:

determining that the selected data center initializes a new virtual machine; and

reducing a number of virtual machines available at the selected data center.

5 . The method of claim 4 , further comprising:

determining that the number of virtual machines available at the selected data center is 0; and

removing the selected data center from a set of data centers with available capacity.

6 . The method of claim 5 , further comprising:

determining a list of candidate data centers for each of at least of portion of the plurality of clients; and

removing the selected data center from each set of candidate data centers.

7 . The method of claim 1 , wherein determining a plurality of sets of candidate clients further comprises: calculating the remaining demand for at least one of the candidate clients.

8 . The method of claim 7 , wherein determining a plurality of sets of candidate clients further comprises:

calculating the cost of each of at least a portion of data centers providing capacity to a first candidate client;

selecting the data center with the lowest calculated cost; and

placing the selected data center in a set of candidate data centers for the first candidate client.

9 . The method of claim 1 , wherein determining a cost of providing service and a capacity capability for each of at least a portion of the select plurality of data centers further comprises:

initializing the cost of providing service for each of at least a portion of the select data centers;

determining the demand available at each of at least a portion of the select data centers for a first client; and

calculating the cost of providing service by each of at least a portion of the select data centers based upon the determined available demand at each of at least a portion of the select data centers and a cost of transporting demand between the data centers and the first client.

10 . The method of claim 9 , wherein initializing the cost of providing service for each of at least a portion of the select data centers further comprises:

determining that a first data center has remaining capacity and setting a first capacity to the remaining capacity; and

setting a cost of providing service by the first data center to 0.

11 . The method of claim 9 , wherein initializing the cost of providing service for each of at least a portion of the select data centers further comprises:

determining that a first data center has no remaining capacity and setting a first capacity to a capacity of an additional virtual machine; and

setting a cost of providing service by the first data center to the cost of an additional virtual machine.

12 . The method of claim 9 , wherein determining the demand available at each of at least a portion of the select data centers for a first client further comprises:

initializing a first capacity for a first data center; and

determining the demand available at the first data center as the minimum of the first capacity and remaining demand for the first client.

13 . The method of claim 1 , wherein the plurality of data centers becomes a second plurality of clients with demand and second plurality of data centers that satisfies the demand of the second plurality of clients further comprising:

determining a plurality of sets of candidate second clients from the plurality of second clients corresponding to a select plurality of second data centers, the plurality of second data centers comprising the select plurality of second data centers;

determining a cost of providing service and a capacity capability for each of at least a portion of the select plurality of second data centers; and

selecting a second data center from the select plurality of second datacenters to provide service to the plurality of second clients based on the determined costs of providing service and the capacity capabilities.

14 . A non-transitory program storage device readable by a machine, embodying a program of instructions executable by the machine to perform method steps of claim 1 .

15 . A cloud controller for distributing an application in a distributed cloud computing system including a plurality of clients with demand and a plurality of data centers, the cloud controller comprising:

a data storage;

a processor in communication with the data storage, the processor being configured to:

determine a plurality of sets of candidate clients from the plurality of clients corresponding to a select plurality of data centers, the plurality of data centers comprising the select plurality of data centers;

determine a cost of providing service and a capacity capability for each of at least a portion of the select plurality of data centers; and

select a data center from the select plurality of datacenters to provide service to the plurality of clients based on the determined costs of providing service and the capacity.

16 . The cloud controller of claim 15 , wherein determining a plurality of sets of candidate clients further comprises: calculating the remaining demand for at least one of the candidate clients.

17 . The cloud controller of claim 16 , wherein determining a plurality of sets of candidate clients further comprises:

calculating the cost of at least a portion of each data center providing capacity to a first candidate client;

selecting the data center with the lowest calculated cost; and

placing the selected data center in a set of candidate data centers for the first candidate client.

18 . The cloud controller of claim 15 , wherein determining a cost of providing service and a capacity capability for each of at least a portion of the select plurality of data centers further comprises:

initializing the cost of providing service for each of at least a portion of the select data centers;

determining the demand available at each of at least a portion of the select data centers for a first client; and

calculating the cost of providing service by each of at least a portion of the select data centers based upon the determined available demand at each of at least a portion of the select data centers and a cost of transporting demand between the data centers and the first client.

19 . The cloud controller of claim 18 , wherein initializing the cost of providing service for each of at least a portion of the select data centers further comprises:

determining that a first data center has remaining capacity and setting a first capacity to the remaining capacity; and

setting a cost of providing service by the first data center to 0.

20 . The cloud controller of claim 18 , wherein initializing the cost of providing service for each of at least a portion of the select data centers further comprises:

determining that a first data center has no remaining capacity and setting a first capacity to a capacity of an additional virtual machine; and

setting a cost of providing service by the first data center to the cost of an additional virtual machine.