∎

11institutetext:  Atherve Tekawade 22institutetext: Department of Computer
Science and Engineering,
Indian Institute of Technology Jammu.
22email<EMAIL_ADDRESS>33institutetext: Suman Banerjee
44institutetext: Department of Computer Science and Engineering,
Indian Institute of Technology Kharagpur.
44email<EMAIL_ADDRESS>
#  Cost and Reliability Aware Scheduling of Workflows Across Multiple Clouds
with Security Constraints

Atherve Tekawade  Suman Banerjee

(Received: date / Accepted: date)

###### Abstract

Many real-world scientific workflows can be represented by a Directed Acyclic
Graph (DAG), where each node represents a task and a directed edge signifies a
dependency between two tasks. Due to the increasing computational resource
requirements of these workflows, they are deployed on multi-cloud systems for
execution. In this paper, we propose a scheduling algorithm that allocates
resources to the tasks present in the workflow using an efficient list-
scheduling approach based on the parameters cost, processing time, and
reliability. Next, for a given a task-resource mapping, we propose a cipher
assignment algorithm that assigns security services to edges responsible for
transferring data in time-optimal manner subject to a given security
constraint. The proposed algorithms have been analyzed to understand their
time and space requirements. We implement the proposed scheduling and cipher
assignment algorithm and experimented with two real-world scientific workflows
namely Epigenomics and Cybershake. We compare the performance of the proposed
scheduling algorithm with the state-of-art evolutionary methods. We observe
that our method outperforms the state-of-art methods always in terms of cost
and reliability, and is inferior in terms of makespan in some cases.

###### Keywords:

Multi-Cloud System Workflow Virtual Machine Data-Security Pricing schemes
Scheduler

##  1 Introduction

In recent times, _cloud computing_ has emerged as an alternative computing
framework and become popular due to many features including ‘pay as you use’
kind of billing strategy, virtualization, rapid elasticity, on-demand use, and
so on Mastelic et al. (2014). A scientific workflow is defined as a set of
tasks where there are several dependencies among tasks Zhou et al. (2019). In
recent times cloud infrastructure has been used extensively used for the
execution of workflows and many scientific workflows from different domains
such as _Epigenomics_ in bio-informatics, _Cybershake_ in earthquake
engineering, etc. has been successfully deployed on commercial clouds Zhou et
al. (2019); Farid et al. (2020). Recently, due to large-scale computational
resource and diversity requirements, multiple cloud providers club together to
form a larger infrastructure, and such a framework is known as a multi-cloud
system Tang (2021). In many cases, they are managed by a third party. Each one
of them provides its own set of Virtual Machines (VMs) and billing mechanisms.

#### Motivation

As mentioned in the literature, recently the resource requirements for the
execution of these workflows have been increased extensively Guo et al.
(2018). In such a situation, one solution is to use a multi-cloud system to
execute such gigantic size workflows. A multi-cloud system is highly
heterogeneous with its respective hardware, software, and network
infrastructure Miraftabzadeh et al. (2016). Hence, it is prone to failure. As
in a workflow, there are dependencies among the tasks so the failure of one
task may lead to the failure of the entire workflow. For successful execution
of the workflow, the cloud infrastructure must provide highly reliable
computing services. Also in a multi-cloud system, VMs of two different cloud
services may reside in two different locations and the network link connecting
two servers where these two VMs resides may be accessible to the adversaries.
It may so happen that the two tasks allocated to these VMs have dependencies.
So some kind of security measures needs to be imposed before transmitting the
data from one VM to the other. As a whole for the successful execution of a
workflow in a multi-cloud system both security and reliability become
important issues.

#### Related Work

In the past few years, there has been an extensive study on multi-cloud
systems Li et al. (2015); Diaz-Montes et al. (2015); Tekawade and Banerjee
(2023). Several scheduling strategies have been proposed for multi-cloud
systems Miraftabzadeh et al. (2016); Kang et al. (2018). Recently, there are a
few methodologies for scheduling workflows in the multi-cloud systems as well
Al-Maytami et al. (2019); Sooezi et al. (2015); Li et al. (2018). In general,
in a scientific workflow, tasks have a very high level of data and control
flow dependency with the precedence task(s). Recently, there are several
studies that focus on the reliability issues for workflow execution Han et al.
(2018); Wen et al. (2016); Di et al. (2016); Zhou et al. (2016). Guo et al.
Guo et al. (2018) studied the problem of scheduling workflows to minimize the
cost subject to deadline constraints using a heuristic approach which is a
hybridization of the Genetic Algorithm and the Particle Swarm Optimization.
Tang et al. Tang (2021) considered the problem of scheduling workflows to
minimize makespan, cost and maximize reliability. There are a few studies that
consider both the security and reliability of the workflow. Wen et al. Wen et
al. (2016) proposed an algorithm to find deployments for workflows that are
reliable, less expensive and satisfy security requirements in federated
clouds. Zhu et al. Zhu et al. (2021) looked at the problem of task scheduling
subject to reliability and security constraints. Apart from this, workflows
are also known to be scheduled on multi-processor platforms taking into
account the makespan, energy consumption and reliability requirements. Zhou et
al. (2016) -Xie et al. (2017). To the best of our knowledge, there are limited
literature on security and reliability of workflow execution. In this paper,
we focus on these two aspects for workflow scheduling.

#### Our Contributions

In this paper, we make the following contributions:

  * •

We propose a system model to study workflow scheduling in a multi-cloud system
considering communication costs and billing mechanisms of different cloud
providers.

  * •

We integrate the notion of data confidentiality in our model by assuming that
data is encrypted using cryptographic ciphers of varying strengths. We develop
an optimal assignment of ciphers to data to minimize the total encryption and
decryption overhead.

  * •

We also perform the reliability analysis for task execution considering that
the failure of the tasks is modeled using Poisson Distribution.

  * •

We propose a list-based heuristic followed by an iterative local-search
algorithm that assigns the best resource to a task based on the makespan,
cost, and reliability.

  * •

The proposed solution approach has been implemented with real-world scientific
workflows and compared with the state-of-art approaches.

#### Organization of the Paper

The rest of the paper is organized as follows. Section 2 describes the
system’s model and problem formulation. The proposed list-based heuristic
solution has been described in Section 3. Section 4 contains the experimental
evaluation of the proposed solution methodology. Finally, Section 5 concludes
our study and gives future research directions.

##  2 Systems Model & Problem Formulation

In this section, we describe the system’s model and describe our problem
formally. For any positive integer $n$, $[n]$ denotes the set
$\\{1,2,\ldots,n\\}$.

###  2.1 Tasks and Workflow

A task is a job that needs to be executed on the multi-cloud system. A
_scientific workflow_ consists of multiple interrelated tasks and is modeled
as a _directed acyclic graph_ (DAG) $G(V,E)$, where $V(G)=\\{v_{i}:i\in[n]\\}$
is the set of $n$ tasks and $E(G)=\\{e_{h}=(v_{i},v_{j}):v_{i},v_{j}\in
V(G)\\}$ is the set of edges. Here an edge $(v_{i},v_{j})$ signifies a
precedence relationship between tasks $v_{i}$ and $v_{j}$, i.e., the execution
of $v_{j}$ can only be started after the execution of $v_{i}$ is finished and
its output is transferred to $v_{j}$. The weight of the edge $(v_{i}v_{j})$ is
denoted by $w_{v_{i},v_{j}}$ and signifies the amount of data to be
transferred. The computational resource requirement of the task $v_{i}$ is
denoted by $w_{v_{i}}$. Next, we present some definitions related to workflow.

######  Definition 1 (Predecessor of a Task)

For any task $v_{i}$, $pred(v_{i})$ denotes the set of immediate predecessor
tasks of this task and defined as $pred(v_{i})=\\{v_{j}:(v_{j},v_{i})\in
E\\}$.

######  Definition 2 (Successor of a Task)

For any task $v_{i}$, $succ(v_{i})$ denotes the set of immediate successor
tasks of this task and defined as $succ(v_{i})=\\{v_{j}:(v_{i},v_{j})\in
E\\}$.

######  Definition 3 (Entry Task)

It is a redundant task denoted by $v_{entry}$ having an outgoing edge with
zero weight to every $v$ such that $pred(v)=\emptyset$.

######  Definition 4 (Exit Task)

$v_{exit}$ denotes the exit task. It is a redundant node having an incoming
edge with zero weight from every $v$ such that $succ(v)=\emptyset$.

For simplicity, we assume that $v_{entry}=v_{1}$ and $v_{exit}=v_{n}$.

######  Definition 5 (Topological Level)

For a task $v$, $top\\_level(v)$ denotes its topological level and defined by
Equation No. 1.

$\scriptsize top\\_level(v)=\left\\{\begin{array}[]{ c l }0&\quad\textrm{if
}v=v_{1}\\\ \underset{u\in
pred(v)}{max}\\{top\\_level(u)+1\\}&\quad\textrm{otherwise}\end{array}\right.$
(1)

The topological level can be computed using the Breadth-first search algorithm
(BFS) Bundy and Wallen (1984).

###  2.2 Multi-Cloud System

Our model consists of $m$ different cloud providers, each providing their
resources. These resources are offered in the form of Virtual Machines
(henceforth mentioned as VMs) Stillwell et al. (2012). Assume that the
$k^{th}$ cloud provider offers a total of $m_{k}$ different VM types. Let
$VM(k,p)$ denote the $p^{th}$ type VM offered by the $k^{th}$ cloud provider.
A VM is characterized by its CPU, Disk, and Memory. We assume that VMs have
sufficient memory to execute the workflow tasks Rodriguez and Buyya (2014).
Let $w_{k,p}$ denote the processing capacity of $VM(k,p)$, which is
proportional to the MIPS (amount of computation performed per second). The
higher the processing capacity of a VM, the faster it executes a task. The
amount of time it takes to execute $v_{i}$ on $VM(k,p)$ is denoted by
$T_{exec}[v_{i},VM(k,p)]$ and is given by Equation No. 2. Additionally, we
assume that a newly launched VM needs a specific initial boot time denoted by
$T_{boot}[VM(k,p)]$.

$T_{exec}[v_{i},VM(k,p)]=\frac{w_{v_{i}}}{w_{k,p}}$ (2)

###  2.3 Network

The bandwidth between two VMs depends on multiple factors like their physical
location, the cloud provider, etc. For simplicity, we assume VMs belonging to
the same center are connected by a high-speed internal network. In contrast,
those belonging to different centers are connected by slower external networks
Tang (2021). Let $B_{k}$ and $B_{k,k^{\prime}}$ denote the bandwidth of the
communication links of the VMs within the $k$-th cloud and the bandwidth of
the communication links connecting the $k$-th and $k^{{}^{\prime}}$-th clouds,
respectively. Communication time between two tasks $v_{i}$ and $v_{j}$ is
denoted by $T_{comm}[v_{i},v_{j}]$. This depends on the amount of data to be
transferred and the clouds where the tasks are hosted. This can be computed
using Equation No. 3.

$\scriptsize T_{comm}[v_{i},v_{j}]=\left\\{\begin{array}[]{ c l
}0&\quad\textrm{if }\text{$v_{i},v_{j}$ are scheduled on the same VM
instance}\\\ \frac{w_{v_{i},v_{j}}}{B_{k}}&\quad\textrm{else if
}k^{\prime}=k\\\
\frac{w_{v_{i},v_{j}}}{B_{k,k^{\prime}}}&\quad\textrm{otherwise}\end{array}\right.$
(3)

###  2.4 Resource Model and Timing Metrics

Due to the flexibility of resource acquisition provided by cloud providers, a
client can run any number of instances of a given VM Rodriguez and Buyya
(2014). Hence the maximum number of instances can be at most $\mathcal{N}\cdot
n$, where $\mathcal{N}=\sum_{k=1}^{m}\sum_{p=1}^{m_{k}}1$ assuming each task
is run on every possible VM type. Let $R=\\{vm_{r}:r\in[\mathcal{N}\cdot
n]\\}$ denote the set of VM instances to be leased (pool of resources), and
$LST_{vm_{r}}$ and $LFT_{vm_{r}}$ denote the start and end times respectively
for which $vm_{r}$ is leased. For task $v_{i}$, once all the data between
$v_{j}$ and $v_{j}$, $\forall v_{j}\in pred(v_{i})$ is received, the
decryption starts happening. Then, execution of the task $v_{i}$ on its
allocated VM starts happening, after which encryption of all data between
$v_{i}$ and $v_{j}$, $\forall v_{j}\in succ(v_{i})$ happens. Then finally, the
data needs to be transferred. A VM must be kept on until a task has
transferred data to all its successor nodes Rodriguez and Buyya (2014). Hence
the total processing time denoted by $PT_{v_{i}}$ includes the decryption,
execution, encryption, and communication time as shown in Equation No. 4.

$\scriptsize PT_{v_{i}}=\left\\{\begin{array}[]{ c l
}T_{exec}[v_{i},VM(k,p)]\\\ +\sum_{v_{j}\in
succ(v_{i})}(T_{enc}[v_{i},v_{j}]+T_{comm}[v_{i},v_{j}])&\quad\textrm{if
}v_{i}=v_{1}\\\ \\\ \sum_{v_{j}\in
pred(v_{i})}T_{dec}[v_{j},v_{i}]+T_{exec}[v_{i},VM(k,p)]&\quad\textrm{else if
}v_{i}=v_{n}\\\ \\\ \sum_{v_{j}\in
pred(v_{i})}T_{dec}[v_{j},v_{i}]+T_{exec}[v_{i},VM(k,p)]\\\ +\sum_{v_{j}\in
succ(v_{i})}(T_{enc}[v_{i},v_{j}]+T_{comm}[v_{i},v_{j}])&\quad\textrm{otherwise}\end{array}\right.$
(4)

where $v_{i}$ is assumed to be executed on VM of type $VM(k,p)$. Let the start
and finish times of task $v_{i}$ be denoted by $ST_{v_{i}}$ and $FT_{v_{i}}$,
respectively. As shown in Equation No, a task can start only after all its
predecessors are complete. 5.

$ST_{v_{i}}=\left\\{\begin{array}[]{ c l }0&\quad\textrm{if }v_{i}=v_{1}\\\
\max_{v_{j}\in
pred(v_{i})}FT_{v_{j}}&\quad\textrm{otherwise}\end{array}\right.$ (5)

The finish time is given by the sum of start and processing times, as shown in
Equation No. 6.

$FT_{v_{i}}=ST_{v_{i}}+PT_{v_{i}}$ (6)

The makespan is the total time required to execute the workflow which happens
when the last task finishes.

$makespan=FT_{v_{n}}$ (7)

###  2.5 Pricing Mechanisms

In this study, we consider three popular cloud-providing services: Microsoft
Azure (_MA_), Amazon Web Services (_AWS_), and Google Cloud Platform (_GCP_).
Each cloud provider charges the customer after a specified billing period
$\tau$. Let $c_{k,p}$ denote the price for renting $VM(k,p)$ for a single
billing period. Let the cost corresponding to renting VM $vm_{r}$ be denoted
by $C_{vm_{r}}$. Below we discuss the pricing mechanisms used by different
cloud providers Tang (2021).

  * •

_MA_ follows a fine-grained scheme where the customer is charged per minute of
usage _i.e._ $\tau=$ 1 min. The cost is given in Equation No. 8.

$C_{vm_{r}}=\lceil\frac{LFT_{vm_{r}}-LST_{vm_{r}}}{\tau}\rceil\cdot c_{k,p}$
(8)

  * •

_AWS_ follows a coarse-grained pricing mechanism where the customer per hour
of usage. _i.e._ $\tau=$ 1 hr. Equation No can obtain the cost. 8.

  * •

_GCP_ follows a hybrid pricing mechanism where the customer is charged for a
minimum of ten minutes, after which per-minute billing is followed. The cost
is formulated in Equation No. 9 where $C_{k,p}$ denotes the price for the
first ten minutes and $\tau=$ 1 min.

$\scriptsize
C_{vm_{r}}=C_{k,p}+\max(0,\lceil\frac{LFT_{vm_{r}}-LST_{vm_{r}}-10\cdot\tau}{\tau}\rceil)\cdot
c_{k,p}$ (9)

Table 1 illustrates the prices of various VMs Tang (2021). Apart from this,
each cloud provider has a specific pricing scheme associated with sending data
out. Generally, ingress data is not charged data transfer costs (Accessed 11
September 2022c), data transfer costs (Accessed 11 September 2022a), data
transfer costs (Accessed 11 September 2022b). Let $c_{k,k^{\prime}}$ denote
the price per unit data for sending data between the $k$-th and
$k^{{}^{\prime}}$-th providers. This price depends on many factors: Location
where the VMs are hosted, size of data, etc. Table 2 shows the rates for
transferring data as taken from the official websites data transfer costs
(Accessed 11 September 2022c), data transfer costs (Accessed 11 September
2022a), data transfer costs (Accessed 11 September 2022b). In the table,
across centers refers to locations managed by the same cloud provider but
located in different places. The prices vary depending on the location (US,
Europe, Asia, etc.). For simplicity, we consider the median value across all
locations. Across clouds refers to the transfers across different cloud
providers over the external internet. Again this price depends on the
location, so we consider the median value. The cost for transferring data
between $v_{i}$ and $v_{j}$ is denoted by $C_{v_{i},v_{j}}$ and is given by
Equation No. 10.

$C_{v_{i},v_{j}}=w_{v_{i},v_{j}}\cdot c_{k,k^{\prime}}$ (10)

where $v_{i},v_{j}$ are assumed to be scheduled on the $k$-th and
$k^{{}^{\prime}}$-th clouds respectively.

As shown in Equation No, the total execution cost is the sum of costs
associated with task execution on a VM and the cost of transferring data from
one task to another. 11.

$cost=\sum_{vm_{r}\in R}C_{vm_{r}}+\sum_{i=1}^{n}\sum_{v_{j}\in
succ(v_{i})}C_{v_{i},v_{j}}$ (11)

_MA_ | _AWS_ | _GCP_
---|---|---
_VM_ | _Per Minute($)_ | _VM_ | _Per hour($)_ | _VM_ | _Ten Minutes($)_ | _Per Minute($)_
B2MS | 0.0015 | m1.small | 0.06 | n1-highcpu-2 | 0.014 | 0.0012
B4MS | 0.003 | m1.medium | 0.12 | n1-highcpu-4 | 0.025 | 0.0023
B8MS | 0.006 | m1.large | 0.24 | n1-highcpu-8 | 0.05 | 0.0047
B16MS | 0.012 | m1.xlarge | 0.45 | n1-highcpu-16 | 0.1 | 0.0093
Table 1: VM costs for different cloud providers _MA_ | _AWS_ | _GCP_
---|---|---
Same center - Free | Same center- Free | Same center - Free
Across centers - $0.08/GB | Across centers - $0.02/GB | Across centers - $0.05/GB
Across clouds
_Data size_ | _Per GB($)_ | _Data size_ | _Per GB($)_ | _Data size_ | _Per GB($)_
Upto 100GB | Free | Upto 100GB | Free | 0-1TB | 0.19
First 10 TB | 0.11 | First 10 TB | 0.09 | 1-10TB | 0.18
Next 40TB | 0.075 | Next 40TB | 0.085 | 10TB+ | 0.15
Next 100TB | 0.07 | Next 100TB | 0.07 | -
Next 350TB | 0.06 | Greater than 150 TB | 0.05 | -
Table 2: Data-Transfer costs for different cloud providers Level | Rounds | Plaintexts | Vul | Time ($\mu s/block$)
---|---|---|---|---
1 | 4 | $2^{29}$ | 98 | 3.08
2 | 8 | $2^{61}$ | 67 | 3.58
3 | 12 | $2^{94}$ | 34 | 4.15
4 | 16 | $2^{118}$ | 10 | 4.63
5 | 20 | $2^{128}$ | 0 | 5.21
Table 3:  Security comparison of RC6 variants.

###  2.6 Security Mechanism

Due to data dependencies between tasks, data needs to be transferred between
tasks. To ensure secure communication, different security mechanisms can be
employed to achieve the goal of confidentiality. Similar to Jiang et al.
(2017), we focus on achieving data confidentiality using block ciphers. The
notion of _Security Level_ is used to measure of the strength of a cipher. The
security level is proportionally related to the number of rounds of
encryption. The designer has to make a trade off between security and time: To
ensure more security, we must go for a cipher with more encryption rounds.
Table 3 captures this trade off, where each row corresponds to one cipher with
level $L_{i}$. The Plaintexts column represents the number of plaintexts
needed for a successful cryptanalysis attack, and the Time column represents
the time required to encrypt a block (128 bits) of data. The Vul column
represents the vulnerability $V_{i}$ defined as the logarithm of the ratio of
the maximum number of plaintexts required by the brute-force search,
$PT_{bf}$, to the number of plaintexts required using a chosen cryptanalysis
algorithm, $PT_{cc}(L_{i})$ as shown in Equation No. 12 Chandramouli et al.
(2006). The table illustrates the comparison of parameters for different
variants of RC6, a widely used block cipher Jiang et al. (2011).

$V_{i}=\log_{2}\lfloor\frac{PT_{bf}}{PT_{cc}(L_{i})}\rfloor$ (12)

The system vulnerability is defined as a weighted sum of the vulnerabilities
of each data item, as shown in Equation No. 13 Jiang et al. (2017).

$V_{system}=\sum_{i=1}^{n}\sum_{v_{j}\in succ(v_{i})}W_{v_{i},v_{j}}\cdot
V_{v_{i},v_{j}}$ (13)

where $W_{v_{i},v_{j}}$ and $V_{v_{i},v_{j}}$ denote the weight and
vulnerability of the data between $v_{i}$ and $v_{j}$ respectively. The
maximum vulnerability $V_{\max}$ is got by setting $V_{v_{i},v_{j}}$ to the
cipher with the maximum vulnerability in Equation 13.

The encryption time can be characterized by a linear function of data size and
selected security level Xie and Qin (2007). If the data between $v_{i}$ and
$v_{j}$ is encrypted using level $L_{i}$ security, the time required to
encrypt is denoted by $T_{enc}[v_{i},v_{j}]$ given by Equation No. 14.

$\scriptsize T_{enc}[v_{i},v_{j}]=\left\\{\begin{array}[]{ c l
}0&\quad\textrm{if }\text{$v_{i},v_{j}$ are scheduled on the same VM
instance}\\\
t_{i}\cdot\frac{w_{v_{i},v_{j}}}{B}\cdot\frac{1}{w_{k,p}}&\quad\textrm{otherwise}\end{array}\right.$
(14)

where $t_{i}$ denotes the amount of time required to encrypt one block of data
using cipher of level $L_{i}$, $B$ denotes the block size (128 bits), and the
$v_{i}$ is assumed to be executed on $VM(k,p)$. The decryption overhead is
similar to that of encryption Jiang et al. (2017) and is denoted by
$T_{dec}[v_{i},v_{j}]$, the only difference is that it is executed on the VM
executing $v_{j}$.

###  2.7 Reliability Analysis

Reliability is defined as the probability of a failure-free execution of the
workflow. The occurrence of a failure is modeled as a Poisson Distribution
Farid et al. (2020). Let $\lambda_{k,p}$ denote the parameter of the
distribution for $VM(k,p)$. Similarly, let $\lambda_{k}$ and
$\lambda_{k^{\prime},k}$ denote the parameters for the communication links for
the $k$-th cloud and for those between the $k^{{}^{\prime}}$-th and the $k$-th
cloud, respectively. The probability that the data will be transferred
successfully between $v_{i}$ and $v_{j}$ is denoted by
$\mathcal{R}_{v_{i},v_{j}}$ and is given by Equation No. 15.

$\scriptsize\mathcal{R}_{v_{i},v_{j}}=\left\\{\begin{array}[]{ c l
}1&\quad\textrm{if }\text{$v_{i},v_{j}$ are scheduled on the same VM
instance}\\\ e^{-\lambda_{k}\cdot T_{comm}[v_{i},v_{j}]}&\quad\textrm{if
}k^{\prime}=k\\\ e^{-\lambda_{k^{\prime},k}\cdot
T_{comm}[v_{i},v_{j}]}&\quad\textrm{otherwise}\end{array}\right.$ (15)

where $v_{i},v_{j}$ are assumed to be scheduled on the $k^{{}^{\prime}}$-th
and $k$-th clouds respectively.

The probability that the VM instance $vm_{r}$ will execute successfully is
denoted by $\mathcal{R}_{vm_{r}}$ and is given in Equation No. 16.

$\mathcal{R}_{vm_{r}}=e^{-\lambda_{k,p}\cdot(LFT_{vm_{r}}-LST_{vm_{r}})}$ (16)

The workflow will execute successfully if all the data is transferred and all
the tasks are executed successfully. Assuming the failures are independent,
Equation No 17 gives the workflow’s reliability.

$reliability=\prod_{i=1}^{n}\prod_{v_{j}\in
pred(v_{i})}\mathcal{R}_{v_{j},v_{i}}\cdot\prod_{vm_{r}\in
R}\mathcal{R}_{vm_{r}}$ (17)

###  2.8 Problem Definition

A schedule $\mathcal{S}=(R,\mathcal{M},\mathcal{C},makespan,cost,reliability)$
is defined as a tuple consisting of: A pool of resources ($R$), a task to
resource mapping ($\mathcal{M}$), and an edge to cipher mapping
($\mathcal{C}$). $R$ is a mapping from each resource to the times it is leased
for, consisting of tuples of the form $(vm_{r},LST_{vm_{r}},LFT_{vm_{r}})$.
$\mathcal{M}$ is a mapping consisting of tuples of the form
$(v_{i},vm_{u_{i}},ST_{v_{i}},FT_{v_{i}})$, where task $v_{i}$ is allocated to
resource $vm_{u_{i}}$. $\mathcal{C}$ is a mapping consisting of tuples of the
form $(v_{i},v_{j},C_{v_{i},v_{j}})$, where $v_{j}\in succ(v_{i})$ and
$C_{v_{i},v_{j}}$ is the cipher used to encrypt the data between $v_{i}$ and
$v_{j}$. The problem we address in this paper is that of minimizing the total
makespan and cost and maximizing reliability subject to the security
constraints stated below.

Minimize $\left\\{\begin{array}[]{ c l }\textit{makespan}\\\
\textit{cost}\end{array}\right.$ Maximize $\left\\{\begin{array}[]{ c l
}\textit{reliability}\end{array}\right.$

Subject To $\left\\{\begin{array}[]{ c l }V_{system}\leq UV_{req}\\\
V_{v_{i},v_{j}}\leq UV_{v_{i},v_{j}}\end{array}\right.$

where $UV_{req}$ and $UV_{v_{i},v_{j}}$ denote the upper bounds on the system
and data item between $v_{i}$ and $v_{j}$ vulnerabilities, respectively. The
trade-off is between more security and time-overhead leading to more makespan,
cost and lower reliability. Before presenting our algorithm, we first present
the pseudocode to convert a task to resource mapping to a schedule in
Algorithm 1 similar to the one in Guo et al. (2018) and is described as
follows. We initialize the resources leased till now $R_{curr}$ and task to
resource mapping $\mathcal{M}$ to empty. If a task has predecessors, it can
start only after they finish, as illustrated in Lines No. 9, 10. For each
task, we find the decryption, encryption, transfer times, transfer costs, and
reliability associated with transferring data using the $process\\_task()$
routine in Algorithm 2. The routine simply computes the encryption, decryption
time using Equation No. 14, transfer time using Equation No. 3, transfer cost
using Equation No. 10 and reliability using Equation No. 15. The processing
time is computed in Line No. 13 using Equation No. 4. If the resource is
already hosted, we know that the task can start only after the current lease
finish time $LFT_{vm_{u_{i}}}$ as shown in Line No. 15, 16. Otherwise, we
first launch the corresponding VM instance with lease start time
$LST_{vm_{u_{i}}}$ set as shown in Line No. 19 and task start time after
booting as shown in Line No. 18. Finally, the finish time of the task is
calculated by adding the processing time to the start time as shown in Line
No. 21. In Line No. 22, the lease finish time updated to the finish time of
the task. After processing all the tasks, the makespan is given by the finish
time of the last task as shown in Line No. 24. Lines 25 to 30 compute the cost
and reliability associated with executing tasks.

Input: $G(V,E)$, Multi-cloud system parameters, Resource Pool ($R$), Security
Cipher Table similar to Table 3 ($cipher\\_tab$), Data to cipher mapping
($\mathcal{C}$), Task to resource mapping ($X$)

Output: $\mathcal{S}$

1 $\mathcal{M},R_{curr}\longleftarrow\emptyset$;

2 $cost\longleftarrow 0$;

3 $reliability\longleftarrow 1$;

4 for  _$v_{i}\in V$_ do

5 $vm_{u_{i}}\longleftarrow R[X[v_{i}]]$;

6 $VM(k,p)\longleftarrow type(vm_{u_{i}})$;

7 $exec\\_time\longleftarrow\frac{w(v_{i})}{w(VM(k,p))}$;

8 $ST_{v_{i}}\longleftarrow 0$;

9 for  _$v_{j}\in pred(v_{i})$_ do

10 $ST_{v_{i}}\longleftarrow\max(ST_{v_{i}},FT_{v_{j}})$;

11

12 $dec\\_time,transfer\\_time,transfer\\_cost,enc\\_time,rel\longleftarrow
process\\_task(v_{i})$;

13 $reliability\longleftarrow reliability\cdot rel$;

14 $PT_{v_{i}}\longleftarrow
dec\\_time+exec\\_time+transfer\\_time+enc\\_time$;

15 $cost\longleftarrow cost+transfer\\_cost$;

16 if  _$vm_{u_{i}}\in R_{curr}$_ then

17 $ST_{v_{i}}\longleftarrow\max(ST_{v_{i}},LFT_{vm_{u_{i}}})$;

18

19 else

20 $ST_{v_{i}}\longleftarrow\max(ST_{v_{i}},T_{boot}[VM(k,p)])$;

21 $LST_{vm_{u_{i}}}\longleftarrow ST_{v_{i}}-T_{boot}[VM(k,p)]$;

22 $R_{curr}\longleftarrow R_{curr}\cup\\{vm_{u_{i}}\\}$;

23

24 $FT_{v_{i}}\longleftarrow ST_{v_{i}}+PT_{v_{i}}$;

25 $LFT_{vm_{u_{i}}}\longleftarrow FT_{v_{i}}$;

26
$\mathcal{M}\longleftarrow\mathcal{M}\cup\\{(v_{i},vm_{u_{i}},ST_{v_{i}},FT_{v_{i}})\\}$;

27

28$makespan\longleftarrow FT_{v_{n}}$;

29 for  _$vm_{r}\in R_{curr}$_ do

30 $VM(k,p)\longleftarrow type(vm_{r})$;

31 Compute $cost_{vm_{r}}$ corresponding to lease period
$LFT_{vm_{r}}-LST_{vm_{r}}$ using Equation No. 8, 9;

32 $cost\longleftarrow cost+cost_{vm_{r}}$;

33 Compute $\mathcal{R}_{vm_{r}}$ corresponding to lease period
$LFT_{vm_{r}}-LST_{vm_{r}}$ using Equation No. 16;

34 $reliability\longleftarrow reliability\cdot\mathcal{R}_{vm_{r}}$;

35

36$\mathcal{S}\longleftarrow(R,\mathcal{M},\mathcal{C},makespan,cost,reliability)$;

37 return $\mathcal{S}$;

38

Algorithm 1 Particle to Schedule Mapping

Input: $G(V,E)$, Multi-cloud system parameters, Resource Pool ($R$), Security
Cipher Table similar to Table 3 ($cipher\\_tab$), Data to cipher mapping
($\mathcal{C}$), Task to resource mapping ($X$), $v_{i}$

Output: $dec\\_time,transfer\\_time,transfer\\_cost,$

$enc\\_time,rel$

1 $vm_{u_{i}}\longleftarrow R[X[v_{i}]]$;

2 $VM(k,p)\longleftarrow type(vm_{u_{i}})$;

3 $dec\\_time,transfer\\_time,transfer\\_cost,enc\\_time\longleftarrow 0$;

4 $rel\longleftarrow 1$;

5 for  _$v_{j}\in pred(v_{i})$_ do

6 $vm_{u_{j}}\longleftarrow R[X[v_{j}]]$;

7 if  _$u_{i}\neq u_{j}$_ then

8 Find $cipher$ used to encrypt data between $v_{j}$ and $v_{i}$ from
$\mathcal{C}$;

9 Find $T_{dec}[v_{j},v_{i}]$ encrypted using $cipher$ and executed on
$VM(k,p)$ from Equation No. 14;

10 $dec\\_time\longleftarrow dec\\_time+T_{dec}[v_{j},v_{i}]$;

11

12

13for  _$v_{j}\in succ(v_{i})$_ do

14 $vm_{u_{j}}\longleftarrow R[X[v_{j}]]$;

15 $VM(k^{\prime},p^{\prime})\longleftarrow type(vm_{u_{i}})$;

16 if  _$u_{i}\neq u_{j}$_ then

17 Find $cipher$ used to encrypt data between $v_{i}$ and $v_{j}$ from
$\mathcal{C}$;

18 Find $T_{enc}[v_{i},v_{j}]$ encrypted using $cipher$ and executed on
$VM(k,p)$ from Equation No. 14;

19 if  _$k^{\prime}\neq k$_ then

20 $transfer\\_time\longleftarrow
transfer\\_time+\frac{w(v_{i},v_{j})}{B_{k,k^{\prime}}}$;

21 Find pricing $c_{k,k^{\prime}}$ according to Table 2;

22 $transfer\\_cost\longleftarrow transfer\\_cost+c_{k,k^{\prime}}\cdot
w(v_{i},v_{j})$;

23 $rel\longleftarrow rel\cdot
e^{\lambda_{k,k^{\prime}}\cdot\frac{w(v_{i},v_{j})}{B_{k,k^{\prime}}}}$;

24

25 else

26 $transfer\\_time\longleftarrow
transfer\\_time+\frac{w(v_{i},v_{j})}{B_{k}}$;

27 $rel\longleftarrow rel\cdot
e^{\lambda_{k}\cdot\frac{w(v_{i},v_{j})}{B_{k}}}$;

28

29 $enc\\_time\longleftarrow enc\\_time+T_{enc}[v_{i},v_{j}]$;

30

31

32return $dec\\_time,transfer\\_time,transfer\\_cost,enc\\_time,rel$;

Algorithm 2 $process\\_task$

##  3 Proposed Algorithm

Our solution methodology is divided into two parts: assigning each task to a
VM and then the appropriate ciphers. We first describe the process employed to
assign ciphers to data because this applies to any task to resource
allocation.

###  3.1 Cipher Assignment

Given a particular task to resource mapping, we wish to assign the ciphers to
data so that the total encryption and decryption overhead is minimized subject
to the security constraints as stated below.

Minimize $\left\\{\begin{array}[]{ c l }\sum_{i=1}^{n}\sum_{v_{j}\in
succ(v_{i})}T_{enc}[v_{i},v_{j}]+T_{dec}[v_{i},v_{j}]\end{array}\right.$

Subject To $\left\\{\begin{array}[]{ c l }V_{system}\leq UV_{req}\\\
V_{v_{i},v_{j}}\leq UV_{v_{i},v_{j}}\end{array}\right.$

We use a Dynamic Programming (DP) strategy to solve this problem as presented
in Algorithm 3 and described as follows. The DP entry $dp[h][Vul]$ describes
the least time to encrypt and decrypt the first $h$ edges and the
corresponding cipher for the $h-$th edge, as shown in Line No. 21 for the
security constraint $V_{system}\leq Vul$. We begin by finding the VMs that the
tasks $v_{i},v_{j}$ are executed on in Line No 4. Then assignment of all
possible ciphers to the $h-$th edge is done in Line No. 8. If the constraints
in Line No. 9 are satisfied, we calculate the encryption and decryption time
in Line No. 10. If this is the first edge ($h=1$), we find the least
encryption time as in Line No. 13. If not, we find the remaining vulnerability
$V_{remaining}$ in Line No. 16 that the first $h-1$ edges should satisfy using
Equation No. 13. The total time will be given by the best time to encrypt the
$h-1$ edges and the time to encrypt the $h-$th edge, which is calculated in
Line No. 17. The total minimum time is updated in Line No. 19. The overall
recurrence relation is shown in Equation No. 18. Finally, we begin assigning
the ciphers to each edge in Line No. 23- 27. We start adding the ciphers in a
reverse manner _i.e._ first the last edge will be assigned the cipher, then
the second last, and so on. As mentioned earlier, the DP entry $dp[\lvert
E\rvert][UV_{req}]$ stores the total minimum time and the cipher corresponding
to the last edge for the constraint of $UV_{req}$. Hence, we start with
$Vul=UV_{req}$ as shown in Line No. 22. The corresponding cipher is got from
the dp table entry $dp[h][Vul]$ in Line No. 25, and $Vul$ is updated to the
new constraint for the reduced edge set $\\{e_{1},e_{2},\ldots,e_{h-1}\\}$
according to Equation No. 13 in Line No. 27.

$\scriptsize dp[h][Vul][0]=\left\\{\begin{array}[]{ c l }\min_{cipher\in
cipher\\_tab}T_{enc}[v_{i},v_{j}]+T_{dec}[v_{i},v_{j}]&\quad\textrm{if
}\text{h = 0}\\\ \min_{cipher\in
cipher\\_tab}T_{enc}[v_{i},v_{j}]+T_{dec}[v_{i},v_{j}]\\\ +dp[h-1][Vul-
W_{v_{i},v_{j}}\cdot
V_{v_{i},v_{j}}]&\quad\textrm{otherwise}\end{array}\right.$ (18)

Note that the weights $W_{v_{i},v_{j}}$ and constraint $UV_{req}$ may be
decimals, so we convert them into integers by multiplying with powers of 10.

Input: $G(V,E)$, Multi-cloud system parameters, Task to resource mapping
($X$), Security Cipher Table similar to Table 3 ($cipher\\_tab$),
$W_{v_{i},v_{j}},UV_{req},UV_{v_{i},v_{j}}$

Output: $\mathcal{C}$

1 Initialize DP table $dp[\lvert E\rvert+1][UV_{req}+1]$;

2 for  _$h\longleftarrow 1$ to $\lvert E\rvert$_ do

3 $(v_{i},v_{j})\longleftarrow e_{h}$;

4 $VM(k,p)\longleftarrow
type(R[X[v_{i}]]),VM(k^{\prime},p^{\prime})\longleftarrow type(R[X[v_{j}]])$;

5 for  _$Vul\longleftarrow 0$ to $UV_{req}$_ do

6 $best\\_time\longleftarrow INT\\_MAX$;

7 $best\\_cipher\longleftarrow None$;

8 for  _$cipher\in cipher\\_tab$_ do

9 if  _$W_{v_{i},v_{j}}\cdot V_{cipher}\leq Vul,V_{cipher}\leq
UV_{v_{i},v_{j}}$_ then

10 Calculate $T_{enc}[v_{i},v_{j}],T_{dec}[v_{i},v_{j}]$ corresponding to
$cipher$ and assuming $v_{i},v_{j}$ are executed on
$VM(k,p),VM(k^{\prime},p^{\prime})$ respectively from Equation No. 14;

11 if  _$h=1$_ then

12 if  _$T_{enc}[v_{i},v_{j}]+T_{dec}[v_{i},v_{j}] <best\\_time$_ then

13 $best\\_time\longleftarrow T_{enc}[v_{i},v_{j}]+T_{dec}[v_{i},v_{j}]$;

14 $best\\_cipher\longleftarrow cipher$;

15

16

17 else

18 $V_{remaining}=Vul-W_{v_{i},v_{j}}\cdot V_{cipher}$;

19 $total\\_time\longleftarrow
dp[h-1][V_{remaining}][0]+T_{enc}[v_{i},v_{j}]+T_{dec}[v_{i},v_{j}]$;

20 if  _$total\\_time <best\\_time$_ then

21 $best\\_time\longleftarrow total\\_time$;

22 $best\\_cipher\longleftarrow cipher$;

23

24

25

26

27 $dp[h][Vul]\longleftarrow[best\\_time,best\\_cipher]$;

28

29

30$Vul\longleftarrow UV_{req}$;

31 for  _$h\longleftarrow\lvert E\rvert$ to $1$_ do

32 $(v_{i},v_{j})\longleftarrow e_{h}$;

33 $C_{v_{i},v_{j}}\longleftarrow dp[h][Vul][1]$;

34 Add tuple $(v_{i},v_{j},C_{v_{i},v_{j}})$ to $\mathcal{C}$;

35 $Vul\longleftarrow Vul-W_{v_{i},v_{j}}\cdot V_{v_{i},v_{j}}$;

36

37

38return $\mathcal{C}$;

Algorithm 3 Cipher Assignment Algorithm

###  3.2 VM Allocation

We follow an efficient list-based approach to assign resources to tasks. List-
based scheduling generally works in two phases: Ordering the tasks based on
some rank followed by assigning the resources to the tasks in order one by
one. Firstly, we reduce the size of the resource pool under consideration
similar to Rodriguez and Buyya (2014) as follows: Let $\mathcal{P}$ denote the
largest set of tasks that can be executed in parallel. Then $R$ can be
redefined as $R=\\{vm_{r}:r\in[\lvert\mathcal{P}\rvert\cdot n]\\}$, by
considering a VM instance of each type for each task in $\mathcal{P}$. One way
to find the set $\mathcal{P}$ is to find the largest set of tasks, all having
the same topological level. Since all the tasks have the same topological
level, they have no dependency relation. The set $\mathcal{P}$ computed in
this manner may not necessarily be the largest one. Secondly, we define the
notion of rank of a task in Definition 6.

###### Definition 6

$Rank(v_{i})$ denotes the rank of the task $v_{i}$, which gives an idea of the
worst-case processing time along all paths from $v_{i}$ to $v_{n}$ formulated
in Equation No. 19.

$\scriptsize Rank_{v_{i}}=\left\\{\begin{array}[]{ c l }\max_{v_{j}\in
succ(v_{i})}\\{Rank(v_{j})\\}+\overline{T_{exec}[v_{i},VM(k,p)]}\\\
+\sum_{v_{j}\in succ(v_{i})}\overline{T_{comm}[v_{i},v_{j}]}&\quad\textrm{if
}v_{i}=v_{1}\\\ \\\ \sum_{v_{j}\in
pred(v_{i})}\overline{T_{exec}[v_{i},VM(k,p)]}&\quad\textrm{else if
}v_{i}=v_{n}\\\ \\\ \max_{v_{j}\in
succ(v_{i})}\\{Rank(v_{j})\\}+\overline{T_{exec}[v_{i},VM(k,p)]}\\\
+\sum_{v_{j}\in
succ(v_{i})}+\overline{T_{comm}[v_{i},v_{j}]}&\quad\textrm{otherwise}\end{array}\right.$
(19)

where $\overline{T_{exec}[v_{i},VM(k,p)]}$ denotes the average execution time
of executing $v_{i}$ on VM types,
$\overline{T_{comm}[v_{i},v_{j}]}=\frac{w(v_{i},v_{j})}{\overline{B}}$,
$\overline{B}$ denoting the average bandwidth. The allocation algorithm known
as List Based Scheduler (LBS) is presented in Algorithm 4 and described as
follows: We start allocating tasks bottom-up because the processing time of a
task depends majorly on the successor nodes, as seen from Equation No. 4. For
this, we sort the tasks in decreasing order of their topological levels,
prioritizing tasks with a higher rank in Line No. 1, 2. Since tasks with the
same topological level can execute simultaneously, we assign different VM
instances to each of them, and the set $vms\\_allocated$ keeps track of the
VMs allocated till now, which is initialized to empty set in Line No. 8. We
use the $process\\_task$ routine to come up with the necessary components in
the processing time, denoted by $PT_{v_{i},vm_{r}}$ when $v_{i}$ is assumed to
be executed on $vm_{r}$ in Line No. 12, 13. Since we know where each successor
is allocated, we can compute the $transfer\\_time,transfer\\_cost,rel$. Since
we do not know the cipher assignment yet, we assume $enc\\_time,dec\\_time$ to
be zero. The cost and reliability associated with processing time and data-
transfer are calculated in Line No. 14-17. After this, we calculate a metric
$metric_{v_{i},vm_{r}}$ based on a linear combination of cost, processing
time, and reliability with each parameter normalized using min-max
normalization in Line No. 20. The weights $\alpha$, $\beta$, and $\gamma$ give
the relative importance between the parameters. In this study, we give more
importance to cost and choose the weights: $\alpha=0.7,\beta=0.2,\gamma=0.1$.
A VM instance with a lesser value of $metric_{v_{i},vm_{r}}$ is desirable.
Hence we sort the instances in increasing order of $metric_{v_{i},vm_{r}}$ and
assign the first VM instance yet not assigned to any previous task with the
same topological level in Line No. 22-27 to increase parallelizability. Our
algorithm differs from list-based methods used in other algorithms Tang (2021)
Xie et al. (2017), in that it allocates tasks in a reverse order, i.e., it
allocates a successor task before its predecessor task. This is because, as
mentioned earlier, the processing time is mostly dependent on the successor
nodes.

Lastly, we propose an iterative local search algorithm (LS) that takes as
input a VM allocation and reassigns VMs to tasks for better makespan, cost,
and reliability, as illustrated in Algorithm 5. The tasks are first ordered by
their Ranks in Line No. 1. For a fixed number of iterations, the algorithm
begins by reassigning a VM instance $vm_{r}$ to each task $v_{i}$ and
computing the corresponding
$makespan(s_{v_{i},vm_{r}}),cost(cost_{v_{i},vm_{r}}),reliability(\mathcal{R}_{v_{i},vm_{r}})$.
Similar to Algorithm 4, we use min-max normalization to come up with a metric
with $\alpha=0.6,\beta=0.2,\gamma=0.2$ in Line No. 9. The VM instance
$vm_{u_{i}}$ with least value is assigned to the task $v_{i}$ in Line No. 10.
If there is no change in the allocation, we terminate the procedure as shown
in Line No. 11, 12.

Input: $G(V,E)$, Multi-cloud system parameters, Resource Pool ($R$)

Output: Task to resource mapping ($X$)

1 Sort tasks in decreasing order of their Ranks in list $Q$;

2 Sort tasks in decreasing order of their topological levels, break ties based
on the order in $Q$. Store the resulting order in list $L$;

3 $prev\\_lvl\longleftarrow-1$;

4 $vms\\_allocated\longleftarrow\emptyset$;

5 for  _$v_{i}\in L$_ do

6 $curr\\_lvl\longleftarrow top\\_level(v_{i})$;

7 if  _$prev\\_lvl\neq curr\\_lvl$_ then

8 $vms\\_allocated\longleftarrow\emptyset$;

9

10 for  _$vm_{r}\in R$_ do

11 $VM(k,p)\longleftarrow type(vm_{r})$;

12 $exec\\_time\longleftarrow\frac{w(v_{i})}{w(VM(k,p))}$;

13 $dec\\_time,transfer\\_time,transfer\\_cost,$ $enc\\_time,rel\longleftarrow
process\\_task(v_{i})$;

14 $PT_{v_{i},vm_{r}}\longleftarrow
dec\\_time+exec\\_time+transfer\\_time+enc\\_time$;

15 Calculate $lease\\_cost$ corresponding to lease period $PT_{v_{i},vm_{r}}$
using Equation No. 8, 9;

16 $cost_{v_{i},vm_{r}}\longleftarrow lease\\_cost+transfer\\_cost$;

17 Calculate $lease\\_rel$ corresponding to lease period $PT_{v_{i},vm_{r}}$
using Equation No. 16;

18 $\mathcal{R}_{v_{i},vm_{r}}\longleftarrow rel\cdot lease\\_rel$;

19

20 Calculate
$PT_{v_{i},\min},PT_{v_{i},\max},cost_{v_{i},\min},cost_{v_{i},\max},$

21 $\mathcal{R}_{v_{i},\min},\mathcal{R}_{v_{i},\max}$ over all VM instances
in $R$;

22 for  _$vm_{r}\in R$_ do

23
$metric_{v_{i},vm_{r}}\longleftarrow\alpha\cdot\frac{cost_{v_{i},vm_{r}}-cost_{v_{i},\min}}{cost_{v_{i},\max}-cost_{v_{i},\min}}+\beta\cdot\frac{PT_{v_{i},vm_{r}}-PT_{v_{i},\min}}{PT_{v_{i},\max}-PT_{v_{i},\min}}+\gamma\cdot\frac{\mathcal{R}_{v_{i},\max}-\mathcal{R}_{v_{i},vm_{r}}}{\mathcal{R}_{v_{i},\max}-\mathcal{R}_{v_{i},\min}}$

24 Sort the VM instances in increasing order of $metric_{v_{i},vm_{r}}$ in
list $U$;

25 for  _$vm_{r}\in U$_ do

26 if  _$vm_{r}\notin vms\\_allocated$_ then

27 $X[v_{i}]\longleftarrow r$;

28 $vms\\_allocated\longleftarrow vms\\_allocated\cup\\{vm_{r}\\}$;

29 break;

30

31

32 $prev\\_lvl\longleftarrow curr\\_lvl$;

33

34return $X$;

Algorithm 4 LBS Allocation Algorithm

Input: $G(V,E)$, Multi-cloud system parameters, Resource Pool ($R$), Task to
resource mapping ($X$)

Output: New task to resource mapping ($X^{\prime}$)

1 Sort tasks in decreasing order of their Ranks in list $L$;

2 for  _$itr\longleftarrow 1$ to $num\\_iter$_ do

3 for  _$v_{i}\in L$_ do

4 for  _$vm_{r}\in R$_ do

5 Assign $vm_{r}$ to $v_{i}$ to get new schedule $X^{\prime}$;

6 Calculate $s_{v_{i},vm_{r}},cost_{v_{i},vm_{r}},\mathcal{R}_{v_{i},vm_{r}}$
corresponding to $X^{\prime}$ using Algorithm 1;

7

8 Calculate
$s_{v_{i},\min},s_{v_{i},\max},cost_{v_{i},\min},cost_{v_{i},\max}$

9 $\mathcal{R}_{v_{i},\min},\mathcal{R}_{v_{i},\max}$ over all VM instances in
$R$.;

10 $vm_{u_{i}}\longleftarrow\min_{vm_{r}\in
R}\\{\alpha\cdot\frac{cost_{v_{i},vm_{r}}-cost_{v_{i},\min}}{cost_{v_{i},\max-
cost_{v_{i},\min}}}+\beta\cdot\frac{s_{v_{i},vm_{r}}-s_{v_{i},\min}}{s_{v_{i},\max}-s_{v_{i},\min}}+\gamma\cdot\frac{\mathcal{R}_{v_{i},\max}-\mathcal{R}_{v_{i},vm_{r}}}{\mathcal{R}_{v_{i},\max}-\mathcal{R}_{v_{i},\min}}\\}$;

11 $X^{\prime}[v_{i}]\longleftarrow u_{i}$;

12

13 if  _$X^{\prime}=X$_ then

14 break;

15

16

17return $X^{\prime}$;

Algorithm 5 LS Algorithm

The overall algorithm proceeds by the below-listed steps:

  * •

Calculate the reduced resource pool $R$ using BFS Bundy and Wallen (1984).

  * •

Use Algorithm 4 to obtain the task to VM allocation using Algorithm 4.

  * •

(Optional) Use Algorithm 5 to get an improved task for VM allocation.

  * •

Compute the edge to cipher mapping $\mathcal{C}$ corresponding to the obtained
task to VM allocation using Algorithm 3.

  * •

Use Algorithm 1 to compute the final schedule $\mathcal{S}$.

###  3.3 Complexity Analysis

The time complexity for the $process\\_task$ routine is $\mathcal{O}(n)$
because each task can have at most $n$ successors or predecessors, hence the
time needed for one task in Algorithm 1 is $\mathcal{O}(n)$. For all tasks,
the total time needed will be $\mathcal{O}(n^{2})$. Finally iterating through
$R_{curr}$ in Line No. 25 of Algorithm 1 takes at most
$\mathcal{O}(\mathcal{N}\cdot n)$ time as $\lvert
R_{curr}\rvert\leq\mathcal{N}\cdot n$. Algorithm 3 is a DP-based approach, and
the time needed for computing one entry $dp[i][j]$ depends on the number of
ciphers available for encryption $\lvert cipher\\_tab\rvert$ as seen from Line
No. 7. Hence, the total time needed to compute all entries will be
$\mathcal{O}(\lvert cipher\\_tab\rvert\cdot UV_{req}\cdot n^{2})$ as $\lvert
E\rvert\leq n^{2}$. In Algorithm 4, computing the topological levels and Ranks
takes $\mathcal{O}(n^{2})$ time. For each task, for each VM instance pair,
calculating the processing time, cost and reliability take $\mathcal{O}(n)$
time as seen from the $process\\_task$ routine. Sorting the metrics over all
VM instance pairs takes $\mathcal{O}(\lvert R\rvert\cdot log\lvert R\rvert)$
time. Hence for one task, the time required is $\mathcal{O}(\lvert
R\rvert\cdot(n+\log\lvert R\rvert))$. For all tasks, the time complexity will
be $\mathcal{O}(n\cdot\lvert R\rvert\cdot(n+\log\lvert R\rvert))$. As $\lvert
R\rvert\leq\mathcal{N}\cdot n$, the time complexity will be at most
$\mathcal{O}(\mathcal{N}\cdot n^{2}\cdot(n+\log
n+\log\lvert\mathcal{N}\rvert))$. Most approaches use evolutionary methods for
VM allocation Choudhary et al. (2018), Beegom and Rajasree (2015), Guo et al.
(2018), which are very time-consuming compared to Algorithm 4. Lastly, we look
at the time needed for Algorithm 5. For each reassignment of a VM instance to
a task in Line No. 5, we compute the schedule in Line No. 6, which takes
$\mathcal{O}(n^{2})$ time. Hence the total time needed over all iterations,
tasks, and VM instances will be $\mathcal{O}(num\\_iter\cdot\mathcal{N}\cdot
n^{4})$.

##  4 Experimental Evaluation

In this section, we describe the experimental evaluation of the proposed
solution approach. First, we start by describing the experimental setup and
example task graphs.

###  4.1 Experimental setup, Task graphs, and Algorithms

We implement the proposed methodology on a workbench system with i7
$12^{\text{th}}$ generation processor and 16GB memory in Python 3.8.10. For
this study, we consider two real-world task graphs: Epigenomics and LIGO,
which are widely used in literature Tang (2021), Szabo and Kroeger (2012) for
comparison. We consider Epigenomics workflows with $n=24,100$ and Cybershake
workflows with $n=30,100$ Szabo and Kroeger (2012). The structure of each
workflow can be obtained in XML format from the website Generator (Accessed 14
September 2022). The smaller size of each workflow is called Small (S), and
the larger one is called Large (L). Due to space limitation, we only consider
two workflows with two sizes each. More information about the workflows can be
obtained from bharathi2008characterization.

###  4.2 Competitive Algorithms

LBS is compared with the following methods:

  * •

Gravitational Search Algorithm (GSA) Choudhary et al. (2018): It aims to
minimize the makespan and cost of scheduling the workflow in single cloud.

  * •

Fault-tolerant Cost-Efficient workflow Scheduling (FCWS) Tang (2021): This is
a list-based approach for scheduling workflows on multi-cloud systems taking
into account the makespan, cost and reliability. VMs are assigned based on a
linear combination of cost and reliability. Fault-tolerance is based on hazard
rate of the distribution used for reliability analysis. In our case of Poisson
distribution, the condition for fault-tolerance used in FCWS algorithm does
not apply, so we do not consider it. Also FCWS does not consider communication
cost while assigning VMs, so we include it in the cost while assigning VMs.

Since LBS, GSA and FCWS are task to VM allocation algorithms, we use Algorithm
3 on top of them to decide the ciphers for encryption. We do not compare with
other workflow scheduling algorithms that take into account security
constraints like Wen et al. (2016), because it does not consider makespan.

###  4.3 Experimental description

We implement the proposed methodology on a workstation having $i5$,
$10^{\text{th}}$ generation processor and 32GB memory in Python 3.8.10.
Parameters of our multi-cloud system are set as in Tang (2021). VMs are set
with varying computation capacities from 1 to 32. The average bandwidth
internal to a cloud is set to 20Mbps, and external bandwidth is set to
100Mbps. Pricing mechanisms are set proportional to VM compute capacities as
in Table 1 and data transfer costs according to Table 2. The boot time of each
VM was set to 97 seconds Rodriguez and Buyya (2014). The number of cloud
providers considered is six, two from each type of _MA_ , _AWS_ , and _GCP_.
Two cloud providers with the same types are assumed to be located in different
centers. The encryption levels and overhead is chosen as in Table 3. We assume
that $w_{k,p}=1$. The security constraints are set as follows Jiang et al.
(2017): $UV_{req}=\eta\cdot V_{\max}$, where $\eta\in[0.1,0.7]$ in steps of
0.1. $UV_{v_{i},v_{j}}$ is a randomly chosen security cipher from Table 3 and
the weights $W_{v_{i},v_{j}}\in[0.1,1]$. The parameter of the Poisson
Distribution is set uniformly at random $\lambda\in[10^{-8},10^{-7}]$. We use
Algorithm 5 on top of each algorithm to see the improvement obtained. Each
experiment is performed 15 times, and the results are reported on average.

|  |
---|---|---
(a) | (b) | (c)
Figure 1: Epigenomics graph with $n=24$ |  |
---|---|---
(a) | (b) | (c)
Figure 2: Epigenomics graph with $n=100$ |  |
---|---|---
(a) | (b) | (c)
Figure 3: Cybershake graph with $n=30$ |  |
---|---|---
(a) | (b) | (c)
Figure 4: Cybershake graph with $n=100$

  1. 1.

_Epigenomics:_ For Small size, GSA gives the least makespan with LBS having
slightly more makespan, both perform much better than FCWS by 71.93% as seen
from Fig. 1 (a). From Fig. 1 (b) LBS gives much lesser cost than GSA by 59.37%
followed by FCWS by 77.18%. From Fig. 1 (c), in terms of reliability, all
algorithms perform similarly with LBS performing slightly better than GSA by
0.15% and FCWS by 0.2%. The application of LS gives a slight improvement in
makespan for GSA and LBS and a significant improvement in FCWS by 52.74%. The
improvement in cost is significant in all algorithms: 78.09% for GSA, 90.52%
for LBS, and 58.86% for FCWS. The improvement in reliability is not so much.

For Large size, LBS gives the least makespan outperforming GSA by 13.6%
followed by FCWS by 85.5% from Fig. 2 (a). From Fig. 2 (b) in terms of cost,
LBS performs significantly better than GSA by 74.66% and FCWS by 94.04%. In
terms of reliability, GSA and FCWS perform similarly and LBS outperforms them
by 1.06% as seen from Fig 2 (c). The application of LS gives a slight
improvement in makespan for LBS and significant improvement in GSA by 13.47%
and FCWS by 52.74%. The improvement in cost is significant in all algorithms:
96.84% for GSA, 92.02% for LBS, and 85.09% for FCWS.

  2. 2.

_Cybershake:_ For Small size, LBS gives the least makespan outperforming GSA
by 33.81% followed by FCWS by 84.27% as seen in Fig. 3 (a). From Fig 3 (b) LBS
gives the least cost outperforming GSA by 29.92% and FCWS by 69.24%. From Fig.
3 (c), in terms of reliability, all algorithms perform similarly. The
application of LS gives a degraded makespan of LBS by 20.71% while giving a
significant improvement in GSA by 7.34% and FCWS by 58.78%. The improvement in
cost is significant in all algorithms: 26.39% for GSA, 26.24% for LBS, and
94.44% for FCWS. The improvement in reliability is considerable only in GSA by
0.53%.

For Large size, LBS gives the least makespan outperforming GSA by 69.12%
followed by FCWS by 81.16% from Fig. 2 (a). From Fig. 2 (b) in terms of cost,
LBS performs significantly better than GSA by 53.02% and FCWS by 68.47%. In
terms of reliability, LBS gives the most reliability outperforming FCWS by
0.84% and GSA by 3.92% as seen from Fig 2 (c). The application of LS gives a
degraded makespan for LBS by 33.83% while giving a significant improvement in
GSA by 30.72% and FCWS by 54.26%. The improvement in cost, and reliability is
significant in all algorithms: 42.69%, 2.77% for GSA, 27.73%, 0.84% for LBS,
and 89.75%, 1.63% for FCWS.

In summary, as the task graph size increases, performance degrades because we
have more task nodes and hence more processing time is needed. As the value of
$\eta$ increases, makespan, and cost decrease while reliability increases.
This is because when the security constraint becomes looser, we can use
ciphers with less overhead to encrypt data reducing the processing time. LBS
always outperforms the other algorithms in terms of cost and reliability and
makespan for the majority of the cases. The application of LS brings
improvement in makespan, cost, and reliability of GSA and FCWS. For LBS, the
application of LS always gives improvements in cost and reliability. The
makespan also improves in some cases.

##  5 Conclusion and Future Research Directions

In this paper, we have studied the problem of scheduling the tasks present in
a scientific workflow in a multi-cloud system. The goal of the scheduling is
to minimize the makespan and cost and to maximize reliability subject to
security constraints. For this problem, we have developed an efficient
solution methodology. This has been validated with real-life scientific
workflows. In the future, we would like to include fault tolerance in our
model and look for more efficient solution methodologies.

## References

  * Al-Maytami et al. (2019) Al-Maytami BA, Fan P, Hussain A, Baker T, Liatsis P (2019) A task scheduling algorithm with improved makespan based on prediction of tasks computation time algorithm for cloud computing. IEEE Access 7:160916–160926
  * Beegom and Rajasree (2015) Beegom A, Rajasree M (2015) Genetic algorithm framework for bi-objective task scheduling in cloud computing systems. In: International Conference on Distributed Computing and Internet Technology, Springer, pp 356–359
  * Bundy and Wallen (1984) Bundy A, Wallen L (1984) Breadth-first search. In: Catalogue of artificial intelligence tools, Springer, pp 13–13
  * Chandramouli et al. (2006) Chandramouli R, Bapatla S, Subbalakshmi K, Uma R (2006) Battery power-aware encryption. ACM Transactions on Information and System Security (TISSEC) 9(2):162–180
  * Choudhary et al. (2018) Choudhary A, Gupta I, Singh V, Jana PK (2018) A gsa based hybrid algorithm for bi-objective workflow scheduling in cloud computing. Future Generation Computer Systems 83:14–26
  * data transfer costs (Accessed 11 September 2022a) data transfer costs AWS (Accessed 11 September 2022a) [online]. https://aws.amazon.com/ec2/pricing/on-demand/
  * data transfer costs (Accessed 11 September 2022b) data transfer costs GCP (Accessed 11 September 2022b) [online]. https://cloud.google.com/vpc/network-pricing
  * data transfer costs (Accessed 11 September 2022c) data transfer costs MA (Accessed 11 September 2022c) [online]. https://azure.microsoft.com/en-in/pricing/details/bandwidth/
  * Di et al. (2016) Di S, Robert Y, Vivien F, Cappello F (2016) Toward an optimal online checkpoint solution under a two-level hpc checkpoint model. IEEE Transactions on parallel and distributed systems 28(1):244–259
  * Diaz-Montes et al. (2015) Diaz-Montes J, Diaz-Granados M, Zou M, Tao S, Parashar M (2015) Supporting data-intensive workflows in software-defined federated multi-clouds. IEEE Transactions on Cloud Computing 6(1):250–263
  * Farid et al. (2020) Farid M, Latip R, Hussin M, Hamid NAWA (2020) Scheduling scientific workflow using multi-objective algorithm with fuzzy resource utilization in multi-cloud environment. IEEE Access 8:24309–24322
  * Generator (Accessed 14 September 2022) Generator W (Accessed 14 September 2022) [online]. https://confluence.pegasus.isi.edu/display/pegasus/Deprecated+Workflow+Generator
  * Guo et al. (2018) Guo W, Lin B, Chen G, Chen Y, Liang F (2018) Cost-driven scheduling for deadline-based workflow across multiple clouds. IEEE Transactions on Network and Service Management 15(4):1571–1585
  * Han et al. (2018) Han L, Canon LC, Casanova H, Robert Y, Vivien F (2018) Checkpointing workflows for fail-stop errors. IEEE Transactions on Computers 67(8):1105–1120
  * Jiang et al. (2011) Jiang K, Eles P, Peng Z (2011) Optimization of message encryption for distributed embedded systems with real-time constraints. In: 14th IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems, IEEE, pp 243–248
  * Jiang et al. (2017) Jiang W, Pop P, Jiang K (2017) Design optimization for security-and safety-critical distributed real-time applications. Microprocessors and Microsystems 52:401–415
  * Kang et al. (2018) Kang S, Veeravalli B, Aung KMM (2018) Dynamic scheduling strategy with efficient node availability prediction for handling divisible loads in multi-cloud systems. Journal of Parallel and Distributed Computing 113:1–16
  * Li et al. (2018) Li R, Wu CQ, Hou A, Wang Y, Gao T, Xu M (2018) On scheduling of high-throughput scientific workflows under budget constraints in multi-cloud environments. In: 2018 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications (ISPA/IUCC/BDCloud/SocialCom/SustainCom), IEEE, pp 1087–1094
  * Li et al. (2015) Li X, Ma H, Yao W, Gui X (2015) Data-driven and feedback-enhanced trust computing pattern for large-scale multi-cloud collaborative services. IEEE transactions on services computing 11(4):671–684
  * Mastelic et al. (2014) Mastelic T, Oleksiak A, Claussen H, Brandic I, Pierson JM, Vasilakos AV (2014) Cloud computing: Survey on energy efficiency. Acm computing surveys (csur) 47(2):1–36
  * Miraftabzadeh et al. (2016) Miraftabzadeh SA, Rad P, Jamshidi M (2016) Efficient distributed algorithm for scheduling workload-aware jobs on multi-clouds. In: 2016 11th System of Systems Engineering Conference (SoSE), IEEE, pp 1–8
  * Rodriguez and Buyya (2014) Rodriguez MA, Buyya R (2014) Deadline based resource provisioningand scheduling algorithm for scientific workflows on clouds. IEEE transactions on cloud computing 2(2):222–235
  * Sooezi et al. (2015) Sooezi N, Abrishami S, Lotfian M (2015) Scheduling data-driven workflows in multi-cloud environment. In: 2015 IEEE 7th international conference on cloud computing technology and science (CloudCom), IEEE, pp 163–167
  * Stillwell et al. (2012) Stillwell ML, Vivien F, Casanova H (2012) Virtual machine resource allocation for service hosting on heterogeneous distributed platforms. In: IPDPS 2012, IEEE, x-pays= US
  * Szabo and Kroeger (2012) Szabo C, Kroeger T (2012) Evolving multi-objective strategies for task allocation of scientific workflows on public clouds. In: 2012 IEEE Congress on Evolutionary Computation, IEEE, pp 1–8
  * Tang (2021) Tang X (2021) Reliability-aware cost-efficient scientific workflows scheduling strategy on multi-cloud systems. IEEE Transactions on Cloud Computing
  * Tekawade and Banerjee (2023) Tekawade A, Banerjee S (2023) A cost effective reliability aware scheduler for task graphs in multi-cloud system. In: 15th International Conference on COMmunication Systems & NETworkS, COMSNETS 2023, Bangalore, India, January 3-8, 2023, IEEE, pp 295–303, DOI 10.1109/COMSNETS56262.2023.10041331, URL https://doi.org/10.1109/COMSNETS56262.2023.10041331
  * Wen et al. (2016) Wen Z, Cała J, Watson P, Romanovsky A (2016) Cost effective, reliable and secure workflow deployment over federated clouds. IEEE Transactions on Services Computing 10(6):929–941
  * Xie et al. (2017) Xie G, Chen Y, Xiao X, Xu C, Li R, Li K (2017) Energy-efficient fault-tolerant scheduling of reliable parallel applications on heterogeneous distributed embedded systems. IEEE Transactions on Sustainable Computing 3(3):167–181
  * Xie and Qin (2007) Xie T, Qin X (2007) Improving security for periodic tasks in embedded systems through scheduling. ACM Transactions on Embedded Computing Systems (TECS) 6(3):20–es
  * Zhou et al. (2016) Zhou A, Wang S, Cheng B, Zheng Z, Yang F, Chang RN, Lyu MR, Buyya R (2016) Cloud service reliability enhancement via virtual machine placement optimization. IEEE Transactions on Services Computing 10(6):902–913
  * Zhou et al. (2019) Zhou X, Zhang G, Sun J, Zhou J, Wei T, Hu S (2019) Minimizing cost and makespan for workflow scheduling in cloud using fuzzy dominance sort based heft. Future Generation Computer Systems 93:278–289
  * Zhu et al. (2021) Zhu QH, Tang H, Huang JJ, Hou Y (2021) Task scheduling for multi-cloud computing subject to security and reliability constraints. IEEE/CAA Journal of Automatica Sinica 8(4):848–865