822 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3.MARCH 2014 5.5 Rearrangement D2 D3 D4 D6 D7 P-0.1 Due to the dynamics of virtual network requests,the substrate resources may become fragmented,i.e.,some tsz -tss ts4 ts5 tse ts7 ts8.tsN shared time slots are not in full use.In this section,we frame propose to use rearrangement to avoid resource fragmenta- Fig.6.A snapshot of time slot allocation in a substrate link.ts and tss tion and improve resource utilization. are assigned to some basic subrequirements:each of ts2,tss,ts,ts, We start with an illustrating example,shown in Fig.4. and ts is assigned to a set of variable subrequirements,denoted as Di, Fig.4a shows a snapshot of the time slot assignment in a respectively;the other slots are unused. substrate link.Note that only the shared time slots are shown in the figure,since the dedicated time slots are in full use all tsi and tss are assigned to some basic subrequirements;each the time.After some time,the first virtual link along with its of ts2,ts3,ts4,ts6,and ts7 is assigned to a set of variable variable subrequirement leaves,and the fifth virtual link subrequirements,denoted as Di;the other slots are unused. along with its variable subrequirement arrives.According to The residual resource should include the unused slots and the first-fit-based algorithms,we first check whether ts can the residual "room"in the shared slots.We then propose a accommodate a unit of subrequirement from the fifth virtual reasonable method to properly measure the latter. link,and it cannot,since paps =0.12 pth.We then check the For a substrate node or link that has N time slots,where following slots and,finally,reach the assignment shown in N=C(n")if it is a substrate node n',or N B(e)if it is a Fig.4b,where eight slots are used. substrate link e,denote the set of slots that are assigned to However,if we rearrange the time slot assignment when basic subrequirements as So;denote the set of slots that are the first virtual link leaves,we could assign ts and ts2 to assigned to variable subrequirements as S;and denote the the variable subrequirements from the fourth virtual link.In rest as S.For example,in Fig.6,S=(1,5),S={2,3, doing so,slots tss and ts would be assigned to the newly 4,6,7),and S.=(1,2,3.....N)(SUS). arrived virtual link.The final assignment is shown in The residual room rre in the kth slot which belongs to Fig.4c,where we can see that the rearrangement reduces S is defined as a probability that satisfies the following the number of slots used by 2. condition:if we assign tsk to a new variable subrequire- This example motivates us to propose the rearrangement ment,which occurs with this probability,then the collision protocol as follows:On a virtual network request's leave,or at intervals set by an InP,the following operations are probability would be equal to pth.This definition is performed in every substrate node and link:for decreasing j intuitively reasonable,as it indicates the maximum from N to 1,the subrequirements in D;are reassigned by probability of a variable subrequirement that we can using CFF or EFF.The loop ends upon an encounter with a assign tsk to. substrate slot,which is just assigned to a new subrequire- When Dl =1 and D=[h},rrk pth/ph;when Dl> ment by this rearrangement protocol. 1,according to (3),we have In a sense,rearrangement "compresses"the assignment so that it takes up less time slots,which is beneficial to 1-A(De)(1-rrk)-(B(D)(1-rrk)+A(De)rrk)=pth. future VN requests,and improves substrate resources After solving it,we get utilization.It is worth noticing that,after the rearrangement is performed,the residual resources of substrate nodes and Tk三 A(D)+B(D)+pu-1_Pu Pr(De) (4) links change.To capture this change,the residual resource B(Dk B(Dk) estimation should be executed.We can see that the rearrangement incurs some computational overhead;there- Thereby,the residual resource of this substrate link is fore,our protocol allows InPs to achieve a tradeoff between resource utilization and computational overhead by tuning RB(e)=Sul+>minfrrk:1}. (5) kES the trigger intervals. Take ts in Fig.2,for example,Pr({1,3))=0.08, 5.6 Estimating Residual Resource B({1,31)=0.44;thus,the residual room in ts is rr= This section presents how we estimate the residual (ph-Pr({1,3})/B({1,3})≈0.045. resources of each substrate node and link in the context of opportunistic resource sharing. 5.7 Remarks and Summary Residual resources are traditionally defined as follows: In summary,this section starts with the formulation and the RC"(n")=C(n")-vn-fe(n",n")and RB(e")=B(e")- NP-hard result of the microlevel time slot assignment ve f(e",e"),where fe(n",n")denotes the amount of the problem and then provides an ILP-based optimal solution, CPU resources in n"that are allocated to n",and fo(e",e") which is not practical.The similarities between our problem denotes the amount of the bandwidth resources in es that and bin packing further motivate us to propose two first-fit- are allocated to e".Since both CPU and bandwidth are based heuristics,the performances of which are to be expressed in time slots,this section focuses on RB(e); investigated in our extensive simulations.We then design a RC"(n")can be analyzed similarly. simple rearrangement protocol to cope with resource However,when we apply opportunistic resource sharing fragmentation and show how to estimate residual resources to the resource allocation in substrate networks,some of substrate nodes and links.We also provide in Section 1 of substrate time slots are shared among multiple virtual the supplemental material,available online,some intuitive networks;then,it is nontrivial to calculate the amount of insights on how opportunistic resource sharing can lead to a residual resources in a substrate node or link.Fig.6 shows a win-win situation-service providers'costs are lowered, time slot allocation snapshot in a substrate link.We see that while infrastructure providers'revenues increase,as well.5.5 Rearrangement Due to the dynamics of virtual network requests, the substrate resources may become fragmented, i.e., some shared time slots are not in full use. In this section, we propose to use rearrangement to avoid resource fragmenta￾tion and improve resource utilization. We start with an illustrating example, shown in Fig. 4. Fig. 4a shows a snapshot of the time slot assignment in a substrate link. Note that only the shared time slots are shown in the figure, since the dedicated time slots are in full use all the time. After some time, the first virtual link along with its variable subrequirement leaves, and the fifth virtual link along with its variable subrequirement arrives. According to the first-fit-based algorithms, we first check whether ts1 can accommodate a unit of subrequirement from the fifth virtual link, and it cannot, since p3p5 ¼ 0:12 > pth. We then check the following slots and, finally, reach the assignment shown in Fig. 4b, where eight slots are used. However, if we rearrange the time slot assignment when the first virtual link leaves, we could assign ts1 and ts2 to the variable subrequirements from the fourth virtual link. In doing so, slots ts5 and ts6 would be assigned to the newly arrived virtual link. The final assignment is shown in Fig. 4c, where we can see that the rearrangement reduces the number of slots used by 2. This example motivates us to propose the rearrangement protocol as follows: On a virtual network request’s leave, or at intervals set by an InP, the following operations are performed in every substrate node and link: for decreasing j from N to 1, the subrequirements in Dj are reassigned by using CFF or EFF. The loop ends upon an encounter with a substrate slot, which is just assigned to a new subrequire￾ment by this rearrangement protocol. In a sense, rearrangement “compresses” the assignment so that it takes up less time slots, which is beneficial to future VN requests, and improves substrate resources utilization. It is worth noticing that, after the rearrangement is performed, the residual resources of substrate nodes and links change. To capture this change, the residual resource estimation should be executed. We can see that the rearrangement incurs some computational overhead; there￾fore, our protocol allows InPs to achieve a tradeoff between resource utilization and computational overhead by tuning the trigger intervals. 5.6 Estimating Residual Resource This section presents how we estimate the residual resources of each substrate node and link in the context of opportunistic resource sharing. Residual resources are traditionally defined as follows: RCsðnsÞ ¼ CsðnsÞ  P 8nv fcðnv; nsÞ and RBsðesÞ ¼ Bsðes P Þ  8ev fbðev; esÞ, where fcðnv; nsÞ denotes the amount of the CPU resources in ns that are allocated to nv, and fbðev; esÞ denotes the amount of the bandwidth resources in es that are allocated to ev. Since both CPU and bandwidth are expressed in time slots, this section focuses on RBsðesÞ; RCsðnsÞ can be analyzed similarly. However, when we apply opportunistic resource sharing to the resource allocation in substrate networks, some substrate time slots are shared among multiple virtual networks; then, it is nontrivial to calculate the amount of residual resources in a substrate node or link. Fig. 6 shows a time slot allocation snapshot in a substrate link. We see that ts1 and ts5 are assigned to some basic subrequirements; each of ts2, ts3, ts4, ts6, and ts7 is assigned to a set of variable subrequirements, denoted as Di; the other slots are unused. The residual resource should include the unused slots and the residual “room” in the shared slots. We then propose a reasonable method to properly measure the latter. For a substrate node or link that has N time slots, where N ¼ CsðnsÞ if it is a substrate node ns, or N ¼ BsðesÞ if it is a substrate link es, denote the set of slots that are assigned to basic subrequirements as Sb; denote the set of slots that are assigned to variable subrequirements as Sv; and denote the rest as Su. For example, in Fig. 6, Sb ¼ f1; 5g, Sv ¼ f2; 3; 4; 6; 7g, and Su ¼ f1; 2; 3; ... ; NgnðSb [ SvÞ. The residual room rrk in the kth slot which belongs to Sv is defined as a probability that satisfies the following condition: if we assign tsk to a new variable subrequire￾ment, which occurs with this probability, then the collision probability would be equal to pth. This definition is intuitively reasonable, as it indicates the maximum probability of a variable subrequirement that we can assign tsk to. When jDkj ¼ 1 and Dk ¼ fhg, rrk ¼ pth=ph; when jDkj > 1, according to (3), we have 1  AðDkÞð1  rrkÞðBðDkÞð1  rrkÞ þ AðDkÞrrkÞ ¼ pth: After solving it, we get rrk ¼ AðDkÞ þ BðDkÞ þ pth  1 BðDkÞ ¼ pth  P rðDkÞ BðDkÞ : ð4Þ Thereby, the residual resource of this substrate link is RBs ðes Þ¼jSuj þ X k2Sv minfrrk; 1g: ð5Þ Take ts1 in Fig. 2, for example, P rðf1; 3gÞ ¼ 0:08, Bðf1; 3gÞ ¼ 0:44; thus, the residual room in ts1 is rr1 ¼ ðpth  P rðf1; 3gÞÞ=Bðf1; 3gÞ  0:045. 5.7 Remarks and Summary In summary, this section starts with the formulation and the NP-hard result of the microlevel time slot assignment problem and then provides an ILP-based optimal solution, which is not practical. The similarities between our problem and bin packing further motivate us to propose two first-fit￾based heuristics, the performances of which are to be investigated in our extensive simulations. We then design a simple rearrangement protocol to cope with resource fragmentation and show how to estimate residual resources of substrate nodes and links. We also provide in Section 1 of the supplemental material, available online, some intuitive insights on how opportunistic resource sharing can lead to a win-win situation—service providers’ costs are lowered, while infrastructure providers’ revenues increase, as well. 822 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 Fig. 6. A snapshot of time slot allocation in a substrate link. ts1 and ts5 are assigned to some basic subrequirements; each of ts2, ts3, ts4, ts6, and ts7 is assigned to a set of variable subrequirements, denoted as Di, respectively; the other slots are unused