Offering network performance guarantees in multi-tenant datacenters

1. A method of resource allocation within a datacenter comprising:

receiving a request for resources from a user, the request comprising a number of virtual machines, a user-specified performance characteristic, an oversubscription factor, and a group size;

mapping the request to physical resources within the datacenter to allocate the requested number of virtual machines on physical machines within the datacenter, mapping the request to physical resources within the datacenter to allocate the requested number of virtual machines including mapping the request to allocate a virtual oversubscribed cluster to the user, the virtual oversubscribed cluster including the requested number of virtual machines arranged in groups of the specified size, each group comprising virtual machines connected to a virtual group switch and wherein the virtual oversubscribed cluster further comprises a virtual root switch connected to all of the virtual group switches; and

if the allocation is successful, updating stored data identifying residual capacity on a set of elements within the datacenter as a result of the allocation of virtual machines to the user; and

sending a message to the user accepting the request.

2. A method according to claim 1 , wherein the performance characteristic comprises a bandwidth characteristic on links between virtual machines and wherein the stored data identifying residual capacity comprises stored data identifying residual bandwidth on each link in the datacenter.

3. A method according to claim 1 , wherein mapping the request to physical resources within the datacenter to allocate the requested number of virtual machines comprises mapping the request to allocate a virtual cluster to the user, the virtual cluster comprising the requested number of virtual machines and a virtual switch connecting all of the virtual machines in a one-level tree topology.

4. A method according to claim 1 , wherein mapping the request to physical resources within the datacenter to allocate the requested number of virtual machines comprises:

starting at a first level in a topology tree within the datacenter, determining how many virtual machines can be allocated in each sub-tree in the level;

if a sub-tree in the level can accommodate all the requested virtual machines, allocating the requested number of virtual machines in the sub-tree to the user; and

if none of the sub-trees in the level can accommodate all the requested virtual machines, moving to a next level in the topology tree and repeating the determining step.

5. A method according to claim 4 , wherein the performance characteristic comprises a bandwidth characteristic, B, on links between virtual machines and the set M v of virtual machines m that can be allocated in each sub-tree, v, in a level is defined by:

M v ={mε[ 0,min( k v ,N )] s.t .min( m,N−m )* B≦R l }

where N is the requested number of virtual machines, k v is the number of empty slots in the sub-tree and R l is the residual bandwidth for a link l.

6. A method according to claim 4 , wherein if the request received from the user further comprises an oversubscription factor and a group size, the requested number of virtual machines are divided into groups of virtual machines of a size specified by the group size and the mapping step is performed for each group of virtual machines in turn.

7. A method according to claim 1 , wherein the request further comprises at least one additional user-specified performance characteristic, at least one additional oversubscription factor, or at least one additional group size.

8. A method according to claim 7 , wherein mapping the request to physical resources within the datacenter to allocate the requested number of virtual machines comprises, for each group:

starting at a first level in a topology tree within the datacenter, determining how many virtual machines can be allocated in each sub-tree in the level;

if a sub-tree in the level can accommodate all the virtual machines in the group, allocating those virtual machines in the sub-tree to the user; and

if none of the sub-trees in the level can accommodate all the virtual machines in the group, moving to a next level in the topology tree and repeating the determining step.

9. A method according to claim 8 , wherein the performance characteristic comprises a bandwidth characteristic, B, on links between virtual machines and the set M v,i of virtual machines that can be allocated to each sub-tree, v, for group i in a level is defined by:

M v,i ={g i ε[0,min( k v ,S )] s.t.Σ j=1 i CB r,j,i ( i )≦ R f }

where

CB r,j,l (i)=min(g j *B,(S−g j )*B+min(S*B/O,E))

E=Σ k=1,k≠j i (S−g k )*B+Σ k=i+1 P S*B

and g i is the number of members of group i in the sub-tree, S is the requested number of virtual machines in a group, O is the oversubscription factor, k v is the number of empty slots in the sub-tree and R l is the residual bandwidth for a link l.

10. A system comprising:

a datacenter, the datacenter comprising:

a network manager; and

a plurality of machines connected by switches, each machine comprising at least one slot for allocation of a virtual machine to a tenant,

wherein the network manager is arranged to:

receive a request from a tenant, the request comprising a number of virtual machines requested, a tenant-specified performance characteristic, an oversubscription factor, and a group size,

allocate virtual machines to the tenant to satisfy the performance characteristic based on stored residual capacity data for the datacenter, including mapping the request to allocate a virtual oversubscribed cluster to the user, the virtual oversubscribed cluster including the requested number of virtual machines arranged in groups of the specified size, each group comprising virtual machines connected to a virtual group switch and wherein the virtual oversubscribed cluster further comprises a virtual root switch connected to all of the virtual group switches, and

update the stored residual capacity data as a result of the new allocation.

11. A system according to claim 10 , wherein the network manager comprises a data store arranged to store the residual capacity data, network topology information for the datacenter and a record of available virtual machine slots within the datacenter.

12. A system according to claim 11 , wherein the data store is further arranged to store allocation information corresponding to previously allocated tenant requests and wherein the network manager is arranged to use the allocation information to reallocate virtual machines upon failure or network reconfiguration.

13. A system according to claim 10 , wherein, in use, the datacenter further comprises a plurality of virtual networks, each virtual network corresponding to an allocated request from a tenant and comprising a plurality of virtual machines interconnected by at least one virtual switch.

14. A system according to claim 13 , wherein at least one of the plurality of virtual networks comprises a number of virtual machines specified in the request and a virtual switch connecting to each of the virtual machines in a one-level tree topology.

15. A system according to claim 13 , wherein at least one of the plurality of virtual networks comprises a number of virtual machines specified in the request arranged in groups, each group comprising a number of virtual machines as specified in the request and each virtual machine in a group is connected to a virtual group switch and wherein the virtual group switches are all connected to a virtual root switch.

16. A system according to claim 10 , wherein the network manager is arranged to allocate virtual machines to the tenant to satisfy the performance characteristic by:

starting at a first level in a topology tree within the datacenter, determining a number of virtual machines that can be allocated to each sub-tree in the level subject to the tenant-specified performance characteristic;

if a sub-tree in the level can accommodate all the requested number of virtual machines, allocating the requested number of virtual machines in the sub-tree to the tenant; and

if none of the sub-trees in the level can accommodate all the requested number of virtual machines, moving to a next level in the topology tree and repeating the determining step until a sub-tree is identified that can accommodate all the requested number of virtual machines.

17. A system according to claim 10 , further comprising an enforcement module at each virtual machine, wherein the enforcement module is arranged to limit traffic to and from the virtual machine in accordance with the tenant-specified performance characteristic.

18. A system according to claim 17 , wherein the performance characteristic comprises a bandwidth characteristic and wherein an enforcement module at a virtual machine is arranged to measure traffic rates from the virtual machine to other virtual machines and to perform per-destination-virtual-machine rate limiting to enforce calculated rate limits.

19. A system according to claim 10 , further comprising a tenant device arranged to transmit the request to the datacenter.

20. A method of resource allocation within a datacenter comprising:

receiving a request from a user, the request comprising a requested number of virtual machines and a user-specified bandwidth characteristic;

determining if the request further comprises an oversubscription factor and a group size;

if the request does not comprise an oversubscription factor and a group size, mapping the request to physical resources within the datacenter to allocate the requested number of virtual machines on physical machines within the datacenter by:

starting at a first level in a topology tree within the datacenter,

determining a number of virtual machines that can be allocated in each sub-tree in the level;

if a sub-tree in the level can accommodate all the requested number of virtual machines, allocating the requested number of virtual machines in the sub-tree to the user; and

if none of the sub-trees in the level can accommodate all the requested number of virtual machines, moving to a next level in the topology tree and repeating the determining step;

if the request does comprise an oversubscription factor and a group size, mapping the request to allocate a virtual oversubscribed cluster to the user, the virtual oversubscribed cluster including the requested number of virtual machines arranged in groups of the specified size, each group comprising virtual machines connected to a virtual group switch and wherein the virtual oversubscribed cluster further comprises a virtual root switch connected to all of the virtual group switches;

updating stored data identifying residual bandwidth on each link within the datacenter as a result of the allocation of the requested number virtual machines to the user; and

sending a message to the user accepting the request.