domain: spi math phys

text:
David Doose
email: david.doose@onera.fr

The Generalized Graph Real-Time Task Model 1 st

Keywords: Real-Time Systems, Graph Task Model, Schedulability Analysis

Safety-critical real-time embedded systems are becoming difcult to model and analyze as they accommodate more and more functionalities, and they rely on more and more complex HW and SW implementations. One of the main difculty with such systems is to nd the right coupling between the task model and the analysis method. Indeed, if the task model is too simple it may add pessimism to the result of the analysis, and it may not be possible to prove the correctness of the systems. If the model is too complex, the analysis may be not efcient enough to be usable; or worst the model may have an incomplete method only or no method at all, so the system cannot be analyzed. Finding, the right couple task model analysis method is a balance between expressiveness and analysis efciency.

In this article, we introduce a new graph real-time task model (noted GGTM) which has been used for several years for the deployment and the analysis of different embedded systems. We discuss its expressiveness compared to the literature and demonstrate its advantages. We also, present a decidable and efcient, exact schedulability analysis.

I. INTRODUCTION

Today's HW and SW implementations are making safetycritical real-time embedded systems more and more complex. This is especially true with drones and robots, for which there are also the missions and the interactions with the environment to become more diverse and their human interactions implies safety guarantees. In such a complex ecosystem, the timing behavior of task is crucial, since modeling, and analysis apply for assuring the system timing behavior, i.e. determinism; timing analyses and schedulability analysis enforce the timing guarantees.

An expressive model must capture and abstract the complexity of the real system. In the past decade's different realtime task models have been developed. The widely known Liu and Layland task model [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] has been upgraded with new models and conditions that have been introduced to answer real problems of modeling, execution, and analysis. Then the notion of sporadic tasks was introduced [START_REF] Mok | Fundamental design problems of distributed systems for the hard-real-time environment[END_REF], [START_REF] Baruah | Preemptively scheduling hard-real-time sporadic tasks on one processor[END_REF], followed by the notion of multiframe tasks [START_REF] Mok | A multiframe model for real-time tasks[END_REF], [START_REF] Mok | A multiframe model for real-time tasks[END_REF], [START_REF] Baruah | Static-priority scheduling of multiframe tasks[END_REF] in which a task is split in a sequence of executions. These two models are subsumed by the Generalized Multiframe Tasks model [START_REF] Baruah | Generalized multiframe tasks[END_REF]. All these models have based "list" task modeling in which the task is represented with a sequence of executions. The next structural extension of the tasks model is to take into account the "tree" tasks model, more precisely the DAG task model. The recurring real-time task model [START_REF] Baruah | A general model for recurring real-time tasks[END_REF], [START_REF]Dynamic and static-priority scheduling of recurring real-time tasks[END_REF], [START_REF] Baruah | Schedulability analysis of nonpreemptive recurring real-time tasks[END_REF], noncyclic generalized multiframe tasks [START_REF] Tchidjo Moyo | On schedulability analysis of non-cyclic generalized multiframe tasks[END_REF] and the non-cyclic recurring real-time task model [START_REF] Baruah | The non-cyclic recurring real-time task model[END_REF], [START_REF] Baruah | Preemptive uniprocessor scheduling of non-cyclic GMF task systems[END_REF] are embedding that. Finally, complex real-time systems composed graph tasks model [START_REF] Guan | Approximate response time analysis of real-time task graphs[END_REF], [START_REF] Stigge | Graph-based models for real-time workload: a survey[END_REF] was introduced [START_REF] Stigge | The digraph real-time task model[END_REF], [START_REF] Stigge | On the tractability of digraph-based task models[END_REF], [START_REF] Guan | Resource sharing protocols for real-time task graph systems[END_REF]. Each previously cited task model came with a specic schedulability analysis, which can determine if the real-time system is schedulable or not.

Another approach to handle a more complex real-time systems is to use other techniques with more general and more powerful models like model-checking. Some theories like timed automata [START_REF] Alur | A theory of timed automata[END_REF] or Timed Petri Nets [START_REF] Ramchandani | Analysis of asynchronous concurrent systems by timed petri nets[END_REF], because they are dealing with time seem well-tted for this kind of problem. But it has already been shown that are undecidable while deadline with real-time preemptive systems [START_REF] Henzinger | What's decidable about hybrid automata?[END_REF], [START_REF] Cassez | The impressive power of stopwatches[END_REF]. And even if the decidability can be proven on a specic model the method can still be not efcient enough [START_REF] Abdeddaïm | Preemptive job-shop scheduling using stopwatch automata[END_REF], [START_REF] Fersman | Schedulability analysis of xed-priority systems using timed automata[END_REF] or incomplete [START_REF] Fersman | Task automata: Schedulability, decidability and undecidability[END_REF].

To analyze more complex real-time systems it is important to have a precise model and a well-tted analysis. If the task model is too abstract or if the analysis is too simple, then it can not take into account the neness of the actual behavior of the system. From the schedulability point of view, this means that method is pessimistic (i.e. it indicates that the system is not schedulable whereas a more precise method demonstrates the schedulability). On the other hand, there are model-checking techniques that can approach complex task models but cannot analyze it due to the undecidability problem or the lack of efciency. In between there is a gray zone that this paper wants to tackle with.

Contribution: We propose a new task model named Generalized Graph real-time Task Model (GGTM), in which the task execution is described by a graph. We discuss the expressiveness of this task model compared to the previously cited ones. Moreover, we propose a non-pessimistic (exact) and decidable analysis method. The complexity and the efciency of the method will also be discussed and benchmarking is provided to support considerations on analysis and method computation time.

Organization of the paper: In section II we present the GGTM and its real-time execution behavior semantic. Section III details the expressiveness of the model and compares it to the state of the art. Section IV presents the exact analysis method. Section V the schedulability analysis is applied to a simple example rst, then a benchmarking analysis is presented to highlight the cost of the analysis method proposed. Section VI is for concluding and future work.

II. GGTM TASK MODEL

A. Task model notations

A GGTM system is a set of independent tasks (Γ = { τ 1 , . . . τ N }). Each task τ i has a priority P i , an afnity cpu i , and a graph G i which describes its internal behavior:

τ i = {P i , cpu i , G i }.
Notice that task migration from one processor to another is not allowed in this model. The graph G i is composed of a set of vertices V = {v i,1 , . . . , v i,n }, an initial vertex v 1 , a set of arcs A = {a i,1 , . . . , a i,m } representing the transitions between the vertices. Each oriented arc is a pair of two vertices, its source and its destination a i,j :

 a - i,j , a + i,j  . The set of v i previous (resp. next) vertices in the graph is noted prev(v i ) (resp. next): prev(v i ) = {v j | 〈v j , v i 〉 ∈ A} next(v i ) = {v j | 〈v i , v j 〉 ∈ A} .
Each vertex of G i can be either an execution vertex or a wait vertex. To ease the presentation, if a vertex v i,j is an execution (resp. wait) vertex then it will be noted e i,j (resp. w i,j ). An execution vertex represents the execution of a specic code of the task. Thus, an execution vertex (e i,j : 〈c i,j , d i,j 〉) is characterized by its worst-case execution (c i,j ) time and optionally its relative deadline (d i,j , or if none). A wait vertex is characterized by its clock duration w i,j : δ i,j . A wait vertex means that the task will wait until its internal clock reached the value specied in the corresponding vertex. These notions will be detailed later. The type function is also added to ease the following formula; the type of vertex v i can be either Exec for an execution vertex or W ait for a wait vertex. Moreover, the GGTM contains a parameter that characterizes the internal clock bound noted K i . This parameter has an important role during the analysis, thus it will be explained in detail later in this article.

Notice that worst case-executions, deadlines, and clocks are positive (non-strict) values. We can also notice that this model allows for arbitrary deadlines. To simplify the notations, the task indexed will be omitted while considering a single task.

B. Semantic of the task model

The execution of a GGTM τ i is based on its internal graph model and the interactions of the higher priority tasks. During its execution, a task has exactly one active vertex at a time. The current active vertex of a task changes according to the GGTM arcs. Each task has an internal clock which is set to zero when the system starts. This clock increases according to time and can be reduced while nishing a wait vertex. There is no restriction in the GGTM structure: execution vertex (resp. wait) can be followed by either another execution or a wait.

Execution vertex: While running an execution vertex (e i,j ) the task is computing its corresponding code, thus the task is consuming 0 to c i,j time processor unit. But this task can be delayed or preempted by others, thus this action can take longer than c i,j . During the execution vertex run, the internal clock (I i ) is increased with time. Notice that I i is still increasing if the task is preempted by another task. At the end of the execution vertex any next vertex v i,k can be selected according to the GGTM arcs.

Wait vertex: A wait vertex (w i,j ) does not consume CPU time. While entering a wait vertex two cases may occur: 1) if the task internal clock is lower than the wait vertex clock then the task waits until the internal clock value is equal to the vertex clock value; 2) if the task internal clock is greater than or equal to the wait vertex then its internal clock is decreased by the wait clock value and the next vertex is selected. a) Task system: The behavior of the complete system is the combination of the behavior of each task according to the preemptive xed priority scheduler in which each task is mapped to a single processor according to its afnity (cpu i ).

Deadline: In our model, the deadline is relative to the internal clock of the task. A task τ i misses its deadline iff while running an execution vertex (e i,j : 〈c i,j , d i,j 〉) its internal clock value I i is greater than the deadline specied in the vertex: I i > d i,j . Notice that deadlines of the execution vertices have no impact on the real-time execution of the tasks. Thus, if a task misses one of its deadlines it goes on.

Killing parameter: The killing parameter K i is the maximum value of the task internal clock allowed. As stated before, the task internal clock increases with time, it is decreased when running a wait vertex. If the internal clock of the task reaches this bound (K i ) then the task is stopped. For the analysis point of view, the killing parameter is used as a task clock bound.

C. Example

Let's consider the example in Figure 1 composed of one GGTM task composed of three execution vertices (e 1 , e 2 and e 1 ), three wait vertices (w 4 , w 5 and w 6 ) and eight transitions. A trace is a sequence of vertices of the studied task noted [v i,j , . . . , v i,k ]. In order to explain the behavior of such a task model we will consider the following trace: [e 1 , w 4 , e 1 , e 2 , w 5 , e 1 , w 4 ]. In this trace, the task is executed without being delayed nor preempted by any other task. The timeline of the trace is presented in gure 2.

III. GGTM EXPRESSIVENESS AND MOTIVATIONS

We describe the expressiveness of the GGTM, and compare it to relevant execution models from the literature.

A. Periodic task model

Let's consider the classical periodic task model [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] with release date (r i ), priority (P i ), period (T i ), deadline (D i ), and WCET (C i ).In our model, the periodic task is easily translated with a GGTM composed of 2 wait vertices (the rst represents the release, and the second the period) and as execution vertex for the task computation, and the deadline. Figure 3 represents the GGTM for a periodic task. Consequently, our model is strictly more expressive than the periodic task model.

w 1 : r i e 2 : 〈C i , D i 〉 w 3 : T i Fig. 3. Periodic task representation.

B. Multiframe and generalized multiframe task model

The multiframe task model and the Generalized Multiframe (GMF) task model [START_REF] Baruah | Generalized multiframe tasks[END_REF] are two extensions of the periodic task model. The GMF task model subsumes the multiframe task model [START_REF] Mok | A multiframe model for real-time tasks[END_REF]. Both have a schedulability analysis for the xedpriority preemptive scheduler. The translation of the GMF task model into the GGTM is straight forward. Indeed, a GMF task is a sequence of alternate an execution vertex followed by a wait vertex. However, a major difference exists. GMF deals with sporadic tasks, thus the period is the minimum separation between two execution. In our execution model, the wait vertex represents an exact "separation" between two vertices.

C. Graph based task model

Another kind of extension is to use a graph (or Direct Acyclic Graph -DAG) to describe the task behavior. The Recurring Real-Time task model [START_REF] Baruah | A general model for recurring real-time tasks[END_REF] (RRT) extends the GMF task model by considering a DAG instead of a sequence of execution and "period". The non-cyclic RRT mode [START_REF] Baruah | Preemptive uniprocessor scheduling of non-cyclic GMF task systems[END_REF] also extends both recurring RT and non-cyclic GMF. Finally, the digraph real-time task model [START_REF] Stigge | The digraph real-time task model[END_REF] subsumes the previous ones by considering a directed graph composed of vertices representing the executions (and deadlines) and edges for the "period" (delay between executions). Let's consider the digraph (Directed graph) task represented in gure 4. It can be translated into the GGTM by representing each digraph vertex with an execution vertex and each edge of the digraph with a wait vertex in the proposed model. Figure 5 shows the result of the translation. The GGTM is more general than the digraph real-time task model because we can chain execution vertices and also wait for vertices contrary to the digraph real-time model in which an execution is always followed by a "period". However, there are four main differences: rst, the GGTM has a unique initial vertex, contrary to the digraph RTT in which the initial node is not specied. Then, the digraph real-time task model is sporadic; the edges are minimum inter-release separation time and not exact inter-release time. Moreover, the digraph realtime task model is based on the preemptive earliest deadline rst scheduler. Finally, in the task model presented in this paper, we can have deadlines greater than the periods.

v 1 v 2 v 3 〈e 1 , d 1 〉 〈e 2 , d 2 〉 〈e 3 , d 3 〉 p 1 p 2 p 3 p 4

D. Concrete motivation a) Re-synchronization:

The rst issue we had on different robots came from the sensors reading. In practice, the sensors (laser, GNSS, cameras, . . . ) produce data with a specic frequency. The rate is accurate but never perfect. Thus, sometimes the synchronization can be lost, and some data may be lost. To avoid this issue we need to specify a task made with two-part: one for the synchronization and one for data computation. Figure 6 shows how to answer this problem with the proposed task model. The cycle composed of e 1 and w 3 is used to check if a new data is produced by the sensor. If one data is produced then the vertex e 2 is executed to treat the input. In practice, this pattern is characterized by a tiny wait duration in w 3 depending on the sensor specication and a longer wait duration after the data computation in w 4 . This pattern also gives a precise bound of the delay between the data produced by the sensor and the beginning of its computation: δ 3 .

b) Complex tasks: In practice, if a task has complex behavior from the time point of view, the GGTMmodel can be helpful. This execution model has proven to be useful for the implementation of various complex tasks such as path planning and tracking, SLAM, and various decision tasks.

IV. GGTM ANALYSIS

A. Methodology

The main objective of the analysis of the GGTM is to compute the behavior graph of each task. Once this graph obtained we can check if the deadlines are missed and highlight counter-examples traces. This graph may also provide valuable information about the real-time behavior of the systems.

Theorem 1. In GGTM, there is no possible interaction between tasks mapped to different processors.

Proof. The tasks are mapped on a single processor and are not allowed to change their allocation during the execution. Moreover, there is no synchronization nor precedence between tasks. Consequently, tasks from different processors are independent, from the real-time point of view.

Theorem 2. In GGTM, task behavior can only be altered by the tasks running on the same CPU with a higher priority.

Proof. The only interactions between tasks can be either delay or preemption. A task can only be delayed (resp. preempted) by another task with a higher priority. Consequently, the interactions between tasks can be completely ordered.

Lemma 1. Consequently, the analysis of system composed of several GGTM can be done incrementally: one processor at a time and one task at a time-ordered by their priorities.

The main algorithm consists of: for each processor, for each task τ i allocated on this processor ordered by priority, compute its behavior graph (noted B i ). The behavior graph of a task is computed by taking into account its supply graph of the processor. The supply graph represents the availability of the processor for a specic task. Because we are dealing with graphs for the tasks, the supply "function" is also a graph. Once the behavior graph of a task computed we can check different properties such as looking for deadline miss. Finally, the current processor utilization induced by the behavior of the current task is added to the supply graph for the next task. Then the supply graph is compacted to reduce as possible its size. This methodology is described by the algorithm 1.

foreach cpu ∈ cpus do tasks ← {τi ∈ Γ | cpui = cpu}; tasks ← sort

B. Supply graph denition

A supply graph is a directed graph noted S composed of vertices noted V S and arcs noted A S . Each vertex v S i is a tuple made of the vertex type and the duration (noted ∆ i ); the vertex type can be either Idle or loaded Loaded. While analyzing the task τ i the Loaded vertices correspond to the executions of the tasks with a higher priority than τ i . If the supply graph current vertex type is Idle then the task τ i can be executed. According to the analysis algorithm 1 a specic supply graph is only used for the computation of specic task behavior. Thus, to ease the paper reading while analyzing the task τ i the corresponding supply graph will be noted S i .

C. Behavior graph denition

The main objective of the behavior graph of a task is to show its behavior according to its supply graph. Consequently, it contains both information related to the supply graph and information on the task. The behavior graph B is a directed graph composed of vertices noted V B and arcs noted A B . Each vertex contains a tuple 〈s, t, begin, end〉 in which: s is the current supply vertex, t is the current task vertex, begin is used to represent the internal behavior parameters while entering the current vertex, and end at the end of the vertex. Both begin and end contains three parameters 〈S, I, E〉:

1) S is a positive number representing the remaining duration of the Supply vertex s. This duration can only decrease. 2) I is a positive number representing the task's Inner clock value. This value can only increase up to K i .

3) E is a positive number representing the remaining

Execution time needed by the task to nish t. This value can only decrease. A behavior vertex represents the evolution of the system behavior while time changes but the vertices of both the supply graph and task graph remain unchanged. The arcs of the behavior graph represent the change of either the supply graph vertex or the task graph vertex. The pointed notation will be used if the vertex is not needed (ex. begin.I).

D. Killing parameter

As previously described, each task τ i has a killing parameter K i which is an upper bound for the internal clock. Thus, during the computation of the behavior task, if the internal clock reaches K i is marked as killed. Because our main objective is to study the schedulability of the task the killer parameter must be long enough to detect deadline miss, but it also has to be as small as possible to reduce computation time. Thus, it must be greater than all the deadlines (K i > max(d i,j )) and greater than the wait duration to avoid stopping the task while waiting (K i > max(δ i,j )).

We can determine K i value with the following formula:

K i = max(d i,j ) + max(δ i,k ) + 1

E. Supply graph initialization

The initial supply graph is used to represent a processor fully available for the tasks. It is composed of a single vertex: 〈Idle, +∞〉

F. Behavior graph computation

The behavior graph computation principle is to compute, for each vertex from the initial one, the next possible vertices. This is repeated until no new vertex can be added to the graph. We will explain later why this process terminates.

1) Initial vertex: The rst vertex is composed of the supply and the task vertex are the corresponding initial vertices: s 1 = v S 1 and t 1 = v 1 . The remaining time into the initial supply vertex is equal to its duration. The initial internal clock value is set to zero. The initial remaining computation time of the initial execution vertex is set to its WCET if the rst task vertex is equal to an execution vertex, or it equals to zero if it's a wait vertex.

 v S 1 , v 1 , begin, end



The initial vertex begin parameters depend on the rst task vertex type. If the task vertex type is Exec then E the parameter representing the remaining computation time is equal to c 1 otherwise it is equal to 0. In both cases, the supply duration is set according to the rst supply vertex duration and the initial task internal clock value is set to 0.

(type(v 1 ) = Exec) =⇒ (begin = 〈∆ 1 , 0, c 1 〉) (type(v 1 ) = W ait) =⇒ (begin = 〈∆ 1 , 0, 0〉)
2) Vertex length: The length of a behavior vertex v B i is the time spent is this vertex before a transition occurs. Thus, the length of a behavior vertex depends on the supply and the task vertex types.

Supply is loaded: The supply graph represents the tasks with higher priority. Thus, if the supply is loaded then the system have to wait for the end of the current supply vertex:

(type(s) = Loaded) =⇒ (length = begin.S)
Task is running: If the supply is idle and the current task vertex is an execution then the system is running the studied task. This ends as soon as the execution is nished or the current supply vertex ends: (type(s) = Idle ∧ type(t) = Exec) =⇒ (length = min (begin.S, begin.E)) Task is waiting: If the supply is Idle and the task is waiting then the current vertex ends as soon as the supply vertex ends or the clock reached the wait vertex clock duration.

(type(s) = Idle ∧ type(t) = W ait) =⇒ (length = min (begin.S, max (begin.Iδ, 0)))

The max part of the formula is necessary to maintain a nonnegative duration if the wait vertex is late (I > δ). In this conguration, the behavior vertex ends without consuming time.

3) Time evolution: A time transition is represented in each behavior graph vertex using the begin and end parameters which dened the internal changes of the systems when the time evolves. The begin parameter is computed while entering the vertex, thus the end parameter depends on the inner vertex parameters: the supply and the task current vertex and the 'begin' parameter.

Task is waiting: If the task is waiting then the supply duration decreases according to time, the clock increases and the remaining computation is 0:

(type(t) = W ait) =⇒ ⎛ ⎝ end = 〈 begin.S -length, begin.I + length, 0 〉 ⎞ ⎠
Task is running: If the supply is idle and the task is running an execution vertex then the supply duration decreases according to time, the clock increases and the remaining computation of the task vertex decreases:

(type(s) = Idle ∧ type(t) = W ait) =⇒ ⎛ ⎝ end = 〈 begin.S -length, begin.I + length, begin.E -length 〉 ⎞ ⎠
Task is preempted: If the supply is loaded and the task is an execution vertex (the tasks is preempted by higher priority tasks) then the supply duration decreases according to time, the clock increases and the remaining computation stay unchanged:

(type(s) = Idle ∧ type(t) = W ait) =⇒ ⎛ ⎝ end = 〈 begin.S -length, begin.I + length, begin.E 〉 ⎞ ⎠ 4
) "Choice" transition: Supply transitions: At the end of the vertex time evolution, the next supply or task graph transition has to be selected. The supply graph represents the higher priority tasks, thus if its current vertex is nished (end.S = 0) then its next transition is selected even if the task graph vertex is also nished. It is important to notice that the process is repeated for each next transitions. To ease the following formula, the next vertex according to the task graph will be noted v ′ . This notation is also applied to every behavior graph element including to supply vertices, begin and end parameters. 〈s, t, begin, end〉 〈s ′ , t, begin ′ , end ′ 〉 (end.S = 0) =⇒ (begin ′ = 〈∆ s ′ , end.I, end.E〉)

Task transition: The next task vertex is selected only if the current task vertex is nished and the supply vertex is not nished. 〈s, t, begin, end〉 〈s, t ′ , begin ′ , end ′ 〉 If the next task vertex type is wait then the clock is reduced by the clock duration specied in the task graph vertex:

(end.S = 0 ∧ type(t ′ ) = W ait) =⇒ (begin ′ = 〈S, end.I -δ, 0〉)
If the next task vertex is an execution then the remaining computation time is set to the WCET of the corresponding task vertex:

(end.S = 0 ∧ type(t ′ ) = Exec) =⇒ (begin ′ = 〈S, end.I, c ′ 〉)

G. Next supply graph

Once the behavior graph computed for a task, the next supply graph, for the next task, has to be computed. The next supply graph is a graph with the same structure as the current behavior graph (same vertices number and same transitions). Each behavior vertex is transformed into a supply vertex depending on the fact the vertex uses the processor or not:

〈s, t, begin, end〉  Loaded(length) if type(s) = (Loaded ∨ Exec) Idle(length) otherwise H. Compact supply graph
The computation of the behavior graph highly depends on the supply graph size that's why it is important to keep it as small as possible. A next supply graph created from the behavior graph can be compacted by two operations that maintain the supply graph's semantic.

Remove empty: consists in removing all the empty vertices. A supply vertex s i is empty if its duration is equal to zero (∆ i = 0). To achieve this simplication every out coming arc of the empty vertex is added to every previous vertex. Finally, the empty supply vertex is removed.

Merge: consists in merging two consecutive "single" vertices with the same type. Indeed, if two vertices s 1 and s 2 have the same type (type(s 1 ) = type(s 2 )) and the rst one has only one out coming transition to the second (next(s 1 ) = {s 2 }) which has only one incoming transition (prev(s 2 ) = {s 1 }) (from the rst one), then these two vertices can be merged into a single one. This functionality is described by algorithm 2.

foreach x ∈ V S , y ∈ V S do if mergeable(x, y) then v ← new vertex; type(v) ← type(x) ; ∆v ← ∆x + ∆y ; V S ← V S + v ; foreach p ∈ prev(x) do A S ← A S + 〈p, v〉 end foreach n ∈ next(y) do A S ← A S + 〈v, n〉 end V S ← V S -x -y end end
Algorithm 2: Merge two supply vertices.

I. Check task properties

Once the behavior graph computed we can check properties. Deadline miss: A behavior graph vertex is deadline miss if the task vertex is execution and if the internal clock is greater than (strictly) its corresponding deadline:

deadline miss := (typet(t) = Exec ∧ end.I > d)
Killed: A behavior graph vertex is killed if its internal clock is greater than the killing parameter: killed := end.I > K.

Late: A behavior graph vertex is late if its internal clock greater than its corresponding wait duration: late := end.I > δ.

Response time: The worst-case response time (WCRT) of a task execution vertex e is the maximum internal clock value for a behavior vertex with the same task vertex:

wcrt(e) := max {end.I | t = e} .

Schedulable: A task is schedulable if the behavior graph contains neither killed vertex nor deadline miss vertex.

Other properties: Any other properties related to the behavior graph can also be tracked. For example, we already used the behavior graph to study the impact of some specic task preemption on the worst-case response time of another task. The behavior graph can also be used for explanation, for example, if the task is not schedulable it is interesting to determine which paths can lead to a deadline miss.

J. Discussion a) Pessimism: The main principle of the analysis method presented in this article is to compute every possible behavior of GGTM tasks. By construction, the behavior graph exhibits the exact behavior of the corresponding tasks. Consequently, the analysis method is exact (non-pessimistic).

b) Completeness: Moreover, the analysis can be applied to any GGTM systems without any restriction. Consequently, the method is complete. c) Decidability: To prove the decidability of the method we have demonstrated that the decision procedure ends. The main algorithm iterates over the tasks. The number of tasks is bounded. For each task three algorithms are applies: computing behavior graph, checking real-time properties, computing the next supply graph and compacting the supply graph.

Checking the real-time properties is a simple request on the behavior graph, at worst each node is checked once. Thus, the termination is guaranteed.

Computing the next supply graph principle is to create a supply graph with the same structure as the input behavior graph. Thus, the next supply computation simply iterates on the behavior graph. Thus, the termination is also guaranteed.

Compacting the supply graph applies recursively two operations (remove empty and merge). Each operation reduces the size (number of vertices); thus the procedure ends.

To demonstrate that the computation of the behavior graph ends, we have to demonstrate that the number of vertices is bounded. Each node is a tuple 〈s, t, begin, end〉 in which begin and end are tuples 〈S, I, E〉. The supply graph and the task graph are bounded by denition. The parameter S is a positive number bounded by the maximum duration of the supply nodes. The I parameter is a positive number bounded by the killing parameter. The parameter E is a positive number bounded maximum duration of the executions vertices of the task graph. All the parameters are bounded then the number of nodes is also bounded. Consequently, the size of the behavior graph is bounded, and the procedure ends.

V. EXPERIMENTAL RESULTS

A. Example

To illustrate the analysis method proposed in this article let's consider an example of three tasks. The three tasks are executed on the same processor and ordered by priority.

1) Tasks set: The rst task is a simple periodic task with a rst release date equals to zero, C = 1 and D = P = 10.

The second task has the same pattern as the one presented in gure 6 with the following parameters values: 2) Analysis: First task: The analysis is made task by task: for each task, the corresponding supply graph is given, and the result is the behavior graph and/or traces that highlight a specic property.

a) Supply graph: The supply graph of the rst task is the empty supply graph in which the processor is never used.

b) Behavior graph: As a result of the analysis of the rst task, its behavior graph is computed. Because the supply graph is empty the behavior graph is very similar to the GGTM. Figure 7 shows the behavior graph. 3) Analysis: Second task: a) Supply graph: The supply graph of the second task is computed based on the behavior graph of the rst task. Thus, it only contains two vertices: at rst, the processor is loaded for 1 time unit and then the processor is idle for 9 time units. These two vertices are repeated indenitely.

b) Behavior graph: The behavior graph of the second task is made of 15 vertices as presented in gure 8:

• the vertices in blue and noted P xxx represents the preemption of the second task by higher priorities tasks;

• the vertices in green and noted R xxx represents the moments in which the second task is running;

• the vertices in white and noted I xxx represents the vertices in which the processor is idle:

• the vertices in gray and noted L xxx represents the moments in which the higher priority tasks are executed while the second task is waiting. c) Properties: The behavior graph of the second task shows that there is no deadline miss, thus the second task is schedulable. It also shows the preemption and other information about task real-time behavior.

4) Analysis: Third task: a) Supply graph: The supply graph of the third task is based on the behavior graph of the second task but compacted. Figure 9 shows the supply graph. For example, the vertices R 8 , P 9 and R 10 are merged because they represent three consecutive processor utilization with a total duration of 6. The vertices I 7 and P 15 are removed because they are not consuming time.

b) Properties: Due to the number of vertices, the behavior graph won't be displayed here. But our analysis tool also provides the minimal (in length) traces for each property. In this case, the task is not schedulable and the minimal trace that leads to a deadline miss composed of ve vertices:

1) 〈L 0 , e 1 , (1, 0, 4) → (0, 1, 4)〉: at rst the processor is used by the higher priority tasks for 1 time unit; 2) 〈L 1 , e 1 , (1, 1, 4) → (0, 2, 4)〉: then the processor is loaded for 1 other time unit; 3) 〈L 3 , e 1 , (5, 2, 4) → (0, 7, 4)〉: the processor is loaded for 5 time units; at this point the task is unschedulable. 4) 〈I 4 , e 1 , (3, 7, 4) → (0, 10, 1)〉: the task is running the vertex e 1 for 3 time units 5) 〈L 5 , e 1 , (1, 10, 1) → (0, 11, 1)〉: nally the task is preempted for 1 time unit and the task misses its deadline for the vertex e 1 .

B. Computation Time Benchmark

In the following, we discuss the computation time of the analysis we proposed. a) Tasks generation: We have previously demonstrated the expressiveness of our model and its schedulability analysis in the previous sections thus, we decided to generate periodic tasks because generating a GGTM for many tasks is a very complex problem. Indeed, most of the generated complex tasks system may be trivially not schedulable and then the computation won't increase with the number of the tasks. Moreover, the use of periodic tasks provides a clearer insight into the complexity of the system. Thus, We decided to generate periodic tasks and increase the number of tasks to increase the computation of our method. The task period is randomly chosen, its computation time is randomly picked between 0 to T i /n with n the number of tasks of the system. Thus, the task load is homogeneously dispatched between the different tasks and the load of the system stays relatively small. Each task has a deadline equals to its period. For each task number n a hundred simulation is run.

b) Results: The benchmark is executed on an i7-8850H@ 2.60GHz. Figure 10 shows that the computation increase according to the number of the tasks but even for many tasks the computation time is just a few seconds. Let's remind that the computation time is for one processor and increases linearly with the number of processors. As mentioned previously, we used this method on different systems and the computation time was never an issue; rst, because of the number of tasks by processor is quite small. Moreover, task time parameters are correlated.

c) Discussion: The previous benchmark highlight the efciency of the analysis method. However, it is also interesting to notice the difference between the complexity and the computation time. Indeed, the complexity relies on the worst-case scenario in which : during the computation of the behavior graph each time unit leads to a new vertex, each behavior graph and supply graph are completely connected, the size of the supply graph is the size of the behavior graph, and the compact algorithm does not affect. In practice, the compact algorithm and the links between timings restrain the size of the behavior and supply graph.

VI. CONCLUSIONS

In this paper, we introduce the Generalized Graph Real-Time Task Model. Then, we compare its expressiveness with the state of the art and demonstrated that the proposed model is more general than most of the previous ones, and does not subsume by the other ones. We also present an exact analysis method, and shows that it can scale to large real-time systems.

Different extensions are under investigation. First, we are exploring the possibility to check different temporal logic formulas (LTL/CTL) on the behavior graph obtained by the analysis. The main objective is to checks complex properties about the real-time behavior of the tasks.

Another perspective to be considered is to translate part of the algorithm semantic on the task graph. The intent here is to add branching conditions described by rst-order logic formulas. Indeed, in our model, all the next arcs are allowed but in practice, the transitions are ordered and guarded. This enhancement may remove unreachable traces.

e 1 : 4 : 2 w 5 : 5 w 6 : 10

 14255610 〈1, 2〉 e 2 : 〈2, 4〉 e 3 : 〈5, 8〉 w

Fig. 1 .

 1 Fig. 1. GGTM example.

e 1 w 4 e 1 e 2 w 5 e 1 w 4 w 4 w 5 w 4 Fig. 2 .

 42 Fig. 2. Execution trace [e1, w4, e1, e2, w5, e1, w4].

Fig. 4 .

 4 Fig. 4. Digraph task.

e 1 : 2 : 〈e 2 , d 2 〉 e 3 : 〈e 3 , d 3 〉 w 4 : p 1 w 5 : p 2 w 6 : p 3 w 7 : p 4 Fig. 5 .

 122233341526745 Fig. 5. Digraph task translation.

e 1 : 3 w 4 : δ 4 Fig. 6 .

 13446 Fig. 6. Synchronization issue solved.

e 1 :

 1 c 1 = 1 and d 1 = 2, e 2 : c 2 = 5 and d 2 = 7, w 3 : δ 3 = 5, w 4 : δ 4 = 10. The third task is a periodic task with release date equals to zero, c 1 = 4, d 1 = 10 and δ 2 = 10

Fig. 7 .

 7 Fig. 7. Behavior graph of the rst task

Fig. 8 .

 8 Fig. 8. Behavior graph of the second task.

Fig. 9 .

 9 Fig. 9. Supply graph of the third task

Fig. 10 .

 10 Fig. 10. Computation time benchmark.


Sara Maqrot

Stéphanie Roussel

Gauthier Picard

Cédric Pralet

Bundle Allocation with Conflicting Preferences Represented as Weighted Directed Acyclic Graphs Application to Orbit Slot Ownership

We introduce resource allocation techniques for a problem where (i) the agents express requests for obtaining item bundles as compact edge-weighted directed acyclic graphs (each path in such graphs is a bundle whose valuation is the sum of the weights of the traversed edges), and (ii) the agents do not bid on the exact same items but may bid on conflicting items, that cannot be both assigned. This setting is motivated by real applications such as Earth observation slot allocation, virtual network functions, or multi-agent path finding. We study several allocation techniques and analyze their performances on an orbit slot ownership allocation problem.

Introduction

Imagine the following scenario. The operator of an Earth Observation Satellite Constellation X has to attribute ownership of some orbit portions to clients. Each client has some points of interest (POI) she wishes to acquire at some frequency, e.g. capture L'Aquila city every 2 hours for 6 months. Since several satellites may capture the very same point on Earth around the defined time plots, several bundles are specified by each client, which valuate differently depending on the quality of the sequence of orbit slot, e.g. proximity to the time plots or acquisition angles. Moreover, several clients may be interested in very close POIs, resulting in overlapping orbit slots that cannot be simultaneously allocated to the corresponding clients. This situation can be captured by the model we propose in this paper.

We consider a problem of allocation of bundles of indivisible items constrained by item chaining (to allocate to each agent a chain of successive items) and conflicting items. The first constraint is captured by an edge-weighted directed acyclic graph (DAG), with a source node and a sink node, representing all the valid bundles (i.e. paths) of items for an agent, where the quality of a bundle is represented by additive edge weights. The second constraint has to be handled so that each agent obtains one conflict-free path in her graph. Such a setting occurs in application domains such as network function virtualization (NFV) where users request to allocate directed graphs of services into a shared networked infrastructure [START_REF] Yang | Recent advances of resource allocation in network function virtualization[END_REF], or in Earth observation using a constellation of satellites, where users demand the ownership of some repetitive orbit slots (without overlapping with other users' slots) to implement periodic observation requests [START_REF] Lemaître | Equitable allocation of earth observing satellites resources[END_REF][START_REF] Picard | Auction-based and distributed optimization approaches for scheduling observations in satellite constellations with exclusive orbit portions[END_REF], as illustrated before. In such settings, beside the additive edge weights, other criteria can be considered to guide the allocation process, especially when constellation users are stakeholders expecting allocations to be fair or proportional to their investment. Fig. 1: An orbit slot allocation problem involving 2 agents (a in red, b in blue) requesting slots around 2 time plots (t1 and t2), tolerance windows around each plot (in gray), and with 2 opportunities for each plot (a1, . . . , a4, b1, . . . , b4).

Related Work. Literature contains some work related to allocation of goods structured as graphs. In fair division of graph, the objective is to divide a graph of items between several agents, with additive utilities attached to nodes [START_REF] Bouveret | Fair division of a graph[END_REF][START_REF] Igarashi | Pareto-optimal allocation of indivisible goods with connectivity constraints[END_REF]. These works provide interesting properties to find envy-free or Pareto-optimal allocations, in an efficient manner in some specific graph structures, e.g. paths, trees, stars. However, in our problem, (i) agents do not compete for the very same set of items, (ii) the graph is directed to compose paths from a start time to an end time, (iii) even by mapping our problem to a graph division one and by regrouping conflicting items into composite items, it is highly improbable that the resulting graph is acyclic. Here, graphs are used to express preferences, and not the goods to allocate. In short, our work does not fall into the existing graph fair division frameworks, or cannot benefit from theoretical results on path-shaped or star-shaped graphs. Another related work is path auctions [START_REF] Immorlica | First-price path auctions[END_REF][START_REF] Du | Path auctions with multiple edge ownership[END_REF][START_REF] Zhang | False-name-proof mechanisms for path auctions in social networks[END_REF], where agents bid for paths in a graph where each edge is owned by an agent. The goal is to assign paths to agents by the means of auctions, and optionally to keep some privacy for the edge owners. In the case of a utilitarian objective function for the winner determination problem, without price privacy, this falls into the Vickrey-Clarke-Groves framework, and thus guarantees some efficient and strategyproof mechanisms. But, here again, agents bid on the very same set of nodes and edges.

In the transportation domain, investigations on very similar structures, that is flow networks, provide techniques for fair maximum flow in multi-source and multi-sink networks [START_REF] Megiddo | Optimal flows in networks with multiple sources and sinks[END_REF]. While the techniques used are very similar to ours (linear programming), the maximum flow objective is very different from path utility maximization. Besides, [START_REF] Hughes | The multiple shortest path problem with path deconfliction[END_REF] worked on multiple shortest path problems based on deconflicting techniques. While the problem displays similar characteristics, once again the agents evolve on the very same graphs, and the objective is focused on minimizing path length and minimizing conflicting paths, without fairness desiderata.

In congestion games, agents are allocated paths so that delay incurred by crossing paths are minimized. The more agents are allocated the same nodes, the more delay is attached to their paths [START_REF] Nisan | Algorithmic Game Theory[END_REF][START_REF] Panagopoulou | Algorithms for pure nash equilibria in weighted congestion games[END_REF]. In our work, we don't consider delay but incompatibilities. Even if they could be modeled as non linear {0,∞} functions, in our problem some path allocations are unfeasible, contrarily to congestion games. Besides, using congestion game solution methods as in [START_REF] Panagopoulou | Algorithms for pure nash equilibria in weighted congestion games[END_REF] may result in unfair Nash equilibria, because of numerous unfeasible paths.

More generally, another classical approach to fair allocation of indivisible goods is round-robin, which is almost envy-free [START_REF] Caragiannis | The unreasonable fairness of maximum nash welfare[END_REF]. This is notably one favored technique to allocate virtual network functions in network function virtualization infrastructures [START_REF] Riera | Virtual network function scheduling: Concept and challenges[END_REF], or to schedule tasks. We will use it as a competitor for our techniques.

Contributions. This paper introduces and expounds a model for such scenarios, under the prism of optimality and fairness, which captures any application where agents express preferences as edge-weighted DAGs and where there exist conflicts between some nodes of these DAGs. We show that this allocation problem is NP-hard. We expound and assess several algorithms on data coming from simulated satellite constellations and requests, with respect to utilitarian optimality, computation time, and fairness.

Problem Model

We study allocation problems where agents' valuations of item bundles are represented as edge-weighted DAGs and some conflicts exists between nodes of these graphs. An allocation consists in choosing one full path in each graph, so that selected paths do not conflict with each other.

Definitions and Notations

Definition 1. A problem of path allocation in multiple conflicting edge-weighted directed acyclic graphs (PADAG) is a tuple ⟨A,G,µ,C⟩, where -A={1,...,n} is a set of agents; -G ={g 1 ,...,g m } is a set of edge-weighted DAGs, where each g ∈G is a triple ⟨V g ,E g ,u g ⟩ that represents some preferences over some items in V g , with connections between items in E g ⊂V g ×V g , weighted using utility function u g :V g ×V g →R; we also assume that V g contains two specific nodes, the source s g and the sink t g , and that E g contains an edge from s g to t g labeled by utility 0 (useful to deal with cases where no bundle of items can be selected in g); µ:G →A maps each graph g in G to its owner a in A; -C ⊆{(v,v ′ )|(v,v ′ )∈V g ×V g ′ ,g,g ′ ∈G 2 ,µ(g)̸ =µ(g ′ )} is a set of conflicts between pairs of items from two distinct graphs in G from two distinct agents.

For each graph g and each set of edges X ⊆ E g , the utility of X for g is defined by u g (X)= e∈X u g (e), which means that edge valuations are considered as additive in this paper. As a result, each path from s g to t g in a graph g is evaluated by summing the utilities of the traversed edges, and each DAG represents in a compact manner a set of valuations for bundles of items, as in combinatorial auctions. Also, we denote by G a =µ -1 (a) the set of graphs owned by agent a, and the utility of a set of edges X for agent a is defined by u a (X)= g∈µ -1 (a) u g (X ∩E g ). Definition 2. An allocation is a function π that associates, with each graph g ∈G, one path π(g) from s g to t g in g. Formally, π(g) can be represented as a set of nodes in V g . Indeed, as DAGs are manipulated, it is easy to reconstruct the edges successively traversed by the path from this set. By extension, the allocation for agent a is given by π(a)=∪ g∈µ -1 (a) π(g).

By convention, we denote by u(π(g)) = u µ(g) (π(g)) (resp. u(π(a)) = u a (π(a))), the utility of graph g (resp. agent a) for allocation π. Last, the global utility obtained with allocation π is given by u(π)= g∈G u(π(g)) (or equivalently u(π)= a∈A u(π(a))). Definition 3. An allocation π is valid if for each pair of distinct graphs g and g ′ there is no conflict between nodes in the resulting paths, i.e. (π(g)×π(g ′ ))∩C =∅.

π ex = {a → {s a ,a 2 ,a 4 ,t a },b → {s b ,b 1 ,b 3 ,t b }} with global utility u(π ex ) = u(π ex (a))+u(π ex (b))=0.35+1.0=1.35.
The problems we consider in this paper are (i) how to compute an optimal (utilitarian) allocation π that maximizes u(π), and (ii) how to compute an optimal fair allocation π, by the way of a leximin optimization, i.e. maximizing the ordered utility vector (Λ 1 ,...,Λ n ) containing one component per agent. Formally, ∀i ∈ A, there exists a unique j such that u(π(i))=Λ j and ∀i≤j, Λ i ≤Λ j .

Complexity Analysis

The two following propositions provide complexity results on the two problems studied, relatively to utilitarian optimization and leximin optimization respectively. Proposition 1 Determining whether there exists a valid allocation π such that utilitarian evaluation u(π) is greater than or equal to a given value is NP-complete.

Proof. First, the problem is NP since u(π) is computable in polynomial time. Then, there exists a polynomial reduction of 3-SAT (which is NP-complete) to our problem. Basically, in a 3-SAT formula, each clause over propositional variables x,y,z can be represented as a weighted DAG g where (1) the set of nodes is V g ={x,¬x,y,¬y,z,¬z,s g ,t g }, (2) the set of paths from s g to t g in g corresponds to the set of truth-values for x,y,z that satisfy the clause (decision diagram representation), (3) the weight of every edge is set to 0 except for edges s g → n where n ̸ = t g that have weight 1/m, with m the number of clauses in the 3-SAT formula. Last, for every propositional variable x, we can add one conflict (n,n ′ ) for each pair of nodes labeled by literals x and ¬x in two distinct graphs. Then, as one path is selected in each graph and as there are m graphs, determining whether there exists a valid allocation π such that u(π)≥1 is equivalent to finding a solution that satisfies all the clauses, hence the NP-completeness result given that all operations used in the transformation are polynomial.

Proposition 2 It is NP-complete to decide whether there exists a valid allocation whose leximin evaluation is greater than or equal to a given utility vector. The proposition holds even if there is a unique graph per agent.

Proof. In the general case, it suffices to consider a problem involving a unique agent owning all the graphs, and to use the result of the previous proposition. If there is a unique graph per agent, it suffices to use the exact same 3-SAT encoding as before but to replace weights 1/m by weights 1. Then, it is possible to show that there exists a valid allocation whose leximin evaluation is greater than or equal to (1,1,...,1) iff there exists a solution for the 3-SAT problem. Moreover, the leximin evaluation of an allocation π can be computed in polynomial time, hence the NP-completeness result.

Path Allocation Schemes

We propose here several allocation schemes for PADAGs. Some of them are based on integer linear programming (ILP) and mixed integer linear programming (MILP), so we first introduce decision variables and constraints for these models.

For any DAG g = ⟨V g ,E g ,u g ⟩, we define binary variables x e ∈ {0,1}, for any e ∈ E g , stating whether edge e is selected in the path defining the solution bundle. We also use auxiliary binary variables β v stating whether node v is selected in solution path π(g), i.e.

β v = 1 if v ∈ π(g), 0 otherwise. For any node v in V g , we denote by In(v) (resp. Out(v))
its set of incoming (resp. outcoming) edges. In all ILP models introduced thereafter, we impose Constraints ( 1)-( 3) to define all the possible paths, Constraints (4)-( 5) to account for item selection conflicts, and Constraint [START_REF] Igarashi | Pareto-optimal allocation of indivisible goods with connectivity constraints[END_REF] to ensure that sources and sinks are selected.

e∈In(v) x e = e∈Out(v)
x e , ∀g ∈G,∀v ∈V g \{s g ,t g } (1)

e∈Out(sg)
x e =1, ∀g ∈G

e∈In(tg)

x e =1, ∀g ∈G

x e =β v , ∀g ∈G,∀v ∈V g \{s g ,t g } (4)

v∈c β v ≤1, ∀c∈C (5)
β sg =β tg =1, ∀g ∈G (6)

Utilitarian Allocation (util)

The classical approach to allocation is the utilitarian one. It consists in finding the allocation that maximizes the sum of utilities of all selected paths. This corresponds to solving the integer linear program P util (⟨A,G,µ,C⟩) given below:

max a∈A g∈Ga e∈Eg u g (e)•x e (7)
s.t. (1),( 2),(3),( 4),( 5), [START_REF] Igarashi | Pareto-optimal allocation of indivisible goods with connectivity constraints[END_REF] x e ∈{0,1}, ∀a∈A,∀g ∈G a ,∀e∈E g

The resulting allocation π is decoded from the β v variables. Formally, for all g ∈ G,

π(g)={v ∈V g | β v =1}.

Leximin Allocation (lex)

Beyond utilitarianism, one way to implement fair allocation and Pareto-optimality is to consider the leximin rule that selects, among all possible allocations, an allocation leading to the best utility profiles wrt the leximin order [START_REF] Moulin | Fair division and collective welfare[END_REF]. More precisely, let z = [z 1 ,...,z n ] be the utility vector where each component z a ∈ [0,Z a ] represents the utility for agent a ∈ A. Z a denotes here the best utility value for user a considered alone, i.e. for the mono-agent problem where the best path can be chosen for each graph g ∈G a . In leximin optimization, the objective is to lexicographically maximize vector Λ=[Λ 1 ,...,Λ n ] obtained after ordering [z 1 ,...,z n ] following an increasing order.

Such a leximin rule can be implemented through a sequence of ILP [START_REF] Kurokawa | Leximin allocations in the real world[END_REF]. We adapt here such a procedure to the specific case of PADAGs. Suppose we have already optimized over the first

K -1 components [Λ 1 ,...,Λ K-1 ] of Λ, for K ∈[1..n].
Then, one can use the MILP presented thereafter to optimize the K th component Λ K of the leximin profile of z. In this model, λ represents the utility obtained at level K in Λ, with λ∈[Λ K-1 ,max a∈A Z a ] and by convention Λ 0 =0. y ak is a binary variable equal to 1 if agent a∈A plays the role of the agent associated with level k ∈[1..K -1] in [Λ 1 ,...,Λ K-1 ], 0 otherwise. The optimization of Λ K can be performed using program P lex (⟨A,G,µ,C⟩,K,[Λ 1 ,...,Λ K-1 ]) given below: max λ (9) s.t. (1),( 2),(3),(4),( 5),( 6)

z a = g∈Ga e∈Eg u g (e)•x e , ∀a∈A (10)
a∈A

y ak =1, ∀k ∈[1..K -1] (11)
k∈[1..K-1]

y ak ≤1, ∀a∈A (12)
λ≤z a +M k∈[1..K-1] y ak , ∀a∈A (13)
z a ≥ k∈[1..K-1] Λ k •y ak , ∀a∈A (14)
In Constraint 13, M = max a∈A Z a is used to ignore agents associated with levels strictly lower than K when optimizing λ (big-M formulation). Constraint 14 ensures that the utility obtained for the agent associated with level k ∈ [1..K -1] must not be less than Λ k . To implement the leximin rule, it then suffices to solve a sequence of P lex problems for K ∈A to optimize the value of each component of the utility profile.

Example 3. For the example in Figure 2, the leximin-optimal allocation is π lex = {a → {s a ,a

Approximated Leximin Allocation (a-lex)

This previous model implements an exact leximin rule, and thus enforces fairness in the resulting allocation, but may not scale well when increasing the number of agents and edges. This is why we provide an approximate version of the computation of the leximin, based on an iterated maximin scheme. Basically, this approach considers at each step a minimum utility ∆ a ≥ 0 for some agents and maximizes the worst utility among the remaining agents, for which we arbitrarily assume ∆ a = -1. The problem to solve, referred to as P a-lex (⟨A,G,µ,C⟩,∆), is the following one: max δ (15) s.t. (1),( 2),( 3),( 4),( 5), [START_REF] Igarashi | Pareto-optimal allocation of indivisible goods with connectivity constraints[END_REF] δ ≤ g∈Ga e∈Eg

u g (e)x e , ∀a∈A | ∆ a =-1 (16)
g∈Ga e∈Eg

u g (e)x e ≥∆ a , ∀a∈A | ∆ a ̸ =-1 (17)
The solution method then consists in optimizing in an iterated manner, as for leximin. As sketched in Algorithm 2, at each iteration (one per agent), P a-lex is solved, one worst agent â is determined, and its minimum utility ∆ â is fixed.

The main difference with P lex is that at each iteration, in P a-lex , the position of an agent in the order is implicitly determined once for all, while in P lex the order can be revised at each iteration. Moreover, if any equality occurs at line 5 to determine the worst agent (case |S|>1), one may rely on some heuristic or arbitrary choice. Thus, P a-lex is an approximation of P lex that contains fewer variables and constraints.

Example 4. The approximated leximin allocation for the example in Figure 2 is π a-lex = {a → {s a ,a 1 ,a 4 ,t a },b → {s b ,b 2 ,b 3 ,t b }}, with utility vector (u(π a-lex (a)),u(π a-lex (b))) = (0.62,0.70) and global utility u(π a-lex ) = 0.62+0.70 = 1.32. This is the same as π lex since there are only two agents and no equality between the worst utilities.

Greedy Allocation (greedy)

For very fast decisions, iterated maximin might still be too slow. In such cases, a greedy approach can provide valid allocations quickly. The main idea of greedy path allocation is to iterate over the set of graphs. At each step, one graph g * that has the best utility path is selected, this path is chosen as π(g * ), and all nodes in the other graphs that are in conflict with nodes in π(g * ) are deactivated. Graph g * is then removed, and the process continues until there is no more graph to consider. This process ensures that constraints (1), ( 2), ( 3), ( 4), ( 5), ( 6) are met.

Determining the best path in a DAG g is linear time

O(|E g | + |V g |) [3]
. Obviously, greedy is equivalent to utilitarian when there is no conflict between graphs. Indeed, greedy will return the best path for each graph, which is the best utilitarian solution in such settings. Moreover, this greedy approach results in a Nash equilibrium where no agent might be able to improve its utility without a negative impact on other agents. This is equivalent to the Nashify procedure from [START_REF] Panagopoulou | Algorithms for pure nash equilibria in weighted congestion games[END_REF] in the context of congestion games, with only one turn. We will see in the experiments that this equilibrium is far from being fair.

Round-Robin Allocations (p-rr and n-rr)

One fast approach to fair allocation of indivisible goods is round-robin. It consists in making each agent choose in turn (in a predefined fixed order) one item (depending on her preferences) until there is no more item to allocate. As greedy, it is polynomial in the number of agents and items. In our case, one may consider two kinds of items to allocate: paths (noted p-rr) or nodes (noted n-rr). In the case of paths, at her turn, each agent selects her best feasible path, given the already allocated nodes (to prevent conflicts). This process operates similarly to greedy, but alternates between users to balance the utilities. In the case of nodes, each agent incrementally builds the path associated with each of her graphs, by choosing in turn her next best feasible node until either it reaches the sink or there is no more feasible node to choose (a dead-end path). In the latter case, the agent is allocated the 0-utility source-to-sink path and looses the previously chosen nodes. In both approaches, constraints (1), ( 2), (3), (4), ( 5), ( 6) are met since considered paths are all feasible. Let's note that p-rr results in a Nash equilibrium where each agent has been allocated the best path given the other allocations. This is not the case for n-rr, since some nodes left by some agent falling in a dead-end may have prevented some other agents to find a better solution.

Example 6. The path-round-robin allocation π p-rr for the example in Figure 2 is equivalent to π greedy , since a chooses {s a ,a 1 ,a 3 ,t a } and then b chooses {s b ,b 2 ,b 4 ,t b }}. The noderound-robin allocation π n-rr is also equivalent to π greedy because a first chooses a 1 , then b chooses b 2 (only feasible option), then a chooses a 3 (best option), and finally b chooses b 4 (only feasible option).

Experimental Evaluation

In this section, we evaluate the different allocation methods proposed when applied to an orbit slot allocation problem1 encoded as PADAGs. We expound the experimental setup and analyze some results obtained on synthetic instances.

Experimental Setup. We consider a Low-Earth Orbit constellation (500km altitude) composed of n p regularly-spaced orbital planes having a 60-degree inclination, with n p ∈{2,4,8,16} and 2 regularly spaced satellites over each orbital plane. To generate PADAG instances, we randomly generate requests for 4 agents wishing to obtain orbit slot ownerships to implement some repetitive ground acquisitions of Points Of Interest (POIs) belonging to the same area. POIs are randomly selected within a extracted subset from [START_REF]OpenStreetMap: Openstreetmap points of interest[END_REF]. All the agents have the same template for a request r: getting an observation every day at 8:00 + δ r , 12:00 + δ r , and 16:00 + δ r , with a tolerance of 1 hour around each time plot, and uniform random time shift δ r ∈[-2,2] for all the time plots of the same request. For each POI and each time plot, the orbit slots over which orbit ownership can be claimed for performing observations are determined thanks to a space mechanics toolbox, based on the assumption that a satellite is relevant for a POI as soon as its elevation above the horizon is greater than 15 degrees. Incompatible time slots are those which overlaps while belonging to the same satellite.

We then encode these requests and orbit slots into PADAGs. Each request is mapped to a graph, in which nodes (except source and sink) are orbit slots for capturing a POI at some time plot, and edges links two such consecutive orbit slots to answer the request. For instance, Figure 2 represents two requests from two users (a and b), with two time plots, each having two possible orbit slots per time plot per user (e.g. for user a, a 1 and a 2 for the first time plot, a 3 and a 4 for the second one). For simplicity, we only consider utilities attached to the slots, and not to the transitions between slots. We study a linear utility function, which is linear in the distance between the middle τ of the allocated slot and the requested time plot (utility linearly decreasing from 1 when τ is exactly on the time plot to 0 when τ reaches the bounds of the tolerance window). We normalize each utility wrt the maximum utility that can be achieved for each graph individually. We consider 2 requests per agent, and a horizon of 365 days resulting in DAGs having 1095 layers (1095 time plots). This setting results in DAGs having the following properties on average: Solvers are coded in Java 1.8 and executed on 20-core Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60GHz, 62GB RAM, Ubuntu 18.04.5 LTS. Utilitarian, leximin and approximated 1 which is a novel problem, not to be confused with orbit scheduling problems [START_REF] Lemaître | Equitable allocation of earth observing satellites resources[END_REF]. leximin make use of the Java API of IBM CPLEX 20.1 (with 10min timeout). We ran 30 instances of randomly generated PADAGs and plot the average with [0.05,0.95] confidence.

n p 2
Utility. Figure 3a shows the average normalized global utility for each algorithm and constellation size (expressed in number of orbital planes). Normalized global utility is the mean graph utility, thus between 0 and 1. Obviously util provides the optimal utilitarian allocation. In second position, a-lex provides good allocations at almost 85% of the optimal value on average. Interestingly, lex performs equivalently to a-lex (gap less than 5% on average). Indeed, a-lex provides slightly better allocations from the utilitarian point of view, at the expense of fairness approximation. Round-robin approaches really differ in utility. While p-rr provides allocations at almost 71% of the optimal, n-rr results in low-utility allocations, at almost 10% of the optimal on smaller constellations. In fact, in such settings, there are few feasible paths for each request. Thus, for most of the requests, the myopic incremental building of paths results in dead-ends, and thus on 0-utility allocations; while, by considering another agent order, the allocations could have been better. Finally, greedy behaves slightly worse than p-rr, at almost 68% of the optimal value on average. On larger instances, where many paths exist to answer each request, greedy performs even better. More generally, larger constellation problems are easier to solve from the utilitarian point-of-view for non-optimal algorithms, since there are more options to avoid conflicts, even if the number of conflicts is higher.

Fairness.

To analyze the fairness of the resulting allocations, Figure 4 provides the utility profiles obtained for the first 5 instances for each algorithm. greedy, by principle, seeks to first allocate the highest utility paths, resulting in unfair allocations where only the first 2 or 3 users are served, while most of the time the fourth user has no request fulfilled. Round-robin approaches are fairer than greedy and often fulfill requests for more users. util results in profiles with the larger surface, but most of the time the fourth user is neglected. Finally, lex and a-lex behave almost identically (their profiles are superimposed), showing that the a-lex approximation is sufficient to output fair allocations. Let's note that with growing constellations, since there is more and more options to serve users, all the algorithms tend to result in fairer allocations. Still, lex and a-lex are the best choices here, and the round-robin competitors output unsatisfactory allocations.

Computation Time. Figure 3b shows the average computation time in milliseconds for each algorithm and each constellation size. As expected (by design), greedy, p-rr and n-rr are the fastest. n-rr which does not even perform shortest path operations is the fastest by far, but results in very bad and not-so-fair allocations. greedy and p-rr are very fast, but are based on multiple max path search in DAGs. p-rr still quickly provides quite good utilitarian and fair allocations. util, based on a single ILP solving, is 100 times slower than the fastest algorithms. Then, lex and a-lex are up to two orders of magnitude slower than util on the largest constellations. This is due to the multiple calls (|A|) to the MILP solver on large problems. a-lex is 2 to 3 times faster than lex since it solves smaller MILPs, while resulting in allocations that are as fair as lex's ones.

Conclusion

In this paper, we proposed the PADAG model, a novel allocation problem where agents express their preferences over bundles of items as edge-weighted DAGs. We introduced and analyzed several solution methods (utilitarian, leximin, approximate leximin, greedy) against the round-robin allocations, from the utilitarianism and fairness perspectives. We evaluated these methods on large randomly generated instances of orbit slot allocation problems, with more than 1000 layers. On larger constellations, we observe that approximate leximin constitutes a good trade-off between utilitarian optimality, leximin optimality and computation time, compared to all other solution methods. It is even equivalent to exact leximin on most of the instances, while dividing the computation times by a factor 2 to 3. We identify several tracks for future investigations. First, as approximate leximin is a trade-off between fairness and computation times, we would like to investigate other solution methods, even more reactive, as to solve larger PADAGs and specific topologies. Indeed, as for path division and congestion games, dedicated techniques could be devised for given topologies (stars, chains, etc.). Second, since PADAGs are strongly constrained by conflicts, we aim to explore min-conflict heuristics to improve our algorithms. Finally, we believe PADAGs have great potential to be used in a variety of domains, and we thus aim to evaluate the proposed techniques on problems coming from other application fields, like the NFV domain where function chains are modeled as graphs, and incompatibilities control the access to nodes or multi-agent path finding domain (path preferences are modeled as graphs, and incompatibilities model the constraints to avoid two agents to occupy the same position at the same time).

Fig. 2 :

 2 Fig. 2: Sample users' bundle valuations (or preferences) represented as DAGs. Conflicts are represented as gray hypernodes.

Example 2 .

 2 In Figure 2, the utilitarian allocation is π util = {a → {s a , a 2 , a 3 , t a }, b → {s b ,b 1 ,b 4 ,t b }}, with global utility u(π util )=u(π util (a))+u(π util (b))=0.80+0.60=1.40.

1 ,a 4 Algorithm 1 :Algorithm 2 : 5 â←choose an agent a in S 6 ∆

 141256 ,t a },b →{s b ,b 2 ,b 3 ,t b }}, with utility vector (u(π lex (a)),u(π lex (b)))=(0.62,0.70) and global utility u(π lex )=0.62+0.70=1.32. Leximin algorithm Data: A PADAG problem ⟨A,G,µ,C⟩ Result: A leximin-optimal path allocation π 1 for K =1 to |A| do 2 (λ * ,sol)←solve P lex (⟨A,G,µ,C⟩,K,[Λ1,...,ΛK-1]) 3 ΛK ←λ * 4 for g ∈G do π(g)←{v ∈Vg | sol(βv)=1} 5 return π Approximated leximin algorithm Data: A PADAG problem ⟨A,G,µ,C⟩ Result: An iterated maximin-optimal allocation π 1 ∆←[-1,...,-1] 2 for K =1 to |A| do 3 (δ * ,sol)← solve P a-lex (⟨A,G,µ,C⟩,∆) 4 S ← argmin a∈A | ∆a=-1 g∈Ga e∈Eg ug(e)sol(xe) â ←δ * 7 for g ∈G do π(g)←{v ∈Vg | sol(βv)=1} 8 return π

Example 5 .

 5 The greedy allocation for the example in Figure2is π greedy ={a →{s a ,a 1 ,a 3 ,t a },b → {s b ,b 2 ,b 4 ,t b }}, with global utility u(π greedy ) = u(π greedy (a))+u(π greedy (b)) = 1.0+0.3 = 1.3 and utility vector (1.0,0.3).

Fig. 3 :

 3 Fig. 3: Average overall utility (left) and computation time (right) obtained by each algorithm for each constellation size.

  0