Enterprises build private clouds to provide IT resources for geographically distributed subsidiaries or product divisions. Public cloud providers like Amazon lease their platforms to enterprise users, thus, enterprises can also rent a number of virtual machines (VMs) from their data centers in the service provider networks. Unfortunately, the network cannot always guarantee stable connectivity for their clients to access the VMs or low-latency transfer among data centers. Usually, both latency and bandwidth are in unstable network environment. Being affected by background traffics, the network status can be volatile. To reduce the latency uncertainty of client accesses, enterprises should consider the network status when they deploy data centers or rent virtual data centers from cloud providers. In this paper, we first develop a data center deployment and assignment scheme for an enterprise to meet its users’ requirements under uncertain network status. To accommodate to the changes of the network status and users’ demands, a VMs migration-based redeployment scheme is adopted. These two schemes work in a joint way, and lay out a framework to help enterprises make better use of private or public clouds.