Game theory based reliable virtual network mapping for cloud infrastructure
Yi Zhu, Jiru Xu, Qiong Zhang, Xi Wang, Paparao Palacharla, Tadashi Ikeuchi · 2016
In this paper, we study the reliable virtual network mapping (RVNM) problem for allocating virtual machines (VMs) from multiple data centers (DCs) with the objective of maximizing the total reliability of a virtual network under two capacity constraints: computing capacity constraint at each DC and bandwidth capacity constraint on each link. We first describe graph models of RVNM, formulate the RVNM problem, and prove RVNM is NP-complete. We then formulate the problem as an integer linear programming (ILP) and give results for small-scale cases. A game theory based approach, named Link Mapping First (LMF), is proposed by modeling RVNM to the capacity-constrained potential game and is proved to be convergent to a pure Nash Equilibrium. Numerical results show that LMF achieves high reliability, which is close to the optimal solution, in small-scale cases and outperforms an existing Node Mapping First (NMF) algorithm, especially for large-scale cases.