S Baruah

V Bonifaci

G D'

Angelo H Li

A Marchetti-Spaccamela

S Van Der Ster

L Stougie

The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems

Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non safety critical and does not need to be certified, or is certified to a lower level of assurance. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is described for the scheduling of such mixed-criticality task systems. Analyses of EDF-VD significantly superior to previously-known ones are presented, based on metrics such as processor speedup factor (EDF-VD is proved to be optimal with respect to this metric) and utilization bounds.

I. INTRODUCTION

In implementing safety-critical embedded systems, there is an increasing trend towards integrated computing environments, in which multiple functionalities are implemented on a shared computing platform; this trend is evident in industry-driven initiatives such as Integrated Modular Avionics (IMA) [START_REF] Prisaznuk | Integrated modular avionics[END_REF] in aerospace and AUTOSAR (AUTomotive Open System ARchitecture -see www.autosar.org) in the automotive industry. This trend towards integration means that even in highly safety-critical systems, typically only a relatively small fraction of the overall system is actually of critical functionality and subject to mandatory certification by statutory certification authorities (CAs). Such systems are called mixed-criticality (MC) systems.

In order to certify a system as being correct, the CA must make certain assumptions about the worst-case behavior of the system during run-time. CAs tend to be very conservative and require that the safety-critical functionalities be shown to be correct at a very high level of assurance; the remaining (non safety-critical) functionalities are usually validated correct by the system designer/ integrator, at lower levels of assurance.

To show that real-time systems meet timing properties, worst-case execution times (WCETs) must be estimated for certain pieces of code, denoting an upper bound on the amount of time the piece of code would take to execute. One consequence of the different levels of assurance of correctness sought by the CA and the system designer is 1 Baruah and Li are with the University of North Carolina. Bonifaci is with Istituto di Analisi dei Sistemi ed Informatica "Antonio Ruberti". D'Angelo is with MASCOTTE project, INRIA. Marchetti-Spaccamela is with Sapienza Università di Roma. Van der Ster and Stougie are with Vrije Universiteit Amsterdam; Stougie is also affiliated with CWI.

that the same piece of code may be characterized by different WCET parameters for the purposes of certification, and for design validation. Multiple WCET parameters. Why would we wish to specify multiple WCET parameters for a single piece of code? It is well known that determining exact worst-case execution times of pieces of code is a very difficult problem; instead, system engineers work with upper bounds on the exact value. However, for many non-trivial kinds of code strict upper bounds are extremely pessimistic, and represent scenarios that are highly unlikely, or indeed impossible, to occur in practice [START_REF] Burns | Reasoning about the reliability of multi-version, diverse real-time systems[END_REF]. For such code, less pessimistic upper bounds on their WCET's may be obtained at lower degrees of confidence than absolute certainty. Based on the observation that "the more confidence one needs in a task execution time bound, the larger and more conservative that bound tends to be in practice," Vestal [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] proposed that multiple different WCET values be specified, with the different values being determined at different levels of assurance. These different values may be obtained by using different execution-time analysis tools; we expect that the tool used by the CA is more conservative than the one used by the system engineer, and hence the CA's WCET estimates are larger than the estimates used during the design process. Dual-criticality systems. We have considered two criticality levels -needing certification, and not needing certification -in the discussion above. However, in many safety-critical application domains more than two criticality levels are specified; for instance, the DO-178B standard that is widely used in the avionics domain specifies five different criticality levels (A:-catastrophic/ B:-hazardous/ C:-major/ D:-minor/ E:-no effect -the adjectives denote the potential consequences of failure at the corresponding level) and mandates that each functionality be assigned one of these levels. Functionalities at higher criticality levels (A is the highest level, and E the lowest) are then subject to more rigorous validation requirements. We are eventually interested in systems with arbitrarily many criticality levels; however in this document we will, for ease of presentation, focus primarily on systems with just two criticality levels that we will call LO and HI; we call such systems dual-criticality systems. We postpone a discussion regarding how our results generalize to more than two criticality levels to an extended paper combining these results with those in [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF], currently under preparation.

Context and Related work. In traditional (i.e., not mixedcriticality) real-time systems, a sporadic task [START_REF] Mok | Fundamental Design Problems of Distributed Systems for The Hard-Real-Time Environment[END_REF], [START_REF] Leung | On the complexity of fixedpriority scheduling of periodic, real-time tasks[END_REF] τ i is characterized by a WCET C i , a relative deadline D i , and a period T i ; such a task generates an unbounded sequence of jobs with successive jobs arriving at least T i time units apart, and each job needing up to C i units of execution by a deadline that occurs D i time units after the job's arrival. Vestal [START_REF] Vestal | Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[END_REF] proposed generalizing the model to mixed-criticality systems by allowing for several WCETs to be specified for each task, and studied the fixed-priority scheduling of such mixed-criticality sporadic task systems on a preemptive uniprocessor. Further results on this problem appear in [START_REF] Baruah | Response-time analysis for mixed criticality systems[END_REF], [START_REF] Burns | Timing faults and mixed criticality systems[END_REF].

The preemptive uniprocessor scheduling of collections of mixed-criticality independent jobs was studied in [START_REF] Baruah | Towards the design of certifiable mixed-criticality systems[END_REF], [START_REF] Baruah | Mixed-criticality scheduling: improved resource-augmentation results[END_REF], [START_REF] Baruah | Scheduling realtime mixed-criticality jobs[END_REF], [START_REF] Baruah | Scheduling real-time mixed-criticality jobs[END_REF]. An efficient scheduling algorithm and associated polynomial-time schedulability test was proposed that makes the following guarantee: any dual-criticality system that can be scheduled by an optimal clairvoyant algorithm on a given processor can be scheduled by this algorithm on a processor that is (1+ √ 5)/2 ≈ 1.62 times as fast. In [START_REF] Li | An algorithm for scheduling certifiable mixed-criticality sporadic task systems[END_REF], [START_REF] Guan | Effective and efficient scheduling for certifiable mixed criticality sporadic task systems[END_REF], this result was extended to mixed-criticality sporadic task systems: a scheduling algorithm and associated pseudopolynomialtime schedulability test was proposed that makes the same guarantee. These scheduling algorithms, however, have too large a run-time complexity to be implementable in practice: the run-time complexity per scheduling decision of the algorithm in [START_REF] Li | An algorithm for scheduling certifiable mixed-criticality sporadic task systems[END_REF] is pseudo-polynomial in the representation of the task system, while the one in [START_REF] Guan | Effective and efficient scheduling for certifiable mixed criticality sporadic task systems[END_REF] is quadratic in the number of tasks.

An important special case of sporadic task systems are task systems in which each task τ i satisfies the property that D i = T i -such systems are called implicit-deadline or Liu & Layland task systems. The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems was studied in [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF]. An algorithm called EDF-VD was proposed that has the same speedup guarantee as above -any task system that can scheduled by an optimal clairvoyant algorithm on a given processor can be scheduled by EDF-VD on a processor that is (1 + √ 5)/2 times as fast. Moreover, the schedulability test of EDF-VD has polynomial run-time complexity, and the run-time complexity per scheduling decision was logarithmic in the number of tasks. Based on these run-time properties it is evident that EDF-VD, in contrast to the algorithms in [START_REF] Li | An algorithm for scheduling certifiable mixed-criticality sporadic task systems[END_REF], [START_REF] Guan | Effective and efficient scheduling for certifiable mixed criticality sporadic task systems[END_REF], can be considered suitable for implementation in actual systems. This research. Our main contribution in this paper is a more refined analysis of EDF-VD showing that EDF-VD can actually make a better performance guarantee: any task system that can be scheduled by an optimal clairvoyant algorithm on a given processor can be scheduled by EDF-VD on a processor that is 4/3 times as fast. This new analysis is based upon some sophisticated new techniques and deep insights that we have recently developed, and represents a substantial improvement over the bound proved in [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF]. It was previously shown [START_REF] Baruah | Scheduling real-time mixed-criticality jobs[END_REF]Prop. 2] that (1 + √ 5)/2 is a lower bound on the speedup of any non-clairvoyant algorithm for scheduling collections of independent jobs; it is somewhat surprising that this bound does not hold for the more expressive implicit-deadline task model. We also show that no non-clairvoyant algorithm can guarantee to always meet all deadlines on a processor that is less than 4/3 times as fast as the processor available to the optimal clairvoyant algorithm, thereby proving that EDF-VD is an optimal nonclairvoyant algorithm from the perspective of this metric. In addition, we spell out the details as to how EDF-VD can actually be implemented to have the logarithmic runtime complexity claimed in [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF]. We also perform further analysis on the behavior of EDF-VD, deriving a utilizationbased schedulability test and exploring its behavior under certain extremal conditions. Organization. The remainder of this paper is organized as follows. In Section II we formally describe the mixedcriticality model that we will be using in the remainder of this paper. In Section III we provide a high-level overview of EDF-VD. We provide a detailed description of the schedulability test in Section IV, and of the run-time algorithm in Section V. We provide a formal analysis of the properties and behavior of EDF-VD in Sections VI-VIII, and describe the outcome of some simulation experiments in Section IX.

II. MODEL AND DEFINITIONS

A mixed-criticality (MC) implicit-deadline sporadic task system τ consists of a finite specified collection of MC implicit-deadline sporadic tasks, each of which may generate an unbounded number of MC jobs. MC jobs. As stated in Section I above, we will, for the most part, restrict our attention here to dual-criticality systems: systems with two distinct criticality levels, which we denote as LO and HI.

Each such dual-criticality job is characterized by a 5-tuple of parameters: J i = (a i , d i , χ i , c i (LO), c i (HI)), where

• ai ∈ R + is the release time, and di ∈ R + the deadline. We require that di ≥ ai. • χi ∈ {LO, HI} denotes the criticality of the job. A HIcriticality job (a Ji with χi = HI) is one that is subject to certification, whereas a LO-criticality job (a Ji with χi = LO) is one that does not need to be certified. • ci(LO) specifies the worst case execution time (WCET) estimate of Ji that is used by the system designer (i.e., the WCET estimate at the LO criticality level). • ci(HI) specifies the WCET estimate of Ji that is used by the certification authorities (i.e., the WCET estimate at the HI criticality level).

System behavior. The MC job model has the following semantics. Job J i is released at time a i , has a deadline at d i , and needs to execute for some amount of time γ i . The value of γ i is not known beforehand, but only becomes revealed by actually executing the job until it signals that it has completed execution. These values of γ i for a given run of the system defines the kind of behavior exhibited by the system during that run. If each J i signals completion without exceeding c i (LO) units of execution, we say that the system has exhibited LO-criticality behavior; if even one job J i signals completion after executing for more than c i (LO) but no more than c i (HI) units of execution, we say that the system has exhibited HI-criticality behavior. If any job J i does not signal completion despite having executed for c i (HI) units, we say that the system has exhibited erroneous behavior. Informally, the system-designer expects LO-criticality behavior, while the CA is allowing for the possibility of HI-criticality behavior. MC implicit-deadline sporadic tasks. Analogously to traditional (non-MC) implicit-deadline sporadic tasks, an MC implicit-deadline sporadic task τ k is characterized by a four-tuple (χ k , C k (LO), C k (HI), T k ), with the following interpretation. Task τ k generates an unbounded sequence of jobs, with successive jobs being released at least T k time units apart. Each such job has a deadline that is T k time units after its release. The criticality of each such job is χ k , and it has LO-criticality and HI-criticality WCET's of C k (LO) and C k (HI) respectively; we assume that C k (LO) ≤ C k (HI) for all tasks τ k .

An MC implicit-deadline sporadic task system is specified by specifying a finite number of such sporadic tasks. As with traditional (non-MC) systems, such a MC sporadic task system can potentially generate infinitely many different MC instances (collections of jobs), each instance being obtained by taking the union of one sequence of jobs generated by each task. Correctness criteria. We define an algorithm for scheduling MC task systems to be correct if it is able to schedule any system such that

• During all LO-criticality behaviors of the system, all jobs receive enough execution between their release time and deadline to be able to signal completion; and • During all HI-criticality behaviors of the system, all HIcriticality jobs receive enough execution between their release time and deadline to be able to signal completion.

Note that if any job executes for more than its LOcriticality WCET, we do not require any LO-criticality jobs (including those that may have arrived before this happened) to complete by their deadlines. This is an implication of the requirements of certification: informally speaking, the system designer fully expects that all jobs will exhibit LOcriticality behavior, and hence is only concerned that they behave as desired under these circumstances. The CA, on the other hand, allows for the possibility that some jobs may exhibit HI-criticality behavior and requires that all HIcriticality jobs nevertheless meet their deadlines; however, the CA is not concerned with the fate of the LO-criticality jobs. Utilization parameters. The utilization of a (regular, i.e., non-MC) implicit-deadline sporadic task denotes the ratio of its WCET to its period; the utilization of a task system denotes the sum of the utilizations of all the tasks in the system. We now define analogous concepts for mixedcriticality sporadic task systems.

Let τ denote a MC implicit-deadline sporadic task system. For each of x and y in {LO, HI}, we define a utilization parameter as follows:

U y x (τ ) = τ i ∈τ ∧χ i =x Ci(y) Ti (1)
Thus for example, U LO HI (τ ) denotes the sum of the utilizations of the HI-criticality tasks in τ , under the assumption that each job of each task executes for no more than its LO-criticality WCET.

III. AN OVERVIEW OF ALGORITHM EDF-VD

Let τ denote the MC implicit-deadline sporadic task system that is to be scheduled on a unit-speed preemptive processor. Prior to run-time, EDF-VD performs a schedulability test to determine whether τ can be successfully scheduled by it or not. If τ is deemed schedulable, then an additional parameter, which we call a modified period denoted Ti , is computed for each HI-criticality task τ i ∈ τ . The algorithm for computing these parameters is described in pseudo-code form in Figure 1; this pseudo-code is proved correct in Section IV. Observe that it is always the case that Ti ≤ T i .

Run-time scheduling is done according to the Algorithm EDF, with virtual deadlines: deadlines that EDF-VD computes (in a manner to be described below) and assigns to jobs before handing them off to the EDF scheduler. The EDF scheduler will then use these virtual deadlines for the purpose of determining scheduling priority.

These virtual deadlines are assigned as follows. Suppose that a job of task τ i arrives at time-instant t a :

• If χi = LO, then this job is assigned a virtual deadline equal to ta + Ti. • If χi = HI, then this job is assigned a virtual deadline equal to ta + Ti.

If some job does execute beyond its LO-criticality WCET without signaling that it has completed execution, the following changes occur:

Task system τ = {τ1, τ2, . . . τn} to be scheduled on a unit-speed preemptive processor.

1) Compute x as follows:

x ← U LO HI (τ ) 1 -U LO LO (τ )
2) If x U LO LO (τ ) + U HI HI (τ ) ≤ 1 then Ti ← x Ti for each HI-criticality task τi declare success and return else declare failure and return As shown in Figure 1, EDF-VD first computes a parameter x (the reason why x is assigned this value is derived below -see Expression 4) and then assigns values to the Ti parameters for all HI-criticality tasks as follows:

Ti ← x × Ti (2)
Theorem 1: The following condition is sufficient for ensuring that EDF-VD successfully schedules all LO-criticality behaviors of τ :

x ≥ U LO HI (τ ) 1 -U LO LO (τ ) (3)
Proof: If EDF is able to schedule all LO-criticality behaviors of the task system obtained from τ by replacing each HIcriticality task τ i by one with a reduced period, then it follows from the sustainability property [START_REF] Baruah | Sustainable scheduling analysis[END_REF] of preemptive uniprocessor EDF that EDF is able to schedule all LOcriticality behaviors of τ as well. Note that scaling down the period of each HI-criticality task by a factor x is equivalent to inflating its utilization by a factor 1/x. From the utilizationbound result of EDF [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF], we therefore conclude that

U LO LO (τ ) + U LO HI (τ ) x ≤ 1 ⇔ U LO HI (τ ) x ≤ 1 -U LO LO (τ ) ⇔ x ≥ U LO HI (τ ) 1 -U LO LO (τ )
is sufficient for ensuring that EDF-VD successfully schedules all LO-criticality behaviors of τ . Algorithm EDF-VD thus chooses for x the smallest value such that Theorem 1 is satisfied:

x ← U LO HI (τ ) 1 -U LO LO (τ ) (4)
With this value of x, we now determine a sufficient condition for ensuring that EDF-VD successfully meets all HI-criticality deadlines during all HI-criticality behaviors of τ :

Theorem 2: The following condition1 is sufficient for ensuring that EDF-VD successfully schedules all HI-criticality

x + U HI HI (τ ) ≤ 1 (5)
behaviors of τ :

xU LO LO (τ ) + U HI HI (τ ) ≤ 1 (6)
Proof: Suppose that τ satisfies Condition 3 but EDF-VD cannot meet all deadlines in all HI-criticality behaviors of τ . Let I denote a minimal instance of jobs released by τ , on which a deadline is missed. (By minimal, we mean that EDF-VD will meet all deadlines if scheduling any proper subset of I.) Without loss of generality, assume that the earliest jobrelease in I occurs at time zero, and let t f denote the instant of the (first) deadline miss -since τ is assumed to satisfy Condition 3, this must be the deadline of a HI-criticality job, in a HI-criticality behavior. Let t * denote the time-instant at which HI-criticality behavior is first flagged (i.e., the first instant at which some job executes for more than its LOcriticality worst-case execution time without signaling that it has completed execution).

We observe that all jobs in I, except perhaps the one that misses a deadline at t f , experiences some execution; else, the job could be removed from I; this would contradict the assumed minimality of I.

We now introduce some notation for the remainder of this section:

1) For each i, 1 ≤ i ≤ n, let ηi denote the amount of execution over the interval [0, t f ] that is needed by jobs in I that are generated by task τi.

2) For each i, 1 ≤ i ≤ n, let ui(χ) denote the quantity C i (χ)
T i . (That is, ui(LO) denotes τi's LO-criticality utilization, and ui(HI) denotes its HI-criticality utilization).

3) Let J1 denote the job with the earliest release time amongst all those that execute in [t * , t f ). Let a1 denote its release time, and d1 its deadline.

Fact 1: All jobs that execute in [t * , t f ) have deadline ≤ t f . Proof: Suppose not. Consider the latest instant t in [t * , t f ) when a job with deadline > t f executes. Only those jobs in I that have release time ≥ t and deadline ≤ t f are sufficient to cause a deadline miss; this contradicts the assumed minimality of I.

Fact 2:

Any LO-criticality task τ i has ηi ≤ ui(LO) a1 + x(t f -a1) (7)
Proof: No LO-criticality job will execute after t * . For it to execute after a 1 , it must have a deadline no larger than J 1 's virtual deadline, which is (a 1 + x(d 1 -a 1 )). Therefore, no LO-criticality job with deadline > (a 1 + x(t f -a 1 )) will execute after a 1 . Suppose that some LO-criticality job with deadline > (a 1 + x(t f -a 1 )) were to execute, at some time < a 1 . Let t denote the latest instant at which any such job executes. This means that at this instant, there were no jobs with effective Note that U LO LO (τ ) ≤ 1 is a necessary condition for τ to be schedulable. It is evident that any schedulable system satisfying Condition 5 also satisfies Condition 6 while the converse is not true: there are task systems satisfying Condition 6 that violate Condition 5.

deadline ≤ (a 1 + x(t f -a 1 )) awaiting execution. Hence the instance obtained by considering only those jobs in I that have release times ≥ t also misses a deadline; this contradicts the assumed minimality of I.

Fact 3: Any HI-criticality task τ i has

ηi ≤ ui(LO) x a1 + (t f -a1)ui(HI) (8)
Proof: We consider separately the cases when τ i does not have a job with release time ≥ a 1 , and when it does.

Case: If τ i does not release a job at or after a 1 . We claim that each job of τ i has a modified deadline ≤ (a 1 + x(t fa 1 )). To see why this is so, consider some job with a modified deadline > (a 1 + x(t f -a 1 )), and let t denote the latest instant at which this job executes. All jobs in I that have release times ≥ t also miss a deadline; this contradicts the assumed minimality of I.

Since each job has a modified deadline ≤ (a 1 + x(t fa 1 )), their actual deadlines are all ≤ a1

x + (t f -a 1 ). Therefore, their cumulative execution requirement is at most

a1 x ui(LO) + (t f -a1)ui(LO) ≤ a1 x ui(LO) + (t f -a1)ui(HI)
Case: If τ i releases a job at or after a 1 . Let a i denote the first release ≥ a 1 . The cumulative execution requirement of all jobs of τ i is at most Let us sum the cumulative demand of all the tasks over [0, t f ):

χ i =LO ηi + χ i =HI ηi ≤ χ i =LO ui(LO) a1 + x(t f -a1) + χ i =HI a1 x ui(LO) + (t f -a1)ui(HI) = a1 U LO LO (τ ) + U LO HI (τ ) x +(t f -a1)(xU LO LO (τ ) + U HI HI (τ )) ≤ (By choice of x [Eqn. 3], (U LO LO (τ ) + U LO HI (τ ) x ) ≤ 1) a1 + (t f -a1)(xU LO LO (τ ) + U HI HI (τ ))
It follows from the infeasibility of this instance that

a1 + (t f -a1)(xU LO LO (τ ) + U HI HI (τ )) > t f ⇔ (t f -a1)(xU LO LO (τ ) + U HI HI (τ )) > t f -a1 ⇔ xU LO LO (τ ) + U HI HI (τ ) > 1
Taking the contrapositive, it follows that (xU LO LO (τ ) + U HI HI (τ ) ≤ 1) is sufficient to ensure HI-criticality schedulability by EDF-VD, as is claimed in this theorem.

We have thus established the correctness of Algorithm EDF-VD: by Theorem 1 the value assigned to x ensures the correctness of all LO-criticality behaviors whereas Theorem 2 guarantees the correct scheduling of all HIcriticality behaviors. Observation. Note that Theorem 1 requires that x ≥ U LO HI (τ ) 1-U LO LO (τ ) , while Theorem 2 requires that x ≤ 1-U HI HI (τ ) U LO LO (τ ) . When these upper and lower bounds on x are not equal to each other, a pragmatic choice would be to choose a value for x that lies somewhere within the interval (e.g., at the midpoint), rather than at either of the boundaries -this would increase the robustness of the algorithm and its tolerance to, e.g., any arrival jitter.

V. RUN-TIME DISPATCHING

During the execution of the system, jobs are selected for execution according to the following rules:

1) There is a criticality level indicator Γ, initialized to LO. 2) While (Γ ≡ LO), a) Suppose a job of some task τi ∈ τ arrives at time t

• if χi ≡ LO, the job is assigned a scheduling deadline equal to t + Ti. • if χi ≡ HI, the job is assigned a scheduling deadline equal to t + Ti. b) At each instant the waiting job with earliest scheduling deadline is selected for execution (ties broken arbitrarily). c) If the currently-executing job executes for more than its LO-criticality WCET without signaling completion, then the behavior of the system is no longer a LO-criticality behavior, and Γ ← HI. 3) Once (Γ ≡ HI), a) The scheduling deadline of each HI-criticality job that is currently active is changed to its release time plus the unmodified period parameter (the Ti, not the Ti) of the task that generated it. That is, if a job of τi that was released at some time t is active, its deadline, for scheduling purposes, is henceforth t + Ti. b) When a future job of τi arrives at some time t, it is assigned a scheduling deadline equal to t + Ti. c) LO-criticality jobs will not receive any further execution.

Therefore at each instant the earliest-deadline waiting job generated by a HI-criticality task is selected for execution(ties broken arbitrarily). 4) An additional rule could specify the circumstances when Γ gets reset to LO. This could happen, for instance, if no HIcriticality jobs are active at some instant in time. (We will not discuss the process of resetting Γ ← LO any further in this document, since this is not relevant to the certification process -LO-criticality certification assumes that the system never exhibits any HI-criticality behavior, while HI-criticality certification is not interested in the behavior of the LOcriticality tasks.)

A. An efficient implementation of run-time dispatching

For traditional (non-MC) sporadic task systems consisting of n tasks, uniprocessor EDF can be implemented efficiently to have a run-time complexity of O(log n) per event, where an event is either the arrival of a job, or the completion of the execution of a job (see, e.g., [START_REF] Mok | Task management techniques for enforcing ED scheduling on a periodic task set[END_REF]). A direct application of such implementations can be used to obtain an implementation of the run-time dispatching of EDF-VD that has a run-time of O(log n) per job-arrival and job-completion event. However, EDF-VD potentially needs to deal with an additional run-time event: the change in the criticality level of the behavior from LO to HI (this is the event that is triggered at the instant that Γ gets assigned the value HI). Since this event requires that each subsequent scheduling be done according to each HI-criticality task's original deadline, explicitly recomputing priorities according to these original deadlines would take time linear in the number of HIcriticality tasks -in the worst case, O(n) time. We now describe an implementation of EDF-VD's run-time system that has a worst-case run-time of O(log n) per event for all three kinds of events: job arrival, job completion, and change in the criticality level of the behavior from LO to HI.

Recall that a priority queue supports the operations of inserting ("insert") and deleting the smallest item ("deleteMin") in logarithmic time, and the operation of finding the smallest item ("min") in constant time. In addition, the standard priority queue data structure can be enhanced to support the deletion of a specified item (the "delete" operation), also in logarithmic time (see, e.g, [START_REF] Cormen | Introduction to Algorithms[END_REF]Sec. 6.5]). We maintain two such enhance priority queues, Q LO and Q HI . We also use a timer that is used to indicate whether the currently-executing job has executed for more than its LO-criticality WCET (thereby triggering the assignment Γ ← HI).

Initially, Γ ≡ LO and there are three kinds of events to be dealt with: (1) the arrival of a job; (2) the completion of a job; and (3) Γ being assigned the value HI. We consider each separately, below. Suppose that the event occurs at timeinstant t c , and let J c denote the currently-executing job.

1) A job of task τi arrives at time tc.

a) Insert the newly-arrived job into QLO, prioritized according to its modified scheduling deadline. b) If χi = HI (i.e., if it is a HI-criticality job), then also insert it into QHI, prioritized according to its unmodified (i.e., actual) scheduling deadline. c) If Jc is no longer the minimum job in QLO, it must be the case that the newly-arrived job has an earlier modified deadline than Jc's modified deadline. In that case, the newly-inserted job becomes Jc, and the timer is set to go off at tc + Ci(LO) (when this newly-inserted job would exceed its LO-criticality WCET if allowed to execute without interruption).

2) The currently-executing job Jc completes execution at time tc. a) Delete this job from QLO, using the deleteMin operation supported by priority queue implementations. b) If it was a HI-criticality job, also delete it from QHI -this would be accomplished by a delete operation. c) Set the current-job indicator Jc to denote the new minimum (modified) deadline job -the "minimum" job in QLO; and set the timer to go off at tc+ this job's remaining LO-criticality WCET (when the job would exceed its LOcriticality WCET if allowed to execute without interruption).

3) The timer goes off, indicating that the currently-executing job has executed beyond its LO-criticality WCET without signaling completion. The system is therefore now in HIcriticality mode, and we switch to scheduling according to QHI. Henceforth, all run-time dispatch decisions are taken as indicated by this priority queue.

After Γ becomes HI, no LO-criticality jobs need execute, and HI-criticality jobs are executed according to EDF with their original (unmodified) deadlines. Hence subsequent runtime dispatching is done as for traditional EDF scheduling (as described in, e.g., [START_REF] Mok | Task management techniques for enforcing ED scheduling on a periodic task set[END_REF]), with Q HI being the priority queue used for this purpose.

VI. SOME PROPERTIES OF EDF-VD

A. Comparison with worst-case reservations

Under the worst-case reservations strategy that is widely used in the design of mixed-criticality systems, computing capacity is provisioned to each task at its own criticality level. That is, the MC task system τ is mapped on to the traditional (non-MC) task system τ i ∈τ Ci(χi), Ti and scheduled using regular EDF. It directly follows from the utilization-bound result of EDF [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF] that the condition

U LO LO (τ ) + U HI HI (τ ) ≤ 1 (9)
is necessary and sufficient for ensuring that EDF can schedule τ to meet all deadlines, provided each LO-criticality job executes for up to its LO-criticality WCET and each HIcriticality job executes for up to its HI-criticality WCET. This covers all LO-criticality and all HI-criticality behaviors of τ .

We now show that Algorithm EDF-VD strictly dominates the worst-case reservations approach: any task system that can be scheduled using worst-case reservations can be scheduled by EDF-VD.

Theorem 3: Any task system τ that is correctly scheduled using worst-case reservations is also correctly scheduled by EDF-VD. Proof: Any task system that can be scheduled using worstcase reservations satisfies Condition 9 above.

U LO LO (τ ) + U HI HI (τ ) ≤ 1 ⇒ (Since U LO HI (τ ) ≤ U HI HI (τ )) U LO LO (τ ) + U LO HI (τ ) ≤ 1 ⇒ U LO HI (τ ) 1 -U LO LO (τ ) ≤ 1
From this and Equation 4, we conclude that x is assigned a value ≤ 1 by Algorithm EDF-VD. Now, Theorem 2 contains the following sufficient condition for EDF-VD schedulability:

xU LO LO (τ ) + U HI HI (τ ) ≤ 1 ,
which always holds since Condition 9 holds and x ≤ 1.

B. Task systems τ with U LO HI (τ ) = 0 It is interesting to analyze the manner in which EDF-VD deals with task systems in which the LO-criticality WCET of each HI-criticality task is equal to zero. (This would be the case for systems in which a "mode change" can be thought to occur when the high-criticality behavior is triggered.) For such a system τ , observe that U LO HI (τ ) = 0. Therefore, the value assigned to the scaling parameter x in Step 1 of Figure 1 is equal to zero, and the test in Step 2 of Figure 1 evaluates to true to all τ with U HI HI (τ ) ≤ 1. Thus EDF-VD can schedule any task system for which U LO HI (τ ) = 0 that satisfies the condition

U LO LO (τ ) ≤ 1 and U HI HI (τ ) ≤ 1 .
I.e., EDF-VD can schedule any such system provided the LO-criticality and the HI-criticality behaviors are separately schedulable.

Continuing to analyze the pseudo-code in Figure 1 for this special case, we observe that EDF-VD assigns each HIcriticality task τ i a modified period Ti equal to zero. Thus during run-time each job of a HI-criticality task immediately becomes an earliest-deadline (and hence highest-priority) one upon arrival. If it is discovered to have a non-zero execution time, the criticality-level indicator is immediately assigned the value HI (i.e., Γ ← HI), and all LO-criticality jobs are immediately discarded.

VII. SPEEDUP BOUNDS

The speedup factor of an algorithm A for scheduling mixed-criticality systems is defined to be the smallest real number f such that any task system τ that is schedulable on a unit-speed processor by a hypothetical optimal clairvoyant2 algorithm is successfully scheduled on a speed-f processor by algorithm A. The speedup factor is a convenient metric for comparing the worst-case behavior of different algorithms for solving the same problem: the smaller the speedup factor, the closer the behavior of the algorithm to that of a clairvoyant optimal algorithm.

Theorem 4: The speedup factor of EDF-VD is ≤ 4 3 . Proof: To prove this theorem, we will show that any MC implicit-deadline sporadic task system that is clairvoyantly schedulable on a speed- 3 4 processor is schedulable by EDF-VD on a unit-speed processor.

Let b denote an upper bound on both the LO-criticality utilization and the HI-criticality utilization of task system τ :

b ≥ max U LO LO (τ ) + U LO HI (τ ), U HI HI (τ ) (10)
By Theorems 1 and 2, we know that if an x satisfying both theorems exists, there will be no deadline miss. Since Theorem 1 requires that

U LO HI (τ ) 1 -U LO LO (τ ) ≤ x
while Theorem 2 requires that

x ≤ 1 -U HI HI (τ ) U LO LO (τ )
, we can derive Expression 11 below as a sufficient condition for τ to be successfully scheduled using EDF-VD:

U LO HI (τ ) 1 -U LO LO (τ ) ≤ 1 -U HI HI (τ ) U LO LO (τ ) ⇐ (Since U LO LO (τ ) + U LO HI (τ ) ≤ b ⇒ U LO HI (τ ) ≤ b -U LO LO (τ )) b -U LO LO (τ ) 1 -U LO LO (τ ) ≤ 1 -U HI HI (τ ) U LO LO (τ ) ⇐ (Since U HI HI (τ ) ≤ b) b -U LO LO (τ ) 1 -U LO LO (τ ) ≤ 1 -b U LO LO (τ ) ⇔ U LO LO (τ ) 2 -U LO LO (τ ) + (1 -b) ≥ 0 (11)
Now if we set b ← 3 4 , Expression 11 becomes

U LO LO (τ ) 2 -U LO LO (τ ) + 1 4 ≥ 0 ⇔ U LO LO (τ ) - 1 2 2 ≥ 0
which is true for all values of U LO LO (τ ). We have thus shown that any task system that is clairvoyant schedulable on a speed- 3 4 processor is scheduled by EDF-VD to meet all deadlines on a unit-speed processor. It therefore follows that any task system that is clairvoyant schedulable on a unit-speed processor is scheduled by EDF-VD to meet all deadlines on a speed- 4 3 processor, as claimed by this theorem.

We now show that EDF-VD is optimal with regard to speedup factor:

Theorem 5: No non-clairvoyant algorithm for scheduling dual-criticality implicit-deadline sporadic task systems can have a speedup bound better than 4 3 . Proof: Consider the example task system τ = {τ 1 , τ 2 }, with the following parameters, where is an arbitrarily small number > 0:

τi χi Ci(LO) Ci(HI) Ti τ1 LO 1 + 1 + 2 τ2 HI 1 + 3 4
This system is schedulable by a clairvoyant scheduler: EDF would meet all deadlines in LO-criticality behaviors (since U LO LO (τ ) + U LO HI (τ ) ≤ 1), while only jobs of τ 2 would get to execute in HI-criticality behaviors.

To see that τ cannot be scheduled correctly by an online scheduler, suppose both tasks were to generate jobs simultaneously. It need not be revealed prior to one of the jobs receiving (1 + ) units of execution, whether the behavior is a LO-criticality or a HI-criticality one. We consider two cases.

1) τ1's job receives (1 + ) units of execution before τ2's job does. In this case, the behavior is revealed to be a HI-criticality one. But now there is not enough time remaining for τ2's job to complete by its deadline at time-instant 4. 2) τ2's job receives (1 + ) units of execution before τ1's job does. In this case, the behavior is revealed to be a LOcriticality one, in that τ2's job signals that it has completed execution. But there is not enough time remaining for τ1's job to complete by its deadline at time 2.

We have thus shown that no non-clairvoyant algorithm can correctly schedule τ . The theorem follows, based on the observation that max U LO LO (τ ) + U LO HI (τ ), U HI HI (τ ) exceeds 3/4 by an arbitrarily small amount.

VIII. UTILIZATION BOUNDS

It is evident that in order for task system τ to be schedulable by any algorithm on a unit-speed processor, it is necessary that both U LO LO (τ ) + U LO HI (τ ) ≤ 1, and

U HI HI (τ ) ≤ 1.
We now derive sufficient conditions on U LO LO (τ ), U LO HI (τ ) and U HI HI (τ ) for the system to be successfully scheduled by EDF-VD.

As we had observed in Section VII above, it follows from Theorems 1 and 2 that if an x satisfying both theorems exists, then EDF-VD will schedule the system correctly. Since Theorem 1 requires that

U LO HI (τ ) 1 -U LO LO (τ ) ≤ x
while Theorem 2 requires that

x ≤ 1 -U HI HI (τ ) U LO LO (τ ) ,
we have

U LO HI (τ ) 1 -U LO LO (τ ) ≤ 1 -U HI HI (τ ) U LO LO (τ ) ⇔ U LO LO (τ ) + U HI HI (τ ) -U LO LO (τ ) U HI HI (τ ) -U LO HI (τ ) ≤ 1 ⇔ U HI HI (τ ) 1 -U LO LO (τ ) ≤ 1 -U LO LO (τ ) -U LO LO (τ )U LO HI (τ ) ⇔ U HI HI (τ ) ≤ 1 -U LO LO (τ ) -U LO LO (τ )U LO HI (τ ) 1 -U LO LO (τ ) ⇔ U HI HI (τ ) ≤ 1 -U LO HI (τ ) U LO LO (τ ) 1 -U LO LO (τ ) (12)
as a sufficient condition for τ to be schedulable by EDF-VD. In Table I

IX. EVALUATION VIA SIMULATION

We have conducted a series of simulation experiments to evaluate the effectiveness of EDF-VD in finding certifiably correct scheduling strategies. Our experiments were conducted upon randomly-generated task systems that were generated according to (a slight modification of) the workloadgeneration algorithm introduced by Guan et al. [START_REF] Guan | Improving the scheduling of certifiable mixed criticality sporadic task systems[END_REF]. The input parameters for our workload generation algorithm are as follows:

• U bound : The desired value of the larger of LO-criticality and HI-criticality utilization of the task system:

max U LO LO (τ ) + U LO HI (τ ), U HI HI (τ ) = U bound (13)
• [UL, UU ]: Utilizations are uniformly drawn from this range;

0 ≤ UL ≤ UU ≤ 1. • [ZL, ZU ]:
The ratio of the HI-criticality utilization of a task to its LO-criticality utilization is uniformly drawn from this range; 1 ≤ ZL ≤ ZU . • P : The probability that a task is a HI-criticality task; 0 ≤ P ≤ 1.

Gives these parameters, the task-generation algorithm initializes the task system τ to be empty and repeatedly adds tasks τ i , i = 1, 2, . . ., until the utilization bound is met. (For further detail please see [START_REF] Guan | Improving the scheduling of certifiable mixed criticality sporadic task systems[END_REF].)

In our experiments, we determined the fraction of randomly-generated task systems that are deemed to be schedulable by the algorithm under consideration, as a function of the system utilization U bound . Some of our results are depicted graphically in Figures 2345. In each 0 . 4 0 0 . 4 5 0 . 5 0 0 . 5 5 0 . 6 0 0 . 6 5 0 . 7 0 0 . 7 5 0 . 8 0 0 . 8 5 0 . 9 0 0 . graph, the fraction of systems that were determined to be schedulable is depicted on the y-axis, and the utilization on the x-axis. Each data-point was obtained by randomly generating 1000 task systems, testing each for schedulability according to the appropriate algorithm, and calculating the fraction of systems deemed schedulable. The parameters used in generating these task systems (other than the system utilization, which is depicted on the x-axis) are provided in the caption of the graph; e.g., the task systems for Figure 2 were generated using the parameters U L = 0.02, U U = 0.2, Z L = 1, Z U = 2, and P = 0.5. For each set of parameters, two different algorithms were compared: regular EDF (i.e., EDF on the task system i {(C i (χ i ), T i )})this is the "worst-case reservations" strategy discussed in VI); and Algorithm EDF-VD (as depicted in Figure 1).

It is evident from the graphs that EDF-VD consistently exhibits noticeable improvement over a simple EDF scheduler. We do not seek to make quantitative claims about the degree of such improvement based on simulation data, but we do notice some trends.

1) When the system utilization is smaller than 0.5, the task system is always schedulable by worst-case reservations (regular EDF); when the system utilization is smaller than 0.75, the task system is always schedulable by EDF-VD. These observation match the known utilization bounds.

2) The improvement becomes more significant as the ratio of 0 . 4 0 0 . 4 5 0 . 5 0 0 . 5 5 0 . 6 0 0 . 6 5 0 . 7 0 0 . 7 5 0 . 8 0 0 . 8 5 0 . 9 0 0 . the HI-criticality WCET to LO-criticality WCET increases (compare Figures 234). The intuitive explanation for this is that EDF-VD takes more advantage from processing LOcriticality and HI-criticality behaviors separately when the LOcriticality and HI-criticality behaviors overlap less.

3) For a similar reason, the improvement becomes more pronounced as the ratio of the HI-criticality utilization (U HI HI (τ )) to the LO-criticality utilization (U LO LO (τ )+U LO HI (τ )) approaches 1 (compare Figures 4-??, in which the ratios are respectively 1.6, 1.06 and 0.34).

X. SUMMARY AND CONCLUSIONS

Devising more cost-efficient techniques for obtaining certication for safety-critical embedded systems has been identified as a prime research challenge [START_REF] Barhorst | White paper: A research agenda for mixed-criticality systems[END_REF]. We believe that in mixed-criticality systems, these certication considerations give rise to fundamental new resource allocation and scheduling challenges that are not adequately addressed by conventional real-time scheduling theory. In this paper, we consider the scheduling, upon preemptive uniprocessors, of mixed-criticality systems that can be modeled using a mixedcriticality generalization of the implicit-deadline sporadic tasks model. An algorithm called EDF-VD was proposed in [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF] for scheduling such systems. We have proved that EDF-VD is speedup-optimal by showing that (i) it has a processor speedup factor equal to 4/3 (Theorem 4); and

(ii) no non-clairvoyant algorithm can have a smaller speedup factor (Theorem 5). The result in Theorem 4 improves on an earlier result presented in [START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF], which had shown a speedup factor of ( √ 5 + 1)/2 ≈ 1.62. This improved speedup factor was obtained by first deriving a superior sufficient schedulability condition (Theorem 2); this sufficient schedulability condition strictly dominates earlier sufficient schedulability tests in that any task system deemed schedulable by these earlier tests is also deemed schedulable by the test of Theorem 2 while the converse of this statement is not true.

As further contributions, we have shown how EDF-VD can be implemented to have a run-time complexity per scheduling decision that is logarithmic in the number of tasks, and thus demonstrated the practical applicability of the algorithm. We have explored further properties of EDF-VD, and have conducted extensive simulation experiments to reveal its behavior on randomly-generated task systems.

Figure 1 .

 1 Figure 1. EDF-VD: The preprocessing phase.

  aiui(LO) + (t f -ai)ui(HI)≤ (Since a1 ≤ ai and ui(LO) ≤ ui(HI)) a1ui(LO) + (t f -a1)ui(HI) ≤ (Since x ≤ 1) a1 x ui(LO) + (t f -a1)ui(HI)

Figure 2 . 5 0Figure 3 .

 253 Figure 2. U L = 0.02, U U = 0.2, Z L = 1, Z U = 2, P = 0.5

Figure 4 . 5 0Figure 5 .

 455 Figure 4. U L = 0.02, U U = 0.2, Z L = 1, Z U = 8, P = 0.5

  we list this upper bound on U HI HI (τ ) for task systems τ with specified U LO LO (τ ) and U LO HI (τ ). Since the schedulability of LO-criticality behaviors of τ requires that U LO LO (τ )+U LO HI (τ ) ≤ 1, bounds are only computed when this condition is satisfied. We note that the model assumption that C i (LO) ≤ C i (HI) for all tasks mandates that U LO HI (τ ) ≤ U HI HI (τ ); thus the range of values that U HI HI (τ ) may take for given values of U LO LO (τ ) and U LO HI (τ ) is bounded from below by the value of U LO HI (τ ), and from above by the table entry (as computed according to Expression 12). Hence for example if we have a system τ with U LO LO (τ ) = 0.6 and U LO HI (τ ) = 0.2, then U HI HI (τ ) may take on any value in [0.2, 0.7] (this entry is highlighted in bold font in Table I).

1) All currently-active LO-criticality jobs are immediately discarded; henceforth, no LO-criticality job will receive any execution. 2) Subsequent run-time scheduling of the HI-criticality tasks (including their jobs that are currently active) continue to be done according to EDF. But the actual job deadlines (arrival time plus period) are used.IV. PRE-RUNTIME PROCESSINGWe now provide a detailed description of the pre-runtime processing conducted by EDF-VD. We describe, and prove correct, the strategy used to determine whether a system is schedulable, and for computing the modified period parameters (the Tk 's) for systems deemed schedulable. This is also represented in pseudo-code form in Figure1.

We note here that this theorem is one of the reasons that the results presented in this paper dominate the ones in[START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF]; the corresponding condition derived in[START_REF] Baruah | Mixed-criticality scheduling of sporadic task systems[END_REF] is

Informally, a clairvoyant algorithm for scheduling MC systems is one that knows prior to run-time whether the system is going to exhibit LOcriticality or HI-criticality behavior.


D ' Gianlorenzo
email: gianlorenzo.dangelo@inria.fr

Angelo

Mattia D'emidio
email: mattia.demidio@univaq.it

Daniele Frigioni
email: daniele.frigioni@univaq.it

Vinicio Maurizio
email: vinicio.maurizio@cc.univaq.it

Engineering a new loop-free shortest paths routing algorithm ⋆

We present LFR (Loop Free Routing), a new loop-free distance vector routing algorithm, which is able to update the shortest paths of a distributed network with n nodes in fully dynamic scenarios. If Φ is the total number of nodes affected by a set of updates to the network, and φ is the maximum number of destinations for which a node is affected, then LFR requires O(Φ • ∆) messages and O(n + φ • ∆) space per node, where ∆ is the maximum degree of the nodes of the network. We experimentally compare LFR with DUAL, one of the most popular loop-free distance vector algorithms, which is part of CISCO's EIGRP protocol and requires O(Φ • ∆) messages and Θ(n • ∆) space per node. The experiments are based on both real-world and artificial instances and show that LFR is always the best choice in terms of memory requirements, while in terms of messages LFR outperforms DUAL on real-world instances, whereas DUAL is the best choice on artificial instances.

Introduction

Updating shortest paths in a distributed network whose topology dynamically changes over the time is considered crucial in today's communication networks. This problem has been widely studied in the literature, and the solutions found can be classified as distance-vector and link-state.

Distance-vector algorithms require that a node knows the distance from each of its neighbors to every destination and stores them in a data structure called routing table; a node uses its own routing table to compute the distance and the next node in the shortest path to each destination. Most of the known distancevector solutions (e.g., see [START_REF] Cicerone | A fully dynamic algorithm for distributed shortest paths[END_REF][START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF][START_REF] Humblet | Another adaptive distributed shortest path algorithm[END_REF][START_REF] Orda | Distributed shortest-path and minimum-delay protocols in networks with time-dependent edge-length[END_REF][START_REF] Ramarao | On finding and updating shortest paths distributively[END_REF]) are based on the classical Distributed Bellman-Ford method (DBF), originally introduced in the Arpanet [START_REF] Mcquillan | Adaptive routing algorithms for distributed computer networks[END_REF], which is implemented in the RIP protocol. The convergence of DBF can be very slow (possibly infinite) due to the well-known looping phenomenon which occurs when a path induced by the routing table entries visits the same node more than once before reaching the intended destination. Furthermore, if the nodes of the network are not synchronized, even though no change occurs in the network, the overall number of messages sent by DBF is exponential in the size of the network (e.g., see [START_REF] Awerbuch | Approximate distributed bellman-ford algorithms[END_REF]).

Link-state algorithms, as for example the Open Shortest Path First (OSPF) protocol widely used in the Internet (e.g., see [START_REF] Moy | OSPF: Anatomy of an Internet routing protocol[END_REF]), require that a node must know the entire network topology to compute its distance to any destination, usually running the centralized Dijkstra's algorithm. Link-state algorithms are free of looping, but each node needs to receive and store up-to-date information on the entire network topology after a change, thus requiring quadratic space per node. This is achieved by broadcasting each change of the network topology to all nodes [START_REF] Moy | OSPF: Anatomy of an Internet routing protocol[END_REF][START_REF] Rosen | The updating protocol of arpanet's new routing algorithm[END_REF] and by using a centralized algorithm for shortest paths.

Related works. In the last years, there has been a renewed interest in devising new efficient light-weight loop-free distributed shortest paths solutions for largescale Ethernet networks (see, e.g., [START_REF] Cicerone | Partially dynamic efficient algorithms for distributed shortest paths[END_REF][START_REF] D'angelo | A speed-up technique for distributed shortest paths computation[END_REF][START_REF] Elmeleegy | On count-to-infinity induced forwarding loops in ethernet networks[END_REF][START_REF] Ray | Always acyclic distributed path computation[END_REF][START_REF] Yao | Rd: Reducing message overhead in DUAL[END_REF][START_REF] Zhao | A more efficient diffusing update algorithm for loop-free routing[END_REF]), where usually the routing devices have limited storage capabilities, and hence distance-vector algorithms seem to be an attractive alternative to link-state solutions. For example, in [START_REF] Ray | Always acyclic distributed path computation[END_REF] a new technique has been introduced, named DIV, which is not a routing algorithm by itself, rather it can run on top of any routing algorithm to guarantee loop freedom. A distance vector algorithm has been recently introduced in [START_REF] Cicerone | A new fully dynamic algorithm for distributed shortest paths and its experimental evaluation[END_REF] and successively developed in [START_REF] Cicerone | Engineering a new algorithm for distributed shortest paths on dynamic networks[END_REF], where it has been named DUST (Distributed Update of Shortest paThs), which suffers of looping, although it has been designed to heuristically reduce the cases where this phenomenon occurs.

Despite the renewed interest of the last years, the most important distance vector algorithm in the literature is surely DUAL (Diffuse Update ALgorithm) [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF], which is free of looping and is indeed part of CISCO's widely used EIGRP protocol. DUAL has been experimentally tested in [START_REF] Cicerone | Engineering a new algorithm for distributed shortest paths on dynamic networks[END_REF] against DUST and DBF in various artificial and real-world scenarios. It has been shown that DUST is always the best choice in terms of space per node. In terms of messages, DUST is the best choice on those real-world topologies in which it does not fall in looping, while DUAL is better than DUST and DBF in all other cases.

Results of the paper. We propose a new loop-free distance vector algorithm, named LFR (Loop Free Routing), which is able to update the shortest paths of a distributed network subject to arbitrary modifications on the edges of the network. Let us denote by n the number of nodes in the network, by ∆ the maximum node degree, by Φ the number of nodes affected by a sequence of updates on the edges of the network, that is the nodes changing their routing table during that sequence, and by φ the maximum number of destinations for which a node is affected. Then LFR requires O(Φ • ∆) messages and O(Φ) steps to converge and requires O(n + φ • ∆) space per node. Compared with DUAL, LFR sends the same number of messages but requires less memory per node. In fact, DUAL requires O(Φ • ∆) messages and O(Φ) steps to converge and Θ(n • ∆) space per node. Compared with DUST, LFR is better in terms of both number of messages sent and memory requirement per node. In fact, the number of messages sent by DUST cannot be bounded, as it suffers of looping, and its space requirement per node is O(n • ∆).

From the experimental point of view, we conducted an extensive study with the aim of comparing the performances of the loop-free algorithms LFR and DUAL also in practical cases. Our simulations were performed in the OM-NeT++ simulation environment [START_REF] Omnet++ | Discrete event simulation environment[END_REF]. As input to the algorithms, we used both real-world and artificial networks. In detail, we considered some of the Internet topologies of the CAIDA IPv4 topology dataset [START_REF] Hyun | The CAIDA IPv4 routed/24 topology dataset[END_REF] (CAIDA -Cooperative Association for Internet Data Analysis provides data and tools for the analysis of the Internet infrastructure) and Erdös-Rényi random graphs [START_REF] Bollobás | Random Graphs[END_REF]. The results of our experiments can be summarized as follows: in real-world networks LFR outperforms DUAL in terms of both number of messages and space occupancy per node. In the experiments, we observe that this is in part due to the topological structure of the CAIDA instances which are sparse and contain a high number of nodes of small degree. Therefore, we considered also Erdös-Rényi random instances with a variable degree of density. In this case, DUAL sends a number of messages smaller than that of LFR. However, the space requirements of DUAL grow drastically in these random networks while that of LFR are the same of real-word networks. Since CAIDA instances used in the experiments follow a power-law node degree distribution, we embedded the two algorithms in DLP (Distributed Leaf Pruning), a general framework recently proposed in [START_REF] D'angelo | A speed-up technique for distributed shortest paths computation[END_REF] which can run on top of any routing algorithm and is able to reduce the number of messages sent by such algorithms in this kind of graphs. These further experiments show that the good performances of LFR in real-world instances improve when it is used in combination with DLP.

Preliminaries

We consider a network made of processors linked through communication channels that exchange data using a message passing model, in which: each processor can send messages only to its neighbors; messages are delivered to their destination within a finite delay but they might be delivered out of order; there is no shared memory among the nodes; the system is asynchronous, that is, a sender of a message does not wait for the receiver to be ready to receive the message. Graph notation. We represent the network by an undirected weighted graph G = (V, E, w), where V is a finite set of n nodes, one for each processor, E is a finite set of m edges, one for each communication channel, and w is a weight function w : E → R + ∪ {∞} on the edges. An edge in E that links nodes u and v is denoted as {u, v}. Given v ∈ V , N (v) denotes the set of neighbors of v. A shortest path between nodes u and v is a path from u to v with the minimum weight. The distance d(u, v) from u to v is the weight of a shortest path from u to v. Given two nodes u, v ∈ V , the via from u to v is the set of neighbors of u that belong to a shortest path from u to v. Formally:

via(u, v) ≡ {z ∈ N (u) | d(u, v) = w(u, z) + d(z, v)}.
We denote as w t (), d t () and via t () an edge weight, a distance and a via in G at time instant t, respectively. We denote a sequence of update operations on the edges of G by C = (c 1 , c 2 , ..., c k ). Assuming G 0 ≡ G, we denote as G i , 0 ≤ i ≤ k, the graph obtained by applying c i to G i-1 . We consider the case in which c i occurs at time t i ≥ t i-1 and either increases or decreases the weight of {x i , y i } by a quantity ǫ i > 0. The extension to delete and insert operations is straightforward. In what follows, given a sequence C = (c 1 , c 2 , ..., c k ) of update operations, we denote as φ ci,s the set of nodes that change the distance or the via to s as a consequence of c i , formally:

Procedure: Update(u, s, Du[s]) Input: Node v receives the message update(u, s, Du[s]) from u if STATEv[s] = f alse then if Dv[s] > Du[s] + w(u, v) then Decrease(u, s, Du[s]); else if Dv[s] < Du[s] + w(u, v) then Increase(u, s, Du[s]);
φ ci,s = {v ∈ V | d ti (v, s) = d ti-1 (v, s) or via ti (v, s) = via ti-1 (v, s)}. If v ∈ ∪ k i=1 ∪ s∈V φ ci,s we say that v is affected by c i . We denote as Φ = k i=1
s∈V |φ ci,s |. Furthermore, given a generic destination s in V , we denote as φ s = ∪ k i=1 φ ci,s and by φ = max s |φ s |. Note that a node can be affected for at most φ different destinations. Conditions for loop freedom. A distance vector algorithm can be designed to be loop-free by using sufficient conditions as for example those described in [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF]. In particular, we focus on snc (Source Node Condition), which can be implemented and work in combination with a distance vector algorithm that maintains at least the routing table and the so-called topology table. The routing table of a node v has two entries for each s ∈ V : the estimated distance D v [s] between v and s in G; the node VIA v [s] ∈ via(v, s) representing the via from v to s in G. We denote as D v [s](t) and VIA v [s](t) the estimated distance, and the estimated via at a certain time t. The topology table of v has to contain enough information for v to compute, for each u ∈ N (v) and for each s ∈ V , the quantity D u [s]. These values are used in snc to determine whether a path is free of loops as follows: if, at time t, v needs to change VIA v [s] for some s ∈ V , it can select as VIA v [s](t) any neighbor k ∈ N (v) satisfying the following loop-free test:

D k [s](t) + w t (v, k) = min vi∈N (v) {D vi [s](t) + w t (v i , v)} and D k [s](t) < D v [s](t). If no such neighbor exists, then VIA v [s] does not change. Let VIA G [s](t) be the directed subgraph of G induced by the set VIA v [s](t), for each v ∈ V . In [9] it is proved that if VIA G [s](t 0
) is loop-free and snc is used when nodes change their via, then VIA G [s](t) remains loop-free, for each time t ≥ t 0 .

The new algorithm

In this section, we describe LFR which consists of four procedures named Update, Decrease, Increase and SendFeasibleDist, which are reported in Fig.

[u][s] contains UD u [s], for each u ∈ N (v)
, and hence tempD v requires ∆ space per node for each source for which v is active. The number of nodes for which v is active is at most φ, thus giving an O(n + φ • ∆) bound for the space requirement per node, which is better than DUAL. In Section 4 we will show that also in real practical cases the space per node needed by LFR is always smaller than that of DUAL. Description of LFR. Before LFR starts, at time t < t 1 , we assume that,

for each v, s ∈ V , D v [s](t) and VIA v [s](t) are correct, that is D v [s](t) = d t (v, s)
and VIA v [s](t) ∈ via t (v, s). We focus the description on a source s ∈ V and we assume that each node v ∈ V , at time t, is passive wrt s. The algorithm starts when the weight of an edge {x i , y i } changes. As a consequence, x i (y i resp.) sends to y i (x i resp.) message update(x i , s, D xi [s]) (update(y i , s, D yi [s]) resp.). Messages received at a node wrt a source s are stored in a queue and processed in a FIFO order to guarantee mutual exclusion. If an arbitrary node v receives update(u, s, D u [s]) from u ∈ N (v), then it performs procedure Update in Fig. 1. Basically, Update compares D v [s] with D u [s] + w(u, v) to determine whether v needs to update its estimated distance and its estimated via to s. If node v is active, the processing of the message is postponed by enqueueing it into the FIFO queue associated to s.

Otherwise, if D v [s] > D u [s] + w(u, v) (Line 2), then v performs procedure Decrease, while if D v [s] < D u [s] + w(u, v) (Line 3) v performs procedure Increase. Finally, if node v is passive and D v [s] = D u [s] + w(u, v)
then there is more than one shortest path from v to s. In this case the message is discarded and the procedure ends.

When a node v performs procedure Decrease, it simply updates D, UD and VIA by using the updated information provided by u. Then, the update is forwarded to all neighbors of v with the exception of VIA v [s] (Line 3).

When a node v performs procedure Increase, it first verifies whether the update has been received from VIA v [s] or not (Line 1). In fact, only in the affirmative case v changes its distance to s and needs to find a new via. To this all the neighbors of k. If the Local-Computation does not succeed, that is the snc is violated, then node k initiates the Global-Computation (Lines 11-14), which involves in the worst case all nodes of the network. At this point k has surely found an estimated distance to s which is guaranteed to be loop-free and hence, differently from Increase, it sends this value to its current via v (Line 15) as answer to the get.feasible.dist message. Now, as in procedure Increase, node k can deallocate tempD v , update its local data structures D v [s], UD v [s] and VIA v [s], and propagate the change by sending update messages to all its neighbors (Lines 15-19). Finally, v turns back in passive state.

Differently from the get.dist case, k immediately replies with

UD k [s] only if VIA k [s] = v or STATE v [s] = f alse (Line 25). If VIA k [s] = v,
that is k does not use v to reach s, and k is active with respect to s, then it updates tempD k [v][s] with the received most recent value (Line 24) before sending to v the distance to s through its current via. This is done to send to v the most up to date value.

The next theorems, whose proofs will be given in the full paper, show the loop-freedom, correctness, and complexity of LFR. As highlighted in [START_REF] Garcia-Lunes-Aceves | Loop-free routing using diffusing computations[END_REF], the complexity of a distributed algorithm in the asynchronous model depends on the time needed by processors to execute the local procedures of the algorithm and on the delays incurred in the communication among nodes. Moreover, these parameters influence the scheduling of the distributed computation and hence the number of messages sent. For these reasons, we consider the realistic case where the weight of an edge models the time needed to traverse such edge and all the processors require one unit of time to process a procedure. In this way, the distance between two nodes models the minimum time that such nodes need to communicate. We then measure the time complexity by the number of times that a processor performs a procedure. Note that, in the realistic case, DUAL has the same worst case complexity of LFR.

Theorem 1 (Loop-Freedom). Let s be a node in G and let C = (c 1 , c 2 , ..., c k ) be a sequence of edge weight changes on

G, if VIA G [s](t 0 ) is loop-free, then VIA G [s](t) is loop-free for each t ≥ t 0 .
Theorem 2 (Correctness). There exists a time t F ≥ t k such that, for each pair of nodes v, s ∈ V , and for each time

t ≥ t F , D v [s](t) = d t k (v, s) and VIA t [v, s] ∈ via t k (v, s).

Experimental analysis

In this section, we report the results of our experimental study on LFR and DUAL. Our experiments have been performed on a workstation equipped with a Quad-core 3.60 GHz Intel Xeon X5687 processor, with 12MB of internal cache and 24 GB of main memory, and consist of simulations within the OMNeT++ 4.0p1 environment [START_REF] Omnet++ | Discrete event simulation environment[END_REF]. The program has been compiled with GNU g++ compiler 4.4.3 under Linux (Kernel 2.6.32).

Executed tests.

For the experiments we used both the real-world instances of the CAIDA IPv4 topology dataset [START_REF] Hyun | The CAIDA IPv4 routed/24 topology dataset[END_REF] and Erdős-Rényi random graphs [START_REF] Bollobás | Random Graphs[END_REF]. CAIDA is an association which provides data and tools for the analysis of the Internet infrastructure. We parsed the files in the CAIDA dataset to obtain a weighted undirected graph G IP where nodes represent routers, edges represent links among routers and weights are given by Round Trip Times (RTT). As the graph G IP consists of almost 35000 nodes, we cannot use it for the experiments, due to the memory requirements of DUAL. Hence, we performed our tests on connected subgraphs of G IP , with a variable number of nodes and edges, induced by the settled nodes of a breadth first search starting from a node taken at random. We generated a set of different tests, each consisting of a dynamic graph characterized by a subgraph of G IP with n ∈ {1200, 5000, 8000} nodes (we denote an n nodes subgraph of G IP with G IP -n ) and a set of k concurrent edge updates, where k assumes values in {5, 10, . . . , 200}. An edge update consists of multiplying the weight of a random selected edge by a value randomly chosen in [0.5, 1.5]. For each test configuration (a dynamic graph with a fixed value of k) we performed 5 different experiments and we report average values. We performed the experiments in the realistic case, that is we considered the RTT as the time delay for receiving packets.

Graphs G IP turns out to be very sparse (i.e., m/n ≈ 1.3), so it is worth analyzing LFR and DUAL also on graphs denser than G IP . To this aim we considered Erdős-Rényi random graphs [START_REF] Bollobás | Random Graphs[END_REF]. In detail, we randomly generated a set of different tests, where a test consists of a dynamic graph characterized by: an Erdős-Rényi random graph G ER of 2000 nodes; the density dens of the graph, computed as the ratio between m and the number of the edges of the ncomplete graph; and the number k of edge update operations. We chose different values of dens in [0.01, 0.61] and k = 200. Edge weights are randomly chosen in [START_REF] Awerbuch | Approximate distributed bellman-ford algorithms[END_REF]10000]. Edge updates are randomly chosen as in the CAIDA tests. For each test configuration, we performed 5 different experiments and we report average values. As in G IP , time delays are equal to the edge weights. Analysis. In Fig. 5 we report the number of messages sent by LFR and DUAL on G IP -8000 . The diagram shows that LFR always outperforms DUAL. The ratio between the number of messages sent by DUAL and LFR is between 2.02 and 7.61. The results of our experiments on G IP -1200 and G IP -5000 give similar results. These good performances of LFR are due in part to the topological structure of G IP in which the average node degree is almost one. In fact, LFR uses get.dist messages in order to know the estimated distances of its neighbors. It follows that the number of get.dist messages sent by a node is proportional to the node degree, and hence the contribution to the message complexity of LFR of these messages is basically irrelevant. Note that, DUAL does not need to use get.dist messages as it stores, for each node, the estimated distances of its neighbors. We can hence conclude that the better performance of LFR on G IP with respect to DUAL are basically due to the different way in which the two algorithms manage the distributed computation of shortest paths.

To conclude our analysis on G IP , we considered the space occupancy per node of the implemented algorithms (recall that DUAL and LFR require O(n • ∆) and O(n + φ • ∆) space per node, resp.). The experimental results on the space occupancy are reported in Fig. 6. Since in these sparse graphs the average degree is almost one, the average space occupancy of the two algorithms are almost equivalent although LFR is always slightly better than DUAL (Fig. 6 (left)). If we consider the maximum space occupancy, that is the space occupied by the node with the highest space requirements, then LFR is by far better than DUAL (Fig. 6 (right)). In fact DUAL requires a maximum space occupancy per node which is between 4.81 and 34.97 times the maximum space occupancy required by LFR. This is due to the fact that the topology table, implemented by the tempD data structure, is allocated by LFR only when needed.

As already observed, graph G IP and its subgraphs have a high number of nodes with small degree. For instance, G IP -8000 has 3072 degree-one nodes which corresponds to 38.4% of the nodes of the graph. Indeed, these graphs follow a power-law degree distribution. Hence, we embedded LFR and DUAL in DLP [START_REF] D'angelo | A speed-up technique for distributed shortest paths computation[END_REF], a recently proposed framework which is able to reduce the number of messages sent by any distance vector algorithm in this kind of graphs by avoiding any computation involving degree-one nodes. The algorithms obtained by combining LFR and DUAL with DLP are denoted as LFR-DLP and DUAL-DLP, The ratio between the number of messages sent by DUAL-DLP and LFR-DLP is very similar to the ratio between the number of messages sent by DUAL and LFR since it always lies between 1.47 and 6.25. Finally, our experiments show that the space overhead resulting from the application of DLP is irrelevant.

In fact, the ratio between the average space occupancy of DUAL and DUAL-DLP is 1.04 while the ratio between the average space occupancy of LFR and LFR-DLP is in [1.04, 1.06]. Since the performances of LFR and DUAL on the CAIDA graphs are in part influenced by the topological structure of such graphs, it is worth investigating how these algorithms perform also on dense graphs. To this aim we considered Erdős-Rényi random graphs G ER with 2000 nodes, 200 weight changes and dens ranging from 0.01 to 0.61, which leads to a number of edges ranging from about 20000 to about 1200000. Fig. 7 (left) shows the number of messages sent by LFR and DUAL on these instances. Contrarily to the case of G IP , DUAL is better than LFR on G ER . In fact, in most of the cases DUAL sends half the number of messages sent by LFR. This is due to the high number of get.dist messages sent by LFR which in these dense graphs are of course relevant. However, from the space occupancy point of view, we notice that the space requirements of DUAL increase more than those of LFR with the node degree, as highlighted in Fig. 7 (right). In detail, Fig. 7 (right) shows the ratio between the average space occupancy per node of DUAL and that of LFR in G ER and the ratio between the maximum space occupancy per node of DUAL and that of LFR in G ER . The average space occupancy ratio grows almost linearly with m, as the space occupancy of LFR depends on the degree with a factor φ while that of DUAL is proportional to the node degree with a factor n. Similar observations hold for the maximum space occupancy.

In conclusion, our experiments show that LFR is always the best choice in terms of memory requirements, while in terms of messages LFR outperforms DUAL on real-world instances and DUAL is the best choice on artificial ones.

Fig. 1 .

 1 Fig. 1. Pseudocode of procedure Update.

Fig. 2 .

 2 Fig. 2. Pseudo-code of procedure Decrease.

Theorem 3 (

 3 Complexity). Given a sequence of weight change operations C = (c 1 , c 2 , ..., c k ), LFR requires O(n + φ • ∆) space per node and sends O(Φ • ∆) messages and needs O(Φ) steps to converge.

Fig. 5 .

 5 Fig. 5. Number of messages sent by LFR and DUAL on GIP -8000

Fig. 6 .

 6 Fig.6. Ratio between the average space occupancy of DUAL and LFR (left); ratio between the maximum space occupancy of DUAL and LFR (right) on GIP -8000.

Fig. 7 .

 7 Fig. 7. Experiments on GER with k = 200 and dens = 0.01, 0.05, ..., 0.61: number of messages sent (left); ratio between the space occupancies, maximum (MAX) and average (AVG), of DUAL and LFR (right).

  Data Structures. LFR stores, for each node v, the arrays D v [s] and VIA v [s] plus, for each s ∈ V , the following data structures: STATE v [s], which represents the state of node v wrt source s, v is in active state and STATE v [s] = true, if and only if it is performing procedure Increase or procedure SendFeasibleDist with respect to s; UD v [s] which represents the distance from v to s through VIA v [s]. In particular, if v is active UD v [s] is always greater or equal to D v [s], otherwise they coincide; in addition, node v stores a temporary data structure tempD v needed to implement the topology table. tempD v is allocated for a certain s only when needed, that is when v is active wrt s, and it is deallocated when v turns back in passive state wrt s. The entry tempD v

  resp. Our experiments on these algorithms show that the use of DLP reduced the number of messages sent by a factor in [1.96, 2.78] in LFR and[2, 17, 8.33] in DUAL. This allows us to state that the good performance of LFR obtained in real-world instances are confirmed if it is used in combination with DLP.

⋆ Support for the IPv4 Routed/24 Topology Dataset is provided by NSF, US Department of Homeland Security, WIDE Project, Cisco Systems, and CAIDA.

aim, node v becomes active, allocates the temporary data structure tempD v , and sets UD v [s] to the current distance through VIA v [s] (Lines 2-5). At this point, v first performs the so called Local-Computation (Lines 6-9), which involves all the neighbors of v. If the Local-Computation does not succeed, then node v initiates the so called Global-Computation (Lines 11-14), which involves in the worst case all nodes of the network.

In the Local-Computation, node v sends get.dist messages, carrying UD v [s], to all its neighbors, except u. A neighbor k ∈ N (v) that receives a get.dist message, immediately replies with the value UD k [s], and if k is active, it updates

. When v receives these values from its neighbors, it stores them in tempD v , and it uses them to compute the minimal estimated distance Dmin to s and the neighbor VIAmin which gives such a distance (Lines 8-9).

At the end of the Local-Computation v checks whether a feasible via exists, according to snc, by executing the loop-free test at line 10. If the test does not succeed, then v initiates the Global-Computation (Line 11), in which it entrusts the neighbors the task of finding a loop-free path. In this phase, v sends get.feasible.dist(v, s, UD v [s]) message to each of its neighbors. This message carries the value of the estimated distance through its current via. This distance is not guaranteed to be minimum but it is guaranteed to be loop-free. When v receives the answers to get.feasible.dist messages from its neighbors, again it stores them in tempD v and it uses them to compute the minimal estimated distance Dmin to s and the neighbor VIAmin which gives such a distance (Lines 13-14).

Procedure: SendFeasibleDist(u, s, D) Input: Node v receives get.feasible.dist(u, s, UDu[s]) from u At this point v has surely found a feasible via to s and it deallocates tempD v , updates D v [s], UD v [s] and VIA v [s] and propagates the change by sending update messages to its neighbors (Lines [START_REF] Orda | Distributed shortest-path and minimum-delay protocols in networks with time-dependent edge-length[END_REF][START_REF] Ramarao | On finding and updating shortest paths distributively[END_REF][START_REF] Ray | Always acyclic distributed path computation[END_REF][START_REF] Rosen | The updating protocol of arpanet's new routing algorithm[END_REF][START_REF] Yao | Rd: Reducing message overhead in DUAL[END_REF]. Finally, v turns back in passive state.

A node k ∈ N (v) which receives a get.feasible.dist message performs the procedure SendFeasibleDist. If VIA k [s] = v and k is passive (Line 1), then procedure SendFeasibleDist behaves similarly to procedure Increase, notice indeed that Lines 2-21 of SendFeasibleDist are basically identical to Lines 2-20 of Increase. The only difference is Line 15 of SendFeasibleDist which is not present in Increase, and represents the answer to the get.feasible.dist message. However, within SendFeasibleDist the Local-Computation and the Global-Computation are performed with the aim of sending a reply with an estimated loop-free distance in addition to that of updating the routing table. In particular, node k needs to provide to v a new loop-free distance. To this aim, node k becomes active, allocates the temporary data structure tempD k , and sets UD k [s] to the current distance through VIA v [s] (Lines 2-5). Then, as in procedure Increase, k first performs the Local-Computation (Lines 6-9), which involves