10.1016_J.FUTURE.2012.06.005-Modeling-and-performance-analysis-of-large-scale-IaaS-Clouds

Future Generation Computer Systems 29 (2013) 1216–1234 Contents lists available at SciVerse ScienceDirect Future Generation Computer Systems journal homepage: www.elsevier.com/locate/fgcsModeling and performance analysis of large scale IaaS Clouds✩Rahul Ghosh a,∗, Francesco Longo b, Vijay K. Naik c, Kishor S. Trivedi aa Duke University, Durham, NC 27708, USAb Università degli Studi di Messina, 98166 Messina, Italyc IBM T. J. Watson Research Center, Hawthorne, NY 10532, USAarticle info abstractArticle history: For Cloud based services to support enterprise class production workloads, Mainframe like predictableReceived 15 January 2012 performance is essential. However, the scale, complexity, and inherent resource sharing across workloadsReceived in revised form make the Cloud management for predictable performance difficult. As a first step towards designing10 June 2012 Cloud based systems that achieve such performance and realize the service level objectives, we developAccepted 11 June 2012 a scalable stochastic analytic model for performance quantification of Infrastructure-as-a-Service (IaaS)Available online 27 June 2012 Cloud. Specifically, we model a class of IaaS Clouds that offer tiered services by configuring physical machines into three pools with different provisioning delay and power consumption characteristics.Keywords: Performance behaviors in such IaaS Clouds are affected by a large set of parameters, e.g., workload,Analytic model system characteristics and management policies. Thus, traditional analytic models for such systems tendCloud to be intractable. To overcome this difficulty, we propose a multi-level interacting stochastic sub-modelsCTMC approach where the overall model solution is obtained iteratively over individual sub-model solutions. ByFixed-point iteration comparing with a single-level monolithic model, we show that our approach is scalable, tractable, and yetIaaS retains high fidelity. Since the dependencies among the sub-models are resolved via fixed-point iteration,Interacting sub-models we prove the existence of a solution. Results from our analysis show the impact of workload and systemMonolithic model characteristics on two performance measures: mean response delay and job rejection probability.PerformanceProvisioning © 2012 Elsevier B.V. All rights reserved.1. Introduction Cloud depends on a large number of factors including: (i) nature of physical infrastructure (e.g., CPU, RAM, disk characteristics), An Infrastructure-as-a-Service (IaaS) Cloud, such as Amazon (ii) nature of virtual infrastructure (e.g., hypervisor characteristics), (iii) nature of management and automation tools (e.g., request pro-EC2 [1], IBM SmartCloud Enterprise, IBM SmartCloud Enterprise+ visioning steps), (iv) workload (e.g., arrival rate, request types) and (v) available capacity (e.g., number of physical machines). Hence,[2,3], and IBM Smart Business Desktop Cloud [4], delivers on- systematic performance assessment of Cloud infrastructure is dif-demand operating system (OS) instances provisioning computa- ficult and non-trivial.tional resources in the form of virtual machines deployed in theCloud provider’s data center. Such Cloud based services are gaining This paper presents a scalable analytic approach for modelpopularity leading to increasing business competitions and hence, driven performance analysis of an IaaS Cloud. Traditional mea-performance and dependability guarantees are becoming critical. surement based performance evaluation requires extensive exper-Providers of IaaS Clouds (e.g., IBM and Amazon) offer service level imentation with each workload and system configuration and mayagreements (SLA) to Cloud users. Violations of such SLAs can cause not be feasible in terms of cost due to the sheer scale of Cloud.loss of revenue and business reputation. We observe that, for most A simulation model can be developed and solved but in contrastof the IaaS Cloud providers, offered SLAs are in terms of guaranteed with an analytic model, it might be time consuming as the genera-availability. As technology and business models for Cloud services tion of statistically significant results may require many simulationare getting mature, in future, users will also expect SLAs on Cloud runs [5]. A stochastic model is a more attractive alternative becauseperformance besides availability. However, performance of an IaaS of lower relative cost of solving the model while covering large pa- rameter space. However, such stochastic analytic models are pre- ✩ This research was supported in part by IBM Research and the US National sumed not to scale well when dealing with the rising complexityScience Foundation under grant NSF-CNS-08-31325. associated with Cloud service architectures. Simplifying the model to make it more tractable can result in lower fidelity and, in the ∗ Corresponding author. process, the effects of important parameters affecting the service performance metrics may not be captured [6]. To overcome this E-mail addresses: [email protected], [email protected] (R. Ghosh),[email protected] (F. Longo), [email protected] (V.K. Naik), [email protected](K.S. Trivedi).0167-739X/$ – see front matter © 2012 Elsevier B.V. All rights reserved.doi:10.1016/j.future.2012.06.005

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1217difficulty, in our recent research [7], we described a scalable ap- Fig. 1. Request provisioning and servicing steps.proach using interacting stochastic sub-models where an overallsolution is composed by iteration over individual sub-model solu- paper, we assume that the size of the hot, warm, and cold pools aretions. We quantified effects of changes in workload (e.g., job arrival predetermined. We do not focus on the optimal size of the threerate, job service rate) and system capacity (e.g., number of physi- pools. Those issues are left as future research.cal machines, number of virtual machines per physical machine)on service quality as measured by mean response delay and job re- We assume that all PMs in a pool are identical and all requestsjection probability. In this paper, we extend our previous research are homogeneous, where each request is for one VM with fixedin several directions: size CPU cores, RAM and disk capacity. Under this assumption, the maximum number of VMs (denoted by m) that can be deployed on (1) A monolithic Cloud performance model is constructed using a PM, is given by:our variant of stochastic Petri net (SPN) called stochastic rewardnet (SRN) [8]. We compare the scalability and accuracy of the m = min{⌊(Ct /cv )⌋, ⌊(Rt /rv )⌋, ⌊(Dt /dv )⌋} (1)interacting stochastic sub-models approach proposed in [7], w.r.t.the monolithic model. Our analysis shows that the monolithic where, Ct is the total number of cores per PM, Rt is the total amountmodel becomes intractable and fails to produce results as the scaleof Cloud increases, while interacting sub-models approach quickly of RAM per PM, Dt is the total disk capacity per PM, cv is the num-provides model solutions without significantly compromising the ber of cores required per VM, rv is the amount of RAM required peraccuracy. Thus, we provide an analytic verification and validation VM and dv is the disk capacity required per VM. Having a homo-of the proposed approach. geneous environment can bring certain benefits to a Cloud service (2) Closed-form solutions of sub-models are shown whenever provider [11], e.g., information assurance, security response activ-feasible. Such closed-form expressions can complement the useof analytic modeling software packages such as SHARPE [9] and ities, fault management, load balancing, and system maintenance.SPNP [10], when dealing with large number of model states. Through standardization, on-demand and rapid delivery of com- (3) Since dependencies among the sub-models are resolved viafixed-point iteration, in this paper, we prove the existence of a modity computing resources is also facilitated in a homogeneoussolution for the associated fixed-point equation. Cloud [12]. Examples of such homogeneous environments are (4) Numerical results are expanded and discussions are pre-sented on how the proposed model can be extended to include Cloud federations [13], where, each collaborating Cloud providerdifferent Cloud management aspects. Our developed model canbe applied in capacity planning, forecasting, sensitivity analysis to leverages homogeneous Cloud services from other providers.find bottlenecks, what-if analysis or in an overall design optimiza-tion problem during design, development, testing and operational Examples of Clouds with homogeneous requests include MapRe-phases of an IaaS Cloud. duce workloads, which often have repeated queries on similar or The rest of the paper is organized as follows. In Section 2,we present a system description, assumptions, and formulate the identical datasets [14]. For heterogeneous PMs and/or requests, theproblems of interest. Section 3 describes interacting sub-modelsapproach for performance analysis of IaaS Cloud. An equivalent resource provisioning analysis is more complex (see [15], for ex-monolithic model is described in Section 4. Numerical results arepresented in Section 5. Generalizations of the interacting sub- ample). We plan to address that in the future.models approach and future avenues of research are outlined inSection 6. Related research is highlighted in Section 7. Finally, Shown in Fig. 1 is the life-cycle of a request as it moves throughwe conclude this work in Section 8. Appendix A summarizes thesymbols used in the paper and detailed steps of interacting sub- the system. Submitted user requests (i.e., jobs) enter a first-come,model closed form solutions are shown in Appendix B. first-served (FCFS) job queue. The request at the head of the queue2. System description, assumptions, and problem formulation is processed by a Resource Provisioning Decision Engine (RPDE) as In an IaaS Cloud, when a request is processed, a pre-built imageis used to deploy one or more Virtual Machine (VM) instances follows. The request is provisioned on a hot PM if a pre-instantiatedor a pre-deployed VM may be customized and made available tothe requester. VMs are deployed on Physical Machines (PMs) each but unassigned VM exists. If no hot PM is available, a PM from theof which may be shared by multiple VMs. The deployed VMs areprovisioned with request specific CPU, RAM, and disk capacity. This warm pool is used for provisioning the requested VM. If all warmprocess of provisioning and deploying VMs involves delays whichmay be reduced by various optimization techniques. One such PMs are busy, a PM from the cold pool is used. If none of these PMsapproach is to group the PMs into multiple pools characterizedby different degrees of provisioning delays. Maintaining the PMs are available, the request is rejected (service unavailable). Whenin multiple pools also helps to minimize power and cooling costswithout incurring high startup delays for all VMs. In this paper, a running job exits, the capacity used by that VM is released andwe show the analysis for a Cloud, where the PMs are grouped intothree pools: hot (running), warm (turned on, but not ready) and becomes available for provisioning the next job. For the abovecold (turned off). A pre-instantiated VM can be readily provisionedand brought to ready state on a running PM (hot PM) with described scenario, we investigate the effects of varying job arrivalminimum provisioning delay. Instantiating a VM from an imageand deploying it on a warm PM needs additional provisioning time. rates, job service rates and system capacity on two QoS metrics:PMs in the cold pool are turned-off when not in use and deployinga VM on such a PM suffers from additional startup delays. In this (i) mean response delay and (ii) job rejection probability. Problem formulation. We are interested in analyzing the end-to- end performance of the IaaS Cloud as described above. End-to-end Cloud service delivery is composed of three main steps: (i) resource provisioning decision, (ii) VM provisioning and deployment, and (iii) run-time execution. We first translate these individual steps into analytic sub-models which are tractable and yet of high fidelity. We then connect these sub-models into an overall model to compute the Cloud QoS metrics. To compare the scalability and accuracy of the proposed interacting sub-models approach, we construct an SRN based monolithic Cloud performance model. Finally, we solve these models and show how QoS metrics are affected by variations in workload (job arrival rate, job mean service time) and system capacity. We explain our approach systematically in the following sections.

1218 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–12343. Proposed interacting stochastic sub-models approach Our main motivation behind using an interacting sub-models Fig. 2. Resource provisioning decision engine sub-model.approach is the following. A global monolithic model to capture allthe details of a Cloud service tends to be complex. As we will show of π(0,0) . In the second step, we normalize and find the actual steadyin Section 4, even by using methods for the automated generation state probabilities. For 1 ≤ k ≤ (N − 2), steady state probabilitiesof models such as SRNs, such models become intractable and maynot scale to large sized Clouds. Hence, we resort to an interacting can be computed as:sub-models approach to reduce the complexity of analysis withoutsignificantly affecting the accuracy. A final solution of the overall π(k,h) = A(k,h)π(0,0) (2)model is obtained by fixed-point iteration over individual sub- π(k,w) = A(k,w)π(0,0) (3)models. In this paper, we make the simplifying assumption that π(k,c) = A(k,c)π(0,0) (4)all inter-event times are exponentially distributed and thus allour sub-models are homogeneous continuous time Markov chains where,(CTMC). These assumptions can be relaxed as described in [16,17]. A(k,c) = (λ + δh)A(k−1,h)3.1. Resource provisioning decision engine (RPDE) sub-model δhPhXY + δwPwX + δc + δhPhYZA(k−1,c) + δhPhWA(k−1,w) To capture the resource provisioning decision process, we δhPhXY + δwPwX + δcdesign the CTMC shown in Fig. 2. A finite length decision queue + δwPwZA(k−1,c) − λA(k−2,h)is considered where decisions are made on a first-come, first- δhPhXY + δwPwX + δc (5)serve (FCFS) basis. States in the sub-model in Fig. 2 are labeled as (6) A(k,w) = XA(k,c) − ZA(k−1,c)(i, s), where i denotes the number of jobs currently waiting in the A(k,h) = XYA(k,c) − YZA(k−1,c) − WA(k−1,w) (7)queue and s denotes the type of pool where the job is undergoing = YA(k,w) − WA(k−1,w)provisioning decision. When there is no job in the RPDE, i and s A(−1,h) = 1 (8)are set to zero and state (0, 0) captures this condition. s is set λ (9)to ‘h’ when RPDE is deciding if at least one hot PM can accept W=the job for provisioning. Similarly, when s is set to ‘w’ (or ‘c’), δh(1 − Ph)RPDE is deciding if any warm (or cold) PM can accept the job X = λ + δc (10)for provisioning. In Fig. 2, input parameters are: (i) job arrival δw(1 − Pw)rate (λ), (ii) mean searching delays to find a PM in hot/warm/cold Y = λ + δw (11)pool that can be used for resource provisioning (1/δh, 1/δw, and δh(1 − Ph)1/δc respectively), (iii) probabilities that a hot/warm/cold PM canaccept a job for resource provisioning (Ph, Pw, and Pc respectively) λ (12) Z= .and (iv) maximum number of jobs in RPDE (N). Among all the δw(1 − Pw)input parameters, N is assumed to be given, the arrival rate λand the delay parameters δh, δw and δc can be measured while Steady state probabilities for the boundary states at the extremeprobabilities Ph, Pw and Pc are to be computed as outputs from right side of the CTMC in Fig. 2 are given by:the VM provisioning sub-models described later. From state (0, 0),the sub-model transits to state (0, h) with rate λ, due to the π(N−1,h) = λ/δhπ(N−2,h) (13)arrival of a job. In state (0, h), three possible events can occur: = λ/δhA(N−2,h)π(0,0) (14) (15)(a) with probability Ph, job is accepted for provisioning on one of π(N −1,w) = λ/δw π(N−2,w) + δh(1 − Ph) π(N−1,h) δwthe hot PMs, and the sub-model goes back to state (0, 0), (b) with = λ/δwA(N−2,w)π(0,0)probability (1 − Ph), job cannot be accepted for provisioning on δh(1 − Ph) λ/δhA(N−2,h)π(0,0)any hot PM, and the sub-model goes to state (0, w), (c) arrival + δwof a new job with rate λ and the sub-model goes to state (1, h).State (1, h) represents the condition that one job is waiting in the π(N −1,c ) = λ/δc π(N−2,c) + δw(1 − Pw ) π(N −1,w) δcdecision queue and one job is undergoing provisioning decision. In = λ/δc A(N−2,c)π(0,0) + δw(1 − Pw )state (0, w), RPDE tries to make a decision if at least one warm PM δcis available to provision the job (which could not be provisioned on ×  + δh(1 − Ph)  π(0,0) . λ/δw A(N −2,w) δw λ/δh A(N −2,h)any hot PM). With probability (1 − Pw), no warm PM is availableand a transition occurs from state (0, w) to state (0, c). The jobundergoing provisioning decision goes out of the queue, once adecision has been made for the cold pool. With probability Pc , thejob can be accepted in the cold pool and sub-model goes to state(0, 0). With probability (1 − Pc ), all cold PMs are busy, i.e., job isrejected and the sub-model goes to state (0, 0).3.1.1. Closed form solution for RPDE sub-model Let π(i,s) denote the steady state probability for being in state(i, s), where, 0 ≤ i ≤ (N − 1) and s ∈ {0, h, w, c}. Detailed stepsto obtain the closed form solution are given in Appendix B. In thissection, we briefly summarize our approach. From the steady statebalance equations of the CTMC in Fig. 2, a numerical solution canbe obtained in two steps [18]. In the first step, we start with somevalue of π(0,0) and compute all the state probabilities as a function

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1219Table 1Reward rates to compute different output measures from the RPDE sub-model.Measures Reward rates Expected steady state reward ratesJob rejection probability due to buffer full. (Pblock) 1 for states (N − 1, h), (N − 1, w) and (N − 1, c); 0 for other π + π + π(N−1,h) (N −1,w) (N −1,c ) statesJob rejection probability due to insufficient capacity. (Pdrop) δc (1−Pc ) for states (i, c); where, i = 0, 1, . . . , N − 1; 0 for other (N−1)  δc (1−Pc )π(i,c)  λ i=0 λ statesMean number of jobs in the RPDE queue. i for states (i, h), (i, w) and (i, c); where, i = 0, 1, . . . , N − 1; 0 N −1 i(π(i,h) + π(i,w) + π(i,c) ) for other states i=0 Fig. 3. Graphical representation of the mean decision delay for a job. independent hot PM sub-models. Although, note that only one PM3.1.2. Outputs from RPDE sub-model sub-model needs to be solved. States of the sub-model in Fig. 4 areUsing the Markov reward approach, outputs from the RPDE sub- indexed by (i, j, k), where, i denotes number of jobs in the queue,model are obtained by appropriate reward rate assignment to each j denotes number of VMs currently being provisioned, k denotesstate of the CTMC and then computing the expected reward rate the number of VMs which have already been deployed. Inputin the steady state [16,19]. Let r(i,s) be the reward rate assigned to parameters for the hot PM CTMC are: (i) effective job arrival rate tostate (i, s) of the CTMC in Fig. 2. If π(i,s) denotes the steady state each hot PM (λh), (ii) rate at which VM instantiation, provisioning,probability that the sub-model is in state (i, s), the expected steady and configuration occurs (βh), (iii) job service rate (µ), (iv) buffer size of hot PM (Lh) and (v) maximum number of VMs that can be deployed on a PM (m). We assume that the VMs are provisioned serially, one at a time and hence, the value of j is either 0 or 1. This assumption can be relaxed as described in Section 6. Assuming a total of nh PMs in the hot pool, λh is given by: λh = λ(1 − Pblock) . (18)state reward rate is given by  r(i,s) π(i,s) . nh (i,s)(i) Job rejection probability (Preject ). There are two components of Observe that Pblock in Eq. (18) is computed from the RPDE sub-Preject . First, the probability that an incoming job will be rejected model. Among other input parameters βh can be measured, µ candue to RPDE buffer being full is denoted by Pblock. Second, eventhough a job is inserted in the queue, during its provisioning be computed from the run-time sub-model or can be measured, Lh and m are assumed to be given.decision steps, if all (hot, warm and cold) PMs are fully occupied, We briefly describe the state transitions in the sub-model ofthe inserted job will be dropped. Probability that a job will be Fig. 4. From state (0, 0, 0), after a job arrival, sub-model goesrejected due to insufficient PM capacity is denoted by Pdrop. Reward to state (0, 1, 0), with rate λh. In state (0, 1, 0), the job is beingassignments to compute Pblock and Pdrop are shown in Table 1. Jobrejection probability Preject is the sum of Pblock and Pdrop. provisioned for a VM instance. Mean time to provision a VM on(ii) Mean queuing delay (E[Tq_dec ]) for resource provisioning decision. a hot PM is 1/βh and the sub-model moves from state (0, 1, 0) to state (0, 0, 1) with rate βh. Upon service completion, the VMFirst, we compute mean number of jobs in the queue as shown instance is removed and the sub-model moves from state (0, 0, 1) to state (0, 0, 0) with rate µ. When a VM is being provisioned inin Table 1. Then, using Little’s law [16], the mean queuing delay state (0, 1, 0), arrival of a new job with rate λh will take the sub- model to state (1, 1, 0), where the job is waiting in the queue.conditional upon the job not being rejected: Similarly, new jobs can arrive progressively moving the sub-model N −1 to states (i, 1, 0) with 0 ≤ i ≤ Lh. In state (Lh, 1, 0) the buffer is  i(π(i,h) + π(i,w) + π(i,c) ) i=0 full and hence, no new job can arrive. When a VM is in execution[E Tq_dec ] = . (16) λ(1 − Pblock − Pdrop) (e.g., in state (0, 0, 1)), arrival of a new job with rate λh will take the sub-model to state (0, 1, 1), where the new job is being(iii) Mean decision delay (E[Tdecision ]). In our sub-model, decision provisioned. The rest of the sub-model can be described in similardelay is a random variable which follows a Coxian distribution of manner.order 3 (Fig. 3). Mean decision delay conditional upon the job notbeing rejected is given by:[ ]E Tdecision = 1/δh + (1 − Ph)(1/δw + (1 − Pw)/δc ) . (17) 3.2.2. Closed form solution for hot PM sub-model (1 − Pblock − Pdrop) We derive the closed form expressions for the steady state3.2. VM provisioning sub-models probabilities of the hot PM CTMC when Lh → ∞ and m → ∞. VM provisioning sub-models capture the instantiation, configu-ration, and provisioning of a VM on a PM. For each hot, warm, and We model the hot PM as a two-stage tandem network of queuescold PM, we have one CTMC which keeps track of the number ofassigned and running VMs. VM provisioning sub-model of a pool is as shown in Fig. 5. The queuing system consists of two nodes:the union of individual provisioning sub-models of each PM in thatpool. (i) node A has only one server with service rate βh and (ii) node B has infinite servers with service rate of each server being µ. A3.2.1. Hot PM sub-model Fig. 4 shows a VM provisioning sub-model for a PM in the hot server in the node A denotes the provisioning engine within thepool. Conceptually, the overall hot pool is modeled by a set of PM while the servers in the node B denote the running VMs. The service time distribution at both nodes is exponential. The external arrival process to the node A is Poisson with rate λh. Hence, node A is an M/M/1 queue with server utilization ρA = λh/βh. Burke [20] has shown that the output of an M/M/1 queue is also Poisson with the rate being same as the arrival rate. Thus, arrival process to the node B is Poisson with rate λh and the node B is an M/M/∞ queue with mean number of busy servers ρB = λh/µ. For node A, steady

1220 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234Fig. 4. VM provisioning sub-model for each hot PM. λh is the effective job arrival rate to each hot PM, βh is the rate of VM provisioning on hot PM, µ is job service rate, Lh isbuffer size, m is maximum number of VMs on each PM. differences: (i) Effective arrival rate (λw) to each warm PM is: λw = λ(1 − Pblock)(1 − Ph) . (24) nw This is because, jobs arrive to the warm PM pool only if they areFig. 5. Hot PM modeled as a two-stage tandem network of queues. The queuing not provisioned on any of the hot PMs. (ii) When no VM is runningsystem consists of two nodes: (i) node A is a M/M/1 queue, with service rate βh or being provisioned, (state (0, 0, 0) in Fig. 6), warm PM is turnedand (ii) node B is a M/M/∞ queue, with service rate of each server being µ. on but not ready for use. Upon a job arrival in this state, the warmstate probability mass function (pmf) of i jobs (i > 0) waiting in PM requires some additional startup delay to make it ready to use.the queue and j VMs (j ∈ {0, 1}) being provisioned is given by: So, the sub-model goes from state (0, 0, 0) to state (0, 1∗, 0). Time to make a warm PM ready for use, is assumed to be exponentiallypA (i, j) = (1 − ρA )ρ i+j where, ρA < 1. (19) distributed with mean 1/γw. (iii) Mean time to provision a VM on a A warm PM is 1/βw for the first VM to be deployed on this PM; meanFor node B, steady state pmf of k VMs (k > 0) running, is given by: time to provision VMs for subsequent jobs is the same as that for apB (k) = ρk e−ρB . (20) hot PM, i.e., 1/βh. Observe that, when the running job exits in state B (0, 1, 1), the sub-model moves to the state (0, 1∗∗, 0) (instead of state (0, 1∗, 0)). In state (0, 1∗∗, 0), the warm PM is already ready k!Thus, for the hot PM CTMC shown in Fig. 4, when Lh → ∞ and to use (behaving like a hot PM) and hence mean time to provisionm → ∞, the steady state probability of being in state (i, j, k) is a VM in this state is 1/βh. We assume that the length of buffer ongiven by: each warm PM is Lw.φ(h) = (1 − ρA )ρ i+j ρk e−ρB (21) 3.2.5. Outputs from warm PM sub-model (i,j,k) A B After solving the warm PM sub-model, we compute the steady k! state probability (Bw) that a warm PM cannot accept a job for VMwhere, i ≥ 0, j ∈ {0, 1}, k ≥ 0, ρA = λh/βh and ρB = λh/µ.The condition for stability of the system is ρA < 1. Closed form provisioning:solutions for more complex cases can be obtained using matrix Bw = φ(w) + φ(w) + φ(w) (Lw ,1∗,0) (Lw ,1,0) (Lw ,1∗∗,0)analytic methods, which we leave as future research. m−1 +  φ(w) + φ(w) . (25)3.2.3. Outputs from hot PM sub-model (Lw ,1,i) (Lw ,0,m) i=1 A PM cannot accept a job for provisioning if its buffer is full.After solving the hot PM sub-model, we compute the steady The overall warm pool sub-model is a set of nw independent warmstate probability (Bh) that a hot PM cannot accept a job for VM PM sub-models and its output is the probability (Pw) that at leastprovisioning: one PM in a warm pool can accept a job for VM provisioning. This probability is given by: m−1 Pw = 1 − (Bw)nw . (26)Bh =  φ(h) + φ(h) . (22) (Lh ,1,i) (Lh ,0,m) i=0Thus, probability (Ph) that at least one PM in the hot pool can accept 3.2.6. Cold PM sub-modela job for provisioning can be obtained as the output of the hot pool Sub-model for a cold PM is shown in Fig. 7 and a cold poolsub-model, which is given in Eq. (23). Note that, Ph is used as an sub-model is the set of nc independent cold PM sub-models.input parameter in the RPDE sub-model (Fig. 2). Main differences between a warm and a cold PM sub-model are:Ph = 1 − (Bh)nh . (23) (i) effective arrival rates (λw vs. λc ), (ii) rate at which startup is executed (γw vs. γc ), (iii) initial VM provisioning rates (βw vs. βc )3.2.4. Warm PM sub-model and buffer sizes (Lw vs. Lc ). Expression for effective arrival rate (λc ) CTMC for a warm PM is shown in Fig. 6. While a warm PM to each cold PM is:sub-model is similar to the hot PM sub-model, there are a few λc = λ(1 − Pblock)(1 − Ph)(1 − Pw) . (27) nc

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1221 Fig. 6. VM provisioning sub-model for each warm PM. Fig. 7. VM provisioning sub-model for each cold PM.3.2.7. Outputs from cold PM sub-model Mean queuing delay (E[Tq_vm ]). Mean queuing delay for VM provi- Probability (Bc ) that a cold PM cannot accept a job for provi- sioning is given by:sioning, is given by: PhE[Nhot ] (1−Ph)Pw E[Nwarm] m−1 E[Tq_vm ] = λh (1−Bh ) + λw (1−Bw )= φ + φ + φ +  φ + φ .Bc P∗ P∗(c) (c) (c) (c) (c) (28)(Lc ,1∗,0) (Lc ,1,0) (Lc ,1∗∗,0) (Lc ,1,i) (Lc ,0,m) (1−Ph)(1−Pw )Pc E[Ncold] i=1 + λc (1−Bc )Output of the cold pool sub-model is the probability (Pc ) that at P∗ (30)least one PM in a cold pool can accept a job for VM provisioning. where, P∗ = Ph + (1 − Ph)Pw + (1 − Ph)(1 − Pw)Pc and E[Nhot ], E[Nwarm], E[Ncold] are the mean number of jobs in theThis probability is given by:Pc = 1 − (Bc )nc . (29) queue for each hot, warm and cold PM respectively.3.3. Overall outputs for VM provisioning sub-models Conditional mean provisioning delay (E[Tprov ]). For a job, conditional upon being accepted, E[Tprov ] is given by: Apart from Ph, Pw and Pc , we obtain the following output mea- E[Tprov ] = Ph + (1 − Ph)F (31)sures: βh P∗

1222 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234Table 2Quantities necessary to compute conditional mean provisioning delay.Quantity ValueE1 φ((0w,)0,0) Lw −1 (φ((iw,1)∗ ,0) +φ((iw,1),0) +φ((iw,1)∗∗ ,0) +φ((iw,0),m) )+mi=0 φ((0w,)0,i) +jm=−11 Lw −1 φ((iw,1),j) i=0 i=0E2 (1/γw + 1/βw)E3 φ((0c,)0,0) Lc −1 (φ((ic,)1∗ ,0) +φ((ic,)1,0) +φ((ic,)1∗∗ ,0) +φ((ic,)0,m) )+im=0 φ((0c,)0,i) +jm=−11 Lc −1 φ((ic,)1,j) i=0 i=0E4 (1/γc + 1/βc ) Fig. 8. Run-time sub-model for a single job.where, F= Pw  + (1 − E1)  βh E1 E2  + (1 − Pw )Pc  + (1 − E2)  . βh E3 E4Quantities E1, E2, E3, and E4 are reported in Table 2. The meanresponse delay is then given by:E[Tresp ] = [E Tq_dec ] + [ ]E Tdecision + E[Tq_vm ] + E[Tprov ]. (32)3.4. Run-time sub-model Once a job is successfully provisioned, it utilizes the resources Fig. 9. Interactions among the sub-models.until its execution is completed. Run-time sub-model is used to to buffer full (Pblock), rejection probability due to insufficientdetermine the mean time for a job completion. We use a Discrete capacity (Pdrop), and their sum (Preject ) are obtained. Pblock is anTime Markov Chain (DTMC) (Fig. 8) to capture the details of a job input parameter to the three VM provisioning sub-models. Theexecution. From the initial state labeled CPU, a job can finish its mean response delay (E[Tresp ]) is also computed from the overallexecution with a probability p0 or go for some local I/O operations performance model. Two components of mean response delay:with probability (1 − p0 ). A transition can occur from local I/O to mean queuing delay in RPDE (E[Tq_dec ]) and mean decision delayglobal I/O with a probability (1 − p1 ) or from local I/O to CPU with (E[Tdecision ]) are obtained from the RPDE sub-model and the other two components: mean queuing delay in a PM (E[Tq_vm ]) and meanprobability p1 . Assuming the mean service times on the CPU, local provisioning delay (E[Tprov ]) are obtained from VM provisioningI/O and global I/O to be 1/µc , 1/µl and 1/µg , respectively, mean sub-models. Observe, there are dependencies among the sub- models. Pblock computed in the RPDE sub-model is used as anjob service time is given by: input parameter in VM provisioning sub-models. However, to solve the RPDE sub-model, outputs from VM provisioning sub-models1 1 + (1 − p0 ) + (1 − p0 )(1 − p1 ) . (33) (Ph, Pw, Pc ) are needed as input parameters. This cyclic dependency = p0 p1 µlµ p0 µc p0 p1 µg is resolved via fixed-point iteration [23,24] using a variant of the successive substitution method as described later.More general job executions including the sharing of system re-sources, distributed job executions, and other complex interac- 3.6. Fixed-point iterationtions can be modeled by network of queues. Sharing of CPU or I/Odevices can be modeled using a product-form queuing network Algorithm 1 presents the pseudocode for steady state analysis(see Example 9.2 in [16]) whereas, sharing of memory can be mod- using interacting sub-models approach. Input parameters to thiseled as a non-product-form queuing network (see Example 9.16 algorithm are hot, warm, cold, and RPDE sub-models. From steadyin [16]). While the run-time sub-model shown in Fig. 8 is for a sin- state analysis, we obtain: (i) steady state values of fixed-pointgle job type, multiple job types can be modeled using multi-classproduct form networks (see Example 9.14, in [16]). Finally, jobs variables (Pblock, Ph, Pw, and Pc ) and (ii) steady state values ofrunning in the Cloud environments can be monitored and the meanservice time can also be measured directly from the data collected performance measures. It can be shown that fixed-point variablesfrom the Cloud [2,21] without using the run-time sub-model. Ph, Pw, and Pc can be expressed as a function of Pblock. For this3.5. Interactions among sub-models reason, before starting the fixed-point iteration, we guess an initial All sub-models and the interactions among them are shown value for Pblock (e.g., 0 in step 4 in Algorithm 1) and we check theas an import graph [22] in Fig. 9. The run-time sub-model yields values of Pblock in successive iterations to determine the condition for convergence in fixed-point iteration (step 12 in Algorithm 1).the mean service time (1/µ) that is needed as an input parameter Fixed point iteration starts by calling the function hot(·) to obtainto each type (hot, warm, or cold) of the VM provisioning sub- the steady solution of the hot sub-model. Output of hot(·) is themodel. VM provisioning sub-models compute the steady state steady state probability (Ph) that the job can be accepted in hotprobabilities (Ph, Pw, and Pc ) that at least one PM in a pool (hot, pool. Function warm(·) uses this updated Ph as an input parameterwarm, and cold, respectively) can accept a job for provisioning.These probabilities are used as input parameters to the RPDE and solves the warm sub-model for steady state solution. Outputsub-model. From the RPDE sub-model, rejection probability due

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1223of warm(·) is the steady state probability (Pw) that the job can be 4. Monolithic model for IaaS cloudaccepted in warm pool. Function cold(·) uses updated values of Ph We use SRN to construct a monolithic model for IaaS Cloud.and Pw to solve cold sub-model for steady state solution. Output of SRNs [26] are extensions of GSPNs [27]. Key features of SRNs are:cold(·) is steady state probability (Pc ) that the job can be acceptedin cold pool. Function rpde(·) uses updated values of Ph, Pw and Pc (1) each transition may have a guard function; the transition isto solve the RPDE sub-model for a steady state solution. Output of enabled in a marking only if its guard function evaluates to true;rpde(·) is Pblock. Finally, the value of Pblock is updated for the next (2) marking dependent arc multiplicities are allowed; (3) mark-iteration. Observe, in step 11 in Algorithm 1, we use the bisection ing dependent firing rates are allowed; (4) transitions can be as-method for successive substitution of fixed-point variable Pblock. signed different priorities; (5) besides traditional output measuresAlgorithm 1 Fixed point iteration algorithm for steady statesolution obtained from a GSPN, such as throughput of a transition and meanInput: hot, warm, cold, and RPDE sub-models. number of tokens in a place, more complex measures can be com-Output: steady state values of fixed-point variables (Pblock, Ph, Pw , and Pc ) and puted by associating reward rates to net markings. steady state values of performance measures. An SRN monolithic model for request provisioning in an IaaS 1: declare Ph, Pw , Pc , Pblock: probability; Cloud is shown in Fig. 10. Transition Tarr with rate λ models the job 2: declare Pb′lock: probability; arrivals while tokens in place Pd(h) represent job requests waiting 3: declare ϵf : upper bound on error; to be served by the RPDE. 4: Pblock ← 0; Tokens in places Pv(mhi) (with 1 ≤ i ≤ nh) represent the number 5: do: of VMs that can still be provisioned in the ith hot PM. When the 6: Pb′lock ← Pblock; ith hot PM is not running any job, m tokens will be present in 7: Ph ← hot(Pblock); Pv(mhi) place. Tokens in places Pb(uhfi) represent the number of jobs 8: Pw ← warm(Pblock, Ph); that can still be accepted for provisioning on the ith PM. A job 9: Pc ← cold(Pblock, Ph, Pw );10: Pblock ← rpde(Ph, Pw , Pc ); accepted in the hot pool is provisioned on a randomly selected11: Pblock ← min(Pblock, Pb′lock) + |Pb′lock − Pblock|/2;12: while |Pblock − Pb′lock| < ϵf hot PM which is not full. This is modeled by the conflict among transitions Td(hi) that also model the searching delay to find a hot13: repeat steps 6 to 11 to compute final values of Ph,Pw ,Pc , and Pblock; PM for resource provisioning. Each of such transitions takes a token from the corresponding place Pb(uhfi) and inserts a token in the14: output Ph, Pw , Pc , and Pblock; corresponding place Pi(nhsit) modeling the PM provisioning queue.15: output the values of performance measures at steady state; VM provisioning delay on a hot PM is modeled by transitionsProof of existence of a solution. Fixed point iteration variables are Ti(nhsit) (with rate βh). Places Ps(ehriv) and transitions Ts(ehriv) representreported in the import graph depicted in Fig. 9. Our fixed pointequation is given by: servicing of jobs. Rates of transitions Ts(ehriv) depend on the number of tokens in places Ps(ehriv) to model the concurrent job executionsx = G(x) (34) within the same PM. This is represented by the ‘#’ sign next to thewhere x = (Pblock, Ph, Pw, Pc ). transitions. If no token is present in place Pb(uhfi) (buffer of ith PM in the hot pool is full) or if one token is present in place Pb(uhfi) but We show the proof of existence of a solution for the Eq. (34). no token is present in place Pv(mhi) (the PM is full), then the PM isFirst, we simplify the fixed point equation considering only fewvariables. As described earlier, the fixed point equation (34) can not able to accept any further request ([gTd(hi)] = 0 if #Pb(uhfi) = 1be rewritten as: and #Pv(mhi) = 0). If this happens for all the PMs in the hot pool, transition Tn(h) is enabled ([gTn(h)] = 1 if ∀i : 1 ≤ i ≤ nh #Pb(uhfi) = 0y = F (y) (35) or (#Pb(uhfi) = 1 and #Pv(mhi) = 0)). This models the necessity for thewhere y = Pblock. RPDE to start looking for a free PM in the warm pool by moving a token from place Pd(h) to place Pd(w). Proof of existence of a solution to Eq. (35) implies the exis- We assume that the RPDE can process only one request at atence of a solution to Eq. (34). We use Brouwer’s fixed point theo- time and this is represented by the inhibitor arc from place Pd(w) to transitions Td(hi) and Tn(h). The modeling of the nw PMs in the warmrem [25]: pool is similar to that of PMs in the hot pool. However, when there Let F : C ⊂ R2 → R2 be continuous on the compact, convex set is no job being executed or provisioned on a warm PM, the firstC, and suppose that F(C) ⊆ C. Then, F has a fixed point in C. request to the warm PM requires an additional startup delay. For In our case, F is scalar. Given that Pblock is a probability, we can this reason, two additional immediate transitions are present fordefine C = {y = Pblock : Pblock ∈ [0, 1]}. Set C is compact sincePblock belongs to the closed interval [0, 1] and, according to the each warm PM, ty′(wj) and ′′ (wj ) (with 1 ≤ j ≤ nw ), with properHeine–Borel theorem, if a subset of the Euclidean space Rn is closed tyand bounded then it is also compact. The set C is convex if, giventwo elements x ∈ C and y ∈ C, the element tx + (1 − t)y, with guards. Transitions ′′ (wj ) will be enabled only if the number oft ∈ [0, 1] belongs to C. Since, Pblock is a probability, convexity ofset C is trivial in our case. The function F is continuous over C if, tyfor each point y′ ∈ C, limy→y′ f (y) = f (y′). From the definition ofC, we observe that C is a singleton set of only element y = Pblock. tokens in the corresponding places Pv(mwj) is equal to m, i.e., onlyHence, the limit converges to its (finite) value at y′. Therefore, F is ′′ for the first request to the PM (wj ) ] = 1 if #Pv(mwj) = m). Incontinuous over C. This proves the existence of a solution for the ([gtyfixed point equation y = F (y). this way, we model the additional delay by means of places Ps(twupj) and transitions Ts(twupj) (with rate γw). On the other hand, transitions ty′(wj) will be enabled only if the number of tokens in places Pv(mwj) is strictly less than m, i.e., for every subsequent request after the first one ([gty′(wj)] = 1 if #Pvm(wj) < m).

1224 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 Fig. 10. SRN model for IaaS Cloud. When PMs in the warm pool are all busy, transition Tn(w) is transitions Td(hi) and Tn(h) modeling the RPDE processing only on a request at a time. The modeling of the cold pool is equivalent toenabled modeling the RPDE trying to provision the request in the that of the warm pool. The main difference with the warm poolcold pool ([gTn(w)] = 1 if ∀i : 1 ≤ j ≤ nw #Pb(uwfj) = 0 or (#Pb(uwfj) = 1and #Pv(mwj) = 0)). Also in this case, a token in place Pd(c) disables is that when all PMs are busy in the cold pool, transition Tdrop will fire modeling the rejection of a request due to insufficient PM

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1225 Fig. 11. (a) Job rejection probability vs. mean job service time and (b) mean response delay vs. mean job service time at different number of PMs.Table 3 in each pool. Large Clouds have more than 500 PMs in each pool.Reward rates to compute different output measures from the SRN model. (2) Maximum number of VMs on each PM. We assume that maximum of 1, 2, 4, 8, 16, 32 and 64 VMs can be deployed on eachMeasures Reward rates PM. (3) Job arrival rate (λ). We categorize arrival rates in threeJob rejection probability due to buffer full 1 if [gTarr ] = 0; 0 o/w(Pblock ) δc /λ if Tdrop is enabled; 0 o/w regions: (i) low (10–500 jobs/h), (ii) medium (500–1500 jobs/h)Job rejection probability due to insufficient #Pd(h) + #Pd(w) + #Pd(c) and (iii) high (more than 1500 jobs/h). (4) Mean job service timecapacity (Pdrop ) (1/µ). In our analysis, we assume three ranges for mean serviceMean number of jobs in RPDE (E[NRPDE ]) times: (i) low (less than 5 h), (ii) medium (5–30 h) and (iii) highcapacity ([gTdrop] = 1 if ∀i : 1 ≤ k ≤ nc #Pb(uckf) = 0 or (#Pb(uckf) = (more than 30 h). (5) Buffer size. Buffer size in front of RPDE is in1 and #Pv(mck) = 0)). the range of 0–1000. For each PM, buffer size is varied between 0 In our model N is the maximum number of requests that can and 20. (6) Mean delay to search a PM in a pool (1/δh, 1/δw, 1/δc ).be present in RPDE. By associating a guard function ([gTarr ] = For our current analysis, we assume that the searching delay is1 if #Pd(h) + #Pd(w) + #Pd(c) < N) to transition Tarr we model the independent of number or PMs or type (hot, warm, cold) of pool and varies between 1 and 5 s. However, in the future, we willfinite length FCFS queue of the RPDE. consider different search algorithms and analyze their average running times to estimate the values of these parameters. (7) Mean Outputs from monolithic model. Model outputs are obtained time to provision VM on a hot (1/βh), warm(1/βw), and cold (1/βc )by assigning an appropriate reward rate to each marking of the PM. For hot PMs, the value of 1/βh is in the range of 1–10 min. Values of 1/βw and 1/βc are assumed to be in the range of 2–20 minSRN and then computing the expected reward rate in steady and 5–30 min respectively. (8) Mean time to prepare a warm (1/γw), and cold (1/γc ) PM ready for use. Value of 1/γw is assumed in thestate [16]. Our measures of interest are the following. (i) Job range of 20 s to 2 min. Value of 1/γc is assumed in the rangerejection probability (Preject ). As already specified, there are two of 5–10 min. Though we evaluate our models under such a widecomponents of Preject : Pblock and Pdrop , related to rejection of jobs variation of parameters, we present only the interesting results.when the RPDE buffer is full and when all (hot, warm and cold) Effect of variation in mean job service time. Fig. 11(a) shows, atPMs are busy, respectively. (ii) Mean number of jobs in the RPDE a fixed arrival rate (1000 jobs/h) and fixed number of PMs in each pool (e.g., 80 PMs in each pool), job rejection probability(E[NRPDE ]). It is given by the sum of the number of jobs that are increases with longer mean service time. At a given mean service time, if we increase the PM capacity in each pool, job rejectionwaiting in the RPDE queue and the job that is currently undergoing probability reduces. Fig. 11(b) shows with increasing mean service time, mean response delay increases for a fixed number of PMs inprovisioning decision. Observe, E[NRPDE ] is a measure of mean each pool. We define marginal gain as the amount of reduction in job rejection probability or mean response delay with increasingresponse delay. Reward assignments for these measures is shown PM capacity, when all other input parameter values are kept unchanged. Observe that the marginal gains in Fig. 11(b), changein Table 3. with increasing mean service time, for gradual increase in capacity from 70 to 100 PMs in each pool. In the example scenario5. Numerical results and discussions investigated, marginal gain is maximum when the mean service time is in the medium range (around 1000 min). This can be We exercise the interacting sub-models described earlier to explained in the following way. For a fixed number of PMs, meancompute two QoS metrics: (1) job rejection probability and (2) response delay has three components: (i) mean queuing delay inmean response delay. Using SHARPE [9], we solve the models and front of RPDE, (ii) mean decision delay and (iii) conditional meanshow the effects of changing job arrival rates, mean job service provisioning delay. With increasing mean service time, dependingtimes, and system capacity (number of PMs in each pool, numberof VMs on each PM) on QoS measures.Values of key parameters. We assume a wide range of values forour model parameters so that the model can represent a largevariety of IaaS Cloud services. (1) Number of PMs in each pool. Small,medium and large sized Clouds are assumed. Small Clouds haveless than 50 PMs in each pool. Medium Clouds have 50–500 PMs

1226 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 Fig. 12. (a) Components of rejection probability vs. mean service time and (b) component of mean response delay vs. mean service time.upon which component of the delay is more dominant, marginal Table 4gain varies. When the mean service time is low (100–300 min), Comparison of model states. m.o. means memory overflow.gain due to addition of more PM is almost insignificant. Thisis because, jobs quickly leave the Cloud, making room for new (#PMs per pool, #VMs per PM) Monolithic model Interactingrequests and hence, a small number of PMs is sufficient to keep the sub-modelsoverall mean response delay low. As the mean service time of jobsincreases (say 1000 min), for low capacity systems (e.g., 70 PMs in (1, 1) 912 27each pool for our example), mean queuing delay in front of RPDE (1, 2) 4,655 35starts increasing. So, the benefit of adding more PMs is reflected (1, 4) 20,691 47by having lower mean queuing delay in front of RPDE. When the (1, 8) 116,603 71mean service time is further increased to 1800 min, mean queuing (1, 16) 768,075 119delay in front of RPDE increases even for larger capacity systems (1, 32) 5,543,915 215(e.g., 100 PMs in each pool for our example). Hence, the marginal (1, 38) 9,848,061 251gain diminishes once again. This result shows in overall mean (1, 39) m.o. 257response delay, how the bottleneck component (mean queuing (2, 1) 43,776 27delay in this case) shifts as the job characteristics (mean service (3, 1) 2,101,248 27time in this example) and Cloud capacity (PMs in each pool) are (4, 1) m.o. 27changed. (500, 64) m.o. 407 It is interesting to look at the components of mean response Effect of variation in job arrival rate. Fig. 14(a) and (b) show, at adelay as well as rejection probability. They are shown in Fig. 12(a) fixed mean service time and at a given number of PMs in each pool,(b) for 60 PMs in each pool. For the example shown in Fig. 12(a), increasing arrival rate increases job rejection probability and meanbeyond mean service time of 300 min, rejection due to buffer full response delay. Though increasing system capacity reduces theis dominant compared to rejection due to insufficient capacity. This response delay, marginal gain varies. This effect can be explained inis an example that shows how our models can provide what-if terms of dominant components of response delay as we explainedanalysis to better understand system bottlenecks. In the example in previous cases (Figs. 11(b) and 12(b)).shown in Fig. 12(b), mean provisioning delay is dominant whenmean service time is less than 500 min and mean queuing delay is Comparison of scalability w.r.t. monolithic model. We used Stochasticdominant when mean service time is higher than 500 min. Petri Net Package (SPNP) [10] to solve the monolithic SRN model. Interacting sub-models as well as the monolithic model wereEffect of variation in maximum number of VMs on each PM. In Figs. 11 solved using a desktop PC with Intel Core 2 Duo processor (E8400,and 12, we assumed each PM can run maximum 4 VMs. Fig. 13(a) 3.0 GHz) and 4 GB memory. In Table 4, we report the state space forshows, rejection probability as a function of maximum number of both the monolithic model and interacting sub-models. MonolithicVMs (denoted by m) per PM (at a fixed mean service time and model runs into a memory overflow problem when the numberat a given arrival rate). When the PM capacity in a pool is low, of PMs in each pool increases beyond 3 and the number of VMsbenefits of increasing m is significant. For example, at a mean per PM increases beyond 38. We observe that the state space sizeservice time of 20 h, rejection probability is reduced by a factor of the monolithic model increases quickly and becomes too largeof 5 or more when we increase m from 1 to 2. This is because, to construct the reachability graph even for a small number ofincreasing the value of m allows more jobs to be accepted and PMs. However, with an interacting sub-models approach, the staterun in parallel. However, impact of increasing PM and VM capacity space increases at a slower rate as the maximum number of VMsalmost vanishes when m is increased from 4 to 8. Clearly, for per PM is increased and remains constant w.r.t. increasing numberthis example, putting more than 4 VMs per PM will lead to over- of PMs. Table 5 shows a comparison of non-zero elements in theprovisioning and might increase Cloud service hosting cost. Similar infinitesimal generator matrices of the underlying CTMCs which isresults are obtained for mean response delay as shown in Fig. 13(b). a measure of storage requirements. For the same number of PMs and VMs, number of states and non-zero elements in interacting sub-models are hundreds to thousands orders of magnitude smaller compared to the monolithic model. Reduction in state

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1227Fig. 13. (a) Job rejection probability vs. maximum number of VMs on each PM and (b) mean response delay vs. maximum number of VMs on each PM, at different meanservice times. Fig. 14. (a) Job rejection probability vs. arrival rate and (b) mean response delay vs. arrival rate at different number of PMs.Table 5 Table 6Comparison of non-zero elements in the CTMC generator matrices. m.o. means Comparison of model solution times in seconds. m.o. means memory overflow.memory overflow. (#PMs per pool, #VMs per PM) Monolithic model Interacting sub-models(#PMs per pool, #VMs per PM) Monolithic model Interacting sub-models (1, 1) 0.124 0.066(1, 1) 3,608 57 (1, 2) 0.196 0.074(1, 2) 22,295 71 (1, 4) 0.556 0.088(1, 4) 111,221 95 (1, 8) 2.998 0.141(1, 8) 673,265 143 (1, 16) 79.563 0.208(1, 16) 4,618,985 239 (1, 32) 188.174 0.346(1, 32) 34,075,865 431 (1, 38) 293.672 0.399(1, 38) 60,776,406 503 (1, 39) m.o. 0.406(1, 39) m.o. 515 (2, 1) 2.024 0.063(2, 1) 271,296 57 (3, 1) 166.704 0.062(3, 1) 17,842,944 57 (4, 1) m.o. 0.060(4, 1) m.o. 57 (500, 64) m.o. 0.055(500, 64) m.o. 821space and non-zero entries for interacting sub-models also leads constant with the increase in model size. Observe that, as weto concomitant reduction in solution time needed. A comparison of increase the number of PMs in each pool, the solution time for thesolution times is shown in Table 6. Solution time for a monolithic interacting sub-models approach reduces. This is because, keepingmodel increases almost exponentially with the increase in model all other input parameters constant, increasing the number of PMssize. Solution time for interacting sub-models remains almost reduces the convergence time for fixed-point iteration and hence, reducing overall solution time.

1228 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 Fig. 15. (a) Job rejection probability vs. arrival rate and (b) mean number of jobs in RPDE vs. arrival rate.Accuracy of interacting sub-models approach. We compare the Fig. 16. RPDE sub-model for n pools.values of two performance measures: (i) job rejection probability VMs per PM and remains independent from the number of pools(Preject ) and (ii) mean number of jobs in RPDE (E[NRPDE ]) as obtained or PMs in each pool. In the three pools example, described in thefrom interacting sub-models and the monolithic model. Fig. 15(a)and (b) show that as we change the arrival rate and maximum paper, the number of states in the VM provisioning sub-model fornumber of VMs per PM, outputs obtained from both the modelingapproaches are near similar. This shows that the errors introduced each hot PM is (m(Lh+2)+(Lh+1)). The number of states (nwarm_pm )by the decomposition of the monolithic model are negligible andthe interacting sub-models approach preserves accuracy while in the VM provisioning sub-model for each warm PM is given by:being scalable. Introduced errors are associated with the factthat we solve only one model for all the PMs in each pool nwarm_pm = 4 + 2) + 3(Lw + 1) if m = 1, Lw = 0 (36)and aggregate the obtained results in order to approximate the m(Lw otherwise.behavior of the pool as a whole. Thus, values of the probabilities The number of states ( )ncold_pm in the VM provisioning sub-model(e.g., Ph, Pw, Pc ) that at least one PM is able to accept a job in a for each warm PM is given by:pool, are different in the monolithic (exact) model and interacting(approximate) sub-models. Observe, this approximation is the ncold_pm = 4 + 2) + 3(Lc + 1) if m = 1, Lc = 0 (37)key factor for facilitating fast (e.g., reduced solution time) and m(Lc otherwise.large scale (e.g., reduced memory consumption) model solution.Although, Fig. 15(a) and (b) show that such errors are negligible in Hence, with increasing number of pools, the bottleneck model willpractice, we plan to investigate and reduce the errors in future. be RPDE. However, software packages such as SHARPE, can easily solve thousands of model states in few seconds and can deal with6. Model generalizations and future research a large number of pools. Moreover, we provided a closed form solution for the RPDE sub-model which can be easily generalizedModel generalizations. We discuss three system management to the n pools cases. As a result, such closed form solutions can beaspects w.r.t. which the proposed scalable stochastic models can used when the number of RPDE sub-models states become largebe generalized. and go beyond the capacity of SHARPE. Fig. 17 shows an import graph describing interactions among the sub-models for n pools.(1) Dealing with larger number of pools. In this paper, we described Key differences with the Fig. 9 are in the interactions among the VMperformance analysis of a specific type of IaaS Cloud with three provisioning sub-models. Also, the RPDE sub-model will requirepools of PMs. The PMs were grouped into pools to maintain a outputs from each of the VM provisioning sub-models.balance between power consumption and performance behavior.In general, to offer a differentiated service, Cloud providers (2) Heterogeneous PMs. VM provisioning sub-models presented inmight create a larger number of PM pools. We discuss how the this paper can be extended to model heterogeneous PMs. Whenperformance model for three pools can be extended to n pools. there are multiple classes of PMs with varying characteristics, theyEach pool is labeled as j, where 1 ≤ j ≤ n. Fig. 16 shows an RPDEsub-model for n pools. States are denoted by (i, j), where i denotesnumber of jobs waiting in the queue and j denotes the pool type.Steady state probability that the job is accepted in the j-th pool isdenoted by Pj. Observe that, with n pools, the number of states inthe RPDE sub-model will be (n(N −1)+1), which is linear w.r.t. thenumber of pools and independent of the number of PMs in eachpool. Similarly, there will be n VM provisioning sub-models, onefor each pool. It can be easily shown that the number of states inVM provisioning sub-models grows linearly w.r.t. the number of

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1229Fig. 17. Interactions among sub-models for n pools. performance SLAs, i.e., upper bound on job rejection probability and mean response delay? (ii) for a given arrival rate and givencan be organized in different pools. Then, within each pool, the total power consumption budget, what is the optimal number ofPMs will be homogeneous and all pools together will model PM PMs in each pool that can minimize the job rejection probabilityheterogeneity. If the Cloud is designed in a manner that multiple and mean response delay?classes of PMs are kept in the same pool, we can develop sub-pools within a pool and then combine the results of sub-pools to (3) Cost analysis. Cost analysis can be performed by exploitingobtain the overall results for the pool. In this case, within each our performance sub-models. We will capture both capitalsub-pool, the PMs are homogeneous but the overall pool can have expenditure (e.g., infrastructure cost) and operational expenditureheterogeneous PMs. (e.g., attendant costs, maintenance overhead cost). Our approach of Markov reward models easily lends itself to such analysis [16,19].(3) Different provisioning strategies. In VM provisioning sub-models, Cost analysis will help service providers to understand the benefitwe assumed that only one job is being provisioned at a time, while of Cloud systems over non-Cloud architectures and to compareother jobs wait in the queue. Thus, in the CTMC models in Figs. 4, 6 different Cloud management policies.and 7, the value of j, in state (i, j, k) is always 0 or 1. The assumption (4) Capacity planning. This paper characterizes Cloud service quality as a non-linear complex function of a variety of parameterscan be easily relaxed by associating a state dependent multiplier to including arrival rate, service rate, PM and VM capacity. We will combine the cost models together with the performance models totransition rates βh, βw and βc . For example, in order to introduce carry out an overall optimization for capacity planning of a Cloud system. Specifically, we will compute the number of PMs that aredifferent provisioning strategies in the hot PM CTMC of Fig. 4, rate required in order to minimize the overall cost but still maintainof VM provisioning can be written as: promised SLAs, for a known type of job characteristic. (5) Heterogeneous requests. Our approach can be extended to model heterogeneity in the requests [15]. It is for example possible to vary the number of cores/VMs/sizes of memory being requested, allow different arrival rates and service times for different job types, etc. Preemptive priorities among different request classes can be modeled using the shadow-server approach [29]. Assume that there are 1, 2, . . . , r priority classes where class 1 is the highest priority and class r is the lowest. In a shadow server approach, the service rate of a request with lower priority is slowed down to compensate the utilization of all the higher priority jobs. Thus, if µr (o) be the original (in absence of all the other higher class jobs) service rate of a class r job, its shadow service rate is given by:βh′ = βhψ(i, j, k). (38)  r−1  µr (s) = µr (o)  (39) 1 − UiIf a job require provisioning of several VMs in parallel, ψ (i, j, k) is i=1set to j. Similar state-dependent multipliers can be used in warm where, Ui is the utilization of the class i job.and cold PM CTMC sub-models. (6) Different types of job streams. While in this paper we assumeFuture research. We discuss different types of what-if analyses that job arrival is a homogeneous Poisson process, our approachcan be performed using the proposed models as well as other is amenable to capturing more general arrival processes. Forpossible extensions. example, the use of MMPP (Markov Modulated Poisson Process) and MAP (Markovian Arrival Process) [16,30] can capture bursty(1) Admission control. Fig. 14(a) and (b) show that beyond a certain arrivals and yet result in a homogeneous CTMC, albeit with a largerarrival rate, job rejection probability and mean response delay state space. Non-homogeneous Markov chains with piecewisesignificantly increases with the load. For example, in case of constant arrival rates can capture slow increase in arrival rates100 PMs per pool, sudden increase in job rejection probability is [31,16]; techniques for solving such models are known and can beobserved beyond 1000 jobs/h while a sudden increase in mean easily automated via SHARPE.response delay is observed beyond 900 jobs/h. Depending on targetSLAs on rejection probability or mean response delay, service (7) Different types of service time distributions. Delays such as theproviders may not allow new jobs to enter the Cloud system provisioning times, the job execution time and others, currentlybeyond these threshold arrival rates. Similar phenomena can be assumed to be exponentially distributed, will be allowed toobserved in Fig. 11(a) and (b), as the mean job service time is be generally distributed using MRGP (Markov Re-Generativeincreased. Hence, model driven and predictive admission control Process) [32] and/or phase-type expansions [16,17]. SHARPE doescan be done based on job characteristics (e.g., arrival rate and mean have MRGP as a model type and phase type expansion results injob service time) to maintain promised SLAs. homogeneous CTMC with a larger state space.(2) Optimization using power-performance trade-offs. In this paper, (8) Formal sensitivity analysis. As shown in the paper, IaaS Cloudwe describe a tiered service offering by configuring PMs into performance depends on a large number of parameters. A for-three pools with different response time and power consumption mal sensitivity analysis [6] of the performance measures w.r.t. thecharacteristics. In a related paper [28], we showed that single fixed model input parameters will help to determine important param-partitioning among different pools is not always the best strategy, eters and reveal bottlenecks in the system.especially under varying arrival rate—a common characteristic ofthe Cloud. As part of our future research, we will mathematically (9) Transient analysis. This paper presents only the steady stateformulate several optimization problems such as: (i) for a given analysis of the developed models. Transient solutions of thearrival rate, what is the optimal number of PMs in each pool that interacting sub-models show how the measures of interestcan minimize the total power consumption and do not violate the (e.g., mean response delay) vary with time. Transient analysis

1230 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234of interacting sub-models coupled with fixed-point iterations model to consider heterogeneous requests. In [53], Lenk et al. pro-becomes non-trivial as the values of fixed-point variables change posed a new method for performance evaluation of IaaS Clouds bywith time—leading to non-homogeneous Markov sub-models. In a taking into account the type of application running in a VM. Valida-follow-up paper, we will present a novel algorithm when dealing tion of our performance model can be performed w.r.t. this work.with such non-homogeneous, interacting Markov sub-models. In [54], Gmach et al. proposed three different cost models that can be used by service providers who make significant investments in(10) Model validation. In the future, we will validate our models new virtualized data centers in order to recover costs for infras-using face validation, input–output validation and model assump- tructure resources. They presented a detailed study involving hun-tions validation [33]. We are also analyzing the inter-arrival time, dreds of workloads in order to demonstrate the results. Such workprovisioning response time and service time data collected from an can be used to validate our model and to demonstrate how it canopen source Cloud environment [21]. We plan to report the results be used for cost analysis of IaaS Clouds.of such analyses in a follow-up paper.7. Related research 8. Conclusions Ostermann et al. [34] carried out a measurement-based In this paper, we quantify the effects of variations in workloadperformance evaluation of the Amazon EC2 [1] in the context of (e.g., job arrival rate, job service rate) and system capacity (PMsscientific computing. Through experimentations, they showed that per pool, VMs per PM) on the performance of a class of IaaS Cloudsperformance of Amazon EC2 is insufficient for scientific computing. where PMs are organized in a set of pools for management andIn [35], Deelman et al. presented a similar study of performance power consumption costs reduction. Using interacting stochasticand cost of executing the montage workflow on Clouds. Yigitbasi sub-models, we propose a fast method suitable for analyzing theet al. [36] proposed an experimental framework to analyze the service quality of large sized IaaS Clouds. We discuss how ourresource acquisition and resource release times in Amazon EC2 approach can reduce model complexity both in storage space andunder variety of workloads. Our analytic models can complement in execution time compared to a monolithic analytic model. Wethese studies and analyze the reasons behind the interesting also show closed form solutions of sub-models where feasible andresults. Voorsluys et al. [37] showed performance analysis of VM prove the existence of a solution for the associated fixed pointlive migration and its impacts on SLAs. Other measurement based equation. Results show that our approach enables the Cloud serviceperformance evaluation of Cloud services include [38–42]. providers to detect system bottlenecks. Moreover, optimization for a broad range of provider specific Cloud settings can be performed In [43], Xiong and Perros used percentile of response time as as the model allows to explore a large Cloud parameter space.a QoS metric of Cloud services for a fixed arrival and service rate. In the future, we will relax some of the simplifying assumptionsUnlike our paper, the analytic model they presented does not cap- made in this paper and we plan on developing a predictive toolture details of Cloud service provisioning decisions, VM provision- for management of performance SLAs in IaaS Cloud. To implementing and release. In [44], Varalakshmi et al. focused on scheduling the proposed modeling approach for a real Cloud, one needs toCloud workflows in order to meet user-preferred QoS parameters. understand the specific system behaviors, service requirementsThe performance behavior of PMs was modeled through General- and map them accordingly to the models similar to those describedized Processor Sharing queues. In another work, Bruneo et al. [45] in the paper. Such translations of real system behavior to stochasticshowed energy consumption analysis of IaaS Cloud. In [46], Mills models can be done by strong collaborations between the systemet al. applied an efficient sensitivity analysis method to identify developers and analytic modelers. For the ease of understandingrelevant input parameter combinations and output measures for and translation, high level modeling paradigms e.g., SRN, UML,an IaaS Cloud simulator which compared resource allocation algo- SysML can be used. Underlying models can be generated from theserithms. In [47], Genaud and Gossa evaluated strategies based on higher level models using software packages such as SPNP [10].classic heuristics for online scheduling with the objective of min- Once developed, parameterization and validation of the modelsimizing the wait time of jobs and the monetary cost of the rented should be done based on measured data for specific Cloudresources. Strategies are evaluated through simulation. environments. In [48], Mi et al. proposed an approach to diagnose the source Appendix A. Summary of symbolsof performance degradation in large-scale always available Cloudsystems. The execution path graph of a user request was modeled We summarize the symbols used throughout the paper inby a hierarchical structure. This approach can perhaps be combined Table A.1.with our performance model in order to identify performancebottlenecks in the presence of a different class of PMs and to Appendix B. Closed form solutions for RPDE sub-modeloptimize the placement of PMs in the different pools. In [49],Govindan et al. described a practical technique for predicting Let π(i,s) denotes the steady state probability for being in stateperformance interference due to shared processor caches among (i, s), where, 0 ≤ i ≤ (N − 1) and s ∈ {0, h, w, c}. Steady stateVMs consolidated on the same PM. In [50], Rhoden et al. focused onper-node efficiency, performance, and predictability in Cloud data balance equations for the RPDE model in Fig. 2 are:centers. The results of these works could be used to complementour model and improve our workload placement decisions for λπ(0,0) = δhPhπ(0,h) + δw Pw π(0,w) + δc π(0,c) (B.1)given performance and cost objectives. In [51], Wu and Zhao (λ + δh)π(0,h) = λπ(0,0) + δhPhπ(1,h) + δwPwπ(1,w) + δc π(1,c) (B.2)provided performance models for live migration which can be (λ + δw)π(0,w) = δh(1 − Ph)π(0,h) (B.3)used to predict a VM’s migration time given its application’s (λ + δc )π(0,c) = δw(1 − Pw)π(0,w) (B.4)behavior and the resources available for migration. The model was (λ + δh)π(1,h) = λπ(0,h) + δhPhπ(2,h) + δwPwπ(2,w) + δc π(2,c) (B.5)developed by the use of regression methods on profiling data. In (λ + δw)π(1,w) = λπ(0,w) + δh(1 − Ph)π(1,h) (B.6)our work we do not consider VM migrations so our work can be (λ + δc )π(1,c) = λπ(0,c) + δw(1 − Pw)π(1,w) (B.7)complementary to the one proposed by Wu and Zhao. In [52], Goudarzi and Pedram considered SLA-based resourceallocation problem for multi-tier applications in Cloud. The pro-cessing, memory requirement, and communication resources wereconsidered as three search dimensions, in which optimization wasperformed. Such work could be useful to extend our performance

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1231Table A.1Symbols used throughout the paper.Symbol MeaningCt Total number of CPU cores per PMRt Total amount of RAM per PMDt Total disk capacity per PMcv Number of cores required per VMrv Amount of RAM required per VMdv Disk capacity required per VMm Maximum number of VMs that can be deployed on a PM Job arrival rateλ Mean searching delay to find a PM from hot pool1/δh Mean searching delay to find a PM from warm pool1/δw Mean searching delay to find a PM from cold pool1/δc Steady state probability that a hot PM can accept a job Steady state probability that a warm PM can accept a jobPh Steady state probability that a cold PM can accept a job Maximum number of jobs in RPDEPwPc Steady state probability for being in state (i, s) in RPDE sub-model, where, 0 ≤ i ≤ (N − 1) and s ∈ {0, h, w, c}N Total job rejection probability Job rejection probability due to RPDE buffer fullπ(i,s) Job rejection probability due to insufficient capacity Mean queuing delay for resource provisioning decisionPreject Mean decision delay Effective job arrival rate to each hot PMPblock Rate at which VM instantiation, provisioning, and configuration occurs in hot PMs Mean service time on CPUPdrop Mean service time on local I/O Mean service time on global I/OE[Tq_dec ] Mean job service time Buffer size of hot PMsE [Tdecision ] Server utilization of node A in Fig. 5λh Server utilization of node B in Fig. 5βh1/µc Steady state pmf of i jobs (i > 0) waiting in the queue and j VMs (j ∈ {0, 1}) being provisioned1/µl Steady state pmf of k VMs (k > 0) running on a hot PM1/µg1/µ Total number of PMs in hot poolLh Steady state probability for being in state (i, j, k) in hot PM sub-model, where, 0 ≤ i ≤ Lh, j ∈ {0, 1}, and 0 ≤ k ≤ mρA Steady state probability that a hot PM cannot accept a jobρB Effective job arrival rate to each warm PM Startup delay to make a warm PM ready to usepA (i, j) Rate at which VM instantiation, provisioning, and configuration occurs for the first time in warm PMspB (k) Buffer size of warm PMs Total number of PMs in warm poolnh Steady state probability for being in state (i, j, k) in warm PM sub-model, where, 0 ≤ i ≤ Lw, j ∈ {0, 1, 1∗, 1∗∗}, and 0 ≤ k ≤ mφ((ih,)j,k) Steady state probability that a warm PM cannot accept a jobBh Effective job arrival rate to each cold PM Startup delay to make a cold PM ready to useλw Rate at which VM instantiation, provisioning, and configuration occurs for the first time in cold PMs1/γw Buffer size of cold PMsβw Total number of PMs in cold poolLw Steady state probability for being in state (i, j, k) in warm PM sub-model, where, 0 ≤ i ≤ Lc , j ∈ {0, 1, 1∗, 1∗∗}, and 0 ≤ k ≤ mnw Steady state probability that a cold PM cannot accept a jobφ((iw,j,)k) Mean queuing delay for VM provisioning Mean number of jobs in the queue for each hot PMBw Mean number of jobs in the queue for each warm PM Mean number of jobs in the queue for each cold PMλc Conditional mean provisioning delay1/γc Mean response delayβc Mean number of jobs in RPDE Transition probabilities used in run-time sub-modelLc Transition modeling the job arrival rate in monolithic modelnc Place modeling job requests waiting for the RPDE to look for a hot PMφ((ic,)j,k) Place modeling the number of VMs that can still be provisioned in the ith hot PM, where 1 ≤ i ≤ nhBc Place modeling the number of jobs that can still be accepted in the ith hot PM, where 1 ≤ i ≤ nhE [Tq_vm ] Transitions modeling the searching delay to find a hot PM for resource provisioning, where 1 ≤ i ≤ nhE[Nhot ] Place modeling the PM provisioning queue in the ith hot PM, where 1 ≤ i ≤ nhE [Nwarm ] Transition modeling the VM provisioning delay on the ith hot PM, where 1 ≤ i ≤ nhE [Ncold ] Place modeling the jobs being served in the ith hot PM, where 1 ≤ i ≤ nhE [Tprov ] Transition modeling the service time in the ith hot PM, where 1 ≤ i ≤ nhE [Tresp ] Guard function modeling the ith hot PM not being able to accept jobs, where 1 ≤ i ≤ nhE[NRPDE ] Transition modeling the hot pool not being able to accept jobsp0 , p1 Guard function modeling the hot pool not being able to accept jobsTarr (continued on next page)Pd(h)Pv(mhi )Pb(uhfi )Td(hi )Pi(nhsit)Ti(nhsit)Ps(ehriv)Ts(ehriv)[gTd(hi ) ]Tn(h)[gTn(h) ]

1232 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234Table A.1 (continued)Symbol MeaningPd(w) Place modeling job requests waiting for the RPDE to look for a warm PMty′ (wj ) and ′′ (wj ) Transitions modeling the jth warm PM startup, where 1 ≤ j ≤ nw ty Place modeling the number of VMs that can still be provisioned in the jth warm PM, where 1 ≤ j ≤ nwPv(mwj ) Guard function modeling the first request to the jth PM, where 1 ≤ j ≤ nw ′′ (wj ) ] Place modeling the startup of the jth warm PM, where 1 ≤ j ≤ nw[gty Transition modeling the startup of the jth warm PM, where 1 ≤ j ≤ nwPs(twupj ) Guard function modeling the subsequent requests to the jth PM, where 1 ≤ j ≤ nwTs(twupj ) Transition modeling the warm pool not being able to accept jobs[gty′ (wj ) ] Guard function modeling the warm pool not being able to accept jobsTn(w) Place modeling job requests waiting for the RPDE to look for a cold PM Transition modeling the RPDE dropping a job[gTn(w) ] Guard function modeling the finite length of the RPDE queue Guard function modeling the RPDE dropping a jobPd(c) In generalized RPDE sub-model, steady state probability that the job is accepted in j-th pool, where 1 ≤ j ≤ nTdrop Number of states in VM provisioning sub-model for each warm PM[gTarr ] Number of states in VM provisioning sub-model for each cold PM[gTdrop ] State dependent multiplier to βh for state (i, j, k) of hot PM, modeling different provisioning strategies, where, 0 ≤ i ≤ Lh, j ∈ {0, 1}, and 0 ≤ k ≤ mPj Generalized VM provisioning rate in a hot PM for different provisioning strategiesnwarm_pmncold_pmψ(i, j, k)βh′(λ + δh)π(2,h) = λπ(1,h) + δhPhπ(3,h) + δwPwπ(3,w) + δc π(3,c) (B.8) λ π(0,c) = δhPhXY + δwPwX + δc π(0,0) = A(0,c)π(0,0)(λ + δw)π(2,w) = λπ(1,w) + δh(1 − Ph)π(2,h) (B.9) where,(λ + δc )π(2,c) = λπ(1,c) + δw(1 − Pw)π(2,w) (B.10) λ .... + δwPwX + δc A(0,c) = δhPhXY(λ + δh)π(k,h) = λπ(k−1,h) + δhPhπ(k+1,h) Also, we can compute π(0,w) and π(0,h) w.r.t. π(0,0) : + δw Pw π(k+1,w) + δ πc (k+1,c) (B.11) λX π(0,w) = δhPhXY + δwPwX + δc π(0,0)(λ + δw)π(k,w) = λπ(k−1,w) + δh(1 − Ph)π(k,h) (B.12) = XA(0,c)π(0,0) = A(0,w)π(0,0)(λ + δc )π(k,c) = λπ(k−1,c) + δw(1 − Pw)π(k,w) (B.13) λXY... π(0,h) = δhPhXY + δwPwX + δc π(0,0) = XYA(0,c)π(0,0) = A(0,h)π(0,0)δ πh (N−1,h) = λπ(N−2,h) (B.14) where,δw π(N−1,w) = λπ(N−2,w) + δh(1 − Ph)π(N−1,h) (B.15) λX A(0,w) = δhPhXY + δwPwX + δc = XA(0,c)δ πc (N−1,c) = λπ(N−2,c) + δw (1 − Pw )π(N−1,w) . (B.16) λXYNormalization is provided by: A(0,h) = δhPhXY + δwPwX + δc N −1  = XYA(0,c) = YA(0,w). π(0,0) + π(i,h) + π(i,w) + π(i,c) = 1. (B.17) Steady state probabilities to be in states (1, h), (1, w) and (1, c) i=0 From Eq. (B.7):Steady state probabilities to be in states (0, h), (0, w) and (0, c) π(1,w) = δw λ + δc ) π(1,c ) − λ (1 − Pw δw(1 − Pw) π(0,c) From Eq. (B.4):π(0,w) = λ + δc π(0,c) = X π(0,c) (B.18) = X π(1,c) − Z π(0,c) δw(1 − Pw ) where,where, Z= λ . δw(1 − Pw)X = λ + δc . δw(1 − Pw) From Eqs. (B.19) and (B.6):From Eqs. (B.3) and (B.18): π(1,h) = XY π(1,c) − YZ π(0,c) − W π(0,w) (B.20) λ + δw where, δh(1 − Phπ(0,h) = ) π(0,w) = Y π(0,w) = XY π(0,c) (B.19) W= λ .where, δh(1 − Ph)Y = λ + δw . Substituting π(1,w) and π(1,h) in Eq. (B.2): δh(1 − Ph) (λ + δh)π(0,h) = λπ(0,0) + δhPh(XY π (1, c)Substituting π(0,w) and π(0,h) in Eq. (B.1), we can compute π(0,c) w.r.t. − YZ π(0,c) − W π(0,w) )π(0,0) : + δwPw(X π(1,c) − Z π(0,c) ) + δc π(1,c) . (B.21)

R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234 1233Thus, we can compute π(1,c) w.r.t. π(0,0) : π(k,h) = A(k,h)π(0,0)π(1,c) = A(1,c)π(0,0) π(k,w) = A(k,w)π(0,0) π(k,c) = A(k,c)π(0,0) .where,A(1,c) = (λ + δh)A(0,h) + δhPhYZA(0,c) Steady state probabilities to be in states (N − 1, h), (N − 1, w) and δhPhXY + δwPwX + δc (N − 1, c). + δhPhWA(0,w) + δwPwZA(0,c) From Eq. (B.14): δhPhXY + δwPwX + δc π(N−1,h) = λ/δhπ(N−2,h) = λ/δhA(N−2,h)π(0,0) . λ −. From Eq. (B.15): δhPhXY + δwPwX + δc (B.22) δh(1 − Ph) δw π(N −1,w) = λ/δw π(N−2,w) + π(N −1,h)Also, π(1,w) and π(1,h) can be computed w.r.t. π(0,0) : δh(1 − Ph) λ/δhA(N−2,h)π(0,0) . δwπ(1,w) = (XA(1,c) − ZA(0,c))π(0,0) = λ/δw A(N−2,w)π(0,0) + = A(1,w)π(0,0) From Eq. (B.16):π(1,h) = (XYA(1,c) − YZA(0,c) − WA(0,w))π(0,0) = A(1,h)π(0,0) π(N −1,c ) = λ/δc π(N−2,c) + δw(1 − Pw ) π(N −1,w) δcwhere, δw(1 − Pw ) = λ/δc A(N−2,c)π(0,0) + δcA(1,w) = XA(1,c) − ZA(0,c) (B.23) (B.24) ×  + δh(1 − Ph) A(1,h) = XYA(1,c) − YZA(0,c) − WA(0,w) λ/δw A(N −2,w) δw λ/δhA(N−2,h) π(0,0) . = YA(1,w) − WA(0,w).Steady state probabilities to be in states (2, h), (2, w) and (2, c). Thus, steady state probabilities of all states in the CTMC of Fig. 2 can Using a similar approach, we can compute π(2,c) , π(2,w) , π(2,h) be expressed as a function of the steady state probability of statew.r.t. π(0,0) : (0, 0). Using Eq. (B.17), expression for steady state probability forπ(2,c) = A(2,c)π(0,0) being in state (0, 0) can be obtained, which in turn can be used toπ(2,w) = A(2,w)π(0,0)π(2,h) = A(2,h)π(0,0) compute the steady state probabilities of all other states.where, ReferencesA(2,c) = (λ + δh)A(1,h) [1] Amazon EC2, 2006. http://aws.amazon.com/ec2. δhPhXY + δwPwX + δc [2] IBM SmartCloud Enterprise, 2011. + δhPhYZA(1,c) + δhPhWA(1,w) δhPhXY + δwPwX + δc http://www-935.ibm.com/services/us/en/cloud-enterprise/index.html. + δwPwZA(1,c) − λA(0,h) [3] IBM cloud computing from Wikipedia: 2012. δhPhXY + δwPwX + δc (B.25) (B.26) http://en.wikipedia.org/wiki/IBM_cloud_computing.A(2,w) = XA(2,c) − ZA(1,c) (B.27) [4] IBM Smart Business Desktop Cloud, 2012. http://www-07.ibm.com/A(2,h) = XYA(2,c) − YZA(1,c) − WA(1,w) businesscenter/au/services/cloud_computing/smart_business_desktop_ = YA(2,w) − WA(1,w). cloud.html. [5] R. Buyya, R. Ranjan, R.N. Calheiros, Modeling and simulation of scalableGeneral forms of steady state probabilities to be in states (k, h), (k, w) cloud computing environments and the cloudsim toolkit: challenges andand (k, c). opportunities, in: HPCS, 2009. [6] N. Sato, K.S. Trivedi, Stochastic modeling of composite web services for closed- By observing Eqs. (B.22)–(B.27), we derive general forms for form analysis of their performance and reliability bottlenecks, in: ICSOC, 2007. [7] R. Ghosh, K.S. Trivedi, V.K. Naik, D.S. Kim, Performability analysis forcoefficients A(k,h), A(k,w) and A(k,c) with 1 ≤ k ≤ (N − 2): infrastructure-as-a-service cloud: an interacting stochastic models approach, in: IEEE PRDC, 2010.A(k,c) = (λ + δh)A(k−1,h) + δhPhYZA(k−1,c) [8] G. Ciardo, J. Muppala, K.S. Trivedi, SPNP: stochastic Petri net package, in: δhPhXY + δwPwX + δc Third Int. Workshop on Petri Nets and Performance Models, PNPM89, 1989, + δhPhWA(k−1,w) + δwPwZA(k−1,c) pp, 142–151. δhPhXY + δwPwX + δc [9] K.S. Trivedi, R. Sahner, SHARPE at the age of twenty two, ACM Sigmetrics − λA(k−2,h) Performance Evaluation Review 36 (4) (2009) 52–57. δhPhXY + δwPwX + δc (B.28) [10] C. Hirel, B. Tuffin, K.S. Trivedi, SPNP: stochastic petri nets. Version 6, Lecture (B.29) Notes in Computer Science (2000).A(k,w) = XA(k,c) − ZA(k−1,c) (B.30) [11] W. Jansen, T. Grance, Guidelines on security and privacy in public cloud computing, Technical Report, NIST Special Publication 800-144, 2011.A(k,h) = XYA(k,c) − YZA(k−1,c) − WA(k−1,w) [12] D. Faatz, L. Pizette, Information Security in the Clouds, MITRE Corporation = YA(k,w) − WA(k−1,w) Technical Report Case # 10-3208, 2010. [13] A. Celesti, F. Tusa, M. Villari, A. Puliafito, How to enhance cloud architectureswhere, to enable cross-federation, in: IEEE CLOUD, 2010. [14] A. Ganapathi, Y. Chen, A. Fox, R. Katz, D. Patterson, Statistics-driven workloadA(−1,h) = 1. modeling for the cloud, in: SMDB, 2010. [15] P. Garbacki, V. Naik, Efficient resource virtualization and sharing strategies forThus, general forms of steady state probabilities to be in states heterogeneous grid environments, in: Integrated Network Management, 2007. [16] K.S. Trivedi, Probability and Statistics with Reliability, Queuing and Computerπ(k,h) , π(k,w) , π(k,c) are given by: Science Applications, second ed., Wiley, 2001. [17] D. Wang, R.M. Fricks, K.S. Trivedi, Dealing with non-exponential distributions in dependability models, in: G. Kotsis (Ed.), Symp. on Performance Evaluation Stories and Perspectives, Oesterre-ichchische Computer Gessellschaft, 2003, pp. 273–302. [18] C.H. Sauer, K.M. Chandy, Computer Systems Performance Modeling, Prentice- Hall, Englewood Cliffs, NJ, 1981. [19] N. Sato, K.S. Trivedi, Accurate and efficient stochastic reliability analysis of composite services using their compact Markov reward model representa- tions, in: IEEE SCC, 2007.

1234 R. Ghosh et al. / Future Generation Computer Systems 29 (2013) 1216–1234[20] P.J. Burke, Output of a queuing system, Operations Research 4 (1956) 699–704. [51] Y. Wu, M. Zhao, Performance modeling of virtual machine live migration,[21] Virtual Computing Lab at North Carolina State University, 2008. in: 2011 IEEE International Conference on Cloud Computing, CLOUD, 2011, pp. 492–499. http://vcl.ncsu.edu.[22] G. Ciardo, K.S. Trivedi, A decomposition approach for stochastic reward net [52] H. Goudarzi, M. Pedram, Multi-dimensional SLA-based resource allocation for multi-tier cloud computing systems, in: 2011 IEEE International Conference models, Performance Evaluation 18 (1993) 37–59. on Cloud Computing, CLOUD, 2011, pp. 324–331.[23] L. Tomek, K. Trivedi, Fixed-Point Iteration in Availability Modeling, in: M. Dal [53] A. Lenk, M. Menzel, J. Lipsky, S. Tai, P. Offermann, What are you paying Cin (Ed.), Informatik-Fachberichte, Vol. 91: Fehlertolerierende Rechensys- for? Performance benchmarking for infrastructure-as-a-service offerings, in: teme, Springer-Verlag, Berlin, 1991. 2011 IEEE International Conference on Cloud Computing, CLOUD, 2011,[24] V. Mainkar, K.S. Trivedi, Sufficient conditions for existence of a fixed point in pp. 484–491. stochastic reward net-based iterative models, IEEE Transactions on Software Engineering 22 (9) (1996) 640–653. [54] D. Gmach, J. Rolia, L. Cherkasova, Resource and virtualization costs up in[25] J.M. Ortega, W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in the cloud: models and design choices, in: 2011 IEEE/IFIP 41st International Several Variables, Academic Press, NY, 1970. Conference on Dependable Systems Networks, DSN, 2011, pp. 395–402.[26] G. Ciardo, et al., Automated generation and analysis of Markov reward models using stochastic reward nets, in: Linear Algebra, Markov Chains and Queuing Rahul Ghosh is a Ph.D. candidate in Electrical and Models, Springer, 1993. Computer Engineering at Duke University, USA. He[27] M.A. Marsan, et al., A class of generalized stochastic petri nets for the received his M.S. in Computer Engineering from Duke performance evaluation of the multiprocessor systems, ACM Transactions on University in 2009. Prior to this, he received his B.E. Computer Systems 2 (2) (1984) 93–122. in Electronics and Telecommunication from Jadavpur[28] R. Ghosh, V.K. Naik, K.S. Trivedi, Power-performance trade-offs in IaaS cloud: University, India, in 2007. His research interests include a scalable analytic approach, in: DSN DCDV Workshop, 2011. stochastic processes, queuing systems, Markov chains,[29] K.C. Sevcik, Priority scheduling disciplines in queuing network models of performance and dependability analysis of large scale computer systems, in: IFIP Congr.,1977, pp. 565–570. computer systems. Rahul’s Ph.D. Thesis research is focused[30] H. Okamura, T. Dohi, K.S. Trivedi, Markovian arrival process parameter on developing scalable analytic models for Infrastructure- estimation with group data, IEEE/ACM Transactions on Networking 17 (4) as-a-Service Cloud. During his Ph.D., he worked as a (2008) 1326–1339. research intern at IBM T.J. Watson Research Center. At IBM Research, his work was[31] A. Rindos, S. Woolet, I. Viniotis, K.S. Trivedi, Exact methods for the transient focused on cost optimization, capacity planning and risk analysis of Cloud systems. analysis of non-homogenous continuous time Markov chains, in: W.J. Stewart (Ed.), 2nd Intl. Workshop on the Numerical Solution of Markov Chains, Kluwer Francesco Longo was born in Messina on November 16, Academic Publishers, Boston, 1995. 1982. He received his Degree in Computer Engineering[32] H. Choi, V.G. Kulkarni, K.S. Trivedi, Markov Regenerative Stochastic Petri Nets, from the University of Messina (Italy) in November 2007, Performance Evaluation 20 (1–3) (1994) 337–357.[33] G. Bolch, S. Greiner, H. de Meer, K.S. Trivedi, Queuing Networks and Markov final score 110/110 summa cum laude. The title of his the- Chains, second ed., John Wiley, 2006.[34] S. Ostermann, A. Iosup, N. Yigitbasi, R. Prodan, T. Fahringer, D. Epema, sis was ‘‘Symbolic representation of the reachability graph A performance analysis of EC2 cloud computing services for scientific of non-Markovian stochastic Petri net’’. From September computing, in: Cloudcomp, 2009. 2007 to June 2008 he worked at the University of Messina[35] E. Deelman, G. Singh, M. Livny, J.B. Berriman, J. Good, The cost of doing science within the PON Project ‘‘Progetto per l’Implementazione on the cloud: the montage example, in: SC, 2008. e lo Sviluppo di una e-Infrastruttura in Sicilia basata sul[36] N. Yigitbasi, A. Iosup, D. Epema, C -meter: a framework for performance anal- paradigma della grid (PI2S2)’’ with the aim of designing ysis of computing clouds, in: International Workshop on Cloud Computing, and implementing a QoS management system in Grid en- 2009. vironment. In June 2008 he received a Master’s degree in Open Source and Com-[37] W. Voorsluys, J. Broberg, S. Venugopal, R. Buyya, Cost of virtual machine live puter Security. He received his Ph.D. in ‘‘Advanced Technologies for Information migration in clouds: a performance evaluation, in: CloudCom’09: Proceedings Engineering’’ at the University of Messina in April 2011. Between May 2010 and of the 1st International Conference on Cloud Computing, 2009. October 2010 he spent a period as a visiting scholar in the United States at the[38] H. Liu, S. Wee, Web server farm in the cloud: performance evaluation and Duke University (Durham, NC) where he had the opportunity to collaborate with dynamic architecture, in: CloudCom’09: Proceedings of the 1st International Prof. Kishor S. Trivedi in the modeling of Cloud systems and in the quantitative eval- Conference on Cloud Computing, 2009. uation of their performance and availability. Since 2010 he is a teaching assistant[39] A. Bhadani, S. Chaudhary, Performance evaluation of web servers using central for the subject ‘‘Valutazione delle prestazioni’’ (Performance evaluation) at the Fac- load balancing policy over virtual machines on cloud, in: COMPUTE’10: ulty of Engineering, University of Messina. He is now a post doc researcher within Proceedings of the Third Annual ACM Bangalore Conference, 2010. the Vision Cloud European project at the University of Messina. The project has the[40] J. Che, Q. He, K. Ye, D. Huang, Performance combinative evaluation of typical aim of building a new storage cloud infrastructure and framework. His main re- virtual machine monitors, in: HPCA (China), 2009. search interests include performance and reliability evaluation of distributed sys-[41] A. Iosup, N. Yigitbasi, D. Epema, On the performance variability of production tems (mainly Grid and Cloud) with main attention to the use of non-Markovian cloud services, in: IEEE/ACM CCGrid, 2010, pp. 104–113. stochastic Petri nets.[42] S. Toyoshima, S. Yamaguchi, M. Oguchi, Storage access optimization with virtual machine migration and basic performance analysis of amazon EC2, Vijay K. Naik is a Research Staff Member at IBM T. J. Wat- in: IEEE International Conference on Advanced Information Networking and son Research Center. He has been an active researcher in Applications Workshops WAINA, 2010. the area of distributed & fault tolerant computing and ser-[43] K. Xiong, H. Perros, Service performance and analysis in cloud computing, in: vice computing. Over the past few years, he has been pro- SERVICES’09: Proceedings of the 2009 Congress on Services—I, 2009. viding leadership in developing innovative technologies[44] P. Varalakshmi, A. Ramaswamy, A. Balasubramanian, P. Vijaykumar, An for cloud computing that are now incorporated in IBM pro- optimal workflow based scheduling and resource allocation in cloud, vided solutions. Currently, he is leading research teams to in: A. Abraham, J.L. Mauri, J.F. Buford, J. Suzuki, S.M. Thampi (Eds.), ACC (1), advance the frontiers of hybrid cloud computing, work- in: Communications in Computer and Information Science, vol. 190, Springer, load migration to cloud systems, transformation of enter- 2011, pp. 411–420. prise IT to cloud computing, performance modeling and[45] D. Bruneo, F. Longo, A. Puliafito, Evaluating energy consumption in a Cloud analysis of cloud based services & systems, and quantifying infrastructure, in: IEEE WoWMoM, 2011, pp. 1–6. the economics of cloud computing. He received his Ph.D. degree in computer science[46] K. Mills, J. Filliben, C. Dabrowski, An efficient sensitivity analysis method from Duke University in 1988. Previously he has worked at Google and ICASE, NASA for large cloud simulations, in: 2011 IEEE International Conference on Cloud Langley Research Center. Computing, CLOUD, 2011, pp. 724–731.[47] S. Genaud, J. Gossa, Cost-wait trade-offs in client-side resource provisioning Kishor S. Trivedi holds the Hudson Chair in the Depart- with elastic clouds, in: 2011 IEEE International Conference on Cloud ment of Electrical and Computer Engineering at Duke Uni- Computing, CLOUD, 2011, pp. 1–8. versity. He has been on the Duke faculty since 1975. He is[48] H. Mi, H. Wang, G. Yin, H. Cai, Q. Zhou, T. Sun, Y. Zhou, Magnifier: online the author of a well-known text entitled, Probability and detection of performance problems in large-scale cloud computing systems, Statistics with Reliability, Queuing and Computer Science in: 2011 IEEE International Conference on Services Computing, SCC, 2011, Applications, published by John Wiley. He has also pub- pp. 418–425. lished two other books entitled, Performance and Relia-[49] S. Govindan, J. Liu, A. Kansal, A. Sivasubramaniam, Cuanta: quantifying effects bility Analysis of Computer Systems, published by Kluwer of shared on-chip resource interference for consolidated virtual machines, Academic Publishers and Queueing Networks and Markov in: Proceedings of the 2nd ACM Symposium on Cloud Computing, SOCC’11, Chains, John Wiley. He is a Fellow of the Institute of Elec- ACM, New York, NY, USA, 2011, pp. 22:1–22:14. trical and Electronics Engineers. He has published over 470[50] B. Rhoden, K. Klues, D. Zhu, E. Brewer, Improving per-node efficiency in articles and has supervised 43 Ph.D. dissertations. He is the recipient of IEEE Com- the datacenter with new OS abstractions, in: Proceedings of the 2nd ACM puter Society Technical Achievement Award for his research on Software Aging and Symposium on Cloud Computing, SOCC’11, ACM, New York, NY, USA, 2011, Rejuvenation. He works closely with industry in carrying our reliability/availability pp. 25:1–25:8. analysis, providing short courses and in the development and dissemination of soft- ware packages such as SHARPE and SPNP.