ZHANG ET AL.:VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 817 the macrolevel node-to-node/link-to-path embedding,and 12 10 (8,4,0.3) (6,4,0.5) the microlevel time slot assignment.In the macrolevel (a (b) embedding,we adopt a traditional greedy strategy (e.g, (3,1.0.2) [13])to derive the mapping results of virtual nodes to (4,2,0.3) 3,1,0.1) 6 (3,3.0.3) substrate nodes and virtual links to substrate paths. d d c In the microlevel time slot assignment,we focus on the 14 7,7,0.2 (6,6,0.4) scenario in a single substrate link.The results can adapt (a)Traditional virtual (b)VN request with time-varying naturally to the other substrate links and nodes (details are network request resource requirement in Section 5).Suppose that the substrate link is based on time-division multiplexing,where time is partitioned into Fig.1.Each node or link is associated with a fixed resource requirement in the traditional VN request,while,in our model,the resource multiple frames of equal length,and each frame is further requirement of each node or link is expressed in a tuple <b,v.p>. divided into time slots of equal length.The number of time slots in a frame depends on the physical bandwidth of this in Section 3.We then provide the overview of ORS in substrate link.Several virtual links are embedded in this Section 4,describe the details of ORS in Section 5,and substrate link;then,the problem becomes how to map the conduct performance evaluations in Section 6.Before bandwidth requirement of virtual links to the physical time concluding the paper in Section 8,we survey related work slots.For the basic bandwidth subrequirement from a in Section 7 virtual link,which exists throughout the lifetime of the respective VN,we have no choice but to allocate the corresponding required slots to it.For the variable 2 VIRTUAL NETWORK REQUEST WITH TIME- bandwidth subrequirement,we propose to opportunisti- VARYING RESOURCE REQUIREMENT cally share time slots among multiple virtual links to In this section,we first present the traditional virtual improve resource utilization.However,collisions accom- network request model,and then,we introduce a model pany sharing.To break the tradeoff between utilization and that captures the time-varying properties of virtual network collision,we use a collision probability threshold to resource requirements. represent the "volume"of a time slot and formulate the time slot assignment as an optimization problem.We prove 2.1 Traditional Virtual Network Request Model the decision-version problem to be NP-hard by reducing The main substrate resources that we consider in this paper the 3-partition problem [22]to it.An integer linear are CPU and bandwidth,which is the typical case in almost programming-based (ILP)optimal solution is also pro-all of the related literature so far.However,our framework vided.Due to the similarities between this problem and the can naturally adapt to the scenario where a node has bin packing problem [23],we then propose two practical multiple types of resources.We will give remarks on the first-fit-based solutions from different perspectives:first-fit adaptation in Section 5 when needed. by collision probability (CFF)and first-fit by expectation of For the purpose of unifying resource notations,we indicators'sum (EFF). assume that the substrate network is based on time-division Through extensive simulations,we demonstrate that,in multiplexing,where time is partitioned into multiple frames the long run,ORS accepts more virtual network requests of equal length,and each frame is further divided into equal and provides a more efficient utilization of substrate time slots.In doing so,both CPU and bandwidth require- resources than two state-of-the-art fixed-resource embed- ments can be expressed in time slots. ding schemes.The contributions are summarized as follows: A traditional virtual network request is denoted by a weighted undirected graph,G=(N,E),where N and 1.To the best of our knowledge,this is the first E"are the sets of virtual nodes and links,respectively.Each attempt that considers virtual network embedding virtual node n"E N"is associated with a CPU requirement in the context of opportunistic resource sharing at C(n")in time slots,and each virtual link e"=(n,n)EE the level of the entire network.To provide efficient is associated with a bandwidth requirement B(e")in time resource utilization,which is of great benefit to both slots.Fig.la shows an example,where the corresponding InPs and SPs,an embedding framework,ORS,is resource requirement of each node or link is written next to designed;its effectiveness is confirmed by extensive the respective node or link that represents it. simulations. 2. We propose a novel model that reflects the time-2.2 The Time-Varying Resource Requirement Model varying properties of the resource requirement of a SPs can hardly predict the number of end users of the VN,based on which we formulate the microlevel applications deployed in their virtual networks;to guaran- time slot assignment problem as an optimization tee the quality-of-service of a peak workload,SPs always problem.We first prove the decision version of overpurchase substrate resources.Besides,the resource this problem to be NP-hard in the strong sense,then requirements of many applications experience significant propose an ILP-based optimal solution and two changes over time.Therefore,provisioning fixed resources practical algorithms. for VNs throughout their lifetimes is clearly wasteful.To We conduct extensive theoretical analysis and avoid such wasteful situations,we need to model the time- simulation studies to verify the performance of ORS. varying resource requirement of a VN in the first place. We now continue by proposing the resource requirement By using profiling experimentations,one can potentially model in Section 2 before we introduce the VNE problem derive some complicated functions,for example,high-orderthe macrolevel node-to-node/link-to-path embedding, and the microlevel time slot assignment. In the macrolevel embedding, we adopt a traditional greedy strategy (e.g., [13]) to derive the mapping results of virtual nodes to substrate nodes and virtual links to substrate paths. In the microlevel time slot assignment, we focus on the scenario in a single substrate link. The results can adapt naturally to the other substrate links and nodes (details are in Section 5). Suppose that the substrate link is based on time-division multiplexing, where time is partitioned into multiple frames of equal length, and each frame is further divided into time slots of equal length. The number of time slots in a frame depends on the physical bandwidth of this substrate link. Several virtual links are embedded in this substrate link; then, the problem becomes how to map the bandwidth requirement of virtual links to the physical time slots. For the basic bandwidth subrequirement from a virtual link, which exists throughout the lifetime of the respective VN, we have no choice but to allocate the corresponding required slots to it. For the variable bandwidth subrequirement, we propose to opportunisti￾cally share time slots among multiple virtual links to improve resource utilization. However, collisions accom￾pany sharing. To break the tradeoff between utilization and collision, we use a collision probability threshold to represent the “volume” of a time slot and formulate the time slot assignment as an optimization problem. We prove the decision-version problem to be NP-hard by reducing the 3-partition problem [22] to it. An integer linear programming-based (ILP) optimal solution is also pro￾vided. Due to the similarities between this problem and the bin packing problem [23], we then propose two practical first-fit-based solutions from different perspectives: first-fit by collision probability (CFF) and first-fit by expectation of indicators’ sum (EFF). Through extensive simulations, we demonstrate that, in the long run, ORS accepts more virtual network requests and provides a more efficient utilization of substrate resources than two state-of-the-art fixed-resource embed￾ding schemes. The contributions are summarized as follows: 1. To the best of our knowledge, this is the first attempt that considers virtual network embedding in the context of opportunistic resource sharing at the level of the entire network. To provide efficient resource utilization, which is of great benefit to both InPs and SPs, an embedding framework, ORS, is designed; its effectiveness is confirmed by extensive simulations. 2. We propose a novel model that reflects the time￾varying properties of the resource requirement of a VN, based on which we formulate the microlevel time slot assignment problem as an optimization problem. We first prove the decision version of this problem to be NP-hard in the strong sense, then propose an ILP-based optimal solution and two practical algorithms. 3. We conduct extensive theoretical analysis and simulation studies to verify the performance of ORS. We now continue by proposing the resource requirement model in Section 2 before we introduce the VNE problem in Section 3. We then provide the overview of ORS in Section 4, describe the details of ORS in Section 5, and conduct performance evaluations in Section 6. Before concluding the paper in Section 8, we survey related work in Section 7. 2 VIRTUAL NETWORK REQUEST WITH TIME￾VARYING RESOURCE REQUIREMENT In this section, we first present the traditional virtual network request model, and then, we introduce a model that captures the time-varying properties of virtual network resource requirements. 2.1 Traditional Virtual Network Request Model The main substrate resources that we consider in this paper are CPU and bandwidth, which is the typical case in almost all of the related literature so far. However, our framework can naturally adapt to the scenario where a node has multiple types of resources. We will give remarks on the adaptation in Section 5 when needed. For the purpose of unifying resource notations, we assume that the substrate network is based on time-division multiplexing, where time is partitioned into multiple frames of equal length, and each frame is further divided into equal time slots. In doing so, both CPU and bandwidth require￾ments can be expressed in time slots. A traditional virtual network request is denoted by a weighted undirected graph, Gv ¼ ðNv; EvÞ, where Nv and Ev are the sets of virtual nodes and links, respectively. Each virtual node nv 2 Nv is associated with a CPU requirement CðnvÞ in time slots, and each virtual link ev ¼ ðnv i ; nv j Þ 2 Ev is associated with a bandwidth requirement BðevÞ in time slots. Fig. 1a shows an example, where the corresponding resource requirement of each node or link is written next to the respective node or link that represents it. 2.2 The Time-Varying Resource Requirement Model SPs can hardly predict the number of end users of the applications deployed in their virtual networks; to guaran￾tee the quality-of-service of a peak workload, SPs always overpurchase substrate resources. Besides, the resource requirements of many applications experience significant changes over time. Therefore, provisioning fixed resources for VNs throughout their lifetimes is clearly wasteful. To avoid such wasteful situations, we need to model the time￾varying resource requirement of a VN in the first place. By using profiling experimentations, one can potentially derive some complicated functions, for example, high-order ZHANG ET AL.: VIRTUAL NETWORK EMBEDDING WITH OPPORTUNISTIC RESOURCE SHARING 817 Fig. 1. Each node or link is associated with a fixed resource requirement in the traditional VN request, while, in our model, the resource requirement of each node or link is expressed in a tuple <b; v; p>