This paper proposed a two-phase network-aware virtual machine allocation algorithm (NWTP). Firstly, based on the randomness (the mixing of tree topology, servers and fiber) of modern data center network topology, the bandwidth requests of virtual machines were divided into two types of inner-bandwidth and outer-bandwidth according to the difference of interactive objects. Secondly, the virtual machine allocation requests were decomposed into two successive phases, and the corresponding network-aware model was established. Thirdly, pipelining technology was developed to regard the bandwidth region partitioning and physical host allocation as two consecutive steps, and to conduct parallel processing. For bandwidth region partitioning phase, the stability of physical host was dynamically perceived by using node betweenness and clustering coefficient, addressing differential allocation strategy to select the appropriate physical host set for the virtual machines subset. For the physical host allocation phase, more virtual machines were allocated to physical host resources with the largest load variance, which saved inner-bandwidth of data center and balanced physical hosts load. Finally, by comparing with the genetic algorithm GA, the annealing algorithm SA and greedy algorithm GR were simulated. Numerical results have shown the performance of NWTP in allocation time, network delay, network throughput rate, CPU utilization, bandwidth utilization and physical host usage.