# Minimizing Resource Waste in Heterogeneous Resource Allocation for Data Stream Processing on Clouds
## 3 Minimizing Resource Gap
### MRG Algorithm  
To minimize the resource gap among the heterogeneity of resources, the MRG mechanism was proposed in this study. Initially, the possible resource wastage is calculated in the MRG algorithm when an application is launched. Then, the server with the smallest resource gap is determined to allocate resources to this application. Therefore, each server has a low resource wastage for the available but unused resources and the system utilization is enhanced. In this study, the set \(S\) of servers was \(\left\{\,S_{1},S_{2},\ldots,S_{s}\right\}\), and the set \(R\) of resources was \(\left\{\,R_{1},R_{2},\ldots,R_{r}\right\}\). Available resources of the server \(K\left(K\in S\right)\) are \(A_{KR}=\left\{\,A_{KR_{1}},\,A_{KR_{2}},\ldots,A_{KR_{r}}\right\}\). The application demand for resources is presented as the vector \(D=\left\{\,D_{R_{1}},D_{R_{2}},\ldots,D_{R_{r}}\right\}\). The MRG algorithm is invoked when the application demand is submitted for allocating available resources. First, the following is calculated in MGR:  
\[A^{\prime}=\left\{\,A_{KR_{i}}-D_{R_{i}}\right\},\qquad\forall i\in R \tag{1}\]  
This parameter is determined for calculating the remaining amount of resources if the algorithm allocates the candidate server \(K\) to the application. Then, the smallest \(A^{\prime}\) with \(A_{KR_{m}}\) is determined, which indicates that the resource \(R_{m}\) in server \(K\) is going to be depleted. All resource gaps in server \(K\) are then calculated in the MRG algorithm for determining the accumulated resource gap, denoted by \(ARG_{K}\), as follows:  
\[\sum_{i=R_{1},\,\,\,i\
eq R_{m}}^{R_{r}}(A^{\prime}_{KR_{i}}-A^{\prime}_{KR_{ m}}),\,\,\,\,\forall K\in S \tag{2}\]  
Figure 1: Differences between quantities of exhausted resources and remaining resources. Finally, the target server \(T_{S}\) with the smallest \(ARG\) is determined and this server is allocated to the application. The pseudo codes for the proposed MRG algorithm are shown in Figure 2.  
Figure 2: Pseudo codes for the proposed minimizing resource gap (MRG) algorithm. The following examples \(S_{1},\ S_{2},\ AP_{1},\ AP_{2}\) were applied to demonstrate the effectiveness of the proposed algorithm. When only two resources are available, Equation (2) is simplified to the following expression:  
\[\text{Min}\big{|}\big{(}A_{iR_{1}}-D_{R_{1}}\big{)}-\big{(}A_{iR_{2}}-D_{R_{2}} \big{)}\big{|},\ \ \ i\in(S_{1},S_{2}) \tag{3}\]  
Tables 1 and 2 list the examples to illustrate allocation steps when allocating resources for \(AP_{1}\) and \(AP_{2}\). When the resource is allocated to \(AP_{1}\), the \(ARG\) of \(S_{1}\) is \(\mid(4-2)-(2-1)\mid=1\) and the \(ARG\) of \(S_{2}\) is \(\mid(2-2)-(4-1)\mid=3\). Because \(S_{1}\) has a smaller \(ARG\), the MRG algorithm allocates \(AP_{1}\) to be on \(S_{1}\). When allocating resources for \(AP_{2}\), the \(ARG\) of \(S_{1}\) is \(\mid(4-1)-(2-2)\mid=3\), whereas the \(ARG\) of \(S_{2}\) is \(\mid(2-1)-(4-2)\mid=1\). Because \(S_{2}\) has a smaller \(ARG\), \(AP_{2}\) is allocated to \(S_{2}\). These examples show that the proposed algorithm can allocate resources effectively to prevent a high resource gap. To further demonstrate that MRG can reduce resource wastage for the available but unused resources, the proposed algorithm was compared with the default load-balanced algorithm in Apache Spark. In the default algorithm, the servers are allocated with the maximal free CPU cores to the application. Assume that \(S_{1}\) has resources \(R_{1}\), \(R_{2}\), and \(R_{3}\) with values of (4, 6, 8) and \(S_{2}\) has resources of \(R_{1}\), \(R_{2}\), and \(R_{3}\) with values of (8, 6, 4), respectively. The resource demands of \(AP_{1}\) is (1, 2, 3) and that of \(AP_{2}\) is (4, 3, 2). Suppose that these two applications are allocated one after another. Therefore, two cases are possible for the resource-allocation policy. The first case starts with the allocation step for \(AP_{2}\) and the other case starts with the allocation step for \(AP_{1}\).