# US 9,519,500 B2 · Offering network performance guarantees in multi-tenant datacenters > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,519,500 B2 - Document ID: US9519500B2 - Status: Granted - Kind: B2 - Application number: 14/177,202 - Filed: 2014-02-10 - Published: 2014-06-05 - Granted: 2016-12-13 - Earliest claimed: 2011-07-06 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Corporation - Inventors: Hitesh Ballani; Paolo Costa; Thomas Karagiannis; Antony Rowstron - Web page: https://patentgrep.com/patent/US9519500B2 ## CPC - G06F 9/45533: {Hypervisors; Virtual machine monitors} - G06F 9/45558: {Hypervisor-specific management and integration aspects} - G06F 9/5077: {Logical partitioning of resources; Management or configuration of virtualized resources (specific details on emulation or internal functioning of virtual machines G06F9/455)} - H04L 67/101: based on network conditions - H04L 67/131: Protocols for games, networked simulations or virtual reality - G06F 2009/45579: {I/O management, e.g. providing access to device drivers or storage} - G06F 2209/501: Performance criteria - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Methods of offering network performance guarantees in multi-tenant datacenters are described. In an embodiment, a request for resources received at a datacenter from a tenant comprises a number of virtual machines and a performance requirement, such as a bandwidth requirement, specified by the tenant. A network manager within the datacenter maps the request onto the datacenter topology and allocates virtual machines within the datacenter based on the available slots for virtual machines within the topology and such that the performance requirement is satisfied. Following allocation, stored residual capacity values for elements within the topology are updated according to the new allocation and this updated stored data is used in mapping subsequent requests onto the datacenter. The allocated virtual machines form part of a virtual network within the datacenter which is allocated in response to the request and two virtual network abstractions are described: virtual clusters and virtual oversubscribed clusters. ## Claims ### Claim 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 and a user-specified performance characteristic; 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: 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; 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; the user-specified performance characteristic comprising a bandwidth characteristic on links between virtual machines, and the set of virtual machines that can be allocated in each sub-tree in a level being determined based on a minimizing calculation involving the requested number of virtual machines, the number of empty slots in the sub-tree, and the residual bandwidth for a link, the minimization ensuring that the user-specified performance characteristic is satisfied. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) A method according to claim 1, wherein the performance characteristic comprises a bandwidth characteristic, B, on links between virtual machines and the set Mv of virtual machines m that can be allocated in each sub-tree, v, in a level is defined by: Mv={mε[0, min(kv,N)] s.t. min(m,N−m)*B≦Rl} where N is the requested number of virtual machines, kv is the number of empty slots in the sub-tree and Rl is the residual bandwidth for a link l. ### Claim 5 (depends on 1) A method according to claim 1, 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. ### Claim 6 (depends on 1) A method according to claim 1, wherein the performance characteristic comprises a bandwidth characteristic, B, on links between virtual machines and the set Mv, i of virtual machines that can be allocated to each sub-tree, v, for a group of virtual machines i in a level is defined by: Mv,i={giε[0, min(kv,S)] s.t. Σj=1iCBr,j,l(i)≦Rl} where CBr,j,l(i)=min(gj*B,(S−gj)*B+min(S*B/O,E)) E=Σk=1,k≠ji(S−gk)*B+Σk=i+1PS*B and gi 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 an oversubscription factor, kv is the number of empty slots in the sub-tree and Rl is the residual bandwidth for a link l. ### Claim 7 (depends on 1) A method according to claim 1 wherein the minimization calculation further comprises minimizing a first function involving the requested number of virtual machines and the number of empty slots in the sub-tree and minimizing a second function involving a number of virtual machines that can be allocated in a sub-tree and the requested number of virtual machines. ### Claim 8 (depends on 7) A method according to claim 7 wherein the minimization calculation further comprises a product of the second function and the bandwidth characteristic on links between virtual machines. ### Claim 9 (depends on 7) A method according to claim 7 wherein the first function is minimized such that a product of the second function and the bandwidth characteristic on links between virtual machines is less than or equal to the residual bandwidth for a link. ### Claim 10 (depends on 1) A method according to claim 1 wherein the request further comprises an oversubscription factor and a group size and the minimization calculation further comprises minimizing a first function such that a result of a summation of a second function is less than or equal to the residual bandwidth for a link. ### Claim 11 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; and wherein the network manager is arranged to receive a request for resources from a user, the request comprising a number of virtual machines and a user-specified performance characteristic; map the request to physical resources within the datacenter to allocate the requested number of virtual machines on physical machines within the datacenter, being arranged to map the request to physical resources within the datacenter to allocate the requested number of virtual machines including: 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; and if the allocation is successful, update 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 send a message to the user accepting the request; the user-specified performance characteristic comprising a bandwidth characteristic on links between virtual machines; and the set of virtual machines that can be allocated in each sub-tree in a level being determined based on a minimizing calculation involving the requested number of virtual machines, the number of empty slots in the sub-tree, and the residual bandwidth for a link, the minimization ensuring that the user-specified performance characteristic is satisfied. ### Claim 12 (depends on 11) A system according to claim 11, 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. ### Claim 13 (depends on 12) A system according to claim 12, 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. ### Claim 14 (depends on 11) A system according to claim 11, 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. ### Claim 15 (depends on 14) A system according to claim 14, 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. ### Claim 16 (depends on 14) A system according to claim 14, 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. ### Claim 17 (depends on 11) A system according to claim 11, 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. ### Claim 18 (depends on 17) 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. ### Claim 19 (depends on 11) A system according to claim 11, further comprising a tenant device arranged to transmit the request to the datacenter. ### Claim 20 One or more tangible computer storage media storing computer readable instructions that when executed cause one or more processors perform actions that implement resource allocation within a datacenter, the actions comprising: receiving a request for resources from a user, the request comprising a number of virtual machines and a user-specified performance characteristic; 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: 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; 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; the user-specified performance characteristic comprising a bandwidth characteristic on links between virtual machines; and the set of virtual machines that can be allocated in each sub-tree in a level being determined based on a minimizing calculation involving the requested number of virtual machines, the number of empty slots in the sub-tree, and the residual bandwidth for a link, the minimization ensuring that the user-specified performance characteristic is satisfied.