A cost efficient framework and algorithm for embedding dynamic virtual network requests

Cloud computing is a novel paradigm that enables transparent resource sharing over the Internet. With cloud computing users access applications/services and infrastructure resources using thin clients without knowing the actual location or characteristics of the resources. These applications are typically hosted and run on servers in interconnected data centers. The task or application request from the same or different users can be abstracted as virtual network (VN) requests, which are supported by the same underlying substrate network and thus share its resources. Thus, efficient mapping techniques that intelligently use the substrate network resources are important. Current research only considers the case when the VN requests are static. However, user demands and the corresponding VN requests can change dynamically. In this paper, we address the issue of how to optimally reconfigure and map an existing VN while the VN request changes. We first model this problem as a mathematical optimization problem with the objective of minimizing the reconfiguration cost by using mixed integer linear programming. Since the optimal problem is NP-hard we also propose heuristic algorithms for solving it efficiently. We validate and evaluate our framework and algorithms by conducting extensive simulations on different realistic networks under various scenarios, and by comparing with existing approaches. Our simulation results show that our approach outperforms existing solutions. (c) 2012 Elsevier B.V. All rights reserved.