DAG-based Task Orchestration for Edge Computing

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 3(a) 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 3(b) 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 3(c), 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 IBDASH and show them in Table II. In particular, we explain the DAG, edge computing, task orchestration, and main system metrics.

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}$.

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 [21]. 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 IBDASH.

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 m and 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}$, $\ldots$, $\alpha_{N}$ running tasks is given by:

The above equation assumes that the interference patterns are independent and additive, which we verify experimentally (Section V Figure 4). 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 $ED_{mc}$, in which each row contains $N^{2}$ pairs of m, 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 k instances of $T_{j}$ are already running on edge device p, the estimated service time for $T_{i}$ can be calculated as $k*m_{ij}+c_{ij}$. We use the matrix $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.

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 1 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.

After staging the DAG, the orchestrator uses the profiling data (saved in matrix $ED_{mc}$) to retrieve the interference coefficients ((m, 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 1 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

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.

In the end, due to the sporadic availability of PEDs, IBDASH 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$, IBDASH 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.

The final optimization problem is given by

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.

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.

In Section IV-A, we assume that the interference patterns among tasks are independent and additive. We validate this assumption through an experiment whose result is shown in Figure 4. Two computationally intensive tasks have been used to verify our assumption on two different platforms. In particular, task $t_{1}$ represents matrix multiplication of randomly generated floating point entries 100 times and task $t_{2}$ denotes inversion of matrices with the above randomly generated floating entries. The two platforms used in this experiment are a Macbook Pro (3.1GHz dual-core Intel core i5 and 8GB 2133 MHz LPDDR3 memory) and a Huawei Nexus 6P (Qualcomm Snapdragon 810 with 3GB RAM), as these reflect two possible PEDs with widely varying capabilities. The matrix size used in tasks $t_{1}$ and $t_{2}$ are 1000$\times$1000 and 100$\times$100 for MacBook Pro and Nexus 6P, respectively. From Figure 4a and 4b, we see that the average execution latency has a linear relationship with the number of (same type) tasks running on the edge device for both platforms by looking at $T(t_{1},k*t_{1})$ and $T(t_{2},k*t_{2})$. Moreover, we also see that the lines representing $T(t_{2},j*t_{1}+k*t_{2})$ and $T(t_{2},j*t_{1})+T(t_{2},k*t_{2})$ have almost complete overlap. The same pattern is also observed for $T(t_{1},j*t_{1}+k*t_{2})$ and $T(t_{1},j*t_{1})+T(t_{1},k*t_{2})$, which verifies our assumption that the interference pattern is additive.

To test IBDASH's joint optimization of end-to-end latency and probability of failure under edge devices with various capabilities, we profiled 7 different AWS EC2 instances and a Macbook Pro for the 4 applications used in our simulation. The detailed configurations are shown in Table III. Note that different configurations emulate different compute power, memory and number of CPUs, which result in different interference patterns for each device.

Every pair of $m,c$ values (task interference parameter) between every two tasks are profiled on each of the eight edge devices. In addition, LaTS [9] makes an assumption that there is a parametric model that captures the relationship between latency and CPU usage. For our baseline experiments with LaTS, we have to determine this parametric relationship in our experimental setting. Therefore, we also profiled the relationship between the CPU usage and task execution latency and fitted a linear regression model to capture such a relationship. Figure 5 shows the profiling data collected on the t2.xlarge EC2 instance at 5 different CPU usage levels for different task types. From this result, we conclude that there is a linear relationship between the log(latency) and the CPU usage. We use this linear relationship for latency estimation for our experiments with the baseline LaTS.

The simulator for our proposed framework IBDASH is built in Python and four applications (Figure 6) from different application domains such as machine learning (LightGBM), data analytics (Mapreduce sort), mathematics (Matrix computation) and video analytics, that span a variety of dependency levels among tasks (DAGs) have been used for testing the generality of IBDASH.

We now describe our four applications and corresponding DAGs representing dependency among tasks.

We compare our orchestration scheme with the following baselines:

Recall that heterogeneity across edge devices is captured in our work through various computing powers (Section V-B) of different edge devices and a mix of PEDs and CEDs.

To show the impact of heterogeneity, we used the exponential function $P(ED_{i})=e^{-\lambda t}$ to simulate the sporadic availability of different edge devices with different failing rates (i.e., different $\lambda$s) for different devices. The exponential form makes sense as the average probability of failure increases as simulation time passes.

This experiment is meant to validate that the exponential model can be used as a good prediction of the probability of availability of edge devices and the set of $\lambda$ values used in our simulation are realistic. We used the mobility trace from [13] to validate our assumption. The mobility data is collected over one month (Feb 7th - Mar 7th, 2018) with 50 users on a university campus. Each user was performing their daily routine while their smartphones were running tasks for collecting sensor data, such as geolocation. The missing data points in the data sets indicate students turned off their devices, have no network access or quit the data collection program for their own reasons. By analyzing the mobility data, we show the corresponding results in Figure 7a, which shows the change of probability of availability since it first becomes available.

Table IV shows different sets of $\lambda$ values that have been used in our simulations. $\lambda_{1}$ simulates the scenario of a mixture of PEDs and CEDs. $\lambda_{2}$ represents the scenario when there are only CEDs present and $\lambda_{3}$ represents when there are only PEDs available. We specifically plot the set of $\lambda_{1}$ (mix of CEDS and PEDs) and the real-world data collected from the real-world participants in Figure 7b, and we see that the model for $ED_{6}$ fits the real-world data well which verifies our assumption that exponential function can be used as a good prediction for device availability with careful selection of failure rates $\lambda$.

In our experiment, we repeated a 15s simulation cycle 20 times giving a total simulation time of 5 minutes. In each cycle, 1000 application instances arrive randomly clustered within the initial 1.5s and there are 100 edge devices uniformly distributed among the 8 device classes listed in Table III. Their corresponding interference coefficients are collected from real-world experiments. It can be observed from Figure 8 that the average service time of IBDASH outperforms other orchestration schemes except for LaTS under all three scenarios (CEDs, PEDs, the mix of CEDs and PEDs (50%:50%)) for all applications due to its awareness of the co-located task interference. The reason that LaTS outperforms IBDASH in execution latency comparison is that LaTS allocates the majority of tasks to a single powerful device. However, if that device were to become unavailable, then the performance of LaTS will suffer drastically.

Figure 9 demonstrates the average probability of failure of application instances under six different orchestration schemes for three different scenarios. We see that IBDASH outperforms other baselines under all three scenarios, especially in the scenario where edge devices are a combination of PEDS and CEDs or all are PEDs as IBDASH offers the redundant replication to reduce the probability of failure. IBDASH is better than LaTS by 29.7% for mix, 58.5% for PEDs, and 34% CEDs on average across four applications. We emphasize that LaTS outperforms IBDASH in rare cases since the majority of tasks are allocated to a single device. If that single device being allocated had a low probability of failure, the overall probability of failure value is low. However, as discussed earlier, this can lead to a catastrophic failure of all application instances.

To show the advantage of using IBDASH in detail, we performed separate experiments (shown in Figure 10 and Figure 11) with 8 edge devices (one from each class) so that we can plot the loads, which is the number of tasks on each device and examine the load distribution. We zoom into one of the 15s simulation cycles for this experiment. We see that IBDASH tends to allocate more tasks on edge devices with low interference coefficients to reduce the overall service time, in this case, devices ED5 and ED6. On the other hand, LAVEA [6] chooses to allocate the task to the edge device with the least number of running tasks, which results in the load being fairly balanced on each edge device. Petrel [7] chooses two edge devices randomly and allocates the task to the one which has a lower expected service time. It results in a fairly balanced load distribution as well except for those edge devices with significantly larger interference coefficients compared to others. LaTS [9] allocates the majority of the tasks to ED5 due to its significant superiority of performance compared to others. Even though it does produce low execution latency, it results in a highly imbalanced allocation, which has negative consequences. Both Round Robin and Random allocation result in task accumulation on edge devices with high interference coefficients due to their fixed task distribution scheme, which leads to a long service time.

From Figure 11, we see that when the probability of failure of edge devices increases toward the end of the simulation, our orchestrator IBDASH starts to replicate the tasks to reduce the probability of failure, which results in increasing the overall number of tasks on some edge devices (Figure 10) and correspondingly the average service time for the application instance goes up due to the redundant tasks. For Petrel [7], LAVEA [6], the average probability of failure is higher as they do not have the extra redundancy to reduce the probability of failure. As for LaTS [9], it assigned most tasks to a single device, which happens to have a low probability of failure, so it shows a fairly low probability of failure.

To evaluate the joint optimization of our orchestration scheme, we performed a sweep of the replication threshold $\gamma$ and (separately) of the joint optimization parameter $\alpha$. The result is shown in Figure 12.

In Figure 12(a), initially, when the probability of failure is assigned much more weight than the service time, the algorithm tends to optimize the probability of failure as much as it can until it meets the probability of failure threshold $\beta$ or replication degree $\gamma$. At around $\alpha=0.3$, IBDASH starts to prioritize optimizing service time as more weight is given to it and shorter service time gives a better joint optimization score. Throughout the sweep, we see the general trend is that as the normalized service time decreases, the average probability of failure increases. However, there are some fluctuations in the sweep. For example, at $\alpha\approx 0.8$, we see that there is a temporary drop in the probability of failure and an increase in the average service time. The reason for this is that as the $\alpha$ value changes in each sweep, the task allocation changes as well. Therefore, this change in task allocation can result in fluctuations for both probability of failure and service time, but the general trend is not affected as shown in Figure 12(a).

From Figure 12(b), we see that as we increase the replication degree, the average service time increases while the average probability of failure decreases, then it stays fairly stable after around 6 replications as IBDASH is able to determine that further replications will not result in better joint optimization, therefore it stops replicating.