A Virtual Data Center Network Embedding Algorithm With Perturbation

This paper mainly analyses and solves the problem of virtual data center embedding in multi-path networks. The main contribution of this paper lies in that it is the first time to provide a local optimal solution for virtual data center embedding in multi-root networks, and it is the first time to propose a heuristic algorithm for virtual data center embedding in general networks.This paper splits the problem of virtual data center network embedding into two steps, which are virtual machine placement and traffic routing. This paper proposes a general solution, which is called the exhaustive searching algorithm with linear programming, to solve the problem of embedding virtual data center in multi-root substrate networks. The solution applies dual linear programming to deal with the bandwidth constraints and exhaustive searching to provide virtual machine placements. The algorithm provides a local optimal solution by setting the objective functions of the linear programs.To reduce the complexity of the exhaustive searching algorithm with linear programming, this paper then proposes a heuristic algorithm with perturbation. The algorithm places the virtual machines step by step, and each time after refreshing virtual machine placements, a check on network congestions is conducted. A perturbation is triggered if a link with congestion is found. This paper proposes a multi-path routing perturbation algorithm with load balance and a single-path routing perturbation algorithm separately. Then the paper extends the perturbation algorithm from multi-root tree networks to general networks, and applies it to several typical data center networks.Experiment simulations are conducted for the proposed algorithms, which include static simulation and dynamic simulation, as well as substrate networks with different topologies. The simulation results shows that the multi-path routing heuristic algorithm with load balance achieves performances that is close to the local optimal solution, and significantly reduces the time complexity of the exhaustive searching algorithm with linear programming at the same time, thus it provides a good tradeoff between embedding performance and time complexity.