A method in a computing device for determining an optimal allocation of network bandwidth on a plurality of communications links (130A-130K) for connecting a plurality of virtual machines (VMs) of a tenant in a multi-tenant cloud network based upon a set of bandwidth requirements for the plurality of VMs, the method comprising: generating, by the computing device, a plurality of tree data structures (TDSs), wherein each TDS of the plurality of TDSs includes a plurality of nodes representing both the plurality of VMs and a plurality of network devices that forward traffic in the multi-tenant cloud network, and wherein each TDS of the plurality of TDSs further includes a plurality of edges representing at least some of the plurality of communications links (130A-130K), wherein each edge of the plurality of edges includes a computed bandwidth value indicating an amount of bandwidth to be reserved over the communications link represented by the edge for the plurality of VMs of the tenant, wherein the computed bandwidth value is based upon the set of bandwidth requirements, wherein each TDS of the plurality of TDSs is a spanning tree having a root node, wherein each spanning tree has a different respective node as its root node, and wherein each spanning tree is constructed such that the sum of computed bandwidth values for that spanning tree is minimized; generating, by the computing device, a weighted distance value for each TDS of the plurality of TDSs based upon, numbers of hops in the TDS between the root node and each other node representing a VM, and the computed bandwidth values in the TDS between the root node and each other node representing a VM; and selecting, by the computing device, the TDS of the plurality of TDSs having a smallest weighted distance value as the TDS having computed bandwidth values representing the optimal allocation of network bandwidth. generating, by the computing device, a plurality of tree data structures (TDSs), wherein each TDS of the plurality of TDSs includes a plurality of nodes representing both the plurality of VMs and a plurality of network devices that forward traffic in the multi-tenant cloud network, and wherein each TDS of the plurality of TDSs further includes a plurality of edges representing at least some of the plurality of communications links (130A-130K), wherein each edge of the plurality of edges includes a computed bandwidth value indicating an amount of bandwidth to be reserved over the communications link represented by the edge for the plurality of VMs of the tenant, wherein the computed bandwidth value is based upon the set of bandwidth requirements, wherein each TDS of the plurality of TDSs is a spanning tree having a root node, wherein each spanning tree has a different respective node as its root node, and wherein each spanning tree is constructed such that the sum of computed bandwidth values for that spanning tree is minimized; generating, by the computing device, a weighted distance value for each TDS of the plurality of TDSs based upon, numbers of hops in the TDS between the root node and each other node representing a VM, and the computed bandwidth values in the TDS between the root node and each other node representing a VM; and numbers of hops in the TDS between the root node and each other node representing a VM, and the computed bandwidth values in the TDS between the root node and each other node representing a VM; and selecting, by the computing device, the TDS of the plurality of TDSs having a smallest weighted distance value as the TDS having computed bandwidth values representing the optimal allocation of network bandwidth.