This article has been accepted for publication in a future issue of this journal,but has not been fully edited.Content may change prior to final publication.Citation information:DOI 10.1109/TPDS.2015.2425403,IEEE Transactions on Parallel and Distributed Systems IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,VOL.-.NO.-,MONTH YEAR As we mentioned in Section 5.2,we assume that all VMs have the same state switch probabilities.The PM =25 R1=15 threshold p of capacity overflow ratio is set to 0.05.The R3=20 maximum number d of VMs allowed on a single PM is 4.We now present the details of running QUEUE. In the preprocessing phase,we are to generate the array MinN.Taking k =4 for example,according to Equ.(7),we can obtain the transition matrix P: PM =15 R=20 R=15 0.65610.29160.04860.00360.0001 0.36450.48600.1350 0.01400.0005 Normal Workload ☒Qucucing Block P 0.20250.45000.29500.05000.0025 0.11250.35000.3750 0.15000.0125 Fig.8.The final placement of our example using QUEUE, 0.06250.25000.3750 0.25000.0625 where only 2 PMs are needed.We conservatively round the block size up to the maximum spike size of all co- By solving m=TP,we have the stationary distribution: located VMs on a PM,e.g.,on PM H1,the size of each queueing block is max{R,R,R2,Re}=15. π=(0.4823.0.3858.0.1157.0.0154.0.0008) Since To +1<1-p<To +T1+T2,we have K =2, physical resources.Let us take PM H1 in Fig.8 for exam- which is also the value of MinN[4].Similarly,we can ple,by the current design of QUEUE,a total of 30 units find that,MinN[0]=0,MinN[1]MinN[2]=1,and of physical resources need to be reserved for workload MinN[3]=2(see the green circles in Fig.7). spikes;however,instead of considering the four VMs In the clustering phase,these 8 VMs are first clustered (i.e.,V5,V3,Vi,and V6)together,we can partition them into two groups,i.e.,Vi,V2,Va,and Vs are the first group, into two groups and consider each of them separately. and the rest is the second group.In each cluster,we sort For instance,we choose to have V and V3 in the first VMs to be in the descending order of their R's.The group,and have Vi and Ve in the second group.For final order of VMs is Vs,V3,Vi,V2,V,Vi,Ve,and Vs.the former group,since MinN2]=1,we only have to In the third phase of QUEUE,we first try to place reserve one block with a size of max{Re,Re}=15;for Vs on H1.Since R+Re C1,it succeeds and we set the latter group,we also have to reserve one block with 51 1.We then try to place V3 on H1.According to a size of max{R2,Re}=13.In doing so,a total of 28 Equ.(10),we have units of resources are reserved,which is less than that max{R2,max{R2}×MinN[{3H+1]+R+R路<C, in the previous case. We,therefore,have the following intuition:on each so we set z31 =1.We then try to place Vi on Ci,which PM,we can try to partition the co-located VMs into also succeeds and we set z11 =1.Similarly,we then find several groups and consider them separately,so as to that,in the final placement,V5,V3,Vi,and Ve are placed improve QUEUE by reducing the amount of resources on H1,and the rest is placed on H2. reserved for workload spikes. Fig.8 shows the final placement of our example using A key problem in achieving our goal is how to par- QUEUE.Note that,we conservatively round the block tition a set of k VMs into non-overlapped groups,i.e., size up to the maximum spike size of all co-located VMs how to partition an integer k,which is an interesting and on a PM,e.g.,on PM H1,the size of each queueing block important problem in number theory [32].A g-partition is max{R5,R2,RI,Re}=15. of an integer k is a multi-set {1,x2,...,xi,...,}with In contrast,without opportunistic resource sharing in xi>1 for every element zi and 1+x2+...+xg=k the queueing blocks,if resources are provisioned for For example,{1,2,4}and {1,3,3}are two possible 3- peak workload,then 3 PMs are needed to host these partitions of integer 7.Denote by pa(k)the number of 8 VMs,i.e.,V5,V3,and V6 are on H1;Vi,V2,and V4 are different g-partitions of an integer k,and by p(k)the on H2;and the remaining two VMs are on H3. number of all possible partitions of an integer k.For example,p3(7)=4,p(7)=15.According to [33],we 6 COPING WITH HETEROGENOUS SPIKES have the following recursive relations of pa(k): In this section,we present how to improve the consol- Pg(k)=Pg-1(k-1)+Pg(k-g). (11) idation performance of QUEUE through more careful Alg.3 shows the main steps to find the optimal treatment of heterogenous workload spikes. ordered partition.Without loss of generality,we assume Remember that,in the last section,we conservatively that,R,R2,..,R are sorted in descending order of round the block size up to the maximum spike size of their values.The array MinN is computed using Alg.1. all co-located VMs on each PM,as shown in Fig.8.It is Since the number of all possible partitions of an integer k easy to see that,this kind of rounding may waste some is very large(logp(k)=O(vk)[33]),enumerating them 1045-9219(c)2015 IEEE.Personal use is permitted,but republication/redistribution requires IEEE permission.See http://www.ieee.org/publications standards/publications/rights/index.html for more information.1045-9219 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/TPDS.2015.2425403, IEEE Transactions on Parallel and Distributed Systems IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. –, NO. -, MONTH YEAR 8 As we mentioned in Section 5.2, we assume that all VMs have the same state switch probabilities. The threshold ρ of capacity overflow ratio is set to 0.05. The maximum number d of VMs allowed on a single PM is 4. We now present the details of running QUEUE. In the preprocessing phase, we are to generate the array M inN. Taking k = 4 for example, according to Equ. (7), we can obtain the transition matrix P: P =         0.6561 0.2916 0.0486 0.0036 0.0001 0.3645 0.4860 0.1350 0.0140 0.0005 0.2025 0.4500 0.2950 0.0500 0.0025 0.1125 0.3500 0.3750 0.1500 0.0125 0.0625 0.2500 0.3750 0.2500 0.0625         By solving π = πP, we have the stationary distribution: π = (0.4823, 0.3858, 0.1157, 0.0154, 0.0008). Since π0 + π1 < 1 − ρ ≤ π0 + π1 + π2 , we have K = 2, which is also the value of M inN[4]. Similarly, we can find that, M inN[0] = 0, M inN[1] = M inN[2] = 1, and M inN[3] = 2 (see the green circles in Fig. 7). In the clustering phase, these 8 VMs are first clustered into two groups, i.e., V1, V2, V3, and V5 are the first group, and the rest is the second group. In each cluster, we sort VMs to be in the descending order of their Rb ′ s. The final order of VMs is V5, V3, V1, V2, V4, V7, V6, and V8. In the third phase of QUEUE, we first try to place V5 on H1. Since R5 b + R5 e < C1, it succeeds and we set x51 = 1. We then try to place V3 on H1. According to Equ. (10), we have max{R 3 e , max{R 5 e}} × M inN[|{3}| + 1] + R 3 b + R 5 b < C1, so we set x31 = 1. We then try to place V1 on C1, which also succeeds and we set x11 = 1. Similarly, we then find that, in the final placement, V5, V3, V1, and V6 are placed on H1, and the rest is placed on H2. Fig. 8 shows the final placement of our example using QUEUE. Note that, we conservatively round the block size up to the maximum spike size of all co-located VMs on a PM, e.g., on PM H1, the size of each queueing block is max{R5 e , R3 e , R1 e , R6 e} = 15. In contrast, without opportunistic resource sharing in the queueing blocks, if resources are provisioned for peak workload, then 3 PMs are needed to host these 8 VMs, i.e., V5, V3, and V6 are on H1; V1, V2, and V4 are on H2; and the remaining two VMs are on H3. 6 COPING WITH HETEROGENOUS SPIKES In this section, we present how to improve the consol￾idation performance of QUEUE through more careful treatment of heterogenous workload spikes. Remember that, in the last section, we conservatively round the block size up to the maximum spike size of all co-located VMs on each PM, as shown in Fig. 8. It is easy to see that, this kind of rounding may waste some PM H1 R5 b = 25 R1 b = 15 R6 b = 10 R3 b = 20 PM H2 R2 b = 15 R7 b = 15 R8 b = 10 R4 b = 20 Normal Workload Queueing Block 15 15 13 13 Fig. 8. The final placement of our example using QUEUE, where only 2 PMs are needed. We conservatively round the block size up to the maximum spike size of all co￾located VMs on a PM, e.g., on PM H1, the size of each queueing block is max{R5 e , R3 e , R1 e , R6 e} = 15. physical resources. Let us take PM H1 in Fig. 8 for exam￾ple, by the current design of QUEUE, a total of 30 units of physical resources need to be reserved for workload spikes; however, instead of considering the four VMs (i.e., V5, V3, V1, and V6) together, we can partition them into two groups and consider each of them separately. For instance, we choose to have V5 and V3 in the first group, and have V1 and V6 in the second group. For the former group, since M inN[2] = 1, we only have to reserve one block with a size of max{R5 e , R3 e} = 15; for the latter group, we also have to reserve one block with a size of max{R1 e , R6 e} = 13. In doing so, a total of 28 units of resources are reserved, which is less than that in the previous case. We, therefore, have the following intuition: on each PM, we can try to partition the co-located VMs into several groups and consider them separately, so as to improve QUEUE by reducing the amount of resources reserved for workload spikes. A key problem in achieving our goal is how to par￾tition a set of k VMs into non-overlapped groups, i.e., how to partition an integer k, which is an interesting and important problem in number theory [32]. A g-partition of an integer k is a multi-set {x1, x2, . . . , xi , . . . , xg} with xi ≥ 1 for every element xi and x1 + x2 + · · · + xg = k. For example, {1, 2, 4} and {1, 3, 3} are two possible 3- partitions of integer 7. Denote by pg(k) the number of different g-partitions of an integer k, and by p(k) the number of all possible partitions of an integer k. For example, p3(7) = 4, p(7) = 15. According to [33], we have the following recursive relations of pg(k): pg(k) = pg−1(k − 1) + pg(k − g). (11) Alg. 3 shows the main steps to find the optimal ordered partition. Without loss of generality, we assume that, R1 e , R2 e , ..., Rk e are sorted in descending order of their values. The array M inN is computed using Alg. 1. Since the number of all possible partitions of an integer k is very large (log p(k) = O( √ k) [33]), enumerating them