816 EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3,MARCH 2014 Virtual Network Embedding with Opportunistic Resource Sharing Sheng Zhang,Student Member,IEEE,Zhuzhong Qian,Member,IEEE, Jie Wu,Fellow,IEEE,Sanglu Lu,Member,IEEE,and Leah Epstein Abstract-Network virtualization has emerged as a promising approach to overcome the ossification of the Intemet.A major challenge in network virtualization is the so-called virtua/network embedding problem,which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network.A number of heuristics have been proposed to cope with the NP- hardness of this problem;however,all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network.In this paper,we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration,and we present an opportunistic resource sharing-based mapping framework,ORS,where substrate resources are opportunistically shared among multiple virtual networks.We formulate the time slot assignment as an optimization problem;then,we prove the decision version of the problem to be NP-hard in the strong sense.Observing the resemblance between our problem and the bin packing problem,we adopt the core idea of first-fit and propose two practical solutions:first-fit by collision probability(CFF)and first-fit by expectation of indicators'sum (EFF).Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes. Index Terms-Virtual network embedding,opportunistic resource sharing,NP-hard,3-partition,bin packing 1 INTRODUCTION HE Internet has been extremely successful in support- flexible [7].Second,physical resources can be used more L ing global commerce,communication,and defense [1], efficiently,and thus,high energy efficiency can be achieved. [2].However,the multiprovider nature of the Internet and The fundamental challenge that network virtualization end-to-end design of Internet Protocol (IP)are now faces is how to embed multiple virtual networks with creating hurdles for the further evolution of the Internet. resource constraints into a substrate network,so as to Network virtualization has been proposed recently as a efficiently utilize substrate resources.Known as the virtual promising approach to overcome the current ossification network embedding (VNE)problem,it is proven to be NP- of the Internet [2],[3],[4],and it has been investigated in complete by reducing the multiway separator problem to this several projects,including CABO [3],PlanetLab [5],and problem [8];therefore,a number of heuristics [9],[10],[11], VINI [6]. [12],[13l,[14,[15l,[16,[17],[18l,[19]have been proposed. In a network virtualization environment,an infrastructure Unfortunately,all of the prior proposals reserve fixed provider (InP)maintains a physical/substrate network (SN), resources throughout the entire lifetime of a virtual net- which is composed of substrate nodes and links;a service work,which wastes the precious substrate resources.First, provider (SP)leases physical resources (e.g.,CPU,band- SPs potentially target users all over the world,so it is width,and memory space)from InPs and creates custo- extremely difficult to predict the workload before they are mized virtual networks (VNs)to provide value-added ready to serve end users.As the resource requirement of a services (e.g.,video conferencing,VolP,content distribu- VN at a particular time is generally proportional to the tion)for end users.Network virtualization has some workload at that time,to cope with a peak workload on desirable properties.First,the separation of the control demand,service providers often overpurchase substrate and data tiers makes the network core programmable and resources,which may lead to a considerable waste of resources for a normal workload.Second,the resource .S.Zhang,Z.Qian,and S.Lu are with the State Key Laboratory for Novel requirements of many applications experience significant Softiare Technology,Nanjing University,Computer Science Building, changes over time [20].Given these two factors,provision- Xianlin Campus Mailbox 603,163 Xianlin Avenue,Qixia District, Nanjing,Jiangsu 210023,P.R.China. ing fixed resources for virtual networks throughout their E-mail:zhangsheng@dislab.nju.edu.cn,fqzz,sanglul@nju.edu.cn. lifetimes is clearly wasteful. .I.Wu is with the Department of Computer and Information Sciences, In this paper,we exploit this key observation and propose Temple UIniversity,Room 302,Wachman Hall,1805 North Broad Street, a Philadelphia,PA 19122.E-mail:jiewu@temple.edu. novel model that reflects the time-varying resource L.Epstein is with the Department of Mathematics,University of Haifa, requirement of a VN.More specifically,we model the Mount Carmel,Haifa 31905,Israel.E-mail:lea@math.haifa.ac.il. resource requirement of a VN as the combination of a basic Manuscript received 26 Sept.2012;revised 15 Jan.2013;accepted 14 Feb. subrequirement,which exists throughout the lifetime of the 2013;published online 27 Feb.2013. VN,and a variable subrequirement,which occurs with a Recommended for acceptance by X.Tang. For information on obtaining reprints of this article,please send e-mail to: probability.Based on this model,this paper designs an tpds@computer.org,and reference IEEECS Log Number TPDS-2012-09-0992. opportunistic resource sharing-based embedding framework, Digital Object Identifier no.10.1109/TPDS.2013.64. ORS [21],which in general consists of two components,i.e., 1045-9219/14/S31.00C2014IEEE Published by the IEEE Computer SocietyVirtual Network Embedding with Opportunistic Resource Sharing Sheng Zhang, Student Member, IEEE, Zhuzhong Qian, Member, IEEE, Jie Wu, Fellow, IEEE, Sanglu Lu, Member, IEEE, and Leah Epstein Abstract—Network virtualization has emerged as a promising approach to overcome the ossification of the Internet. A major challenge in network virtualization is the so-called virtual network embedding problem, which deals with the efficient embedding of virtual networks with resource constraints into a shared substrate network. A number of heuristics have been proposed to cope with the NP￾hardness of this problem; however, all of the existing proposals reserve fixed resources throughout the entire lifetime of a virtual network. In this paper, we re-examine this problem with the position that time-varying resource requirements of virtual networks should be taken into consideration, and we present an opportunistic resource sharing-based mapping framework, ORS, where substrate resources are opportunistically shared among multiple virtual networks. We formulate the time slot assignment as an optimization problem; then, we prove the decision version of the problem to be NP-hard in the strong sense. Observing the resemblance between our problem and the bin packing problem, we adopt the core idea of first-fit and propose two practical solutions: first-fit by collision probability (CFF) and first-fit by expectation of indicators’ sum (EFF). Simulation results show that ORS provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embedding schemes. Index Terms—Virtual network embedding, opportunistic resource sharing, NP-hard, 3-partition, bin packing Ç 1 INTRODUCTION THE Internet has been extremely successful in support￾ing global commerce, communication, and defense [1], [2]. However, the multiprovider nature of the Internet and end-to-end design of Internet Protocol (IP) are now creating hurdles for the further evolution of the Internet. Network virtualization has been proposed recently as a promising approach to overcome the current ossification of the Internet [2], [3], [4], and it has been investigated in several projects, including CABO [3], PlanetLab [5], and VINI [6]. In a network virtualization environment, an infrastructure provider (InP) maintains a physical/substrate network (SN), which is composed of substrate nodes and links; a service provider (SP) leases physical resources (e.g., CPU, band￾width, and memory space) from InPs and creates custo￾mized virtual networks (VNs) to provide value-added services (e.g., video conferencing, VoIP, content distribu￾tion) for end users. Network virtualization has some desirable properties. First, the separation of the control and data tiers makes the network core programmable and flexible [7]. Second, physical resources can be used more efficiently, and thus, high energy efficiency can be achieved. The fundamental challenge that network virtualization faces is how to embed multiple virtual networks with resource constraints into a substrate network, so as to efficiently utilize substrate resources. Known as the virtual network embedding (VNE) problem, it is proven to be NP￾complete by reducing the multiway separator problem to this problem [8]; therefore, a number of heuristics [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19] have been proposed. Unfortunately, all of the prior proposals reserve fixed resources throughout the entire lifetime of a virtual net￾work, which wastes the precious substrate resources. First, SPs potentially target users all over the world, so it is extremely difficult to predict the workload before they are ready to serve end users. As the resource requirement of a VN at a particular time is generally proportional to the workload at that time, to cope with a peak workload on demand, service providers often overpurchase substrate resources, which may lead to a considerable waste of resources for a normal workload. Second, the resource requirements of many applications experience significant changes over time [20]. Given these two factors, provision￾ing fixed resources for virtual networks throughout their lifetimes is clearly wasteful. In this paper, we exploit this key observation and propose a novel model that reflects the time-varying resource requirement of a VN. More specifically, we model the resource requirement of a VN as the combination of a basic subrequirement, which exists throughout the lifetime of the VN, and a variable subrequirement, which occurs with a probability. Based on this model, this paper designs an opportunistic resource sharing-based embedding framework, ORS [21], which in general consists of two components, i.e., 816 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 . S. Zhang, Z. Qian, and S. Lu are with the State Key Laboratory for Novel Software Technology, Nanjing University, Computer Science Building, Xianlin Campus Mailbox 603, 163 Xianlin Avenue, Qixia District, Nanjing, Jiangsu 210023, P.R. China. E-mail: zhangsheng@dislab.nju.edu.cn, {qzz, sanglu}@nju.edu.cn. . J. Wu is with the Department of Computer and Information Sciences, Temple University, Room 302, Wachman Hall, 1805 North Broad Street, Philadelphia, PA 19122. E-mail: jiewu@temple.edu. . L. Epstein is with the Department of Mathematics, University of Haifa, Mount Carmel, Haifa 31905, Israel. E-mail: lea@math.haifa.ac.il. Manuscript received 26 Sept. 2012; revised 15 Jan. 2013; accepted 14 Feb. 2013; published online 27 Feb. 2013. Recommended for acceptance by X. Tang. For information on obtaining reprints of this article, please send e-mail to: tpds@computer.org, and reference IEEECS Log Number TPDS-2012-09-0992. Digital Object Identifier no. 10.1109/TPDS.2013.64. 1045-9219/14/$31.00 2014 IEEE Published by the IEEE Computer Society