Introduction
-
Providing a three-tier hierarchical architecture for Cloud/Fog-based systems. The proposed architecture introduces a sub-layer in the Fog to provide a scheduling management system with resource mobility.
-
Extracting a Critical Path extraction method according to the priority of workflow tasks, which helps to create more accurate schedules.
-
Considering the mobility behavior of the Fog layer nodes and calculating the mobility score of the Fog nodes using a multi-criteria fuzzy method and introducing a new dynamic clustering algorithm.
-
Proposing a new workflow scheduling algorithm, which achieves the best scheduling using a new utility function.
Related work
Work | Target system | Scheduling Type | Minimum Makespan | Minimum Cost | Privacy | Delay | Deadline | Task priority | Energy consumption | Resource Management | Resource Mobility |
---|---|---|---|---|---|---|---|---|---|---|---|
[7] (2020) | Cloud | Workflow Scheduling | Yes | Yes | Yes | No | No | No | No | No | No |
[8] (2017) | Cloud | Scientific Workflow Scheduling | Yes | Yes | No | No | Yes | Yes | No | No | No |
[13] (2020) | Cloud | Workflow Scheduling | Yes | Yes | No | No | Yes | No | No | No | No |
[24] (2018) | Cloud | Task Scheduling | Yes | Yes | No | No | No | Yes | No | No | No |
[25] (2018) | Cloud | Workflow Scheduling | Yes | Yes | No | No | No | No | No | No | No |
[26] (2021) | Fog | Workflow Scheduling | Yes | Yes | No | Yes | No | No | Yes | No | No |
[27] (2021) | Cloud | Workflow Scheduling | Yes | Yes | No | No | No | No | Yes | No | No |
[28] (2021) | Cloud | Workflow Scheduling | Yes | Yes | No | No | No | No | Yes | No | No |
[29] (2021) | Cloud | Task Scheduling | Yes | Yes | No | No | No | No | Yes | No | No |
[33] (2019) | Fog | Task Scheduling | Yes | Yes | No | Yes | No | Yes | Yes | Yes | No |
[34] (2016) | Fog | Task Scheduling | Yes | Yes | No | No | No | Yes | No | No | No |
[35] (2016) | Fog | Task Scheduling | Yes | Yes | No | No | No | No | No | No | No |
[36] (2020) | Fog | Task offloading | Yes | No | No | Yes | No | No | No | No | No |
[37] (2020) | Fog | Task Scheduling | Yes | Yes | No | No | No | No | Yes | No | No |
[38] (2019) | Fog/ Cloud | Task Scheduling | Yes | Yes | No | Yes | No | No | No | No | No |
[39] (2020) | Cloud | Workflow Scheduling | Yes | Yes | No | No | No | No | Yes | Yes | No |
[41] (2017) | Fog/ Cloud | Workflow Scheduling | Yes | Yes | No | No | Yes | Yes | No | No | No |
[42] (2022) | Fog | Task Scheduling | Yes | Yes | No | No | Yes | No | Yes | Yes | No |
This Work | Fog/ Cloud | Workflow Scheduling | Yes | Yes | No | No | Yes | Yes | Yes | Yes | Yes |
Scheduling management system architecture
-
Cloud/Fog information services
-
Scheduling management systemThe core of the system is the scheduling management system that is responsible for managing the actual execution of the workflow. It includes the following components:
-
Resource provisioningThe resource provisioning component is responsible for selecting and supplying Cloud/Fog resources and is done according to the requirements of the scheduling system and service quality requirements.
-
Runtime estimationWhen a task is entered into the system, preprocessing is performed and a deadline is assigned to each task, which is provided in the system by the runtime estimation component.
-
Task dispatcherThis component is responsible for interacting with Cloud APIs to send tasks ready to run.
-
Data managementThe data management component in the scheduling management system manages the collection, motion, placement, storage, and dependency between data when needed to perform task operations.
-
SchedulerThis component performs the task of scheduling according to the information and factors obtained from other components to make accurate and efficient decisions, using scheduling algorithms.
-
MonitoringThe monitoring includes components that enable dynamic and continuous monitoring of workflow tasks and resource performance, as well as resource management.
-
Performance Evaluation parameters | Description |
---|---|
Resource Utilization | Resource utilization in the Fog and Cloud can be defined as the amount of resource time used to perform scheduled tasks on it |
Success Rate | Success rate is defined in terms of the number of successful requests in relation to the total number of tasks, and represents the fraction of tasks that have been successfully scheduled and completed before the deadline |
Time related scheduling performance | |
Parallelism Degree | Parallelism Degree is the number of tasks running in parallel |
MakeSpan | Makespan is the amount of time from providing a workflow to completing it |
Waiting Time | Waiting time is the average time it takes for a task to complete the scheduling process |
Energy Consumption | Energy consumption report in each stage in the average and total mode |
Packet Delivery Report | Package delivery report in three modes: Wi-Fi, cellular and lost |
Throughput | Throughput rate during the scheduling process |
Alive node | Number of live nodes during the scheduling process |
Problem model
Task graph model
Resource clustering algorithm
Term | Description |
---|---|
SoCH | Scored cluster head node point |
SoMob | Cluster member node mobility score |
BWCH | Bandwidth of a cluster relative to the number of its members |
RTCH | Response time for messages for the cluster head node |
PPCH | Processing power of a cluster depends on the number of its members |
VM | Speed of each member node relative to a member of the cluster |
STM | Stability of the position of each node of the cluster relative to the cluster head |
Message name | Message format |
---|---|
CHmsg | {Id_M, SoMob score, Avl list} |
JOINmsg | {Id_M, SoMob score} |
ACCEPTmsg | {Id_CH, size of CH, SoCH score} |
-
The first step (calculating the cluster head score).
-
Step 2 (calculating the mobility score for each node).
-
Step 3 (creating a list of available cluster heads for each node).
-
Step 4 (distributing the global message).
-
Step 5 (selecting the cluster numbers).
Fuzzy inference system for calculating scores of the cluster head
Variable | Membership function | Linguistic Value | |
---|---|---|---|
Input variable | BWCH | \(\mu\left(x\right)=\left\{\begin{array}{cc}1&x<0.2\\{\frac{0.4-x}{0.2}} &x\in[0.2 . 0.4]\\0& x>0.4\end{array}\right.\) | L |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.27\\ {\frac{x-0.27}{0.13}}& x\in [0.27 . 0.4]\\ 1& x\in [0.4 . 0.6]\\ \frac{0.8-x}{0.2}& x\in [0.6 . 0.8]\\ 0& x>0.8\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.62\\ \frac{0.9-x}{0.28}& x\in [0.62 . 0.9]\\ 1& x>0.9\end{array}\right.\) | H | ||
RTCH | \(\mu \left(x\right)=\left\{\begin{array}{cc}\frac{0.4-x}{0.4}& x\in [0 . 0.4]\\ 0& x >0.4\end{array}\right.\) | W | |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.1\\ \frac{x-0.1}{0.4}& x\in [0.1 . 0.5]\\ \frac{0.8-x}{0.3}& x\in [0.5 . 0.8]\\ 0& x>0.8\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.6\\ \frac{x-0.6}{0.4}& x\in [0.6 . 1]\end{array}\right.\) | S | ||
PPCH | \(\mu \left(x\right)=\left\{\begin{array}{cc}\frac{0.35-x}{0.35}& x\in [0 . 0.35]\\ 0& x >0.35\end{array}\right.\) | L | |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.15\\ \frac{x-0.15}{0.35}& x\in [0.15 . 0.5]\\ \frac{0.72-x}{0.22}& x\in [0.5 . 0.72]\\ 0& x>0.72\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x\in [0 . 0.6]\\ \frac{x-0.6}{0.4}& x >0.6\end{array}\right.\) | H | ||
Output variable | SoCH | \(\mu \left(x\right)=\left\{\begin{array}{cc}1& x<0.15\\ \frac{0.22-x}{0.07}& x\in [0.15 . 0.22]\\ 0& x>0.22\end{array}\right.\) | B |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.18\\ \frac{x-0.18}{0.18}& x\in [0.18 . 0.27]\\ 1& x\in [0.27 . 0.4]\\ \frac{0.5-x}{0.1}& x\in [0.4 . 0.5]\\ 0& x>0.5\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.35\\ \frac{x-0.35}{0.15}& x\in [0.35 . 0.5]\\ 1& x\in [0.5 . 0.7]\\ \frac{0.78-x}{0.08}& x\in [0.7 . 0.78]\\ 0& x>0.78\end{array}\right.\) | G | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.58\\ \frac{0.8-x}{0.28}& x\in [0.58 . 0.8]\\ 1& x>0.8\end{array}\right.\) | E |
-
1. SoCH. This output variable has four fuzzy sets which are defined as Bad (B), Moderate (M), Good (G), and Excellent (E).
-
Rule 10: if (BWCH is Moderate) and (RTCH is Weak) and (PPCH is Low) then (SoCH is Bad)
-
Rule 18: if (BWCH is NOT Medium) and (RTCH is Strong) and (PPCH is High) then (SoCH is Good)
Rule no | BWCH | RTCH | PPCH | SoCH |
---|---|---|---|---|
1 | L | W | L | B |
2 | L | W | M | B |
3 | L | W | H | B |
4 | L | ~ W | L | B |
5 | L | M | M | M |
6 | L | M | H | M |
7 | L | S | ~ M | M |
8 | L | S | M | G |
9 | ~ L | S | H | G |
10 | M | W | L | B |
11 | M | W | M | B |
12 | M | W | ~ L | B |
13 | M | M | L | M |
14 | M | M | M | M |
15 | M | M | H | G |
16 | M | S | L | G |
17 | ~ M | S | M | M |
18 | ~ M | S | H | G |
19 | ~ H | W | L | B |
20 | ~ H | W | M | M |
21 | H | W | H | G |
22 | H | M | L | M |
23 | H | M | M | G |
24 | H | M | ~ L | G |
25 | H | S | ~ H | G |
26 | H | S | M | E |
27 | H | S | H | E |
28 | H | ~ S | H | G |
-
1. Speed of each node (VM). The average velocity for each node up to the current time T is calculated by Eq. 4:where (Xt, Yt) and (Xt-1, Yt-1) are the coordinates of node v at time (t) and (t—1) respectively.$${V}_{M} =\frac{1}{T}\sum_{t=1}^{T}\sqrt{{({X}_{t}-{X}_{t-1})}^{2}+{({Y}_{t}- {Y}_{t-1})}^{2}}$$(4)
-
2. Stability (STM). Stability refers to the stability of the cluster member node relative to the cluster head nodes in its range. A higher stability number indicates that a node has been in the same range for a longer time, which means that the intended node is in a more stable state. Stability is calculated by Eq. 5.where TRF is the time of the first packet received and TRL is the time of the last packet received, and n represents the number of neighbors of a node.$${ST}_{M}= \sum_{i=1}^{n}{T}_{RF}- {T}_{RL}$$(5)
-
3. Cluster head node score (SoCH). It is calculated in Input and output variables of the fuzzy SoCH system section.
Variable | Membership function | Linguistic Value | |
---|---|---|---|
Input variable | VM | \(\mu \left(x\right)=\left\{\begin{array}{cc}\frac{0.35-x}{0.35}& x\in [0 . 0.35]\\ 0& x >0.35\end{array}\right.\) | W |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0\\ \frac{x-0.2}{0.3}& x\in [0.2 . 0.5]\\ \frac{0.8-x}{0.3}& x\in [0.5 . 0.8]\\ 0& x>0.8\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}\frac{x-0.6}{0.4}& x< 0.6\\ 0& x\in [0.6 . 1]\end{array}\right.\) | S | ||
STM | \(\mu \left(x\right)=\left\{\begin{array}{ll}\frac{0.35-x}{0.35}& x\in [0 . 0.35]\\ 0& x >0.35\end{array}\right.\) | L | |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0 x<0\\ \frac{x-0.2}{0.3}& x\in [0.2 . 0.5]\\ \frac{0.8-x}{0.3}& x\in [0.5 . 0.8]\\ 0& x>0.8\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}\frac{0.35-x}{0.35}& x\in [0 . 0.35]\\ 0& x >0.35\end{array}\right.\) | H | ||
SoCHM | \(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.65\\ \frac{x-0.65}{0.17}& x\in [0.65 . 0.82]\\ 1& x>0.82\end{array}\right.\) | B | |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.32\\ \frac{x-0.32}{0.18}& x\in [0.32 . 0.5]\\ 1& x\in [0.5 . 0.7]\\ \frac{0.82-x}{0.08}& x\in [0.7 . 0.82]\\ 0& x>0.82\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.32\\ \frac{x-0.32}{0.18}& x\in [0.32 . 0.5]\\ 1& x\in [0.5 . 0.7]\\ \frac{0.82-x}{0.08}& x\in [0.7 . 0.82]\\ 0& x>0.82\end{array}\right.\) | G | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.65\\ \frac{x-0.65}{0.17}& x\in [0.65 . 0.82]\\ 1& x>0.82\end{array}\right.\) | E | ||
Output variable | SoMobM | \(\mu \left(x\right)=\left\{\begin{array}{cc}1& x<0.1\\ \frac{x-0.1}{0.05}& x\in [0.1 . 0.15]\\ 0& x>0.15\end{array}\right.\) | VL |
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.08\\ \frac{x-0.08}{0.07}& x\in [0.08 . 0.15]\\ 1& x\in [0.15 . 0.25]\\ \frac{0.32-x}{0.07}& x\in [025 . 0.32]\\ 0& x>0.32\end{array}\right.\) | L | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.2\\ \frac{x-0.2}{0.15}& x\in [0.2 . 0.35]\\ 1& x\in [0.35 . 0.5]\\ \frac{0.65-x}{0.15}& x\in [0.5 . 0.65]\\ 0& x>0.65\end{array}\right.\) | M | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.45\\ \frac{x-0.45}{0.15}& x\in [0.45 . 0.6]\\ 1& x\in [0.6 . 0.75]\\ \frac{0.9-x}{0.15}& x\in [0.75 . 0.9]\\ 0& x>0.9\end{array}\right.\) | H | ||
\(\mu \left(x\right)=\left\{\begin{array}{cc}0& x<0.75\\ \frac{x-0.75}{0.1}& x\in [0.75 . 0.85]\\ 1& x>0.85\end{array}\right.\) | VH |
-
1. VM. Three fuzzy sets are defined for this input variable: Weak(W), Moderate(M), Strong(S)
-
2. STM. Three fuzzy sets are defined for this input variable: Low(L), Medium(M), High(H)
-
3. SoCH. Four fuzzy sets are defined for this input variable: Bad(B), Moderate(M), Good(G), Excellent(E)
Rule no | V | ST | SoCH | SoMob |
---|---|---|---|---|
1 | W | L | B | VL |
2 | W | M | B | VL |
3 | W | H | ~ B | M |
4 | ~ W | L | B | VL |
5 | M | ~ M | B | L |
6 | M | M | B | M |
7 | ~ M | H | B | M |
8 | M | H | B | M |
9 | S | L | M | M |
10 | S | M | M | M |
11 | W | H | M | M |
12 | W | ~ L | M | VL |
13 | W | ~ M | M | L |
14 | ~ W | M | M | L |
15 | M | H | M | H |
16 | M | M | M | M |
17 | M | L | M | L |
18 | ~ M | M | ~ M | L |
19 | M | ~ H | M | M |
20 | W | L | G | L |
21 | W | M | G | M |
22 | ~ S | H | G | H |
23 | M | M | ~ G | M |
24 | ~ M | L | G | L |
25 | ~ S | H | G | M |
26 | S | M | G | M |
27 | W | L | G | M |
28 | ~ W | M | G | H |
29 | M | H | E | H |
30 | M | ~ L | E | H |
31 | ~ S | M | E | M |
32 | S | H | E | VH |
33 | S | M | E | VH |
Scheduling algorithm
-
Phase 1; Critical path extraction algorithm
-
The second phase; the Soft Deadline Mobility Scheduling (SDMS) algorithm
-
Workflow Distance to Cluster (\({Distance}_{WF}^{{CL}_{i}}\))
-
• Phase 3; Task reservation
Evaluation and discussion
-
In the proposed method, budget constraint is not considered. Since these two methods MOODS and GRP-HEFT have this constraint, it is not considered.
-
GRP-HEFT and MOODS do not support Fog resources for scheduling, but it has been added to both.
-
GRP-HEFT uses a greedy scheme.
-
In the proposed algorithm and MOODS, the first fit scheme is used.
-
The implementation of GRP-HEFT and MOODS in the performed experiments has some minor differences compared with the original work as it was necessary to make the implementation feasible.
-
Configuration of environment
-
• Data-sets
Network | Physical hosts | ||||
Communication Locality | Fog-point to WAN Bandwidth | Inter-Fog point Bandwidth | RAM(GB) | Processing Capacity (TIPS) | Processor type |
70%—75% | 80–200 Mbps | unlimited | 16–64 | 221—412 | • Intel i64_Corei9 • Intel i64_Corei7 |
Environment Structure | |||||
Total count of Fog hosts | No. of Hosts in Fog-points | No. of Fog-Points of each Fog Provider | No. of Fog Providers | ||
120–299 | 5–9 | 6–8 | 4 |
Network | Physical hosts | |||||
Communication Locality | Datacenter to WAN Bandwidth | Inter-DS Bandwidth | RAM(GB) | Capacity (TIPS) | Processor type | |
80%-90% | 1 Tbps | unlimited | 144–192 | 749—2,356 | • Xeon 5500 • Xeon 6500 • AMD Ryzen9 • AMD Magny-Cours • AMD Threadripper | |
Environment Structure | ||||||
Total count of Cloud hosts | Count of nodes in each cluster | No. of Clusters in each Data-center | No. of Data-centers owns by Cloud Providers | Count of Cloud Providers | ||
48– 288 | 4–8 | 2–3 | 2–4 | 3 |
Nodes | Edges | Count of DAGs | Task size (Billion Instructions) | Data dependency weight (Mega Bytes) | RAM requirement (Mega Bytes) |
---|---|---|---|---|---|
6–30 | 8–46 | 100,000 | 9,000—4,500 | 3–80 | 20–3100 |
-
Consumption of energy
-
Fault model
P(CloudDatacenterHostNodeHasOmissionFault) | 0.01 |
P(fullFailureRecoverable | NodeHasOmissionFault) | 0.3 |
P(fullFailurePermanent | NodeHasOmissionFault) | 0.1 |
P(noFailure | NodeHasOmissionFault) | 0.6 |
P(taskFailedAndDeadlinePassed | fullFailureRecoverable) | 0.3 |
P(taskFailedAndDeadlinePassed | fullFailurePermanent) | 0.7 |
P(taskFailedAndDeadlinePassed | NodeHasOmissionFault) | 0 |
P(FogNodeHasOmissionFault) | 0.05 |
-
Location and movement model of nodes
Movement Model | Minimum Speed | Maximum Speed | Environment Dimension |
---|---|---|---|
Random Way Point | 8 m/s | 18 m/s | \({\boldsymbol{20}}{\boldsymbol{k}}{\boldsymbol{m}}\times {\boldsymbol{20}}{\boldsymbol{k}}{\boldsymbol{m}}\) |
Experimental results
-
Fog/Cloud resource utilization for Scheduling performance
Method | Average Utilization of Fog and Cloud Hosts |
---|---|
Proposed Method | ~ 71% |
GRP-HEFT | ~ 58% |
MOODS | ~ 55% |
-
Success rate for scheduling performance
Method | Average Job Scheduling Success Rate |
---|---|
Proposed Method | ~ 82% |
GRP-HEFT | ~ 65% |
MOODS | ~ 62% |
-
Time related parameters for scheduling performance
-
◾ Parallelism degree
-
◾ MakeSpan
-
◾ Waiting time
-
Energy consumption
Conclusion
-
Devising a three-layer architecture that simultaneously takes into account the advantages of the cloud and fog layers to manage the scheduling of workflow tasks and also manage the mobility of fog nodes.
-
Presenting a dynamic, light-weight, multi-criteria, and decentralized clustering algorithm to create clusters considering the mobility of nodes.
-
Extending the scheduling component and introducing a new scheduling algorithm that considers: priority of tasks obtained by using a critical path algorithm, a novel utility function, and considering workflow deadlines.
Declarations
Consent for publication
Not applicable. This manuscript does not have any individual person data.