# Analysing the Impact of Scaling Out SaaS Software on Response Time

Authors: Bo Dong; Shi Ying; Bingming Wang; Guoli Cheng; Jiangyi Geng
Journal: Scientific Programming
 (2021)

---

## Abstract

When SaaS software suffers from the problem of response time degradation, scaling deployment resources that support the operation of software can improve the response time, but that also means an increase in the costs due to additional deployment resources. For the purpose of saving costs of deployment resources while improving response time, scaling out the SaaS software is an alternative approach. However, how scaling out software affects response time in the case of saving deployment resources is an important issue for effectively improving response time. Therefore, in this paper, we propose a method analysing the impact of scaling out software on response time. Specifically, we define the scaling-out operation of SaaS software and then leverage queueing theory to analyse the impact of the scaling-out operation on response time. According to the conclusions of impact analysis, we further derive an algorithm for improving response time based on scaling out software without using additional deployment resources. Finally, the effectiveness of the analysis’s conclusions and the proposed algorithm is validated by a practical case, which indicates that the conclusions of impact analysis obtained from this paper can play a guiding role in scaling out software and improving response time effectively while saving deployment resources.


---

## Body

## 1. Introduction

### 1.1. The Motivation and Research Challenges

Response time degradation is one of the software performance issues that SaaS (Software-as-a-Service) providers may encounter due to changes in the runtime environment of the software. As a new software delivery model, SaaS software is composed of a series of atomic services, which are usually deployed on distributed deployment resources and together perform the function of the software [1, 2]. When response time degradation occurs, for the sake of ensuring the efficient operation of the software, SaaS providers usually solve this problem by adopting scaling techniques, for instance, scaling up the deployment resources (i.e., upgrading the configurations of current deployment resources where the software is deployed) or scaling out the deployment resources (i.e., providing more deployment resources for the software). However, that will also result in more costs due to renting additional deployment resources.For the purpose of saving costs of deployment resources, scaling out SaaS software (i.e., adding more instances of services in software) without using additional deployment resources is another approach to improve the response time. Nevertheless, that may not be an easy task for SaaS providers. In such a situation, the new service instances generated by scaling out the software may have to be deployed on existing deployment resources, and then, resource contention will occur between these service instances, which may have a negative impact on response time. If SaaS providers do not know the appropriate strategies for scaling out software with existing deployment resources, the response time of the software may not be effectively improved, which may also increase the burden of human operation. Therefore, how to scale out SaaS software to effectively improve the response time without increasing the cost of additional deployment resources becomes a challenging issue for SaaS providers.


### 1.2. The Proposed Solution

To address the issue mentioned above, our solution is to study the impact of scaling out SaaS software on response time without using additional deployment resources, in order to provide guidance for SaaS providers to scale out software and improve response time effectively. For this purpose, a method for performance analysis is necessary. Queueing theory has been widely applied in performance analysis [3, 4]. Since queueing theory is a mathematical analysis method, the performance metrics of the software (for instance, response time) can be analysed in combination with deployment resources and solved with mathematical formulas quantitatively and efficiently, which can contribute to subsequently analysing the impact of scaling out software on response time and making decisions for scaling-out operations [5]. Therefore, in this paper, we use queueing theory for our study. In brief, the key contributions of the paper are summarized as follows:(i)
We define the scaling-out operation of SaaS software and then analyse the positive and negative influences of scaling-out operations on response time of the software, which gives the direction of scaling out SaaS software(ii)
According to the analysis conclusions, we put forward an algorithm of scaling out software without using additional deployment resources, which is helpful in effectively improving response time of the software while saving deployment resources(iii)
Aiming to verify the effectiveness of the analysis conclusions and the proposed algorithm, we set up experiments on a practical caseThe rest of this paper is organized as follows. Section2 describes the background and problem statement of this paper. Section 3 introduces the process of analysing the impact of scaling out SaaS software on response time. Section 4 presents a practical case verifying the effectiveness of the analysis conclusions obtained from our study. The discussion of our study is presented in Section 5. Section 6 summarizes the related work, and our work is concluded in Section 7.


## 1.1. The Motivation and Research Challenges

Response time degradation is one of the software performance issues that SaaS (Software-as-a-Service) providers may encounter due to changes in the runtime environment of the software. As a new software delivery model, SaaS software is composed of a series of atomic services, which are usually deployed on distributed deployment resources and together perform the function of the software [1, 2]. When response time degradation occurs, for the sake of ensuring the efficient operation of the software, SaaS providers usually solve this problem by adopting scaling techniques, for instance, scaling up the deployment resources (i.e., upgrading the configurations of current deployment resources where the software is deployed) or scaling out the deployment resources (i.e., providing more deployment resources for the software). However, that will also result in more costs due to renting additional deployment resources.For the purpose of saving costs of deployment resources, scaling out SaaS software (i.e., adding more instances of services in software) without using additional deployment resources is another approach to improve the response time. Nevertheless, that may not be an easy task for SaaS providers. In such a situation, the new service instances generated by scaling out the software may have to be deployed on existing deployment resources, and then, resource contention will occur between these service instances, which may have a negative impact on response time. If SaaS providers do not know the appropriate strategies for scaling out software with existing deployment resources, the response time of the software may not be effectively improved, which may also increase the burden of human operation. Therefore, how to scale out SaaS software to effectively improve the response time without increasing the cost of additional deployment resources becomes a challenging issue for SaaS providers.


## 1.2. The Proposed Solution

To address the issue mentioned above, our solution is to study the impact of scaling out SaaS software on response time without using additional deployment resources, in order to provide guidance for SaaS providers to scale out software and improve response time effectively. For this purpose, a method for performance analysis is necessary. Queueing theory has been widely applied in performance analysis [3, 4]. Since queueing theory is a mathematical analysis method, the performance metrics of the software (for instance, response time) can be analysed in combination with deployment resources and solved with mathematical formulas quantitatively and efficiently, which can contribute to subsequently analysing the impact of scaling out software on response time and making decisions for scaling-out operations [5]. Therefore, in this paper, we use queueing theory for our study. In brief, the key contributions of the paper are summarized as follows:(i)
We define the scaling-out operation of SaaS software and then analyse the positive and negative influences of scaling-out operations on response time of the software, which gives the direction of scaling out SaaS software(ii)
According to the analysis conclusions, we put forward an algorithm of scaling out software without using additional deployment resources, which is helpful in effectively improving response time of the software while saving deployment resources(iii)
Aiming to verify the effectiveness of the analysis conclusions and the proposed algorithm, we set up experiments on a practical caseThe rest of this paper is organized as follows. Section2 describes the background and problem statement of this paper. Section 3 introduces the process of analysing the impact of scaling out SaaS software on response time. Section 4 presents a practical case verifying the effectiveness of the analysis conclusions obtained from our study. The discussion of our study is presented in Section 5. Section 6 summarizes the related work, and our work is concluded in Section 7.


## 2. Background and Problem Statement

To facilitate the description of scaling out SaaS software and the analysis of the response time of software in combination with deployment resources, in this section, first, we will introduce the concepts of SaaS software, deployment scheme, and deployment resources mentioned in this paper. Based on these concepts, we will give a description of the problem to be addressed in this paper.


### 2.1. SaaS Software

The SaaS software consists of different types of atomic services based on specific logical interaction relations. Figure1 shows an example of SaaS software, which is composed of five types of atomic services (S1∼S5). For ease of explanation, we use a tree structure to describe the interaction relationship between atomic services (shown in Figure 2) [6]. In Figure 2, the nodes which are denoted as “seq.,” “branch,” and “loop” represent sequential execution, branch execution, and loop execution, respectively. If the label of the node is “branch,” the value on the subsequent arc means the invocation probability of the corresponding branch, while if the label of the node is “loop,” the value on the subsequent arc represents the execution times of the subsequent node.Figure 1
An example of SaaS software.Figure 2
The tree structure of the interaction relationship of SaaS software.


### 2.2. Deployment Scheme and Deployment Resources

A deployment scheme describes the deployment resources that support the operation of SaaS software and the allocation of the service instances in SaaS software to deployment resources. Figure3 describes a possible deployment scheme for the SaaS software in Figure 1. The deployment resources in this deployment scheme are four deployment nodes, which are marked as n1, n2, n3, and n4 from top to bottom. Each node is a virtual machine (VM), and the value in the parenthesis means the VM type of node. Each service in SaaS software has one or more instances deployed on different deployment nodes. In this deployment scheme, there is one instance of service S1 and S2, respectively, and two instances of service S3, S4, and S5, respectively. For instance, the instance of S3 on n2 is denoted as s3,2, and the instance of S3 on n4 is denoted as s3,4.Figure 3
An example of the deployment scheme for the SaaS software.


### 2.3. Problem Statement

To facilitate the problem statement, first, we give the definition of the scaling-out operation of SaaS software as follows.Definition 1.
(Scaling-Out Operation of SaaS Software). The operation of scaling out SaaS software is defined as a five-tupleSO=Dinit,SS,Si,Actsi,t,nt,Dnew, where we have the following:Dinit is the initial deployment scheme of SSSS is the SaaS softwareSi is one of the services that constitute SSsi,t is the new instance of Si generated after the scaling-out operationnt is a deployment node in DinitActsi,t,nt is a function of the scaling-out operation, which generates the new instance si,t and deploys si,t on ntDnew is the new deployment scheme generated after the scaling-out operation
According to Definition1, the process of scaling out software can be regarded as a series of scaling-out operations. Let the response time of SS before scaling-out operations be RinitSS, and let the response time after scaling-out operations be RnewSS. The problem and goal of this study are to analyse the impact of scaling-out operations on response time of SaaS software and find an effective approach to obtain a better response time RnewSS comparing with RinitSS through scaling-out operations without additional deployment nodes.


## 2.1. SaaS Software

The SaaS software consists of different types of atomic services based on specific logical interaction relations. Figure1 shows an example of SaaS software, which is composed of five types of atomic services (S1∼S5). For ease of explanation, we use a tree structure to describe the interaction relationship between atomic services (shown in Figure 2) [6]. In Figure 2, the nodes which are denoted as “seq.,” “branch,” and “loop” represent sequential execution, branch execution, and loop execution, respectively. If the label of the node is “branch,” the value on the subsequent arc means the invocation probability of the corresponding branch, while if the label of the node is “loop,” the value on the subsequent arc represents the execution times of the subsequent node.Figure 1
An example of SaaS software.Figure 2
The tree structure of the interaction relationship of SaaS software.


## 2.2. Deployment Scheme and Deployment Resources

A deployment scheme describes the deployment resources that support the operation of SaaS software and the allocation of the service instances in SaaS software to deployment resources. Figure3 describes a possible deployment scheme for the SaaS software in Figure 1. The deployment resources in this deployment scheme are four deployment nodes, which are marked as n1, n2, n3, and n4 from top to bottom. Each node is a virtual machine (VM), and the value in the parenthesis means the VM type of node. Each service in SaaS software has one or more instances deployed on different deployment nodes. In this deployment scheme, there is one instance of service S1 and S2, respectively, and two instances of service S3, S4, and S5, respectively. For instance, the instance of S3 on n2 is denoted as s3,2, and the instance of S3 on n4 is denoted as s3,4.Figure 3
An example of the deployment scheme for the SaaS software.


## 2.3. Problem Statement

To facilitate the problem statement, first, we give the definition of the scaling-out operation of SaaS software as follows.Definition 1.
(Scaling-Out Operation of SaaS Software). The operation of scaling out SaaS software is defined as a five-tupleSO=Dinit,SS,Si,Actsi,t,nt,Dnew, where we have the following:Dinit is the initial deployment scheme of SSSS is the SaaS softwareSi is one of the services that constitute SSsi,t is the new instance of Si generated after the scaling-out operationnt is a deployment node in DinitActsi,t,nt is a function of the scaling-out operation, which generates the new instance si,t and deploys si,t on ntDnew is the new deployment scheme generated after the scaling-out operation
According to Definition1, the process of scaling out software can be regarded as a series of scaling-out operations. Let the response time of SS before scaling-out operations be RinitSS, and let the response time after scaling-out operations be RnewSS. The problem and goal of this study are to analyse the impact of scaling-out operations on response time of SaaS software and find an effective approach to obtain a better response time RnewSS comparing with RinitSS through scaling-out operations without additional deployment nodes.


## 3. Impact Analysis of Scaling Out SaaS Software on Response Time

For the purpose of analysing the impact of scaling out SaaS software on response time, an approach to evaluate SaaS software response time is needed. In this section, first, we will briefly introduce the evaluation method of response time by leveraging a queueing performance model. With the evaluation method, we will focus on analysing the impact of scaling-out operations on response time of the software. Finally, based on the analysis conclusions, we will further derive the algorithm of scaling out software for response time improvement. The flow of our work is also shown in Figure4.Figure 4
The flow diagram of our work.


### 3.1. Evaluation of SaaS Software Response Time

Since the SaaS software consists of a series of services that are deployed on multiple deployment nodes, the response time of SaaS software can be calculated by aggregating the response time of each service on each deployment node [7]. Let nk be a deployment node, and the VM type of nk is vnk whose computing power is CPvnk. Si is any service that composes the SaaS software SS, and there is at least one instance of service Si deployed on nk (denoted as si,k). According to the Utilization Law [8], the utilization of service instance si,k to its deployment node nk can be calculated by the throughput of si,k and the actual time requirement of si,k processing a request on nk as follows:(1)Unk,si,k=Tnk,si,k×TRSiCPvnk=qi×pi,k×T×TRSiCPvnk,where Tnk,si,k is the throughput of instance si,k, T is the throughput of SS, qi is the invocation probability of service Si, pi,k is the workload proportion of instance si,k, i.e., the proportion of the workload assigned for si,k to the workload of Si, and TRSi is the time requirement of Si on a node with unit computing resource. Then, the utilization of nk (denoted as Unk) can be calculated by the sum of the utilization of each service instance deployed on nk:(2)Unk=∑Si∈DSnkqi×pi,k×T×TRSiCPvnk,where DSnk is the service type set of service instances that are deployed on nk.According to existing research on performance based on queueing theory, each deployment nodenk can be modelled as an M/M/1 queue with a service centre that has CPvnk computing power and serves the requests in the processor-sharing (PS) discipline, and the interarrival time of requests and the service time requirement follow exponential distribution [9, 10]. Then, the response time of each service instance si,k on nk (denoted as Rnk,si,k) can be calculated from the request arrival rate of si,k on nk (denoted as λnk,si,k) and the average request processing rate of si,k on nk (denoted as μnk,si,k) as follows [11]:(3)Rnk,si,k=1μnk,si,k−λnk,si,k,where λnk,si,k is approximately equal to Tnk,si,k in the balanced status and μnk,si,k can be calculated by dividing the amount of computing resources of nk available to the service instance si,k by the time requirement of service Si processing a request with unit computing resource as follows:(4)μnk,si,k=CPvnk×1−Unk+Unk,si,kTRSi.Therefore, according to equations (1), (2), and (4), equation (3) can be expressed as follows:(5)Rnk,si,k=TRSiCPvnk×1−Unk.Then, the response time of serviceSi (denoted as RSi) can be calculated according to the response times of the corresponding service instances as follows:(6)RSi=∑nk∈DNSipi,k×Rnk,si,k,where DNSi is the set of deployment nodes on which the instances of Si are deployed.Finally, the response time of the entire software can be calculated by aggregating the response time of each service with the corresponding invocation probability as follows:(7)RSS=∑k=1N∑Si∈DSnkqi×pi,k×TRSiCPvnk−T×∑Si∈DSnkqi×pi,k×TRSi,where N is the total number of deployment nodes.After scaling out the software, the response time of the software in the newly generated deployment scheme can also be calculated by equation (7). Therefore, based on equation (7), we can further analyse the relationship between scaling-out operations of software and variation of response time in the next subsection.


### 3.2. Analysing the Variation of Response Time with the Scaling-Out Operation

For ease of description, the following definitions are given first.Definition 2.
(Response-Time Contribution of Service Instance). Letsi,k (deployed on deployment node nk) be an instance of service Si in SaaS software SS, and then, the response time of si,k is Rnk,si,k, which is called the response time contribution of service instance si,k to response time of SS.Definition 3.
(Response-Time Contribution of the Deployment Node). LetDSnk be the service type set of service instances deployed on deployment node nk, and then, the response time contribution of deployment node nk (denoted as Rnk) means the sum of the response time contribution of each service instance on nk, which can be calculated as follows:(8)Rnk=∑Si∈DSnkqi×pi,k×TRSiCPvnk−T×∑Si∈DSnkqi×pi,k×TRSi.
Based on Definition3, the response time of the SaaS software can be seen as the aggregation of the response time contribution of each deployment node in a deployment scheme, as well as the response time after scaling out the software. Assume that, in deployment scheme Dinit, service Si has n instances deployed on nodes nk1,nk2,…,nkm,…,nkn, respectively (the instances are denoted as si,k1,si,k2,…,si,km,…,si,kn, correspondingly, and we call them existing instances of Si). Now, we perform a scaling-out operation according to Definition 1, and then, a new service instance of Si is deployed on node nt (this instance is denoted as si,t) and a new deployment scheme Dnew is generated. Comparing the response time contribution of nodes in Dnew with that in Dinit, we can see that only the response time contribution of the nodes on which the instances of Si are deployed are varied, i.e., the impact of the scaling-out operation on response time is just from the variation of response time contribution of nk1,nk2,…,nkm,…,nkn and nt. Hence, in the following part, we will focus on analysing the impact of the scaling-out operation on response time contribution of these nodes.


#### 3.2.1. The Impact of the Scaling-Out Operation on Response Time Contribution of Nodesnk1,…,nkm,…nkn

In deployment schemeDinit, based on equation (8), the response time contribution of any of these nodes nkm (denoted as Rinitnkm) can be calculated as follows:(9)Rinitnkm=∑Su∈DSnkmqu×pu,km×TRSuCPvnkm−T×∑Su∈DSnkmqu×pu,km×TRSu,where Su represents the service type of instance deployed on node nkm including Si, and equation (9) can be expressed as follows:(10)Rinitnkm=∑So∈DSnkm∩So≠Siqo×po,km×TRSo+qi×pi,km×TRSiCPvnkm−T×∑So∈DSnkm∩So≠Siqo×po,km×TRSo−T×qi×pi,km×TRSi,where So represents the service type (other than Si) of instance deployed on node nkm, qo is the invocation probability of So, po,km is the workload proportion of instance of So deployed on nkm, and TRSo is the time requirement of So.After deployingsi,t on nt, since in deployment scheme Dnew the instance number of service Si changed from n to n+1, the workload proportion of instance si,km on nkm (i.e., pi,km) will decrease (we denoted it as pi,km′ in Dnew):(11)pi,km′<pi,km.Therefore, similar to equation (10), in Dnew the response time contribution of node nkm (denoted as Rnewnkm) can be expressed as follows:(12)Rnewnkm=∑So∈DSnkm∩So≠Siqo×po,km×TRSo+qi×pi,km′×TRSiCPvnkm−T×∑So∈DSnkm∩So≠Siqo×po,km×TRSo−T×qi×pi,km′×TRSi.Comparing equation (12) with equation (10) and according to equation (11), we can obtain the conclusion that Rnewnkm<Rinitnkm, which means that the response time contribution of node nkm will decrease after the scaling-out operation.Similarly, we can obtain the conclusion that the response time contribution of nodesnk1,nk2,…,nkm,…,nkn will all decrease after the scaling-out operation.We combine the example of SaaS software shown in Figure1 and the initial deployment scheme shown in Figure 3 to further explain the abovementioned analysis conclusion. For instance, we consider a scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew, i.e., adding an instance for service S5 (s5,1) and deploying it to node n1 through the scaling-out operation SO. Since before the scaling-out operation there exist two instances of S5, i.e., s5,2 on node n2 and s5,4 on node n4, according to the abovementioned analysis, the response time contribution of node n2 and n4 will decrease after the scaling-out operation.


#### 3.2.2. The Impact of the Scaling-Out Operation on Response Time Contribution of Nodent

Based on equation (8), in deployment scheme Dinit, the response time contribution of node nt (denoted as Rinitnt) can be calculated as follows:(13)Rinitnt=∑Sv∈DSntqv×pv,t×TRSvCPvnt−T×∑Sv∈DSntqv×pv,t×TRSv.After deployingsi,t on nt, the response time contribution of node nt in Dnew (denoted as Rnewnt) can be calculated as follows:(14)Rnewnt=∑Sv∈DSnt∩Sv≠Siqv×pv,t×TRSv+qi×pi,t×TRSiCPvnt−T×∑Sv∈DSnt∩Sv≠Siqv×pv,t×TRSv−T×qi×pi,t×TRSi.Comparing equation (14) with (13), we can obtain the conclusion that Rnewnt>Rinitnt, which means that the response time contribution of node nt will increase after the scaling-out operation.We also combine the example in Figure1 to further explain the abovementioned analysis conclusion. We still consider the scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew. Since the operation adds a new instance s5,1 to node n1, according to the abovementioned analysis, the response time contribution of node n1 will increase after the operation.To conclude, we can see that a scaling-out operation will decrease the response time contribution of the nodes where the instances ofSi already exist before the operation, which makes a positive influence on the response time improvement of the software, while it will also increase the response time contribution of the node where the new instance of Si is deployed, which makes a negative influence on the response time improvement of the software. If a SaaS provider can perform a series of scaling-out operations to make the positive influence larger than the negative influence, the response time of the software can be effectively improved.In the next subsection, we will further give an approach of scaling out software for response time improvement based on the abovementioned analysis conclusions.


### 3.3. Response Time Improvement Based on Scaling Out Software

According to the analysis in Section3.2, it can be seen that scaling out SaaS software without additional deployment resources will lead to both positive and negative influences on response time improvement of SaaS software. Therefore, to effectively improve the response time by scaling out software, we should determine a series of appropriate scaling-out operations that can make a positive influence on the response time of the software larger than the negative influence. For ease of description, first, we give the following theorem.Theorem 1.
LetSi be one of the services that constitute the SaaS software SS, and there are n existing instances of Si deployed on deployment nodes nk1,…,nkm,…nkn (denoted as si,k1,si,k2,…,si,km,…,si,kn) in deployment scheme Dinit. We execute a scaling-out operation SO=Dinit,SS,Si,Actsi,t,nt,Dnew, and then, the response time of SS can be improved if the judgment metric ΔJSO>0, where(15)ΔJSO=pi,km−pi.km′pi,t×∑m=1nCPvnt×1−UDinitnt×1−UDnewntCPvnkm1−UDinitnkm×1−UDnewnkm−1,in which CPvnkm and CPvnt are the computing power of node nkm and nt, respectively, UDinitnkm, UDinitnt, UDnewnkm, and UDnewnt are utilizations of node nkm and nt in Dinit and Dnew, respectively, pi,km and pi,km′ are the workload proportions of si,km in Dinit and Dnew, respectively, and pi,t is the workload proportion of si,t in Dnew.Proof.
LetRinitSS and RnewSS be the response time of SS in Dinit and Dnew, respectively. When the response time is improved after the scaling-out operation, the following inequality should be satisfied:(16)RnewSS<RinitSS.
LetRinitnkm and Rnewnkm be the response time contribution of node nkm in Dinit and Dnew, respectively, and let Rinitnt and Rnewnt be the response time contribution of node nt in Dinit and Dnew, respectively. According to the analysis conclusions in Section 3.2, since the response time contribution of nodes other than nk1,…,nkm,…nkn and nt is constant, inequality (16) can be transformed into(17)Rc+∑m=1nRnewnkm+Rnewnt<Rc+∑m=1nRinitnkm+Rinitnt,where Rc represents the sum of response time contribution of all nodes except nk1,…,nkm,…nkn and nt. Based on equations (2), (9), and (12)–(14), inequality (17) can be transformed into(18)pi,km−pi.km′pi,t×∑m=1nCPvnt×1−UDinitnt×1−UDnewntCPvnkm1−UDinitnkm×1−UDnewnkm−1>0.
Let(19)ΔJSO=pi,km−pi.km′pi,t×∑m=1nCPvnt×1−UDinitnt×1−UDnewntCPvnkm1−UDinitnkm×1−UDnewnkm−1.
Then, we can get the conclusion that the response time will be improved after the scaling-out operation ifΔJSO>0 is satisfied. Therefore, the theorem holds.
We further illustrate Theorem1 with the example in Figure 1 and the scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew. According to Theorem 1, we can calculate the judgment metric ΔJSO by equations (2) and (15). If ΔJSO>0, it indicates that the scaling-out operation SO can make a positive influence on the response time improvement larger than the negative influence, i.e., SO is a feasible operation which can improve the response time of the software effectively, while if ΔJSO≤0, it indicates that SO cannot improve the response time of the software.
Hence, for the given SaaS software, we perform a series of scaling-out operations that satisfy Theorem1, and then, the response time of the software can be effectively improved. Based on the abovementioned analysis conclusions, Algorithm 1 presents the main process of scaling out SaaS software for improving response time. The algorithm searches multiple feasible scaling-out operations in order to constitute an operation series. Besides, the algorithm will find a relatively optimal operation series through multiple iterations.
The time complexity of Algorithm1: the time complexity of the proposed algorithm depends on the number of searching the operation series and the number of searching the feasible operations that constitute the operation series. If the number of searching the operation series is i and for each operation series the number of searching the feasible operations is l, then the time complexity of the algorithm is O(il).Algorithm 1: Scaling out SaaS software for response time improvement.
Input: SaaS SoftwareSS, initial deployment scheme DinitOutput: a series of scaling-out operationsSO_Series=SO1,…,SOl,…SOx, which makes the response time of SS better than in Dinit(1)
whilei≤maxIterationdo(2)
Dold⟵Dinit(3)
operationSearchFlag⟵true(4)
l⟵1(5)
whileoperationSearchFlag = truedo(6)
Select a type of serviceSi in SS(7)
Construct a scaling-out operationSOl=Dold,SS,Si,Actsi,t,nt,Dnew /∗The operation will add an instance si,t for Si and deploy it on node nt∗/(8)
Calculate the judgment metricΔJSOl for SOl /∗Using equations (2) and (15)∗/(9)
ifΔJSOl>0do(10)
SO_Seriestmpl⟵SOl /∗Add the operation SOl to the operation series SO_Seriestmp∗/(11)
l⟵l+1(12)
Dold⟵Dnew(13)
end if(14)
if there are other possible scaling-out operations do(15)
operationSearchFlag⟵true(16)
else(17)
operationSearchFlag⟵false(18)
end if(19)
end while(20)
CalculateRSS after executing operation series SO_Seriestmp/∗Using equation (7)∗/(21)
ifRSS<RbestSSdo(22)
SO_Series⟵SO_Seriestmp /∗Update the optimal operation series SO_Series with current series SO_Seriestmp∗/(23)
RbestSS⟵RSS(24)
end if(25)
i⟵i+1(26)
end while(27)
returnSO_Series


## 3.1. Evaluation of SaaS Software Response Time

Since the SaaS software consists of a series of services that are deployed on multiple deployment nodes, the response time of SaaS software can be calculated by aggregating the response time of each service on each deployment node [7]. Let nk be a deployment node, and the VM type of nk is vnk whose computing power is CPvnk. Si is any service that composes the SaaS software SS, and there is at least one instance of service Si deployed on nk (denoted as si,k). According to the Utilization Law [8], the utilization of service instance si,k to its deployment node nk can be calculated by the throughput of si,k and the actual time requirement of si,k processing a request on nk as follows:(1)Unk,si,k=Tnk,si,k×TRSiCPvnk=qi×pi,k×T×TRSiCPvnk,where Tnk,si,k is the throughput of instance si,k, T is the throughput of SS, qi is the invocation probability of service Si, pi,k is the workload proportion of instance si,k, i.e., the proportion of the workload assigned for si,k to the workload of Si, and TRSi is the time requirement of Si on a node with unit computing resource. Then, the utilization of nk (denoted as Unk) can be calculated by the sum of the utilization of each service instance deployed on nk:(2)Unk=∑Si∈DSnkqi×pi,k×T×TRSiCPvnk,where DSnk is the service type set of service instances that are deployed on nk.According to existing research on performance based on queueing theory, each deployment nodenk can be modelled as an M/M/1 queue with a service centre that has CPvnk computing power and serves the requests in the processor-sharing (PS) discipline, and the interarrival time of requests and the service time requirement follow exponential distribution [9, 10]. Then, the response time of each service instance si,k on nk (denoted as Rnk,si,k) can be calculated from the request arrival rate of si,k on nk (denoted as λnk,si,k) and the average request processing rate of si,k on nk (denoted as μnk,si,k) as follows [11]:(3)Rnk,si,k=1μnk,si,k−λnk,si,k,where λnk,si,k is approximately equal to Tnk,si,k in the balanced status and μnk,si,k can be calculated by dividing the amount of computing resources of nk available to the service instance si,k by the time requirement of service Si processing a request with unit computing resource as follows:(4)μnk,si,k=CPvnk×1−Unk+Unk,si,kTRSi.Therefore, according to equations (1), (2), and (4), equation (3) can be expressed as follows:(5)Rnk,si,k=TRSiCPvnk×1−Unk.Then, the response time of serviceSi (denoted as RSi) can be calculated according to the response times of the corresponding service instances as follows:(6)RSi=∑nk∈DNSipi,k×Rnk,si,k,where DNSi is the set of deployment nodes on which the instances of Si are deployed.Finally, the response time of the entire software can be calculated by aggregating the response time of each service with the corresponding invocation probability as follows:(7)RSS=∑k=1N∑Si∈DSnkqi×pi,k×TRSiCPvnk−T×∑Si∈DSnkqi×pi,k×TRSi,where N is the total number of deployment nodes.After scaling out the software, the response time of the software in the newly generated deployment scheme can also be calculated by equation (7). Therefore, based on equation (7), we can further analyse the relationship between scaling-out operations of software and variation of response time in the next subsection.


## 3.2. Analysing the Variation of Response Time with the Scaling-Out Operation

For ease of description, the following definitions are given first.Definition 2.
(Response-Time Contribution of Service Instance). Letsi,k (deployed on deployment node nk) be an instance of service Si in SaaS software SS, and then, the response time of si,k is Rnk,si,k, which is called the response time contribution of service instance si,k to response time of SS.Definition 3.
(Response-Time Contribution of the Deployment Node). LetDSnk be the service type set of service instances deployed on deployment node nk, and then, the response time contribution of deployment node nk (denoted as Rnk) means the sum of the response time contribution of each service instance on nk, which can be calculated as follows:(8)Rnk=∑Si∈DSnkqi×pi,k×TRSiCPvnk−T×∑Si∈DSnkqi×pi,k×TRSi.
Based on Definition3, the response time of the SaaS software can be seen as the aggregation of the response time contribution of each deployment node in a deployment scheme, as well as the response time after scaling out the software. Assume that, in deployment scheme Dinit, service Si has n instances deployed on nodes nk1,nk2,…,nkm,…,nkn, respectively (the instances are denoted as si,k1,si,k2,…,si,km,…,si,kn, correspondingly, and we call them existing instances of Si). Now, we perform a scaling-out operation according to Definition 1, and then, a new service instance of Si is deployed on node nt (this instance is denoted as si,t) and a new deployment scheme Dnew is generated. Comparing the response time contribution of nodes in Dnew with that in Dinit, we can see that only the response time contribution of the nodes on which the instances of Si are deployed are varied, i.e., the impact of the scaling-out operation on response time is just from the variation of response time contribution of nk1,nk2,…,nkm,…,nkn and nt. Hence, in the following part, we will focus on analysing the impact of the scaling-out operation on response time contribution of these nodes.


### 3.2.1. The Impact of the Scaling-Out Operation on Response Time Contribution of Nodesnk1,…,nkm,…nkn

In deployment schemeDinit, based on equation (8), the response time contribution of any of these nodes nkm (denoted as Rinitnkm) can be calculated as follows:(9)Rinitnkm=∑Su∈DSnkmqu×pu,km×TRSuCPvnkm−T×∑Su∈DSnkmqu×pu,km×TRSu,where Su represents the service type of instance deployed on node nkm including Si, and equation (9) can be expressed as follows:(10)Rinitnkm=∑So∈DSnkm∩So≠Siqo×po,km×TRSo+qi×pi,km×TRSiCPvnkm−T×∑So∈DSnkm∩So≠Siqo×po,km×TRSo−T×qi×pi,km×TRSi,where So represents the service type (other than Si) of instance deployed on node nkm, qo is the invocation probability of So, po,km is the workload proportion of instance of So deployed on nkm, and TRSo is the time requirement of So.After deployingsi,t on nt, since in deployment scheme Dnew the instance number of service Si changed from n to n+1, the workload proportion of instance si,km on nkm (i.e., pi,km) will decrease (we denoted it as pi,km′ in Dnew):(11)pi,km′<pi,km.Therefore, similar to equation (10), in Dnew the response time contribution of node nkm (denoted as Rnewnkm) can be expressed as follows:(12)Rnewnkm=∑So∈DSnkm∩So≠Siqo×po,km×TRSo+qi×pi,km′×TRSiCPvnkm−T×∑So∈DSnkm∩So≠Siqo×po,km×TRSo−T×qi×pi,km′×TRSi.Comparing equation (12) with equation (10) and according to equation (11), we can obtain the conclusion that Rnewnkm<Rinitnkm, which means that the response time contribution of node nkm will decrease after the scaling-out operation.Similarly, we can obtain the conclusion that the response time contribution of nodesnk1,nk2,…,nkm,…,nkn will all decrease after the scaling-out operation.We combine the example of SaaS software shown in Figure1 and the initial deployment scheme shown in Figure 3 to further explain the abovementioned analysis conclusion. For instance, we consider a scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew, i.e., adding an instance for service S5 (s5,1) and deploying it to node n1 through the scaling-out operation SO. Since before the scaling-out operation there exist two instances of S5, i.e., s5,2 on node n2 and s5,4 on node n4, according to the abovementioned analysis, the response time contribution of node n2 and n4 will decrease after the scaling-out operation.


### 3.2.2. The Impact of the Scaling-Out Operation on Response Time Contribution of Nodent

Based on equation (8), in deployment scheme Dinit, the response time contribution of node nt (denoted as Rinitnt) can be calculated as follows:(13)Rinitnt=∑Sv∈DSntqv×pv,t×TRSvCPvnt−T×∑Sv∈DSntqv×pv,t×TRSv.After deployingsi,t on nt, the response time contribution of node nt in Dnew (denoted as Rnewnt) can be calculated as follows:(14)Rnewnt=∑Sv∈DSnt∩Sv≠Siqv×pv,t×TRSv+qi×pi,t×TRSiCPvnt−T×∑Sv∈DSnt∩Sv≠Siqv×pv,t×TRSv−T×qi×pi,t×TRSi.Comparing equation (14) with (13), we can obtain the conclusion that Rnewnt>Rinitnt, which means that the response time contribution of node nt will increase after the scaling-out operation.We also combine the example in Figure1 to further explain the abovementioned analysis conclusion. We still consider the scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew. Since the operation adds a new instance s5,1 to node n1, according to the abovementioned analysis, the response time contribution of node n1 will increase after the operation.To conclude, we can see that a scaling-out operation will decrease the response time contribution of the nodes where the instances ofSi already exist before the operation, which makes a positive influence on the response time improvement of the software, while it will also increase the response time contribution of the node where the new instance of Si is deployed, which makes a negative influence on the response time improvement of the software. If a SaaS provider can perform a series of scaling-out operations to make the positive influence larger than the negative influence, the response time of the software can be effectively improved.In the next subsection, we will further give an approach of scaling out software for response time improvement based on the abovementioned analysis conclusions.


## 3.2.1. The Impact of the Scaling-Out Operation on Response Time Contribution of Nodesnk1,…,nkm,…nkn

In deployment schemeDinit, based on equation (8), the response time contribution of any of these nodes nkm (denoted as Rinitnkm) can be calculated as follows:(9)Rinitnkm=∑Su∈DSnkmqu×pu,km×TRSuCPvnkm−T×∑Su∈DSnkmqu×pu,km×TRSu,where Su represents the service type of instance deployed on node nkm including Si, and equation (9) can be expressed as follows:(10)Rinitnkm=∑So∈DSnkm∩So≠Siqo×po,km×TRSo+qi×pi,km×TRSiCPvnkm−T×∑So∈DSnkm∩So≠Siqo×po,km×TRSo−T×qi×pi,km×TRSi,where So represents the service type (other than Si) of instance deployed on node nkm, qo is the invocation probability of So, po,km is the workload proportion of instance of So deployed on nkm, and TRSo is the time requirement of So.After deployingsi,t on nt, since in deployment scheme Dnew the instance number of service Si changed from n to n+1, the workload proportion of instance si,km on nkm (i.e., pi,km) will decrease (we denoted it as pi,km′ in Dnew):(11)pi,km′<pi,km.Therefore, similar to equation (10), in Dnew the response time contribution of node nkm (denoted as Rnewnkm) can be expressed as follows:(12)Rnewnkm=∑So∈DSnkm∩So≠Siqo×po,km×TRSo+qi×pi,km′×TRSiCPvnkm−T×∑So∈DSnkm∩So≠Siqo×po,km×TRSo−T×qi×pi,km′×TRSi.Comparing equation (12) with equation (10) and according to equation (11), we can obtain the conclusion that Rnewnkm<Rinitnkm, which means that the response time contribution of node nkm will decrease after the scaling-out operation.Similarly, we can obtain the conclusion that the response time contribution of nodesnk1,nk2,…,nkm,…,nkn will all decrease after the scaling-out operation.We combine the example of SaaS software shown in Figure1 and the initial deployment scheme shown in Figure 3 to further explain the abovementioned analysis conclusion. For instance, we consider a scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew, i.e., adding an instance for service S5 (s5,1) and deploying it to node n1 through the scaling-out operation SO. Since before the scaling-out operation there exist two instances of S5, i.e., s5,2 on node n2 and s5,4 on node n4, according to the abovementioned analysis, the response time contribution of node n2 and n4 will decrease after the scaling-out operation.


## 3.2.2. The Impact of the Scaling-Out Operation on Response Time Contribution of Nodent

Based on equation (8), in deployment scheme Dinit, the response time contribution of node nt (denoted as Rinitnt) can be calculated as follows:(13)Rinitnt=∑Sv∈DSntqv×pv,t×TRSvCPvnt−T×∑Sv∈DSntqv×pv,t×TRSv.After deployingsi,t on nt, the response time contribution of node nt in Dnew (denoted as Rnewnt) can be calculated as follows:(14)Rnewnt=∑Sv∈DSnt∩Sv≠Siqv×pv,t×TRSv+qi×pi,t×TRSiCPvnt−T×∑Sv∈DSnt∩Sv≠Siqv×pv,t×TRSv−T×qi×pi,t×TRSi.Comparing equation (14) with (13), we can obtain the conclusion that Rnewnt>Rinitnt, which means that the response time contribution of node nt will increase after the scaling-out operation.We also combine the example in Figure1 to further explain the abovementioned analysis conclusion. We still consider the scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew. Since the operation adds a new instance s5,1 to node n1, according to the abovementioned analysis, the response time contribution of node n1 will increase after the operation.To conclude, we can see that a scaling-out operation will decrease the response time contribution of the nodes where the instances ofSi already exist before the operation, which makes a positive influence on the response time improvement of the software, while it will also increase the response time contribution of the node where the new instance of Si is deployed, which makes a negative influence on the response time improvement of the software. If a SaaS provider can perform a series of scaling-out operations to make the positive influence larger than the negative influence, the response time of the software can be effectively improved.In the next subsection, we will further give an approach of scaling out software for response time improvement based on the abovementioned analysis conclusions.


## 3.3. Response Time Improvement Based on Scaling Out Software

According to the analysis in Section3.2, it can be seen that scaling out SaaS software without additional deployment resources will lead to both positive and negative influences on response time improvement of SaaS software. Therefore, to effectively improve the response time by scaling out software, we should determine a series of appropriate scaling-out operations that can make a positive influence on the response time of the software larger than the negative influence. For ease of description, first, we give the following theorem.Theorem 1.
LetSi be one of the services that constitute the SaaS software SS, and there are n existing instances of Si deployed on deployment nodes nk1,…,nkm,…nkn (denoted as si,k1,si,k2,…,si,km,…,si,kn) in deployment scheme Dinit. We execute a scaling-out operation SO=Dinit,SS,Si,Actsi,t,nt,Dnew, and then, the response time of SS can be improved if the judgment metric ΔJSO>0, where(15)ΔJSO=pi,km−pi.km′pi,t×∑m=1nCPvnt×1−UDinitnt×1−UDnewntCPvnkm1−UDinitnkm×1−UDnewnkm−1,in which CPvnkm and CPvnt are the computing power of node nkm and nt, respectively, UDinitnkm, UDinitnt, UDnewnkm, and UDnewnt are utilizations of node nkm and nt in Dinit and Dnew, respectively, pi,km and pi,km′ are the workload proportions of si,km in Dinit and Dnew, respectively, and pi,t is the workload proportion of si,t in Dnew.Proof.
LetRinitSS and RnewSS be the response time of SS in Dinit and Dnew, respectively. When the response time is improved after the scaling-out operation, the following inequality should be satisfied:(16)RnewSS<RinitSS.
LetRinitnkm and Rnewnkm be the response time contribution of node nkm in Dinit and Dnew, respectively, and let Rinitnt and Rnewnt be the response time contribution of node nt in Dinit and Dnew, respectively. According to the analysis conclusions in Section 3.2, since the response time contribution of nodes other than nk1,…,nkm,…nkn and nt is constant, inequality (16) can be transformed into(17)Rc+∑m=1nRnewnkm+Rnewnt<Rc+∑m=1nRinitnkm+Rinitnt,where Rc represents the sum of response time contribution of all nodes except nk1,…,nkm,…nkn and nt. Based on equations (2), (9), and (12)–(14), inequality (17) can be transformed into(18)pi,km−pi.km′pi,t×∑m=1nCPvnt×1−UDinitnt×1−UDnewntCPvnkm1−UDinitnkm×1−UDnewnkm−1>0.
Let(19)ΔJSO=pi,km−pi.km′pi,t×∑m=1nCPvnt×1−UDinitnt×1−UDnewntCPvnkm1−UDinitnkm×1−UDnewnkm−1.
Then, we can get the conclusion that the response time will be improved after the scaling-out operation ifΔJSO>0 is satisfied. Therefore, the theorem holds.
We further illustrate Theorem1 with the example in Figure 1 and the scaling-out operation SO=Dinit,SS,S5,Acts5,1,n1,Dnew. According to Theorem 1, we can calculate the judgment metric ΔJSO by equations (2) and (15). If ΔJSO>0, it indicates that the scaling-out operation SO can make a positive influence on the response time improvement larger than the negative influence, i.e., SO is a feasible operation which can improve the response time of the software effectively, while if ΔJSO≤0, it indicates that SO cannot improve the response time of the software.
Hence, for the given SaaS software, we perform a series of scaling-out operations that satisfy Theorem1, and then, the response time of the software can be effectively improved. Based on the abovementioned analysis conclusions, Algorithm 1 presents the main process of scaling out SaaS software for improving response time. The algorithm searches multiple feasible scaling-out operations in order to constitute an operation series. Besides, the algorithm will find a relatively optimal operation series through multiple iterations.
The time complexity of Algorithm1: the time complexity of the proposed algorithm depends on the number of searching the operation series and the number of searching the feasible operations that constitute the operation series. If the number of searching the operation series is i and for each operation series the number of searching the feasible operations is l, then the time complexity of the algorithm is O(il).Algorithm 1: Scaling out SaaS software for response time improvement.
Input: SaaS SoftwareSS, initial deployment scheme DinitOutput: a series of scaling-out operationsSO_Series=SO1,…,SOl,…SOx, which makes the response time of SS better than in Dinit(1)
whilei≤maxIterationdo(2)
Dold⟵Dinit(3)
operationSearchFlag⟵true(4)
l⟵1(5)
whileoperationSearchFlag = truedo(6)
Select a type of serviceSi in SS(7)
Construct a scaling-out operationSOl=Dold,SS,Si,Actsi,t,nt,Dnew /∗The operation will add an instance si,t for Si and deploy it on node nt∗/(8)
Calculate the judgment metricΔJSOl for SOl /∗Using equations (2) and (15)∗/(9)
ifΔJSOl>0do(10)
SO_Seriestmpl⟵SOl /∗Add the operation SOl to the operation series SO_Seriestmp∗/(11)
l⟵l+1(12)
Dold⟵Dnew(13)
end if(14)
if there are other possible scaling-out operations do(15)
operationSearchFlag⟵true(16)
else(17)
operationSearchFlag⟵false(18)
end if(19)
end while(20)
CalculateRSS after executing operation series SO_Seriestmp/∗Using equation (7)∗/(21)
ifRSS<RbestSSdo(22)
SO_Series⟵SO_Seriestmp /∗Update the optimal operation series SO_Series with current series SO_Seriestmp∗/(23)
RbestSS⟵RSS(24)
end if(25)
i⟵i+1(26)
end while(27)
returnSO_Series


## 4. Experiments and Analysis

In this section, we conduct experiments with a practical case to verify the theoretical analysis conclusions in the previous section.


### 4.1. Experimental Setup

The experimental case is a travel planning system, which is composed of several types of services (the structure is shown in Figure5). Service S1 counts the most popular places. Service S2, S3, and S4 recommend a set of travel places for customers according to different conditions. Service S2 selects travel places within the most popular places based on the acceptable price of customer. Service S3 selects travel places based on the place popularity. Service S4 selects travel places both considering the price and the popularity of places. The invocation probabilities of S2, S3, and S4 are 0.3, 0.3, and 0.4, respectively. Service S5 plans the best travel route for the trip, and service S6 arranges the luggage for customers.Figure 5
The structure of the experimental case.The deployment nodes for the experimental case are provided by an experimental environment implemented by the server equipped with Intel Core i5-6500 CPU @ 3.60 GHz and 16 GB DDR4 RAM. Each node is a VM running Ubuntu Server 14.04 LTS. The initial deployment scheme (denoted asDinit) of the experimental case is shown in Figure 6, which presents the distribution of service instances in the experimental case on these nodes.Figure 6
The initial deployment scheme of the experimental case.


### 4.2. Analysis and Verification of the Impact of the Scaling-Out Operation on Response Time

In this section, based on the initial deployment schemeDinit of the experimental case, we select the services in the experimental case to conduct three trials to analyse and verify the positive and negative influences of performing scaling-out operations on response time. In each trial, we execute a scaling-out operation by adding a new instance of S4 or S5 and deploy it on one of the nodes. The specific scaling-out operations are shown in Table 1. Then, we obtain the positive and negative influences of each scaling-out operation with our analysis method. In addition, during the experiments, the workload of service is assigned to each instance on average before and after scaling-out operations.Table 1
Scaling-out operations in trials.
TrialScaling-out operation1SO1=Dinit,SS,S4,Acts4,1,n1,Dnew12SO2=Dinit,SS,S5,Acts5,1,n1,Dnew23SO3=Dinit,SS,S5,Acts5,2,n2,Dnew3The experimental results are shown in Table2. In the table, Rinit and Rnew are the response time of the experimental case before and after scaling-out operations, respectively. The positive influence represents the decreased value of response time contribution of nodes where existing instances of S4 and S5 are deployed after scaling-out operations, while the negative influence represents the increased value of response time contribution of nodes where new instances of S4 and S5 are deployed after scaling-out operations.Table 2
Experimental results of verifying the impact of scaling-out operations on response time.
TrialRinitsRnewsPositive influence (s)Negative influence (s)ΔJ10.81100.92090.02030.1303−0.844220.81100.69400.32300.20600.567730.81100.52240.32300.03448.3780As we can see from the results, the scaling-out operation in trial 1 makes a negative influence larger than the positive influence, which means that the response time after the scaling-out operation becomes longer than before, so it is not a feasible scaling-out operation, while the scaling-out operations in trials 2 and 3 can make a negative influence less than the positive influence, so they are feasible scaling-out operations for improving the response time of the experimental case. Besides, the positive influences of scaling-out operations in trials 2 and 3 are the same, and it is because the positive influences all come from noden3, and in trials 2 and 3, the changes of the workload proportion of instance s5,3 deployed on n3 are the same due to the workload-balancing strategy.Moreover, Table2 also presents the value of the judgment metric ΔJ mentioned in Theorem 1 for each scaling-out operation. When ΔJ>0 (in trials 2 and 3), the entire response time of the experimental case is reduced after executing the corresponding scaling-out operation, and vice versa (in trial 1). Therefore, the judgment metric ΔJ can correctly reflect whether the corresponding scaling-out operation can improve the response time of the experimental case, which can also verify the effectiveness of Theorem 1. Moreover, comparing trials 2 and 3, the larger the value of ΔJ, the better the improvement in response time, which illustrates that ΔJ can also reflect the improvement degree in response time.


### 4.3. Analysis and Verification of the Algorithm of Scaling Out Software

In this section, we conduct experiments to further verify the effectiveness of the proposed algorithm in response time improvement through scaling out the experimental case without additional deployment nodes. For the purpose of demonstrating the effectiveness of the algorithm on the experimental case in different configurations of deployment resources, we conduct three groups of experiments. In group 1, we use the configuration of deployment resources shown in Figure6, and based on group 1, we generate the configurations in group 2 and group 3, as shown in Table 3.Table 3
Experimental groups of verifying the algorithm of scaling out software.
GroupComputing power of each nodeThe number of nodesTotal computing powern1n2n3n41121—342122—353121145During the experiments, for each time, we select a type of service to perform a feasible scaling-out operation according to Theorem1. We iterate the abovementioned step until there is no possible scaling-out operation to improve the response time and then terminate the experiments. The first and final deployment schemes are denoted as Dinit and Dfinal. To compare the effectiveness of our algorithm in different groups, for each group, we have recorded the response times of the experimental case under Dinit and Dfinal, including the response times obtained from our analysis method (denoted as RaDinit and RaDfinal, respectively) and the response times actually measured from the experimental environment (denoted as RmDinit and RmDfinal, respectively), as shown in Figure 7.Figure 7
Results of experiments of verifying the algorithm of scaling out software.The improvement degree in response time brought by the algorithm (calculated byRmDinit−RmDfinal/RmDinit·100%) in the three experimental groups is 45.5%, 20.3%, and 27.4%, respectively. The average relative error of Ra compared to Rm (calculated by Ra−Rm/Rm·100%) is generally less than 8%, and according to the experimental results, the accuracy is acceptable for finding feasible scaling operations in order to improve the response time of the experimental case. Specifically, when the initial response time of the experimental case is relatively long (group 1 and group 3), the algorithm can bring a relatively large improvement degree of response time. Even if the initial response time in group 2 is not as long as that in the other two groups, the response time is further improved by scaling out the experimental case. Therefore, the experiments illustrate that the conclusions of impact analysis and the proposed algorithm can help improve the response time effectively by scaling out software in different configurations of deployment resources, even without additional deployment nodes.


### 4.4. Analysis of the Statistical Significance of Our Method in Improving Response Time

With the aim of verifying whether the effectiveness of our method in improving the response time of the experimental case is statistically significant, in this section, we further conduct more simulation experiments and perform statistical hypothesis testing to make extensive evaluation of our method. Specifically, based on the experimental case in Figure5, we conduct three groups of experiments with three different number of initial service instances. Besides, in each group, we also conduct experiments with three different invocation probabilities of services, two different request arrival rates, and two different deployment configurations, i.e., we conduct a total of 36 different experiments.During the experiments, according to the response times before and after executing scaling-out operations found by our method, we conduct the pairedt-test to verify whether the response times of the experimental case after executing the scaling-out operations are significantly different from the initial response times. We consider two different hypotheses as follows:(i)
H0: there is no difference between the response times after executing scaling-out operations and the initial response times(ii)
H1: there is a difference between the response times after executing scaling-out operations and the initial response timesThe results of the pairedt-test are shown in Table 4, which presents the significance level of the improved response times compared to the initial response times. Concretely, the table shows the number of tests in each group, the degrees of freedom (df), the standard deviation differences (SD) and the mean of differences of the improved response times with the initial response times, the t value, and the p value.Table 4
Results of the pairedt-test.
The number of initial service instancesThe number of testsdfSDMean of differencest valuep value1012110.09170.332312.55527.30× 10−081512110.07860.17837.85827.74× 10−062012110.01670.107322.26101.69× 10−10Generally, for a pairedt-test, the significance level is defined as p<0.05, i.e., if the p value is less than 0.05, we should reject the null hypothesis (H0) and accept the alternative hypothesis (H1). As shown in Table 4, the p value in each group is less than 0.05, so the null hypothesis (H0) is rejected and the alternative hypothesis (H1) is acceptable, which means that the differences between the improved response times and the initial response times are significant, allowing us to conclude that the effectiveness of our method in improving the response time of the experimental case is statistically significant.


## 4.1. Experimental Setup

The experimental case is a travel planning system, which is composed of several types of services (the structure is shown in Figure5). Service S1 counts the most popular places. Service S2, S3, and S4 recommend a set of travel places for customers according to different conditions. Service S2 selects travel places within the most popular places based on the acceptable price of customer. Service S3 selects travel places based on the place popularity. Service S4 selects travel places both considering the price and the popularity of places. The invocation probabilities of S2, S3, and S4 are 0.3, 0.3, and 0.4, respectively. Service S5 plans the best travel route for the trip, and service S6 arranges the luggage for customers.Figure 5
The structure of the experimental case.The deployment nodes for the experimental case are provided by an experimental environment implemented by the server equipped with Intel Core i5-6500 CPU @ 3.60 GHz and 16 GB DDR4 RAM. Each node is a VM running Ubuntu Server 14.04 LTS. The initial deployment scheme (denoted asDinit) of the experimental case is shown in Figure 6, which presents the distribution of service instances in the experimental case on these nodes.Figure 6
The initial deployment scheme of the experimental case.


## 4.2. Analysis and Verification of the Impact of the Scaling-Out Operation on Response Time

In this section, based on the initial deployment schemeDinit of the experimental case, we select the services in the experimental case to conduct three trials to analyse and verify the positive and negative influences of performing scaling-out operations on response time. In each trial, we execute a scaling-out operation by adding a new instance of S4 or S5 and deploy it on one of the nodes. The specific scaling-out operations are shown in Table 1. Then, we obtain the positive and negative influences of each scaling-out operation with our analysis method. In addition, during the experiments, the workload of service is assigned to each instance on average before and after scaling-out operations.Table 1
Scaling-out operations in trials.
TrialScaling-out operation1SO1=Dinit,SS,S4,Acts4,1,n1,Dnew12SO2=Dinit,SS,S5,Acts5,1,n1,Dnew23SO3=Dinit,SS,S5,Acts5,2,n2,Dnew3The experimental results are shown in Table2. In the table, Rinit and Rnew are the response time of the experimental case before and after scaling-out operations, respectively. The positive influence represents the decreased value of response time contribution of nodes where existing instances of S4 and S5 are deployed after scaling-out operations, while the negative influence represents the increased value of response time contribution of nodes where new instances of S4 and S5 are deployed after scaling-out operations.Table 2
Experimental results of verifying the impact of scaling-out operations on response time.
TrialRinitsRnewsPositive influence (s)Negative influence (s)ΔJ10.81100.92090.02030.1303−0.844220.81100.69400.32300.20600.567730.81100.52240.32300.03448.3780As we can see from the results, the scaling-out operation in trial 1 makes a negative influence larger than the positive influence, which means that the response time after the scaling-out operation becomes longer than before, so it is not a feasible scaling-out operation, while the scaling-out operations in trials 2 and 3 can make a negative influence less than the positive influence, so they are feasible scaling-out operations for improving the response time of the experimental case. Besides, the positive influences of scaling-out operations in trials 2 and 3 are the same, and it is because the positive influences all come from noden3, and in trials 2 and 3, the changes of the workload proportion of instance s5,3 deployed on n3 are the same due to the workload-balancing strategy.Moreover, Table2 also presents the value of the judgment metric ΔJ mentioned in Theorem 1 for each scaling-out operation. When ΔJ>0 (in trials 2 and 3), the entire response time of the experimental case is reduced after executing the corresponding scaling-out operation, and vice versa (in trial 1). Therefore, the judgment metric ΔJ can correctly reflect whether the corresponding scaling-out operation can improve the response time of the experimental case, which can also verify the effectiveness of Theorem 1. Moreover, comparing trials 2 and 3, the larger the value of ΔJ, the better the improvement in response time, which illustrates that ΔJ can also reflect the improvement degree in response time.


## 4.3. Analysis and Verification of the Algorithm of Scaling Out Software

In this section, we conduct experiments to further verify the effectiveness of the proposed algorithm in response time improvement through scaling out the experimental case without additional deployment nodes. For the purpose of demonstrating the effectiveness of the algorithm on the experimental case in different configurations of deployment resources, we conduct three groups of experiments. In group 1, we use the configuration of deployment resources shown in Figure6, and based on group 1, we generate the configurations in group 2 and group 3, as shown in Table 3.Table 3
Experimental groups of verifying the algorithm of scaling out software.
GroupComputing power of each nodeThe number of nodesTotal computing powern1n2n3n41121—342122—353121145During the experiments, for each time, we select a type of service to perform a feasible scaling-out operation according to Theorem1. We iterate the abovementioned step until there is no possible scaling-out operation to improve the response time and then terminate the experiments. The first and final deployment schemes are denoted as Dinit and Dfinal. To compare the effectiveness of our algorithm in different groups, for each group, we have recorded the response times of the experimental case under Dinit and Dfinal, including the response times obtained from our analysis method (denoted as RaDinit and RaDfinal, respectively) and the response times actually measured from the experimental environment (denoted as RmDinit and RmDfinal, respectively), as shown in Figure 7.Figure 7
Results of experiments of verifying the algorithm of scaling out software.The improvement degree in response time brought by the algorithm (calculated byRmDinit−RmDfinal/RmDinit·100%) in the three experimental groups is 45.5%, 20.3%, and 27.4%, respectively. The average relative error of Ra compared to Rm (calculated by Ra−Rm/Rm·100%) is generally less than 8%, and according to the experimental results, the accuracy is acceptable for finding feasible scaling operations in order to improve the response time of the experimental case. Specifically, when the initial response time of the experimental case is relatively long (group 1 and group 3), the algorithm can bring a relatively large improvement degree of response time. Even if the initial response time in group 2 is not as long as that in the other two groups, the response time is further improved by scaling out the experimental case. Therefore, the experiments illustrate that the conclusions of impact analysis and the proposed algorithm can help improve the response time effectively by scaling out software in different configurations of deployment resources, even without additional deployment nodes.


## 4.4. Analysis of the Statistical Significance of Our Method in Improving Response Time

With the aim of verifying whether the effectiveness of our method in improving the response time of the experimental case is statistically significant, in this section, we further conduct more simulation experiments and perform statistical hypothesis testing to make extensive evaluation of our method. Specifically, based on the experimental case in Figure5, we conduct three groups of experiments with three different number of initial service instances. Besides, in each group, we also conduct experiments with three different invocation probabilities of services, two different request arrival rates, and two different deployment configurations, i.e., we conduct a total of 36 different experiments.During the experiments, according to the response times before and after executing scaling-out operations found by our method, we conduct the pairedt-test to verify whether the response times of the experimental case after executing the scaling-out operations are significantly different from the initial response times. We consider two different hypotheses as follows:(i)
H0: there is no difference between the response times after executing scaling-out operations and the initial response times(ii)
H1: there is a difference between the response times after executing scaling-out operations and the initial response timesThe results of the pairedt-test are shown in Table 4, which presents the significance level of the improved response times compared to the initial response times. Concretely, the table shows the number of tests in each group, the degrees of freedom (df), the standard deviation differences (SD) and the mean of differences of the improved response times with the initial response times, the t value, and the p value.Table 4
Results of the pairedt-test.
The number of initial service instancesThe number of testsdfSDMean of differencest valuep value1012110.09170.332312.55527.30× 10−081512110.07860.17837.85827.74× 10−062012110.01670.107322.26101.69× 10−10Generally, for a pairedt-test, the significance level is defined as p<0.05, i.e., if the p value is less than 0.05, we should reject the null hypothesis (H0) and accept the alternative hypothesis (H1). As shown in Table 4, the p value in each group is less than 0.05, so the null hypothesis (H0) is rejected and the alternative hypothesis (H1) is acceptable, which means that the differences between the improved response times and the initial response times are significant, allowing us to conclude that the effectiveness of our method in improving the response time of the experimental case is statistically significant.


## 5. Discussion

In the previous section, some experiments have been conducted to evaluate our study, which indicates that the analysis conclusions and the proposed algorithm derived from our study can effectively provide guidance for scaling out SaaS software and improving the response time. Our study is based on the queueing performance model, and its advantage is that it can be used for quantitatively analysing the positive and negative influences of scaling-out operations on the response time of the software in combination with the deployment resources, which can assist in subsequently making decisions for scaling out software with existing deployment resources instead of additional deployment resources. However, we also have identified some limitations. Our current study mainly models the performance of SaaS software, but in the deployment nodes, there also exist some performance interference factors outside of SaaS software, which may not be captured by the model and limit the effectiveness of analysing and improving the response time of software. In the future, we can extend our model to take these interference factors into account and further enhance the effectiveness of performance improvement.


## 6. Related Work

In the field of software performance, there are some works aiming to analyse and improve the performance of software and taking into account the scaling techniques. Vondra et al. [12] developed a new simulation tool based on the queueing model to autoscale VMs in the private cloud. Jiang et al. [13] proposed a novel scheme to autoscale cloud resources for web applications. Bouterse et al. [14] proposed a method to dynamically allocate VMs to provide reserved resources for scalable SaaS applications. These works mainly studied the scaling approaches in combination with resource provisioning. Besides, El Kafhali et al. [15] presented a queueing mathematical model to estimate the amount of VMs required for scaling software in order to satisfy the performance requirement. This work mainly studied the approach of adjusting the number of resources for scaling software.Some studies also considered the elasticity of resources to guarantee the performance of the scalable software. Salah et al. [16] presented an analytical model that can be used to guarantee proper elasticity for cloud-hosted applications and services, in order to satisfy particular performance requirements. Ghobaei-Arani et al. [17] presented a framework called ControCity for controlling resources elasticity through using buffer management and elasticity management by leveraging the learning automata technique. The aforementioned works mainly considered how to adjust the resources to meet the performance improvement requirement of the scalable software. However, how to specifically adjust and scale the software to improve performance also needs to be further studied.Zhen et al. [18] proposed a method to automatically scale cloud application instances. Wada et al. [7] presented a method to estimate and optimize the performance of services in a cloud environment by leveraging queueing theory, which considered the strategies of scaling cloud services. These works mainly require adjusting deployment resources while scaling software. Different from the abovementioned works, we aim to improve the response time of SaaS software based on scaling out software without additional adjustment of deployment resources. Therefore, in our work, we analysed both the positive and negative influences of scaling out SaaS software on response time, and based on the abovementioned foundation, we proposed an algorithm of scaling out SaaS software to improve the response time effectively while saving deployment resources.


## 7. Conclusions

In this paper, we defined the scaling-out operation of SaaS software and analysed the impact of the scaling-out operation on response time by leveraging queueing theory. The experiments showed that the analysis conclusions can be used to determine whether a scaling-out operation can effectively improve the response time of the software, which can be the basis of making decision for scaling out software. Based on the analysis conclusions, we further proposed an algorithm of scaling out SaaS software for response time improvement. The experiments demonstrated that the response time can be reduced effectively after scaling out the software with the proposed algorithm, which further illustrated that the analysis conclusions obtained from this paper can play a guiding role in scaling out software and improving response time while saving deployment resources. In the future, we will further explore how to apply the analysis conclusions to optimize the performance of SaaS software.



---

*Source: 6629867-2021-04-05.xml*