A method implemented by a network service provider to provide a virtual network to tenants requiring bandwidth in a cloud computing environment, where the virtual network includes a first set of one or more virtual switches that manage a second set of one or more physical servers that host virtual machines (VMs). The method starts with receiving by one virtual switch a request for a first plurality of VMs, where at least one VM of the first plurality of VMs contains a bandwidth different from bandwidths of the rest of one or more VMs. The it is determined whether to accept the request for the first plurality of VMs by calculating a set of allocation ranges (ARs) associated to the virtual switch, wherein each AR of the set of ARs denotes at least one discontinuous VM allocation space within a virtual switch. Then VMs are allocated for the request.