A Graph Theoretic Algorithm for Virtual Network Embedding

A Graph Theoretic Algorithm for Virtual Network Embedding

Isha Pathak (School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi, India) and Deo Prakash Vidyarthi (School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi, India)
DOI: 10.4018/ijbdcn.2014040101
OnDemand PDF Download:
List Price: $37.50
10% Discount:-$3.75


Cloud computing has emerged as an upcoming platform to provide all types of services to the users. Virtualization is a core activity in Cloud that supports multiple services and virtualization at various levels is supported in Cloud. Network virtualization is an important aspect that gives the network illusion to the users that they can access without bothering about the actual physical network. Virtual network embedding is the problem of mapping the virtual nodes and virtual links of the virtual network to actual physical nodes and links with optimization of certain characteristic parameters. The work, in this paper, addresses the virtual network embedding problem to optimize some characteristic parameters such as running time and residual physical network using graph theory approach. The proposed model has been simulated, for its performance study, and result reveals the efficacy of the proposed method.
Article Preview

1. Introduction

Over the years, virtualization has evolved from enabling the sharing of large mainframes to sharing of various applications. At present, virtualization are being used at many levels including operating system, storage, network etc. to improve the system availability, reliability, flexibility, security, and costs. Virtualization aims to provide services in a timely and on demand manner, transparently to the users, by sharing the underlying hardware/software resources. In virtualization, there is no need to own the resources but it can be rented on an on-demand basis from a cloud service providers. Cloud computing is based on virtualization wherein we do not have to install the applications on every computer but can act using virtualization of computer programs through an internet connection.

Network Virtualization (NV) has several motivations that include cost-effective sharing of resources, customizable networking solutions and convergence of existing network infrastructure. Thus, deploying network virtualization provides various benefits that includes de-ossification of the current network architecture, reduced cost of ownership, resource usage optimization, coexistence of multiple virtual networks over a shared physical infrastructure etc. Network Virtualization can be seen as the new standard of the Internet for future research in realizing Future Networks (FNs) (Feamster, Gao & Rxford,2007). Though, it is next to impossible to change the present Internet protocols and thus de-ossifying the present Internet (Turner & Taylor, 2005), virtualization can aid in building these changes in an incremental and a disciplined way while keeping the core almost same. Network virtualization allows multiple Virtual Networks (VNs) to coexist on a single Substrate Network (SN) and use its resources, thus separating the Service providers (SPs) from the Infrastructure providers (IPs) (Chowdhury & Boutaba, 2010). With network virtualization, all hardware and software in the virtual network appear as a single collection of resources. In classical systems different servers are used by different operating systems as depicted in Figure 1.

Figure 1.

Virtual network as a single collection of resources


Efficient Virtual Network Embedding (VNE) algorithms are important in order to effectively use the resources of the substrate network. Virtual Network Embedding problem can be defined as mapping a virtual network with constraints on the nodes and links, on to specific physical nodes and links in the substrate network while keeping its capacity into account. Whenever a virtual network request arrives, it has to be figured out as to whether it can be satisfied by the substrate network’s limited resources. Wider constraints, along with the characteristic parameters to be optimized, make this problem an NP-class. It is important that during the process, substrate network keeps track of the resources being given to the virtual networks. Likewise, virtual networks should also record the resources it has been granted from the substrate network. This problem of mapping virtual networks with numerous constraints has attracted a voluminous interest lately (Papagianni et al., 2013, Fajjari et al., 2011, Chowdhury et al., 2012, Sun et al., 2013,Li et al., 2012 and Li et al.2013). Virtual Network Embedding (VNE) problem can be solved using either a centralized technique, where some central entity collects the information of the resources needed and pass it to the next level or a de-centralized technique in which a protocol is built to discover the resources.

Complete Article List

Search this Journal:
Volume 19: 1 Issue (2023): Forthcoming, Available for Pre-Order
Volume 18: 2 Issues (2022): 1 Released, 1 Forthcoming
Volume 17: 2 Issues (2021)
Volume 16: 2 Issues (2020)
Volume 15: 2 Issues (2019)
Volume 14: 2 Issues (2018)
Volume 13: 2 Issues (2017)
Volume 12: 2 Issues (2016)
Volume 11: 2 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing