{"id":389876,"date":"2025-09-01T18:26:19","date_gmt":"2025-09-01T18:26:19","guid":{"rendered":"https:\/\/www.europesays.com\/uk\/389876\/"},"modified":"2025-09-01T18:26:19","modified_gmt":"2025-09-01T18:26:19","slug":"crfts-a-cluster-centric-and-reservation-based-fault-tolerant-scheduling-strategy-to-enhance-qos-in-cloud-computing","status":"publish","type":"post","link":"https:\/\/www.europesays.com\/uk\/389876\/","title":{"rendered":"CRFTS: a cluster-centric and reservation-based fault-tolerant scheduling strategy to enhance QoS in cloud computing"},"content":{"rendered":"

This section explains the proposed CRFTS model, which uses a clustering approach for allocation and the advance reservation of VMs to handle the failure in a dynamic, computationally intensive cloud system. The proposed cluster-based allocation technique can be represented as a bipartite graph between the task set and VM set, as shown in Fig.\u00a01<\/a>. Additionally, the notions used are presented in Table\u00a03<\/a>. The System Model and Problem Formulation are illustrated in the subsection below. In this section, we introduced the fault-tolerant-based scheduling algorithm. The incoming tasks are represented as set T= {t1, t2, t3\u2026 tn} and the VMs are represented as set V= {v1, v2, v3\u2026 vk}. At any decision point (t), only subset Tk of T, i.e., Tk \u2286 T, is known. Since the entire task set T is unknown, the scheduler must make decisions without prior knowledge of tasks, which models the problem as online scheduling. The proposed scheduling assigns each arriving task to a VM based only on the current system state.<\/p>\n

Fig. 1<\/b>\"figure<\/a><\/p>\n

Clustered-allocation mapping strategy.<\/p>\n

System model<\/p>\n

The CRFTS system architecture includes several components, as illustrated in Fig.\u00a02<\/a>. User tasks are submitted to the Application Layer. Besides, in the cloud, the tasks may come from any geographical location at any point in time. The Task Sorter sorts the incoming tasks in ascending order of task size. Similarly, the Host\/VM Layer contains a variety of resources with varying processing abilities. VM Sorter sorts the available VMs in ascending order of their processing abilities. Additionally, the sorting of both tasks and VMs is followed by a clustering mechanism where both tasks and VMs are separated into three different clusters, i.e., low, mid, and high clusters, as discussed in the algorithm section. The clustering will further ensure the best-suited task and VM mapping by limiting the task and VM domain of mapping. Furthermore, the VM allocator is responsible for choosing the relevant VM from the cluster for task completion.<\/p>\n

Each VM periodically sends a simulated heartbeat signal at a fixed interval \u03b4. The heartbeat controller records the last received time Hj\u200b of the signal. If the difference between current time \u03c4 and Hj\u200b exceeds a threshold \u201c\u0394\u201d, the VM is considered faulty and the tasks on it are marked as failed and rescheduled accordingly.<\/p>\n

The AR Module\/Fault Handler collaborates with the VM Allocator and the Heartbeat Monitor to detect and manage VM and task failures, initiating reservations to ensure the uninterrupted execution of tasks. This coordination guarantees fault-tolerant execution with minimal downtime. The VM allocator also communicates the generated schedule to the AR Module. In response, the AR Module\u2019s Time Manager component predicts the AR slot as given in Eq.\u00a03<\/a> based on the schedule produced by the VM allocator. The Reservation Producer component provides the alternative VM for the computed AR slot in case of a fault, thereby initiating the reservation.<\/p>\n

Fig. 2<\/b>\"figure<\/a><\/p>\n

System architecture of CRFTS.<\/p>\n

Problem formulation<\/p>\n

The section presents a foundation for the rest of the work, facilitating readers to understand the objectives, variables, constraints\/assumptions, and approach of the research done in the work.<\/p>\n

Task and VM Constraints\/Assumptions:<\/p>\n

\\(1MI~ \\leqslant ~Size{\\text{ }}({t_i}) \\leqslant 100MI\\)<\/p>\n

\\(1MIPS~ \\leqslant ~Speed{\\text{ }}({v_j}) \\leqslant 100MIPS\\)<\/p>\n

Objectives of the model: Minimize makespan while maximizing resource utilization and reliability.<\/p>\n

Allocation Variables: STij, FTij, Rj, P(ti,vj).<\/p>\n

Fault Tolerance Variables: AR, ARM, Status.<\/p>\n

The allocation and fault tolerance variables are calculated in the problem formulation section later. The task allocation problem is modelled mathematically as a mapping of every arriving task to the suitable VM cluster to optimize reliability. The proposed model works in five phases:<\/p>\n

Phase 1: task clustering<\/p>\n

This phase is responsible for organizing the tasks in three clusters, namely, Low task Cluster, Medium task Cluster, and High task Cluster.<\/p>\n

Phase 2: VM clustering<\/p>\n

This phase is responsible for organizing the VMs in three clusters, namely, Low VM Cluster, Medium VM Cluster, and High VM Cluster.<\/p>\n

Phase 3: task to Vm mapping without reservation<\/p>\n

In each cluster, the VMs and tasks may be placed in random order because the task and VM clusters are created based on task size and VM speed, respectively, and not based on the number. Mathematically, the mapping (\u00b5) can be represented as follows:<\/p>\n

\u00b5: T \u2192 V<\/p>\n

Every task has its Start time and Finish time, which are computed in Eqs.\u00a0(1<\/a>) and (2<\/a>). To reserve the VM, the task execution time slot, i.e., the AR slot for every task on a suitable VM, is estimated. The AR slot for each task is calculated by taking the difference between ST and FT as computed in Eq.\u00a0(3<\/a>). The ST is the time when the task starts executing on the allocated VM. The FT is the time when the task completes its execution on that VM. The execution time of the task is added to the ST of that task to compute the FT. Additionally, each VM has a load history (Rj) that is used to determine when it is ready to execute the new task. Whenever any ti will begin to execute on any vj after mapping according to the allocation procedure. The time at which the allocation of ti begins or starts on vj is known as STij. Rj is first assumed to be STij as seen in Eq.\u00a0(1<\/a>)<\/p>\n

$$S{T_{ij}}={\\text{ }}{R_j}$$<\/p>\n

\n (1)\n <\/p>\n

Once ti has completed its execution on vj, the processing time of ti on vj (p(ti, vj)) is added to the STij as indicated in Eq.\u00a0(2<\/a>) to determine the FTij.<\/p>\n

$$F{T_{ij}}={\\text{ }}S{T_{ij}}+{\\text{ }}p\\left( {{t_i},{v_j}} \\right)$$<\/p>\n

\n (2)\n <\/p>\n

$$AR\\,=\\,F{T_{ij}} – {\\text{ }}S{T_{ij}}$$<\/p>\n

\n (3)\n <\/p>\n

Here, p(ti,vj) is computed by dividing the size of ti by the speed of vj.<\/p>\n

Phase 4: failure modelling and detection via heartbeat mechanism<\/p>\n

The model enables every VM to send a heartbeat signal at certain instances (Hj).<\/p>\n

Parameters defined for enabling the heartbeat mechanism:<\/p>\n

\u03b4: Heartbeat interval (VM sends the heartbeat every \u03b4 units of time), Hj\u200b: Last heartbeat timestamp from VM.<\/p>\n

T: Current time, \u0394: Timeout threshold.<\/p>\n

The heartbeat mechanism works in two steps:<\/p>\n

Step 1: Heartbeat Sending<\/p>\n

The phase initially tracks the time of sending the heartbeat by using the \u03b4 as:<\/p>\n

\\(T{\\text{ }}\\bmod {\\text{ }}\\,\\delta =\\,0\\)<\/p>\n

If the heartbeat sending time is detected, then VM sends the heartbeat time stamp to the heartbeat controller. After receiving a heartbeat, the controller updates Hj of the corresponding VM with the current time (\u03c4).<\/p>\n

\\(H\\left( {{v_j}} \\right){\\text{ }}=\\tau\\)<\/p>\n

Step 2: Heartbeat Scanning<\/p>\n

The heartbeat controller performs this phase, and it periodically scans the heartbeat of VMs. If the heartbeat of any VM is not found within the time, then it is declared as faulty and ejected from the cluster. The controller measures the past time since the most recent heartbeat was acknowledged from the VM and uses this interval as a pointer for detecting VM failure as:<\/p>\n

\\(Last\\_Breath\\,=\\,\\tau –H\\left( {{v_j}} \\right)\\)<\/p>\n

If the Last_Breath exceeds the timeout threshold, then the controller declares the VM as failed by indicating the following:<\/p>\n

\\(H\\left( {VM} \\right) = \\left\\{ \\begin{gathered} 1,~~\\,\\,if~heartbeat~received~from\\,~VM~within~Timeout \\hfill \\\\ 0,\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\,\\,\\,Otherwise \\hfill \\\\ \\end{gathered} \\right.\\)<\/p>\n

Phase 5: fault tolerance via reservation<\/p>\n

In this phase, Task VM mapping is performed, and simultaneously, VMs are monitored for faults using the heartbeat mechanism. In case of faults, advance reservation is enabled and an alternative VM is provided to the affected task. If any VM leaves the system or fails at any point in time, and fault tolerance is not there, the associated tasks may suffer premature termination. The problem is addressed by accompanying the scheduling with a proactive, advance reservation fault tolerance technique. Let\u2019s suppose \u2018f\u2019 VMs are failing and these \u2018f\u2019 VMs are taken as a separate set of failed VMs (Vf) and are defined as:<\/p>\n

\\({V_f}={\\text{ }}\\{ {v_f}:{\\text{ }}{v_f} \\in V{\\text{ }}and{\\text{ }}\\left| {{V_f}} \\right|{\\text{ }}=f\\}\\)<\/p>\n

This failure of VMs will affect the corresponding tasks and cause them to fail. Let \u2018u\u2019 be the number of unsuccessful tasks. Similarly, these \u2018u\u2019 unsuccessful tasks are taken as a separate set of unsuccessful tasks (Tu) and are defined as:<\/p>\n

\\({T_u}={\\text{ }}\\{ {t_u}:{\\text{ }}{t_u} \\in T{\\text{ }}and{\\text{ }}\\left| {{T_u}} \\right|{\\text{ }}={\\text{ }}u{\\text{ }}\\& {\\text{ }}u<\/p>\n

Now, these unexecuted tasks need to be reassigned to some alternative VM to complete their execution, which is done by the advance reservation technique. All tasks in Tu are migrated to another VM (Vj) having the least RT from (Vf) for the calculated AR slot such that Vj \u2209 Vf as discussed in Algorithm 5.<\/p>\n

The proposed clustering approach allocates tasks in three ways. First, sorting helps the model to achieve a one-to-one suitable order. Thereafter, clustering before allocation restricts the domain of allocation, which allows the model to assign the most appropriate VM to the task. Lastly, the task from each cluster is allocated to the corresponding VM clusters only, which helps the model to avoid under- and overutilization of the VM up to a certain degree. However, there are still chances of over- and underutilization of VMs, which will be handled by integrating the proposed approach with an efficient load-balancing technique that is under consideration for future work, which continuously monitors the under- and over-utilizing VMs and shifts the load between them.<\/p>\n

Performance metrics<\/p>\n

After the successful task execution, the reliability of the system is checked. Additionally, the makespan is taken as the highest or maximum among all TETj and can be expressed as Eq.\u00a0(4<\/a>)32<\/a>.<\/p>\n

$$Makespan\\,=\\,\\hbox{max} {\\text{ }}\\left( {F{T_{ij}}} \\right),\\forall {V_j}$$<\/p>\n

\n (4)\n <\/p>\n

Progress percentage of makespan (Ppm): It is the percentage of progress in makespan offered in proposed CRFTS over the other existing approaches, i.e., HEFT, E-HEFT, and LB-HEFT approaches, and is calculated in the Eq.\u00a0(5<\/a>)33<\/a>.<\/p>\n

$$P{p_m}\\left( \\% \\right){\\text{ }}=\\frac{{M~\\left( {Compared~Approach} \\right) – ~M\\left( {\\Pr oposed~Approach} \\right)}}{{M\\left( {Compared~Approach} \\right)}}*{\\text{ }}100$$<\/p>\n

\n (5)\n <\/p>\n

Average of (Ppm): To calculate the deviation from the desired rate in percentage, divide the sum of every Ppi for each tested VM by their respective tested numbers, as shown in the Eq.\u00a0(6<\/a>)34<\/a>.<\/p>\n

$$Average{\\text{ }}of{\\text{ }}\\left( {P{p_m}} \\right){\\text{ }}=\\frac{{\\mathop {{\\text{ }}\\sum }\\nolimits_{{i=1}}^{t} Ppm~\\left( {each~tested~VM~EquationNumber} \\right)}}{t}$$<\/p>\n

\n (6)\n <\/p>\n

The Average VM utilization of the system is calculated in the Eq.\u00a0(7<\/a>) as35<\/a>.<\/p>\n

$$UT=\\frac{{\\mathop \\sum \\nolimits_{1}^{k} \\left( {FT~ – ~p\\left( {tf~\\hbox{c}{\\kern-6.5pt}\\raise2.75pt\\hbox{\\vrule height .5pt width3.5pt depth0pt}{\\kern4pt}~Tf~,~Vj~\\hbox{c}{\\kern-6.5pt}\\raise2.75pt\\hbox{\\vrule height .5pt width3.5pt depth0pt}{\\kern4pt}~Vf~} \\right)} \\right)}}{{k~*Makespan}}~\\forall Vj~$$<\/p>\n

\n (7)\n <\/p>\n

Progress percentage of UT (Ppu): It is the ratio defining the progress percentage of average utilization of the proposed CRFTS and other compared approaches and is calculated in the Eq.\u00a0(8<\/a>) as36<\/a>.<\/p>\n

$$P{p_u}\\left( \\% \\right){\\text{ }}=\\left( {\\frac{{UT~\\left( {Compared~Approach} \\right) – ~UT\\left( {\\Pr oposed~Approach} \\right)}}{{UT\\left( {Compared~Approach} \\right)}}} \\right)*{\\text{ }}100$$<\/p>\n

\n (8)\n <\/p>\n

Average of (Ppm): To calculate the deviation from the desired rate in percentage, divide the sum of every Ppu for each tested VM by the respective number of tests, as shown in the Eq.\u00a0(9<\/a>)37<\/a>.<\/p>\n

$$Average{\\text{ }}of{\\text{ }}\\left( {P{p_u}} \\right){\\text{ }}=\\frac{{\\mathop \\sum \\nolimits_{{i=1}}^{t} Ppu~\\left( {each~tested~VM~EquationNumber} \\right)}}{t}$$<\/p>\n

\n (9)\n <\/p>\n

Finally, reliability is computed by the Eq.\u00a0(10<\/a>)<\/p>\n

$$R{\\text{ }}=\\frac{{\\left| {{T_u}} \\right|}}{{\\left| T \\right|}}*{\\text{ }}100$$<\/p>\n

\n (10)\n <\/p>\n

The Model readily provides the reserved VM as an alternative VM for the impacted task to ensure the successful execution of every task. Thereby, confirming maximum reliability in the event of more than 50% of faulty VMs.<\/p>\n

Pseudocode and algorithm<\/p>\n

The proposed pseudocode works by taking some assumptions and parameters listed as follows:<\/p>\n