Virtual Data Centers (VDCs) are a set of virtual machine (VM) end points connected by a virtual network (VN) topology. While VMs are specified by their capacity along the axes of CPU, memory, and other machine level resources, the VN is characterized by the resources of virtual switches, and the bandwidth and latency of links. Today’s cloud data centers support dynamic requests for VDCs, by using software defined embedding strategies, that allow them to mesh multiple VDCs onto their physical data center(PDC) network and machines. Over a period of time, entries and exits of different VDCs create multiple fragments of PDC resources, which are unusable unless consolidated, resulting in poor acceptance rate of VDCs. However, such a consolidation would necessitate costly live VM and virtual switch migrations. A good strategy should tradeoff the cost of migrations for the acceptance rate of VDC requests. In this paper, we present a solution to this VDC embedding problem that achieves a higher acceptance rate by minimizing fragmentation, compared to existing strategies, while minimizing the migrations of VMs in the existing VDCs. Experimental results show that we can achieve up to 5% higher acceptance to existing solutions while having 6% fewer rate of migrations.