A Dynamic Resource Provisioning VNE Algorithm Based on Graph Theory

A Dynamic Resource Provisioning VNE Algorithm Based on Graph Theory

Isha Pathak (Jawaharlal Nehru University, India), Deo Prakash Vidyarthi (Jawaharlal Nehru University, India) and Atul Tripathi (Mahatma Gandhi Central University, India)
DOI: 10.4018/978-1-5225-5323-6.ch004


Business has transformed drastically over the years and cloud computing has emerged as an upcoming platform to provide all types of services, especially in the domain of digital business. Virtualization in cloud is a core activity, done at various levels, to support multiple services. Network virtualization is a significant aspect that liberates the users for seamless network access. Virtual network embedding is a process in which the demand of virtual nodes and virtual links are fulfilled by physical/substrate nodes and links while optimizing certain characteristic parameters. This chapter addresses the virtual network embedding problem to optimize parameters such as running time, residual physical network, and embedding cost using graph theory approach. It also minimizes the exhaustion of substrate network resources and still using its resources efficiently. In this chapter, a concept of graph theory has been applied for the virtual network embedding problem. The proposed model has been simulated for its performance study, and results reveal the efficacy of the method.
Chapter Preview


A larger part of the digital business transactions are being done over the cloud now and therefore making cloud computing efficient for such business transactions are the need of the time. Virtualization offers the facility to run multiple operating systems on one physical machine and share all its hardware resources. Cloud Computing takes this aspect of virtualization a step ahead wherein there is no need to own the hardware. The resources are taken on rent from the cloud and are charged as per the usage. Since many years, virtualization has progressed from facilitating the sharing of large mainframes to sharing of various applications. At present, virtualization is being used at many levels including operating system, storage, network etc. to improve the systems’ availability, reliability, flexibility, security, costs etc. Virtualization share the resources (hardware/software) to meet out the service demand of the users in a timely manner. In virtualization, a cloud service provider rent resources as and when demanded and thus these resources not necessarily have to be owned. Cloud computing heavily relies on virtualization wherein one doesn’t need to install the applications on every computer, but these applications can be virtualized and used 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 numerous 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 (Jin et. al., 2017), virtualization can aid in building these changes in an incremental and a disciplined way while retaining the core. It 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). VNs are logically isolated networks lying over a common architecture but providing the same services as a non-virtualized network. The architecture or the network on which these VNs are mapped is called a Substrate Network (SN). 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.


Virtualization Business Roles

This section discusses in detail the major entities and their business roles in the efficient working of network virtualization environment.

Virtual Network

This is the key entity in network virtualization. A virtual network is a set which consists of virtual nodes connected directly by virtual links overlaid on a set of physical resources.

Complete Chapter List

Search this Book: