Efficient Virtual Network Embedding With Backtrack Avoidance for Dynamic Wireless Networks

Abstract

We develop an efficient virtual network embedding (VNE) algorithm, termed Bird-VNE, for mobile wireless networks. Bird-VNE is an approximation algorithm that ensures a close to optimal virtual embedding profit and acceptance rate while minimizing the number of virtual network migrations resulting from the mobility of wireless nodes. Bird-VNE employs a constraint satisfaction framework by which we analyze the constraint propagation properties of the VNE problem and design constraint processing algorithms that efficiently narrow the solution space and avoid backtracking as much as possible without compromising the solution quality. Our evaluation results show that the likelihood that Bird-VNE results in backtracking is small, thus demonstrating its effectiveness in reducing the search space. We analytically and empirically verify that Bird-VNE outperforms existing VNE algorithms with respect to computational efficiency, closeness to optimality, and its ability to avoid potential migrations in mobile wireless networks.