2012 Proceedings IEEE INFOCOM An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks Sheng Zhang',Zhuzhong Qian',Jie Wu,and Sanglu Lu' State Key Lab.for Novel Software Technology,Nanjing University,China Department of Computer and Information Sciences,Temple University,USA zhangsheng @dislab.nju.edu.cn,(qzz,sanglu)@nju.edu.cn,jiewu@temple.edu Abstract-Network virtualization provides a promising way resources are utilized in an efficient and effective manner.As to overcome Internet ossification.A major challenge is virtual this problem is proven to be NP-complete [5],many heuristic network mapping,i.e,how to embed multiple virtual network algorithms [6-15]have been proposed. requests with resource constraints into a substrate network,such that physical resources are utilized in an efficient and effective However,these early algorithms did not take workload manner.Since this problem is known to be NP-complete,a variety fluctuation,e.g.,Auckland Data Trace [16],into consideration. of heuristic algorithms have been proposed.In this paper,we re- Most web-based service providers potentially target users all examine this problem and propose a virtual network mapping over the world,so it is extremely difficult to predict the framework,ORSTA,which is based on Opportunistic Resource workload before they are ready to serve end users.To cope Sharing and Topology-Aware node ranking.Opportunistic re- source sharing is taken into consideration at the entire network with a peak workload on demand,service providers often over- level for the first time and we develop an online approxima- purchase physical resources,which may lead to a considerable tion algorithm,FFA,for solving the corresponding time slot waste of resources for a normal workload.What is more assignment problem.To measure the topology importance of infrastructure providers may lose some upcoming customers a substrate node,a node ranking method,MCRank,based on due to inefficient resource utilization Markov chain is presented.We also devise a simple and practical method to estimate the residual resource of a substrate node/link. In this paper,we re-examine the virtual network mapping Extensive simulation experiments demonstrate that the proposed problem through two novel aspects,Opportunistic Resource framework enables the substrate network to achieve efficient Sharing and Topology-Aware node ranking,and we propose a physical resource utilization and to accept many more virtual novel framework,ORSTA,which provides efficient physical network requests over time. resource utilization and deployment. Index Terms-virtual network mapping;opportunistic re- source sharing;bin packing;topology-aware;markov chain Inspired by opportunistic spectrum access [17],we envision opportunistic resource sharing.Generally speaking,we model the workload in a virtual network as the combination of a I.INTRODUCTION basic sub-workload,which always exists,and a variable sub- The Internet has been extremely successful in optimizing workload,which occurs with some probability.Then,multiple the way we exchange and process information.However,due variable sub-workloads from different virtual networks are to the competing policies and interests of its stakeholders allowed to share some common resources to achieve efficient and the ever-expanding scale of Internet use,the Internet resource utilization,while for a basic sub-workload,we allo- has become resistant to fundamental changes [1,2].Network cate the corresponding,required resources as usual. virtualization has been proposed as a promising approach that Furthermore,topology-awareness is considered due to the claims to overcome the current ossification of the Internet following fact:suppose that there are two substrate nodes with [1-4].In a network virtualization environment,infrastructure the same residual CPU resources,but the residual resources providers (InPs)maintain physical/substrate networks (SNs). on their neighbors vary a lot.It is then reasonable to choose while service providers (SPs)purchase slices of physical the substrate node with more resources in its proximity,so as resources (e.g.,CPU,bandwidth,memory space,disk storage) to heuristically reduce the length of embedded virtual links. from InPs and then create customized virtual networks (VNs)Hence,to facilitate the efficient embedding of virtual networks to offer their own value-added services to end users.This we develop a Markov Chain-based substrate node ranking decoupling of traditional Internet service providers brings a algorithm to measure the "importance"of each substrate node layered service architecture,which provides flexibility and by assigning a numerical value. diversity to everyone. The contributions of this paper are the following.(i)To the One of the fundamental problems in network virtualization best of our knowledge,this is the first attempt that consid- is the virtual network embedding/mapping (VNE)problem, ers virtual network mapping in the context of opportunistic i.e.,how to embed multiple virtual network requests with re- resource sharing at the entire network level.In our previous source constraints into a substrate network,such that physical work [18],we only considered how to share bandwidth among 978-1-4673-0775-8/12/$31.00©20121EEE 2408An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks Sheng Zhang† , Zhuzhong Qian† , Jie Wu‡ , and Sanglu Lu† † State Key Lab. for Novel Software Technology, Nanjing University, China ‡ Department of Computer and Information Sciences, Temple University, USA † zhangsheng@dislab.nju.edu.cn, {qzz,sanglu}@nju.edu.cn, ‡ jiewu@temple.edu Abstract—Network virtualization provides a promising way to overcome Internet ossification. A major challenge is virtual network mapping, i.e., how to embed multiple virtual network requests with resource constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. Since this problem is known to be NP-complete, a variety of heuristic algorithms have been proposed. In this paper, we re￾examine this problem and propose a virtual network mapping framework, ORS T A, which is based on Opportunistic Resource Sharing and Topology-Aware node ranking. Opportunistic re￾source sharing is taken into consideration at the entire network level for the first time and we develop an online approxima￾tion algorithm, FFA, for solving the corresponding time slot assignment problem. To measure the topology importance of a substrate node, a node ranking method, MCRank, based on Markov chain is presented. We also devise a simple and practical method to estimate the residual resource of a substrate node/link. Extensive simulation experiments demonstrate that the proposed framework enables the substrate network to achieve efficient physical resource utilization and to accept many more virtual network requests over time. Index Terms—virtual network mapping; opportunistic re￾source sharing; bin packing; topology-aware; markov chain I. Introduction The Internet has been extremely successful in optimizing the way we exchange and process information. However, due to the competing policies and interests of its stakeholders and the ever-expanding scale of Internet use, the Internet has become resistant to fundamental changes [1, 2]. Network virtualization has been proposed as a promising approach that claims to overcome the current ossification of the Internet [1–4]. In a network virtualization environment, infrastructure providers (InPs) maintain physical/substrate networks (SNs), while service providers (SPs) purchase slices of physical resources (e.g., CPU, bandwidth, memory space, disk storage) from InPs and then create customized virtual networks (VNs) to offer their own value-added services to end users. This decoupling of traditional Internet service providers brings a layered service architecture, which provides flexibility and diversity to everyone. One of the fundamental problems in network virtualization is the virtual network embedding/mapping (VNE) problem, i.e., how to embed multiple virtual network requests with re￾source constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. As this problem is proven to be NP-complete [5], many heuristic algorithms [6–15] have been proposed. However, these early algorithms did not take workload fluctuation, e.g., Auckland Data Trace [16], into consideration. Most web-based service providers potentially target users all over the world, so it is extremely difficult to predict the workload before they are ready to serve end users. To cope with a peak workload on demand, service providers often over￾purchase physical resources, which may lead to a considerable waste of resources for a normal workload. What is more, infrastructure providers may lose some upcoming customers due to inefficient resource utilization. In this paper, we re-examine the virtual network mapping problem through two novel aspects, Opportunistic Resource Sharing and Topology-Aware node ranking, and we propose a novel framework, ORS T A, which provides efficient physical resource utilization and deployment. Inspired by opportunistic spectrum access [17], we envision opportunistic resource sharing. Generally speaking, we model the workload in a virtual network as the combination of a basic sub-workload, which always exists, and a variable sub￾workload, which occurs with some probability. Then, multiple variable sub-workloads from different virtual networks are allowed to share some common resources to achieve efficient resource utilization, while for a basic sub-workload, we allo￾cate the corresponding, required resources as usual. Furthermore, topology-awareness is considered due to the following fact: suppose that there are two substrate nodes with the same residual CPU resources, but the residual resources on their neighbors vary a lot. It is then reasonable to choose the substrate node with more resources in its proximity, so as to heuristically reduce the length of embedded virtual links. Hence, to facilitate the efficient embedding of virtual networks, we develop a Markov Chain-based substrate node ranking algorithm to measure the “importance” of each substrate node by assigning a numerical value. The contributions of this paper are the following. (i) To the best of our knowledge, this is the first attempt that consid￾ers virtual network mapping in the context of opportunistic resource sharing at the entire network level. In our previous work [18], we only considered how to share bandwidth among 2012 Proceedings IEEE INFOCOM 978-1-4673-0775-8/12/$31.00 ©2012 IEEE 2408