


\section{Our Proposed Solution: {\sc IBDASH}\xspace}\label{sec: framework}
To target the problems we listed in Section \ref{sec: ps}, we propose the framework {\sc IBDASH}\xspace, which is an interference-based orchestration scheme for DAG-based applications that aims at jointly optimizing the end-to-end latency and probability of failure for application instances. The rest of this section covers the task interference in our framework, the components of the framework, and our proposed orchestration algorithm.

\Subsection{Interference service time plots}
We define interference as a linear service time plot $T_{i}=m_{j}*k+c_{j}$ that characterizes the execution time of a new task of type $T_{i}$ on $ED_{p}$, given that $k$ tasks of type $T_{j}$ are already running on that edge device. For example, on a given edge device, for a new task $T_{i}$, we can plot $N$ interference plots for every other type of task including $T_{i}$ itself. Therefore, there are overall $N^{2}$ such plots and $N^{2}$ pairs of \textit{m} and \textit{c} values to characterize all interference plots for that edge device. The expected service time of the new incoming task $T_{i}$ on $ED_{p}$, which has $\alpha_{1}$, $\alpha_{2}$, $\hdots$, $\alpha_{N}$ running tasks is given by:

\begin{align}
& f_{i,(1,2,\hdots,N)}(T_{i},(\alpha_{1}T_{1},\hdots,\alpha_{i}T_{i},\hdots, \alpha_{N}T_{N})) \nonumber \\
& = \sum_{j=1}^N f_{ij}(T_i, \alpha_jT_j)
\label{equ:inter}
\end{align}

The above equation assumes that the interference patterns are independent and additive, which we verify experimentally (Section \ref{sec: experiment} Figure \ref{fig:pairwise}). Lower interference coefficient ($m$, $c$ values) of an application for a device means the shorter estimated execution latency for running that application on the device.
A pairwise interference coefficient matrix has been defined as \textit{$ED_{mc}$}, in which each row contains $N^{2}$ pairs of \textit{m}, \textit{c} values for that particular edge device. The element $<m_{ij}, c_{ij}>_{p}$ means that if we want to schedule a new task of type $T_{i}$ while \textit{k} instances of $T_{j}$ are already running on edge device \textit{p}, the estimated service time for $T_{i}$ can be calculated as $k*m_{ij}+c_{ij}$.
We use the matrix \textit{$Task_{info}$} to record the allocation of each task and the estimated time it will be on that edge device, then we can calculate the number of running tasks on each device at a certain time by a simple summation.

\Subsection{Design Components}
The proposed framework contains three main functions, DAG transformation, minimum service time scheduling, and failure likelihood reduction. When a new application instance arrives, the framework first transforms the application's DAG and divides the execution into stages. The advantage of dividing the DAG into stages is that the dependency of the tasks is embedded within the stages and all tasks within the same stage can be executed in parallel. Figure \ref{fig:sys_overview} shows an example of staged DAG for video analytics applications. 
Such staging process is performed through modified Breadth-First Search where the stage of a node is the length of the longest path from the start node.
\begin{comment}
\begin{figure}[h]
\centering
\includegraphics[scale=0.35]{stage}
\caption{\textbf{Staged DAG}. A staged DAG is a DAG representation of the application instance, in which the tasks are divided into stages, the tasks in each stage can be executed in parallel.}
\label{fig:stage}
\end{figure}
\end{comment}

After staging the DAG, the orchestrator uses the profiling data (saved in matrix $ED_{mc}$) to retrieve the interference coefficients ((\textit{m}, \textit{c}) value pairs) and using $Task_{info}$ matrix to retrieve the number of running tasks of each task type on the edge device of interest. 
The execution latency of the task is estimated using Equation \ref{equ:inter} and denoted as $L(T_{i})_{ED_{p}}$. Besides the execution latency, some tasks may require models to successfully execute the task. Therefore, we introduce the term $M(T_{i})$ to denote the models required for task $T_{i}$ (this may be null in cases) and $L(M(T_{i}))_{ED_{p}}$ to express the corresponding model uploading latency, which depends on both the model size and the network bandwidth $B$. Another important latency factor is the data transfer latency of the input data $T(i)_{d}$ for task $T_{i}$ if it is from other edge devices, and this is expressed as $L(T_{i})_{d}$. The device $p$ that gives minimum latency of the task $T_i$, which is the summation of the minimum execution latency, model uploading latency and data transmission latency for  $T_{i}$. The choice of the edge device is one that minimizes this combined latency and is given by
\begin{align}
& \underset{p}{\text{arg min }} L(T_i) \nonumber \\  
& where \ L(T_i) = L(T_{i})_{ED_p}+L(M(T_{i}))_{ED_{p}}+L(T_{i})_{d} \nonumber \\
& s.t. \ B \leq B_{max},\ H(T_{i}) \leq H(ED_{p}) \nonumber, \ ED_{p}\ \in\ ED \\
\end{align}
Here, $B$ is the current network bandwidth, $B_{max}$ is the maximum available network bandwidth, $H(T_{i})$ is the memory required for $T_{i}$'s execution, including memory to store data and model, and $H(ED_{p})$ is the available memory on $ED_{p}$.

Now, let us define $L(S_{i}) = \max_{T_i \in S_i} L(T_{i})$ as the stage $i$ latency. Therefore, the end-to-end latency of the entire application is the sum of the longest latency task in each stage.
\begin{align}
& L(G) = \Sigma_{i=1}^{i=S}L(S_{i})
\end{align}
In the end, due to the sporadic availability of PEDs, {\sc IBDASH}\xspace adds redundancy to replicate tasks that are assigned to edge devices with a high probability of failure to other edges devices. The goal of this redundant replication is to reduce the average probability of failure of the application instance below a certain threshold or to the minimum probability of failure within the replication degree constraints. For each edge device that was chosen to execute task $T_{i}$, we predict the probability of failure of that edge device during the estimated service time of task $T_{i}$ and this is the probability of failure of task $T_{i}$, which is denoted by $F(T_{i})$. If $F(T_{i})$ is above a certain threshold $\beta$, {\sc IBDASH}\xspace replicates $T_{i}$ on another edge device which gives the next optimal minimum service time. We keep repeating the replication until $F(T_{i})$ is reduced below the probability of failure threshold or the number of replications for $T_{i}$ reaches the replication degree $\gamma$. 
Every task within the application instance needs to be successfully executed so that the entire application can be counted as successful. Therefore, our framework seeks to minimize the probability of failure of every single task. We use $1-F(T_{i})$ 
to denote the probability of success for $T_{i}$, then uses the intersection of the probability of success for all tasks to denote the probability of success for the entire application instance. Such intersection notation captures the dependence among tasks (which is captured by conditional probabilities). In our setup, we used the data to estimate such conditional probabilities of task successes.
\begin{align}
P_{f}(G) = 1 - \cap_{i=1}^{N} (1-F(T_{i}))
\end{align}
The final optimization problem is given by 
\begin{align}
 \min  \alpha L(G)+(1-\alpha)P_{f}(G),
\end{align}
where $\alpha$ is the joint optimization parameter that is controlled by the user to give proper weight for end-to-end latency and probability of failure.




\Subsection{Orchestration algorithm description}
The orchestration algorithm is shown in Algorithm 1.
It greedily examines each task on available edge devices, while concurrently considering the allocation of its prerequisite tasks to minimize application latency and likelihood of failure globally. The algorithm outputs the placement choice for each task in the application on an edge device, PED or CED.

Line 4-17 checks each task in each stage against all available edge devices for estimated latency and consider the extra data transmission and modeling uploading latency globally when tasks with dependency are assigned to different devices. Line 6 calculates the expected execution latency of task $T_{i}$ on $ED_{p}$. Line 7-10 estimates the model uploading latency based on network bandwidth and whether the task requires models for its execution and the model's availability on the targeted edge device. 
 Line 11-14 estimates the input data transmission latency for task $T_{i}$ based on the dependency of task $T_{i}$, which is denoted as $D(T_{i})$. Line 15-16 sums up execution latency, model uploading latency, and data transmission latency then save the end-to-end latency for task $T_{i}$ and the corresponding edge device identifier to a priority queue. By the end of the execution of the for loop from lines 5-17, we will end up with the expected latency of $T_{i}$ on each edge device. Line 18 dequeues from the priority queue and the dequeued item contains the most optimized end-to-end latency placement for task $T_{i}$. Line 19-27 removes not frequently used model to free space and uploads the required models to the targeted edge device and updates the $M_{info}$ structure which is used to keep track of the model availability on each device and $ED_{info}$ structure, which is used to keep track of the memory available on each device. Line 28 calculates the probability of failure of the task on the device based on its dependency then a weighted optimization score is calculated in line 29.
 
 Now, the algorithm checks the probability of failure against the preset threshold $\beta$. If the probability of failure is greater than the threshold and the number of replications for the task is less than replication degree $\gamma$, line 31 dequeues the next item and lines 32-40 recalculate the weighted optimization score with the new probability of failure and the execution latency. If the new weighted optimization score is less than the previous weighted score, we replicate the task. Then repeating this process until the probability of failure is below the threshold $\beta$, or replication degree reached, or the queue is exhausted. Line 42 records the task allocation and line 44 records the longest latency in the current stage and makes sure that tasks from the next stage will not start until the previous stage is finished due to dependency. Finally, line 46 keeps track of the end-to-end latency of the entire application instance.

\begin{comment}
\textbf{Summary of the orchestration algorithm:} The goal of the algorithm is to  minimize the end-to-end latency and probability of failure jointly. This enables latency-sensitive applications such as augmented reality and maintains a low failure rate at the same time.
\end{comment}

\begin{algorithm}
    \SetAlgoLined
    \caption{Orchestration Algorithm}
    \SetKwInOut{KwIn}{Input}
    \SetKwInOut{KwOut}{Output}
    \SetKwInOut{KwInit}{Initialization}
    \SetKwInOut{KwRe}{return}
    \KwIn{DAG representing application instance G}
    \KwOut{Task placement $P(T_{i}) \forall T_{i} \in {T_{1},T_{2},\cdots, T_{N}}$, application end-to-end latency $L(G)$}
    \KwInit{$ED_{mc}$, $ED_{info}$, $Task_{info}$}
    $P.init()$ \# init placement structure\; 
    $S = app\_stage(G)$ \# stagerize the DAG\;
    \For{$S_{i} \in S$}{
        \For{$T_{i} \in S_{i}$}{
            \For{$ED_{p} \in ED$ }{
                $L(T_{i})_{ED_{p}} =
                GetEstimatedTime(T_{i},ED_{p})$\;
                $L(M(T_{i}))_{ED_{p}} = 0$\;
                \If{$M(T_{i})\ not\ on\ {ED_{p}}$}{
                    $L(M(T_{i}))_{ED_{p}}=
                    GetMdUpTime(size(M(T_{i})),B)$\;
                 }
                 $L(T_{i})_{d} = 0$\;
                \If{$T(i)_{d}\ not\ on\ \ ED_{p}$}{
                    $L(T_{i})_{d} = GetDTrTime(size(T(i)_{d}),B,D(T_{i}))$\;
                }
                $L(T_{i})=L(T_{i})_{ED_{p}}+L(M(T_{i}))_{ED_{p}} + L(T_{i})_{d}$\; 
                $PQueue.enqueue([ED_{p},L(T_{i})])$
            }  \;
            $ED_{p},\ L(T_{i}) = PQueue.dequeue()$\;
            \eIf{$M(T_{i})\ not\ on\ {ED_{p}}$}{
                \While{$H(ED_{p})\leq H(T_{i})$}{
                    $M_{info}[ED_{p}].removeEnd()$ 
                }   
                $M_{info}[ED_{p}].add(M(T_{i}))$ \;
                $ED_{info}.Update()$
            }{
                $M_{info}[ED_{p}].moveFront(M(T_{i}))$
            }\;
            $F(T_{i}) = GetPf(T_{i},ED_{p},L(T_{i})_{ED_{p}},D(T_{i}))$\;
            $WeightS=\alpha L(T_{i})+(1-\alpha)F(T_{i})$\;
            \While{$F(T_{i}) \geq \beta$ and $T_{rep}<\gamma$}{
                $ED_{p},\ L(T_{i}) = PQueue.dequeue()$\;
                $F(T_{i}) = GetPf(T_{i},ED_{p},L(T_{i}))$\;
                $WeightSnew=\alpha L(T_{i})+(1-\alpha)F(T_{i})$\;
                \eIf{$WeightSnew \leq WeightS$}{
                    $P(T_{i}).add(ED_{p})$\;
                    $WeightS = WeightSnew$\;
                    $T_{rep}++$\;
                 }{
                 $break$
                 }
            }
            $P(T_{i}) = min(\alpha L(T_{i})+(1-\alpha)F(T_{i}))$ \;
        }
        $L(S_{i})$ = $max_{T_{i} \in S}(L(T_{i}))$
    }
    $L(G)=\sum_{i=1}^{i=S}max(L(S_{i})$)
    
    \KwRe{$P(T_i) \forall T_i \in \{T_1,T_2, \cdots,T_N\}$,\ $L(G)$ }
   
   
\label{algo:orchestration}
\end{algorithm}

\section{Introduction}

There has been a surge of latency-sensitive applications running on user-generated streaming data, such as augmented reality and video analytics. Such a surge has driven the wide popularity of edge computing since it offers low latency by performing the computation near the source of the data and offers scalability by distributing the workload among multiple edge devices. 
After some notable innovations in academic publications over the last few years, we have started seeing the growth of small, edge-located data centers managed by infrastructure providers such as Amazon~\cite{lambda_edge}, Microsoft~\cite{ms_edge} and Google~\cite{google_edge}.
We refer to such devices as ``\textbf{Commercial Edge Devices (CEDs)}".
Being commercially managed, CEDs are expected to be available over extended periods and achieve reasonably low latencies. However, they have the drawbacks of incurring \$ cost and still not being widely available. Almost all existing literature on edge computing systems implicitly deals with CEDs as they assume the above desirable properties.

Edge computing systems could also comprise personal devices such as laptops, tablets, and mobile phones. This trend is increasing as such devices are becoming more ubiquitous and are increasing in their compute power. By the end of 2020, it is estimated 6.06B smartphones were in use globally, which is three times the number of PCs, and it is expected to keep growing at a 4\% rate and hit 7.69B by 2026~\cite{personal_edge}. Moreover, smart devices now have unseen storage and processing power and this trend is continuing. For example, a 2010 Samsung Galaxy S only had just 512MB of RAM and 8GB storage with a single core at 1 GHz, but the 2021 Galaxy Z Fold3 comes with 12GB of RAM and 256GB storage with 8 cores clocking at a maximum of 2.84 GHz.
We call such devices that may be pulled into an edge computing system as ``\textbf{Personal Edge Devices (PEDs)}".
Running latency-sensitive applications on PEDs
is appealing as they are often closer to the user than CEDs, with the same user often carrying multiple PEDs. Furthermore, with the right kind of incentive schemes, the usage of PEDs can be at zero cost.
On the other hand, such devices are expected to have sporadic availability and have little to no management of contention that can arise due to multiple co-located applications. Therefore, one has to carefully manage such PEDs in an edge computing system to achieve reliable and low latency executions.

In this paper, we present the design of an edge computing task scheduling scheme that we call \textbf{{\sc IBDASH}\xspace}\footnote{{\sc IBDASH}\xspace stands for \textbf{I}nterference \textbf{B}ased \textbf{D}AG \textbf{A}pplication \textbf{S}c\textbf{H}eduler\xspace and is pronounced as \textipa{["\={\i}b-dash]}.} that combines PEDs and CEDs into one system to leverage the benefits of both types of devices. In particular, {\sc IBDASH}\xspace introduces a method to schedule complex latency-sensitive applications, whose tasks (stages) have dependencies and can be represented by directed acyclic graphs (DAGs).
The scheduling happens among available PEDs and CEDs to reduce the end-to-end execution latency of each application and the probability of application failure, while accounting for the dependencies among different stages of the application. For example, a video analytic application may do scene change detection and pass onto a second task that does object detection only if there is a scene change. {\sc IBDASH}\xspace also takes into account the interference on a particular device from multiple co-located applications. This is particularly important because in our target class of devices, there do not exist good hardware mechanisms for avoiding contention, as compared to server-class devices~\cite{serverclass}. 

Table \ref{tbl:related_work} compares the features of our proposed solution {\sc IBDASH}\xspace with prior related works. In particular, prior works such as 
LAVEA~\cite{lavea} and Petrel~\cite{petrel} propose their orchestration schemes that target client-edge offloading to provide low-latency video analytic and randomized load balancing by leveraging the ``power of two" choice~\cite{power_o2} to randomly choose two edge devices and allocate the task to the one which gives better performance. Moreover, LaTS~\cite{lats} allocates the task to the device that has the shortest estimated latency based on a pre-profiled latency-CPU usage model. On the other hand, JCAB~\cite{jcab} effectively balances the accuracy and energy consumption while keeping low system latency by jointly optimizing configuration adaption and bandwidth allocation.~\cite{rtod} proposes a system that employs low latency offloading techniques jointly with pipeline decoupling methods and fast object tracking methods to enable accurate object detection. However, among these frameworks, some do not consider the heterogeneity of edge devices at all~\cite{jcab, rtod} and among those that consider the heterogeneity of edge devices,~\cite{lavea} considers the heterogeneity of CPU architectures,~\cite{lats} considers the heterogeneity of CPU and GPU mix, and~\cite{petrel} considers the mix of devices as a cloudlet entity. {\em None of these works considers the mix of PEDs and CED
.} Moreover, most of them (except LaTS~\cite{lats}) do not address the interference of co-located tasks on the same edge device. The previous work IBOT~\cite{suryavansh2020bot} 
proposed an orchestration scheme that takes the interference among tasks on each edge device into account and orchestrates an optimal execution strategy that jointly optimizes both execution latency and probability of failure. However, IBOT treats each task separately and does not take into account dependencies among tasks within an application and it also fails to address the memory constraints of each edge device since some tasks may require loading models into memory to successfully carry out the task execution. 

\begin{comment}
Centralized service system such as cloud-based systems coordinates the execution of service requests on reliable resources~\cite{intro1}. It produces promising results at the price of increasing communication frequency and long communication latency. However, with a surge of latency-sensitive applications such as augmented reality with artificial intelligence, edge computing has attracted more attention as it offers the capability to perform the intensive computation near the place where data is generated by distributing the workload among multiple edge devices closer to user instead of sending the data back to the cloud center for processing to reduce both communication and execution latency. Even though the idea of edge computing is propitious, there are challenges posed by edge computing that need to be considered when employing such ideas. For example, the computational resources on edge are heterogeneous and they may not be as dependable and powerful as cloud servers~\cite{hetero}. There are small, edge-located data centers surfacing during the past decade, such devices are referred to as "\textbf{Commercial Edge Devices (CEDs)}" and they are managed by infrastructure providers such as Amazon, Microsoft, and Google. Many efforts~\cite{edge_benchmark,fog_node,br_fog,edge_sec} have been put into exploring different aspects of CEDs such as  security, energy efficiency, performance, etc. However, personal devices such as laptops, desktops, and tablets also posses more than ever powerful processing and computing ability and they are even more closer to the end users, which makes them potential candidates as edge devices. Such devices are called "\textbf{Personal Edge Devices (PEDs)}".\par
Ideally, running latency-sensitive applications on personal edge devices is economical as it is closer to the user, thus reducing lots of communication latency, but due to the sporadic availability of personal edge devices, it is hard to reach high reliability if we completely depend on PEDs. Therefore, we propose to have a mix of PEDs and CEDs to balance the reliability and performance. Previous works such as LAVEA~\cite{lavea} and Petrel~\cite{petrel} propose their orchestration schemes which target at client-edge offloading to provide low-latency video analytic and randomized load balancing by leveraging the ``power of two" choice~\cite{power_o2}, which randomly chooses two edge devices and allocates the task to the one which gives better performance. However, none of them addressed the interference among tasks that are being executed concurrently on the same edge device. The previous work IBOT~\cite{ibot_shi} proposed an orchestration scheme that takes the interference among tasks on each edge device into account and orchestrates an optimal execution strategy that jointly optimizes both execution latency and \textbf{probability of failure (PF)}. However, IBOT treats each task separately and does not take the dependency among tasks within an application instance into consideration. It also failed to address the memory constraints of each edge device as some tasks may require models to successfully carry out the task execution. On the other hand, in our current work, we introduce \textbf{I}nterference \textbf{B}ased \textbf{D}AG \textbf{A}pplication \textbf{S}cheduler (\textbf{IBDASH}), in which we propose an optimal scheduling scheme for DAG based application along by minimizing both execution latency and probability of failure under the memory and network bandwidth constraints. Table \ref{tbl:related_work} compares the available features of our proposed framework with others.
\end{comment}

\begin{table}[t]
\vspace{0.3mm}
\caption {A comparison between the prior related works and our system in terms of the available features. 
{\sc IBDASH}\xspace offers DAG support, failure reduction and memory consideration. 
}
\label{tbl:related_work}
\centering
\resizebox{\columnwidth}{!}
{%
\begin{tabular}{|l|l|l|l|l|l|l|l|}
\hline
\multicolumn{1}{|l|}{\text{\bf Framework}}
& \multicolumn{1}{l|}{\bf \shortstack{Failure\\ reduction}}
& \multicolumn{1}{l|}{\bf \shortstack{Supporting \\ DAG }}
& \multicolumn{1}{l|}{\bf \shortstack{Heterogeneous\\ edge devices}}
& \multicolumn{1}{l|}{\bf \shortstack{Memory \\ Consideration }}
& \multicolumn{1}{l|}{\bf \shortstack{Low \\ latency }}
& \multicolumn{1}{l|}{\bf \shortstack{Orchestration\\ overhead \\ reduction}}\\
\cline{1-7}
\hline
LaTS~\cite{lats} & \ding{55} & \checkmark & \checkmark & \ding{55} & \checkmark & \ding{55}\\
\hline
Petrel~\cite{petrel}  & \ding{55}  & \ding{55}  &  \checkmark & \ding{55} & \checkmark & \checkmark \\
\hline
LAVEA~\cite{lavea} & \ding{55} & \checkmark & \checkmark & \ding{55} & \checkmark & \ding{55} \\
\hline
Edge Object Detection ~\cite{rtod} & \ding{55} & \ding{55} & \ding{55} & \ding{55} & \checkmark & \ding{55} \\ 
\hline
JCAB~\cite{jcab} & \ding{55} & \ding{55} & \ding{55} & \ding{55} & \checkmark & \ding{55} \\  
\hline
IBOT~\cite{suryavansh2020bot} & \checkmark & \ding{55} & \checkmark & \ding{55} & \checkmark & \checkmark \\  
\hline
{\sc IBDASH}\xspace (This work) & \checkmark & \checkmark & \checkmark & \checkmark & \checkmark & \ding{55} \\  
\hline
\end{tabular}}
\vspace{-0.1in}
\end{table}

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.32]{Figures/system_design.pdf}
\end{center}
\caption{A system overview of {\sc IBDASH}\xspace orchestration scheme for DAG based application. All edge devices in the network need to be profiled before task allocation. {\sc IBDASH}\xspace  do pre-processing the tasks in the application and puts them into different stages, then the scheduler orchestrates the allocation for each task's execution to reduce execution latency and probability of failure.}
\label{fig:sys_overview}
\vspace{-3mm}
\end{figure}
Figure \ref{fig:sys_overview} shows an overview of our proposed solution {\sc IBDASH}\xspace.
Each application instance from the end-user consists of one or more tasks, which may have dependencies among them. 
For example, in Figure \ref{fig:sys_overview}, we show a DAG example of a video analytics application that shows control and data dependencies among stages. The application is explained in detail in Section\ref{sec:testing_app}.

\begin{comment}
The DAG is taken as an input by the orchestrator of {\sc IBDASH}\xspace. The key technical contributions in our orchestration process include
(i) Interference estimation due to multiple co-located tasks on each edge device, (ii) Availability prediction of PEDs, and (iii) Joint optimization for service time and probability of failure of application instances.
\end{comment}

In our evaluation, we compare {\sc IBDASH}\xspace  with two intuitive baselines, Random allocation and Round Robin,
and three state-of-the-art solutions, LAVEA~\cite{lavea}, Petrel~\cite{petrel}, and LaTS~\cite{lats}. To test our framework, we use four applications that span various DAG structures from different application domains. Some tasks require models for their execution and some do not. 
For example, if the task performs object recognition, a pre-trained model is  needed on the designated edge device before the task can start running.
Compared with existing schemes, {\sc IBDASH}\xspace reduces the average service time of applications
by
14\% compared to the best baseline scheme. Concurrently with reducing service time, {\sc IBDASH}\xspace reduces the average probability of failure for the application by
41\% compared to the best baseline scheme.

In summary, this paper makes the following contributions:
\begin{enumerate}
    \item We propose an orchestration framework {\sc IBDASH}\xspace, an interference-based dynamic task orchestration scheme that executes DAG-based user applications in a heterogeneous edge computing environment with low latency and low probability of failure.
    \item To increase the reliability of edge computing, our solution proposes adding redundancy into the platform by replicating the tasks allocated to devices with a high probability of failure to multiple edge devices.
   
   
    \item We propose a device availability prediction model and validate it through the data collected by~\cite{mobility}.
   
   
   
    \item We validate our model via extensive simulation of application instances that arrive randomly within a time period
   
   
    and shows its superiority in reducing average application service time and probability of failure.
   
   
\end{enumerate}

\iffalse
\mustafa{The next paragraph is Candidate for Chop}

The remainder of this paper is organized as follows. 
Section \ref{sec: ps} covers the problem statement. Section \ref{sec: notations} includes the preliminaries and notations used in the paper. Section \ref{sec: framework} describes the proposed framework and the scheduling algorithm. Section \ref{sec: experiment} shows the settings of the experiments and the main results. Section \ref{sec:discussion} includes the discussion and the future improvement of our solution. Section \ref{sec: rw} presents the related literature and Section \ref{sec: conclusion} concludes the paper.
\fi 


\section{Preliminaries and Notations}\label{sec: notations}



\subsection{Feasibility of PEDs: A survey}
We conducted a user study with 110 participants from USA and India that are engaged in diverse fields such as educators, software professionals, students, engineering professionals, etc. to understand their willingness to share their computing devices (e.g., laptops, desktops, tablets, etc.) as edge devices. Figure \ref{fig:incentive_model} shows that 86.4\% of the participants are willing to share their devices under one of four proposed incentive schemes. Only 13.6\% of the participants were not interested in sharing their devices at all, primarily due to privacy and security concerns. Moreover, Figure \ref{fig:resource_shared} indicates that the majority of the participants are willing to share 0-40\% of their CPU resources. The amount of CPU resources people are willing to share varies as well depending on the device type. As shown in Figure \ref{fig:device_usage}, we obtained a double Gaussian device usage pattern with peaks at 90\% and 30\% of usage indicating that most people either use their devices very heavily (video editing, running sophisticated software, etc.) or use them only for computationally light applications such as browsing, reading, etc. The average usage across all users was 50.9\%, thereby supporting our claim that a lot of devices are not utilized to their capacity.


Now, we introduce the notations and terms used in our framework {\sc IBDASH}\xspace and show them in Table \ref{tbl:notation}. In particular, we explain the DAG, edge computing, task orchestration, and main system metrics.

\begin{table}[h]
\caption {The list of symbols and definitions used in our work.}
\label{tbl:notation}
\centering

\begin{tabular}{|l|l|}
\hline
\multicolumn{1}{|c|}{\text{\bf Symbol}}
& \multicolumn{1}{c|}{\bf Definition} \\
\cline{1-2}
\hline
$T = \{T_{1}, T_{2}, \hdots, T_{N}\}$ & Types of tasks for a given application\\
\hline
$ED =\{ED_{1}, \hdots, ED_{N}\}$ & Total number of edge devices\\
\hline
$S =\{S_{1}, \hdots, S_{N}\}$ & Number of stages in DAG\\
\hline
$G=(V_{i},E_{j}),\ V_{i} \in T$  & DAG representation of the application\\
\hline
$L(T_{i})_{ED_{j}}$ & Execution latency of $T_{i}$ on ED j \\
\hline
$L(M(T_{i}))_{ED_{j}}$ & Model upload latency for $T_{i}$ to ED j\\
\hline
$H(ED_{j})$ & Memory available on edge device j\\
\hline
$H(T_{i})$ &  Memory required for $T_{i}$\\
\hline
$L(T_{i})_{d}$ & Data transfer latency for Task i input\\
\hline
$L(T_{i})$ & End-to-end latency for task $T_{i}$\\
\hline
$L(G)$ & End to end latency for the application\\
\hline
$T(i)_{d}$ & Input data for task $T_{i}$\\
\hline
$L(S_{i})$ & End-to-end latency of stage $i$\\
\hline
$P(T_{i})$ & Placement of task $T_{i}$\\
\hline
$D(T_{i})$ & Dependency of task $T_{i}$ \\
& in terms of other tasks\\
\hline
$P(G)$ & Placement of each task in graph G\\
\hline
$P_{f}(G)$ & Probability of failure of application,\\
& given by graph G\\
\hline
$T_{rep}$ & Tracker for the number of replications\\
\hline
$\beta$ & Probability of failure threshold\\
\hline
$\gamma$ & Threshold on the Replication degree\\
\hline
$F(T_{i})$ & Probability that $T_{i}$ fail\\
\hline
$B$ & Network bandwidth\\
\hline
$M(T_{i})$ & Model required for $T_{i}$\\
\hline
$Ed_{info}$ &  Total and free space on each ED\\
\hline
$M_{info}$ & Available models on each edge device\\
\hline
$Task_{info}$ & \# executing tasks and 
 types on each ED  \\
\hline
$WeightS$ & Weight score of joint optimization \\
\hline
$WeightSnew$ & Weighted score after PF reduction\\
\hline
\end{tabular}
\vspace{-5pt}
\end{table}

\begin{figure*}[ht]
        \centering
        \begin{subfigure}[h]{0.66\columnwidth}  
            \centering 
            \includegraphics[width=\columnwidth]{Figures/incentive_model.png}
            \caption[]{Preferred incentive model}
            \label{fig:incentive_model}
        \end{subfigure}
        \hfill
        \begin{subfigure}[h]{0.66\columnwidth}  
            \centering 
            \includegraphics[width=\columnwidth]{Figures/resources_sharing.png}
            \caption[]{Percentage of CPU resources willing to share}
            \label{fig:resource_shared}
        \end{subfigure}
        \hfill
        \begin{subfigure}[h]{0.66\columnwidth}
            \centering
            \includegraphics[width=\columnwidth]{Figures/device_usage.png}
            \caption[] {Device usage (1: Low usage, 10: Very high usage)}
            \label{fig:device_usage}
        \end{subfigure}
        \vspace{-5 pt}
        \caption[]
        {User survey results ($N$ = 110)} 
        \label{fig:survey_results}
        \vspace{-5 pt}
    \end{figure*}

\iffalse
\begin{figure*}[h]
\includegraphics[scale=0.45]{Figures/datastructure.png}
\centering
\caption{\textbf{\textit{$ED_{mc}$} structure: A 2D matrix that is used to save the pairs of m, c values of N types of task on Q edge devices }
\label{fig:structure}
\end{figure*}
\fi

\iffalse
\begin{figure}[h]
\includegraphics[scale=0.25]{Figures/task_info.png}
\centering
\caption{\textbf{\textit{$Task_{info}$} structure: a 3D matrix  used to track number of each type of tasks on edge devices at a specific time $t_{n}$. }

\label{fig:structure}
\vspace{-4mm}
\end{figure}
\fi

\Subsection{Directed Acyclic Graphs}
Each application is represented as a directed acyclic graph (DAG) $G = (V,E)$. The set of nodes $V$ represents the individual tasks in an application instance, while the set of edges $E$ characterizes the dependency among those tasks. The dependency can mean both execution order dependency or data dependency. In particular, an edge from task $v_{i}$ to task $v_{j}$ indicates that $v_{i}$ needs to be finished before the start of $v_{j}$.

\begin{comment}
\Subsection{Orchestration}
The term orchestration is defined as task allocation strategies that determines at which edge device should a task be executed on. The orchestration scheme changes for different optimization goals. In this paper, {\sc IBDASH}\xspace aims at achieving low end-to-end latency and low probability of failure.
However, there are other orchestration schemes which aim at different purposes, for example,  ~\cite{folo} proposed FOLO which focused on latency and quality of service optimization, ~\cite{deep_decision} proposed DeepDecision which focused on latency and energy optimization. Prior works listed in ~\cite{edge_computing} addressed a lot on energy efficiency, low latency, cost and quality of service. To the best of our knowledge, our work is the first that jointly optimizes end-to-end latency and probability of failure for DAG-based applications.
\end{comment}

\Subsection{End-to-end Latency and Probability of Failure}
Throughout the paper, we used the terms end-to-end latency and probability of failure to describe the goal of joint optimization. End-to-end latency is defined as the time from when the first task in the DAG-based application starts executing till the last task finishes its execution. For this purpose, we assume that the clocks on all devices are synchronized, which can be achieved through means such as~\cite{koo2009tale}. In this paper, we use the average end-to-end latency of hundreds of application instances to evaluate the performance of our orchestration strategy. The term probability of failure is defined as the probability that the application instance did not successfully finish its execution. An application instance may not complete its execution because one of the edge devices becomes unavailable in the middle of task execution, or the owner of the edge device decided to perform some heavy-duty task, which results in the edge device being less responsive.
  
Having explained the problem statement and the main notations used in our work, we now turn our attention to the design of {\sc IBDASH}\xspace.


\section{Problem Statement}\label{sec: ps}
The combination of CEDs and PEDs, task dependencies within applications, and sporadic availability of PEDs pose unique challenges that have not been addressed in the edge computing literature. We discuss the four primary challenges, whose solutions bring out the novelty in {\sc IBDASH}\xspace. 

\noindent \textbf{Substantial heterogeneity in computational capacity:} PEDs such as laptops, tablets and mobile devices can have a substantial variation in their compute power, memory, etc. For example, in the current smartphone market, Samsung, Apple, and Xiaomi contribute 20\%, 14\%, and 13\% respectively to the market share and others contribute the remaining 53\%. Within each brand, there  is a  wide range of devices with different capabilities that target different customers.
The penetration of different brands in different markets and economies varies widely leading to a natural heterogeneity in the PEDs. 

\noindent \textbf{Heterogeneity in task interference pattern:} Different tasks, when running on the same edge device, interfere with each other affecting their execution time. There is heterogeneity in the interference experienced by different tasks on an edge device. For example, suppose that we have three tasks where the first task ($t_0$) loads a set of images, the second task ($t_1$) performs convolution on the pre-loaded images, and the third task ($t_2$) rotates the processed images. For such a scenario, Figure \ref{fig:tk_inter} shows the different interference patterns for different task types and the different CPU usages for different task types. In Figure \ref{fig:tk_inter}a, we see that the interference pattern for $t_{1} - t_{1}$ is different from the interference pattern for $t_{2} - t_{1}$. Figure \ref{fig:tk_inter}b shows that the CPU usage for each task under three different scenarios also varies. 
The interference patterns and CPU usage differences can be due to multiple reasons, such as resource contention~\cite{resource_contention}, priority scheduling~\cite{priority_scheduling}, etc. The main insight to note is that the different interference patterns among tasks result in different service times.
\begin{figure}[h]
\centering
\includegraphics[scale=0.31]{Figures/tk_inter.png}
\caption{\textbf{(a) The heterogeneity in interference among different tasks. (b) The  CPU usage of each task varies when different tasks are running in the background.}}
\label{fig:tk_inter}
\end{figure}

 \noindent \textbf{Sporadic availability of PEDs:} Due to the unmanaged nature of the PEDs, their availability in the network can be hard to predict. For example, in a more predictable scenario such as a classroom setting, when students leave the classroom, their laptops and mobile devices will not be available anymore so any tasks that are scheduled close to the end of class will experience a high probability of failure. However, in other scenarios where people come and go less predictably
(e.g., a university library), it would be hard to predict the availability. For instance, in~\cite{mobility} we did an experiment to track the availability of the mobile devices of students on university campus.
The results show that the probability of failure for mobile devices (mobile devices disconnect from the crowdsensing framework) increases with the length of time that elapses since they connected to the framework.

\noindent \textbf{DAG-based application orchestrations:} The dependency among tasks within the same application adds one more layer of complexity into the orchestration problem as the execution of tasks need to follow a certain order. Some can be executed in parallel and some cannot.  
Prior work~\cite{edge_overview} shows that several partition algorithms~\cite{clonecloud,maui} are developed to achieve different optimization goals such as saving energy~\cite{save_energy,deep_decision}, reducing execution latency~\cite{deep_decision}. Our proposed framework {\sc IBDASH}\xspace utilizes the structure within DAG-based application where it explicitly characterizes the task flow and data flow. Then, we orchestrate the task allocation to reduce the overall end-to-end latency and probability of failure. The significant prior work on DAG scheduling in the cloud is less relevant in our context as our EDs are more heterogeneous and less predictable in their availability.


\section{#1}\vspace{-4pt}}
\newcommand{\Subsection}[1]{\vspace{-8pt}\subsection{#1}\vspace{-2pt}}


\newcommand{{\sc IBDASH}\xspace}{{\sc IBDASH}\xspace}
\newcommand{\textbf{I}nterference \textbf{B}ased \textbf{D}AG \textbf{A}pplication \textbf{S}c\textbf{H}eduler\xspace}{\textbf{I}nterference \textbf{B}ased \textbf{D}AG \textbf{A}pplication \textbf{S}c\textbf{H}eduler\xspace}
\newcommand{\textipa{["\={\i}b-dash]}}{\textipa{["\={\i}b-dash]}}

\begin{document}
\sloppy

\pagestyle{plain}
\title{DAG-based Task Orchestration for Edge Computing}

\author{Xiang Li$^\alpha$, Mustafa Abdallah$^\alpha$, Shikhar Suryavansh$^\psi$,  Mung Chiang$^\alpha$, Saurabh Bagchi$^\alpha$ \\
$\alpha$: Purdue University; $\psi$: Cisco Systems


\maketitle

\begin{abstract}
As we increase the number of personal computing devices that we carry (mobile devices, tablets, e-readers, and laptops) and these come equipped with increasing resources, there is a vast potential computation power that can be utilized from those devices. Edge computing promises to exploit these underlying computation resources closer to users to help run latency-sensitive applications such as augmented reality and video analytics. However, one key missing piece has been how to incorporate personally owned unmanaged devices into a usable edge computing system. The primary challenges arise due to the heterogeneity, lack of interference management, and unpredictable availability of such devices. In this paper we propose an orchestration framework {\sc IBDASH}\xspace, which orchestrates application tasks on an edge system that comprises a mix of commercial and personal edge devices. {\sc IBDASH}\xspace targets reducing both end-to-end latency of execution and probability of failure for applications that have dependency among tasks, captured by directed acyclic graphs (DAGs). {\sc IBDASH}\xspace takes memory constraints of each edge device and network bandwidth into consideration. 
To assess the effectiveness of {\sc IBDASH}\xspace, we run real application tasks on real edge devices with widely varying capabilities. We feed these measurements into a simulator that runs {\sc IBDASH}\xspace at scale. Compared to three state-of-the-art edge orchestration schemes, LAVEA, Petrel, and LaTS, and two intuitive baselines, {\sc IBDASH}\xspace reduces the end-to-end latency and probability of failure, by 14\% and 41\% on average respectively. The main takeaway from our work is that it is feasible to combine personal and commercial devices into a usable edge computing platform, one that delivers low latency and predictable and high availability. 

\begin{comment}
As more mobile devices and laptops are equipped with powerful processors, there is a vast potential computation power that can be utilized from those devices. Edge computing is a promising technology that aims at exploiting those underlying computation resources closer to users to help run latency-sensitive applications such as augmented reality and video analytics. This paper proposes an orchestration framework {\sc IBDASH}\xspace, which is an interference-based orchestration scheme that targets reducing both latency and probability of failure jointly for applications that have dependency among tasks, captured by directed acyclic graphs (DAGs). {\sc IBDASH}\xspace takes memory constraints of each edge device and network bandwidth into consideration while orchestrating the optimized end-to-end latency task allocation strategy and minimizing the probability of failure.
To assess the effectiveness of {\sc IBDASH}\xspace, we simulate the orchestration process extensively with various DAG-based applications on multiple edge devices. The simulation results show that {\sc IBDASH}\xspace outperforms two intuitive baseline solutions and three state-of-the-art solutions in both reducing the end-to-end latency and probability of failure. In particular, {\sc IBDASH}\xspace can reduce the average service time by 14\% and reduce the probability of failure by 41\% on average compared with the best baseline solutions.
\end{comment}
\end{abstract}

\begin{IEEEkeywords}
Edge Computing, Directed Acyclic Graphs, Task Orchestration, Service Time.
\end{IEEEkeywords}
\IEEEpeerreviewmaketitle
\input{Introduction}
\input{Problem_Statement}
\input{Pre_Not}
\input{Framework}
\input{Evaluation}
\input{Relatedwork}
\input{Discussion}
\input{Conclusion}


\bibliographystyle{IEEEtran}
