# Research on Multi-DAG Satellite Network Task Scheduling Algorithm Based on Cache-Composite Priority
## 3 System Model
### Algorithm Design  
Different DAG workflows submitted by various users have distinct task requirements. When multiple tasks are simultaneously offloaded to edge servers, considering the limited computing resources of edge servers, allocating computing resources reasonably based on task priorities becomes a crucial issue. Defining any \(DAG_{k}(1\leq k\leq n)\), the priority of \(application_{k}\) can be expressed as  
\[T_{k}=\frac{1}{1+e_{k}^{t_{k}+h_{-}systemtime}} \tag{7}\]where \(t_{k}\) represents the maximum tolerated execution time, \(t_{k}^{start}\) represents the moment when the task accepts scheduling, and _systemtime_ represents the current system time.  
To prevent potential excessive delays in scheduling low-priority DAG tasks, in addition to considering task priorities, this paper introduces the concept of fair scheduling during the DAG selection phase, that is, the tasks in the DAG task queue with the greatest relative lag degree are always scheduled first. In the fair DAG selection step, to address fairness issues in multi-DAG applications, the relative lag degree can be expressed as  
\[Slowdown_{M}(k)=1-\frac{M_{own}(k_{v_{i}})}{M_{mutil}(k_{v_{i}})} \tag{8}\]  
where \(M_{own}(k_{v_{i}})\) represents the completion time of a subtask \(v_{i}\) when \(DAG_{k}\) is scheduled independently, and \(M_{mutil}(k_{v_{i}})\) represents the completion time of subtasks \(v_{i}\) when \(DAG_{k}\) is scheduled in a multi-DAG scenario. Additionally, to prevent excessive waiting times for low-priority tasks, we introduce the waiting time \(wait_{k}\) since the last scheduling of the current \(DAG_{k}\). The final total scheduling priority can be expressed as  
\[Y_{k}=Slowdown_{M}(k)+wait_{k}+T_{k} \tag{9}\]  
The task scheduling algorithm for DAG satellite networks based on cache-composite priority is shown in Algorithm 1.  
```
0: DAG set \(a\) to be scheduled, available resource set \(P\)
0: Scheduling scheme \(S_{result}\) for all DAGs in set \(a\)
1: Apply Formula (6) on the resource set \(P\) to calculate the priority of all subtasks for each DAG in the DAG set \(a\) to be scheduled, and save the results to \(S_{own}\)
2: Mark each DAG as unscheduled and place it into the unscheduled set U
3: Initialize the priority \(T_{k}\) for all DAGs in the unscheduled set U according to Formula (7) and sort them in descending order
4: Preprocess all DAGs, find the public subtask set \(Common\), and cache the results
5:whileU \(\
eq\emptyset\)do
6: Take out the first DAG task \(a_{k}\) from the set U
7: According to the result stored in \(S_{own}\), take out the subtask \(v_{i}\) with the highest current priority from \(a_{k}\)
8:if\(v_{i}\in Common\)then
9: Request the SDN controller to obtain the task result from the cache
10:else
11: Record the completion time of the scheduling subtask \(v_{i}\) as \(d\), and save the scheduling result to \(S_{result}\)
12:endif
13:if\(v_{i}\) is the last task of the current DAG then
14: Delete task \(a_{k}\) from U
15:else
16:\(M_{own}(k_{v_{i}})\) is the scheduling time of \(v_{i}\) in \(S_{own}\), \(d\) is the value of \(M_{mutil}(k_{v_{i}})\). Update the priority \(Y_{k}\) of DAGs in the set U according to Formula (9)
17: Re-sort all DAGs in set U in descending order according to the value of \(Y_{k}\)
18:endif
19:endwhile
```  
**Algorithm 1** DAG Satellite Network Task Scheduling Algorithm Based on Cache-Composite Priority  
Next, we analyze the overhead of scheduling Algorithm 1 in the system. Firstly, the complexity of calculating the priorities of all subtasks in the set of DAGs to be scheduled is \(O(ns\log(ns))\), where \(ns\) represents the number of subtasks. Secondly, the complexity of reordering all DAGs in the set U based on priority is \(O(n^{2}\log n)\), where \(n\) represents the number of DAGs. Therefore, the complexity of the Cache-Composite priority algorithm is \(O(\max(ns\log(ns),n^{2}\log n))\).