Clouds are being widely used for leasing resources to users in the form of on-demand virtual data centers, which comprise sets of virtual machines interconnected by sets of virtual links. Given a user request for a virtual data center with specific resource requirements, a critical problem is to select a set of servers and links in the physical data center of a cloud to satisfy the request in a manner that minimizes the amount of reserved resources. In this paper, we study the main aspects of this Virtual Data Center Allocation (VDCA) problem, and decompose it into three subproblems: virtual data center clustering, virtual machine allocation, and virtual link allocation. We prove the NP-hardness of VDCA and propose an algorithm that solves the problem by dynamically clustering the requested virtual data center and jointly optimizing virtual machine and virtual link allocation. We further compare the performance and scalability of the proposed algorithm with two existing algorithms, called LoCo and SecondNet, through simulations. We demonstrate that our algorithm generates 30%-200% more revenue than LoCo and 55%-300% than SecondNet, while being up to 12 times faster.