NETWORK BANDWIDTH ALLOCATION IN MULTI-TENANCY CLOUD COMPUTING NETWORKS

A computing device determines an optimal allocation of network bandwidth on a plurality of communications links for a plurality of virtual machines (VMs) in a multi-tenant cloud network based upon a set of bandwidth requirements for the plurality of VMs. The computing device generates a plurality of spanning tree data structures (TDSs). Edges in the TDSs include computed bandwidth values indicating an amount of bandwidth to be reserved over a communications link represented by that edge for the plurality of VMs. The computing device generates a weighted distance value for each TDS of the plurality of TDSs, and selects a 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.