The virtualization of both servers and substrate networks will enable the future Internet architecture to support a variety of Cloud computing services and architectures, and prevent its ossification. Since multiple virtual networks (VN) or virtual infrastructure (VI) and services now share the resources of the same underlying network in a network virtualization environment, it is important that efficient techniques are developed for the mapping of the VNs onto the substrate network. Furthermore, due to the sharing of resources, the survivable design of VNs is also very important, since now even small failures in the substrate network will cause the disruption of a large number of VNs that may be mapped on to the substrate network. In this work, the author studies the problem of survivable virtual network mapping (SVNM) and first formulates the problem using mixed integer linear programming (MILP). The author then devises two kinds of algorithms for solving the SVNM problem efficiently: (1) Lagrangian relaxation-based algorithms including LR-SVNM-M and LR-SVNM-D and (2) Heuristic algorithms including H-SVNM-D and H-SVNM-M. The author then compares the performance of the algorithms with other VI mapping algorithms under various performance metrics using simulation. The simulation results and analysis show that the algorithms can be used to balance the tradeoff between time efficiency and mapping cost.
TopIntroduction
With the maturity of networking and changes in user needs, demands on computer networks are also changing rapidly. Network-wide virtualization (Anderson, Peterson, Shenker, & Turner, 2005) can help diversify the Internet and fend off Internet ossification by providing a flexible environment for new and emerging large scale distributed applications such as Cloud and Grid computing (Foster, Zhao, Raicu, & Lu, 2008; Baranovski, et al., 2007; Chowdhury & Boutaba, 2010). With virtualization multiple heterogeneous network architectures can share the same underlying substrate network, and several overlay networks with diverse topologies, as well as bandwidth and resilience properties can be created using the same physical substrate network. Thus, allowing multiple customizable (e.g., customized for a set of users, application, etc.) network architectures over a common physical infrastructure.
Cloud computing is a new paradigm built upon server virtualization within each datacenter (Foster, Zhao, Raicu, & Lu, 2008; Baranovski, et al., 2007). Cloud computing is a pay-per-use model for enabling convenient, on-demand access to a shared pool of configurable computing resources that can be rapidly provisioned and released with minimal management effort or service provider interaction (Yang, 2012). The Cloud infrastructure typically includes the network, server, storage, software stacks and applications. With Cloud computing the network becomes the most critical asset, thereby increasing the impact on network operators, who now have to build highly resilient, high-performance delivery architectures that can scale on-demand. Dynamic optical transport networks (Mukherjee, 2006) using wavelength division multiplexing (WDM) with on-demand capacity provisioning become key in supporting the elastic nature of Cloud computing applications. Furthermore, optical networks can also provide the scalability, availability, reliability, flexibility and agility required by Cloud computing services cost-effectively. The generalized multiprotocol label switching (GMPLS) that extends the MPLS framework can be used to provide the management and control of the optical network.
Since each one of these virtual infrastructure (VI) or virtual network (VN) topologies uses the resources of the same underlying substrate network, it is essential to use these resources efficiently. We use the terms virtual infrastructure and virtual network interchangeably throughout this work. Making an efficient use of the substrate resources requires intelligent techniques that map the virtual network on to the substrate network e.g., optical network. In Cloud-based or large networked computing systems hardware and software failures caused by various disruptions such as maintenance, fiber cut, policy change and misconfiguration, are a norm instead of an exception. Due to the shared nature of virtualization, in case of a substrate node/link failure, all the virtual networks using that node/link will be affected. The service providers may incur a penalty due to the breaking of service level agreements (SLAs) with the customers. Thus survivability, i.e., the ability of a network or VNs mapped on to the substrate network to recover from failures is of prime importance.