A virtual data center allocation architecture with bandwidth guarantees that provides for the creation of multiple virtual data centers from a single physical infrastructure. The virtual data center allocation is accomplished in three steps. First, clusters are created from the servers in the physical infrastructure. Second, a bipartite graph is built to map the virtual machines to the servers located in a particular cluster and finally a path is calculated between two virtual machines. The virtual data centers may be dynamically expanded or contracted based on changing bandwidth guarantees.