Aakash Soni

Jean-Luc Scharbarg

Jérôme Ermont

Quantum assignment for QoS-aware AFDX network with Deficit Round Robin

Keywords: Networks → Network performance modeling, Network performance analysis, Quantum Allocation, Deficit Round Robin, WCTT analysis, AFDX, Switched Ethernet, Quality of Service

Avionics Full Duplex switched Ethernet (AFDX) is the de facto standard for the transmission of critical avionics flows. It is a specific switched Ethernet solution based on First-in First-out (FIFO) scheduling. Timing constraints have to be guaranteed for such critical flows. The worst-case traversal time analysis introduces some pessimism, leading to a very lightly loaded network: typically less than 10 % of the bandwidth is used. One solution to improve the utilisation of the network is to introduce Quality of Service (QoS) mechanisms. First, it can decrease worst-case delays for the most constrained avionics flows. Second less/non critical additional flows can be transmitted on the network with bounded impact on avionics ones. Deficit Round Robin (DRR) is such a QoS mechanism and it is envisioned for future avionics networks. An optimised WCTT analysis has been proposed for DRR on AFDX, based on network calculus. With DRR, the flow set is divided into classes and each class is allocated a quantum. In each round, transmissions are managed, based on these quanta. Thus delays are significantly impacted by quanta. The contribution of this paper is to propose an efficient quantum assignment for a set of critical avionics flow classes and at most one additional class with less/non critical flows.

INTRODUCTION

Up to now, Quality of Service (QoS) mechanisms are not used in practice in the context of avionics. The de facto standard is the AFDX network, which mainly implement a FIFO service discipline in switch output ports. Actually, two priority levels are available, but they are rarely used. Different approaches have been proposed for Worst-case traversal time analysis in the context of avionics, e.g. Network Calculus (NC) [START_REF] Bauer | Improving the Worst-Case Delay Analysis of an AFDX Network Using an Optimized Trajectory Approach[END_REF][START_REF] Boudec | Network Calculus: a theory of deterministic queuing systems for the internet[END_REF] with successful implementation to certify A380 and A350 AFDX backbone [1]. The pessimism of WCTT analysis as well as the fact that worst-case scenarios have a very low probability to occur lead to a very lightly loaded network. Typically, less than 10 % of the available bandwidth is used for the transmission of avionics flows on an AFDX network embedded in an aircraft. One solution to improve the utilisation of the network is to introduce Quality of Service (QoS) mechanisms. Deficit Round Robin (DRR) is such a mechanism and it is envisioned for future avionics networks. The goals are, first to better use the bandwidth for avionics flows by assigning flows with very different timing constraints to different classes, second to allow the transmission of less/non critical additional flows.

Deficit Round Robin (DRR) was proposed in [START_REF] Shreedhar | Efficient fair queuing using deficit round-robin[END_REF] to achieve fair sharing of the capacity of a server among several flow classes. It is based on quanta which are allocated to classes per round. The main interest of DRR is its simplicity of implementation. As long as specific allocation constraints are met, it can exhibit O(1) complexity. A comparison of DRR scheduler with First-In-First-Out (FIFO) and Static Priority (SP) scheduler used in AFDX network is shown in [START_REF] Hua | Scheduling design and analysis for end-to-end heterogeneous flows in an avionics network[END_REF]. The end-to-end delay (ETE) bounds are computed and the paper shows the comparatively better performance of DRR scheduler over FIFO and SP scheduler, given an optimised network configuration. Another DRR implementation is proposed in [START_REF] Boyer | Combining static priority and weighted round-robin like packet scheduling in AFDX for incremental certification and mixed-criticality support[END_REF], which combines the DRR with SP scheduling, to improve schedulability and make more efficient use of hardware resources. A detailed analysis and improvement of DRR latency bound for homogeneous flows is given in [START_REF] Kanhere | On the latency bound of Deficit Round Robin[END_REF]. Some mathematical errors of [START_REF] Kanhere | On the latency bound of Deficit Round Robin[END_REF] are pointed out and corrected in [START_REF] Kos | A More Precise Latency Bound of Deficit Round-Robin Scheduler[END_REF]. Analysis of a server with DRR scheduler using NC method is first discussed in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] which also proposes improvement in DRR latency. [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] generalises the analysis to network with heterogeneous flows. An optimised WCTT analysis for DRR on AFDX is proposed in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF].

The assignment of flows to classes and the quantum allocated to each class has a major impact on the end-to-end latencies of flows. In this paper, we assume that flows have been assigned to classes and we focus on credit allocation. This problem has been addressed in the context of non critical flows with Weighted Round Robin (WRR) [START_REF] Noda | Approach to optimal WRR weight assignment method in delay-limited environment[END_REF]. To the best of our knowledge, no paper considered the situation of a network shared by critical and non critical flows.

In this paper, we propose an efficient quantum allocation for an AFDX network implementing DRR and shared by a set of critical flow classes and at most one less/non critical flow class.

The rest of the paper is organised as follows. Section 2 summarises the context of the paper, i.e. the network model, DRR main features and worst-case analysis as well as the problem statement. Section 3 presents the proposed quantum assignment algorithm. Sections 4 and 5 illustrate the algorithm on a small example and evaluate it on a realistic case study. Section 6 concludes the paper and gives some direction for future works.

CONTEXT

In this section, we present the network model, which considers DRR scheduling, and we state the problem.

Network Model

In this paper, we consider an avionics switched Ethernet network (AFDX). It is composed of a set of end systems, interconnected by switches via full-duplex links.

End-systems are the source and destination of a set of flows. These flows are statically defined as virtual links (VL). They are forwarded by switches, based on a statically defined forwarding table. The forwarding process introduces a switching latency (sl).

Each flow is shaped at the end system. A minimum interval BAG i is guaranteed between any two consecutive frames of flow v i . Each flow v i is also constrained by a maximum frame length (l max i ) and a minimum frame length (l min i ). The path P i followed by a flow v i in the network is statically defined. Figure 1 shows an example of an AFDX network. Four switches (S 1 to S 4 ) interconnect nine end systems (e 1 to e 9 ). Twenty flows (v 1 to v 20 ) are transmitted on this network. Each switch output port has a set of buffers controlled by a Deficit Round Robin (DRR) scheduler. The maximum link bandwidth is R = 100 Mbits/s. Flow features are given in Table 1. Q i represents the number of bytes allocated to C i in each round. The unused fraction of quantum in a given round is deficit ∆ i for the next round. Thus, the total amount of credit that C i can get in any round is Q i +∆ i . Initially each class deficit is set to 0 (lines 1-3). Each active class queue is served in round robin order (lines 4-16). Empty queues are ignored in each round (line 6). The non-empty queues are credited by their quantum Q i added to the previous deficit ∆ i (line 7). Selected class can send frames as long as its queue is not empty and the deficit is larger than the head-of-line packet (line 8-12). On each transmission of frame, the credit is reduced by the frame size. If the queue becomes empty, the deficit is reset to 0 (lines 13-14). Then the next class is selected to be served.

v 17 v 13 v 2 v 14 v 18 v 20 v 6 v 3 v 15 v 19 v 1 v 12 v 13 v 17 v 2 v 14 v 18 v 20 v 3 v 6 v 15 v 19 v 4 v 7 v 9 v 10 v 5 v 8 v 11 v 16 v 1 ... v 5 v 6 ... v 12 v 13 ... v 20 S 4 e 9 S 2 S 1 S 3
Figure 2 illustrates DRR scheduling on the configuration in Figure 1. Each class is assigned a quantum of 1500 bytes. One frame of VLs v 1 , v 3 , v 5 , v 6 , v 7 , v 12 , v 13 , v 14 , v 17 , v 18 , v 20 with maximum frame size arrive at the output port of S 4 simultaneously and they are arbitrarily buffered in this order. We arbitrarily assume that class C 2 is selected first. Since its initial deficit is 0, it gets a credit of 1500 (its quantum). Frame from v 12 is first in the queue and its size (1000 bytes) is less than the credit. Thus it is transmitted. Remaining credit is 500, which is not enough for the transmission of next C 2 pending frame (from v 13 ). Therefore, scheduler moves to class C 3 with a credit of 1500. It allows the transmission of v 6 frame, but not v 7 one and the remaining credit is also 500. Then C 1 frame from v 5 is transmitted with a remaining credit of 510. Then C 2 is selected again. It gets a credit of 2000 (500 of deficit plus 1500 of quantum). It allows the transmission of v 13 and v 18 frames, leading to a remaining credit of 0, and so on.

Algorithm 1: DRR Algorithm Input : Per class quantum: Q h 1 . . . Q h n (Integer) Data: Per class deficit: ∆ h 1 . . . ∆ h n (Integer) Data: Counter: i (Integer) 1 for i = 1 to n do 2 ∆ h i ← 0 ; 3 end 4 while true do 5 for i = 1 to n do 6 if isNotEmpty(C i ) then 7 ∆ h i ← Q h i + ∆ h i ; 8 while (isNotEmpty (C i )) and (headFrameSize(C i ) ≤ ∆ h i ) do 9 send(headFrame(C i )); 10 ∆ h i ← ∆ h i -headFrameSize(C i ); 11 remove(headFrame(C i )); 12 end 13 if isEmpty(C i ) then 14 ∆ h i ← 0 15 end 16 end

DRR WCTT analysis

A WCTT analysis is mandatory in order to guarantee that critical flows never exceed their deadline. Such a WCTT analysis has been proposed for DRR in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] and optimised for AFDX in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. Both approaches are based on network calculus (NC). In this section, we give a very general overview of these approaches (only the details which are needed for the rest of the paper).

The NC theory is based on the (min, +) algebra [START_REF] Boudec | Network Calculus: a theory of deterministic queuing systems for the internet[END_REF]. It models the traffic and network elements by piecewise linear curves called arrival curves and service curves respectively.

The arrival curve of a flow represents an over-estimation of the traffic of this flow at any instant t. For a VL v i at its source end system es x , it is:

α es x i = l max i BAG i × t + l max i f or t > 0 and 0 otherwise l max i
is the burst (one frame) while

l max i
BAG i is the long-term rate. A frame of v i can experience jitter since it can be delayed by other frames before it arrives at a switch output port h. Thus the arrival curve of v i in h is obtained by shifting the arrival curve of v i in es x to the left by this jitter [START_REF] Bauer | Improving the Worst-Case Delay Analysis of an AFDX Network Using an Optimized Trajectory Approach[END_REF].

A switch output port h with maximum service rate R and switching latency sl is modelled by a service curve:

β h (t) = R × [t -sl] +
where [a] + means max(a, 0). In a DRR scheduler, the bandwidth is shared by all the classes at each output port h. Therefore each class C x receives a fraction ρ h x of R, based on its assigned quantum Q h x :

ρ h x = Q h x 1≤j ≤n Q h j × R (1)
(Q h j + ∆ max,h j
) ) and, when it is served for the first time, it might get less than its allocated fraction ρ h x . This latency Θ h x can be illustrated with the example in Figure 2. Let us consider class C 1 . Its first frame (from v 5 ) is served after one frame from C 2 and one frame from C 3 , i.e. 160 µs. In the first round, frames from v 5 , v 13 , v 18 , v 7 , v 14 are served, leading to 5500 transmitted bytes.

Thus C 1 gets 1500 5500 × 100 = 27.27 Mb/s. Based on ρ h x , it should have received 33.33 Mb/s.

Therefore the residual service curve for class C x at port h is given by

β h x (t) = ρ h x × [t -Θ h x -sl] + (2)
The delay computation for class C x in each output port h is bounded by the maximum horizontal difference between the overall arrival curve of C x flows in h (sum of individual arrival curves) and the service curve for class C x . These curves are illustrated in Figure 3. The service curve is an under-approximation of the actual staircase service curve of C x . Indeed C x alternates periods when it get no service and periods when it gets full service at rate R. Such a staircase curve does not fit within NC, since it is not convex. The considered under-approximation is convex. The basic approach in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] implement this delay computation. It does not make any assumption on the volume of competing traffic from other classes. It comes to consider that competing classes are always active. It might not be the case. Thus the approach in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] optimises the one in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] by quantifying the maximum amount of traffic of each competing class within the delay bound computed by [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF].

D h x 1 t sl α h x i ∈ F h x (b i ) X h x Y h x Θ h x β h x ρ h x

Problem statement

Our goal is to allocate the quanta on an AFDX network implementing DRR scheduling so that:

• every critical frame respects its deadline,

• the delay of non critical frames is minimised.

Therefore the goal is to assign as few bandwidth as possible to critical classes in order to maximise the bandwidth assigned to the non critical class. As previously mentioned, we assume a set of n -1 critical classes C 1 . . . C n-1 and one single non critical one C n . We also assume that a given class is assigned the same quantum in all switch output ports. The quantum Q x assigned to a class C x has to allow the transmission of any frame of class C x . Therefore, we must have

Q x ≥ Max x for 1 ≤ x ≤ n (3
) where Max x is the largest frame size among class C x frames.

If V x is the set of class C x VLs, we have

Max x = max v j ∈V x l max j (4)
In the next section we propose an algorithm that solves this quantum allocation problem. This algorithm assumes the basic WCTT computation in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF].

QUANTUM ASSIGNMENT

Since the quantum of a given class is the same in all switch ports, we omit node h in notations in the rest of the paper. Let us define Q as the sum of quanta allocated to classes, i.e.

Q = 1≤i ≤n Q i (5)
If we focus on one class C x , it receives a quantum Q x while the other classes shares Q -Q x . First, we show that the worst-case end-to-end latency of a given class C x depends on the quantum Q x allocated to C x as well as on Q -Q x , but it does not depend on the distribution of Q -Q x among the other classes.

Lemma 3.1. Given Q x and Q, the worst-case delay for C x computed by network calculus approach in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] is the same for any quantum distribution among competing classes.

Proof. The quanta only impact the service curve for class C x in each switch output port. Thus we show that this service curve depends on Q x and Q, but not on quantum distribution. The service curve for class C x in a node is defined by equation 2. It depends on the fraction ρ x of bandwidth allocated to C x and the DRR scheduler latency Θ x .

ρ x is defined by equation 1, which can be rewritten

ρ x = Q x Q × R (6)
Thus ρ x only depends on Q x and Q. Θ x is defined in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] as the sum of two delays X x and Y x , where,

X x = 1≤j ≤n, j x (Q j + ∆ max j ) R (7)
Y x = Q x -∆ max x + 1≤j ≤n, j x Q j R - Q x -∆ max x Q x Q × R (8)
where, ∆ max i is the maximum deficit for class C i , i.e. Max i -1. Thus, we have

Θ x = X x + Y x = 2 × 1≤j ≤n j x Q j R + 1≤j ≤n j x ∆ max j R + Q x -∆ max x R 1 - Q Q x = 2 × 1≤j ≤n j x Q j R + 1≤j ≤n j x ∆ max j R + Q x -∆ max x R Q x -Q Q x = 2 × 1≤j ≤n j x Q j R + 1≤j ≤n j x ∆ max j R + Q x -∆ max x R - 1≤j ≤n j x Q j Q x         since 1≤j ≤n j x Q j = Q -Q x         = 1≤j ≤n j x Q j R + 1≤j ≤n j x ∆ max j R + ∆ max x R 1≤j ≤n j x Q j Q x
Therefore Θ x depends on • the link rate R and the maximum deficits ∆ max i for each class, which does not depend on quanta, • the quantum Q x assigned to class C x under study,

• the sum of the quanta assigned to competing classes 1≤j ≤n, j x Q j , but not the individual Q j values.

□

Based on lemma 3.1 the quantum assignment can be done in the following manner.

• the sum Q of quanta allocated to classes is fixed,

• we calculate the minimum portion of Q that has to be allocated to C 1 so that all the VLs in C 1 respect their deadlines (we do not need to know the quanta that will be assigned to other classes), • we do the same for C 2 . . . C n . Q value has to be large enough to lead to the valid values for each quantum (equation 3). This can be illustrated with the example in Figure 1. Let us consider three cases: case 1: If Q = 4000, on computing the delay bound with NC approach we observe that the minimum quantum required by C 1 and C 2 to respect their delay constraints are 1282 and 1119 bytes and the residual quantum for C 3 is 1599 bytes (which is 34.52 % of Q). However, this is not a valid case since the quantum assigned to C 1 should be at least 1500 bytes (equation 3).

case 2: Now, let us assume a higher value of Q = 6000. In this case, the minimum quantum required by C 1 and C 2 are 2356 and 1995 bytes. The residual quantum for C 3 is 1649 bytes (27.48%). The percentage share of quantum is clearly reduced as compared to the previous case. In the next case, let us try a value of Q somewhere between that in case 1 and case 2.

case 3: Let Q = 4500 bytes. In this case, the minimum quantum required by C 1 and C 2 are 1507 and 1322 bytes, which gives the residual quantum for C 3 as 1671 bytes, thus, the percentage share of quantum for C 3 is increased to 37.13%.

This small example shows that the ratio between computed quanta depends on Q. Since one goal is to minimise the response time for non critical flows (class C n ), we want to get the valid Q value that maximises the percentage of Q which is not assigned to critical classes. Next lemma states that the best Q value is the smallest valid one. Lemma 3.2. When each critical class is assigned the minimum quantum which guarantees that no deadline is missed, based on the WCTT analysis in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF], a smaller valid value of Q never leads to a smaller percentage of Q assigned to the non critical class C n .

Proof. From equation 5, we have

Q n = Q - 1≤j <n Q j (9)
Therefore the percentage of Q assigned to C n is 1 -

1≤j <n Q j Q (10) Let us consider two valid Q values Q ′ and Q ′′ with Q ′′ = σ × Q ′ with σ > 1.
We have to show that the percentage of Q ′ assigned to C n cannot be smaller than the percentage of Q ′′ assigned to C n . Therefore we have to show that 1≤j <n

Q ′ j Q ′ ≤ 1≤j <n Q ′′ j Q ′′ (11)
To show that this inequality is true, we show that

Q ′ j Q ′ ≤ Q ′′ j σ × Q ′ for 1 ≤ j < n (12)
Let us consider one class C x (1 ≤ x < n). When the sum of quanta is Q ′ , it gets a quantum of Q ′ x , which is the minimum quantum it needs to meet all its deadlines. When the sum of quanta is

Q ′′ = σ × Q ′ , we have to show that Q ′′ x ≥ σ × Q ′ x ( 13
)
The worst-case delay of a C x frame is the maximum horizontal distance between C x traffic curve and C x service curve. C x traffic curve does not depend on its assigned quantum. The distance clearly decreases when Q ′′

x increases. Thus inequality 13 is true if moving from a quantum of Q ′

x out of Q ′ to a quantum of σ × Q ′ x out of σ × Q ′ does not lead to a higher service curve for C x .

The service curve for class C x in a node is defined by equation 2. It depends on the fraction ρ x of bandwidth allocated to C x and the DRR scheduler latency Θ x . ρ x is defined by equation 1. Considering Q ′ and Q ′′ we have

ρ ′ x = Q ′ x Q ′ × R and ρ ′′ x = σ × Q ′ x σ × Q ′ × R Thus ρ ′ x = ρ ′′ x
Concerning DRR scheduling latency Θ x , we have shown in lemma 3.1 proof that

Θ ′ x = 1≤j ≤n, j x Q ′ j R + 1≤j ≤n, j x ∆ max j R + ∆ max x R 1≤j ≤n, j x Q ′ j Q ′ x Since Q ′′ = σ × Q ′ and Q ′′ x = σ × Q ′ x , we have Θ ′′ x = 1≤j ≤n, j x σ × Q ′ j R + 1≤j ≤n, j x ∆ max j R + ∆ max x R 1≤j ≤n, j x σ × Q ′ j σ × Q ′ x = σ × 1≤j ≤n, j x Q ′ j R + 1≤j ≤n, j x ∆ max j R + ∆ max x R 1≤j ≤n, j x Q ′ j Q ′ x Since σ > 1, we have Θ ′′ x > Θ ′
x . Thus the service curve for C x when considering Q ′′ and Q ′′

x is under the service curve for C x when considering Q ′

x and Q ′ . This phenomenon is illustrated in Figure 4. When σ increases, the service curve is shifted to the right, leading to a higher horizontal distance with traffic curve and, consequently, a higher worst-case delay. □

Based on lemmas 3.1 and 3.2, the quantum assignment is implemented by algorithm 2. The basic idea of the algorithm is to start from an initial value V alInit for the sum of quanta Q (line 1). It computes for each critical class C i the minimum portion Q i of Q that insures that no C i frame misses its deadline (line 9, function QuantumMin). The process stops as soon as the unused portion QResid of Q is smaller than the computed Q i value (line [START_REF] Shreedhar | Efficient fair queuing using deficit round-robin[END_REF][START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] or all the critical classes have been treated. In the later case, the non critical class gets a quantum of QResid and a solution has been obtained. This solution might be either not valid if condition 3 is not respected (at least one class has a quantum which is smaller than its maximum frame size) or improvable if the quantum of every class exceeds its maximum frame size by more than a configured (small) value ϵ: we tolerate an ϵ difference, since it might be tricky to reach a valid solution where at least one class has its maximum frame size as quantum. In both cases (not valid or improvable solution), we adapt the sum of quanta Q (lines 25-26): we increase it if the solution is not valid, we reduce it if the solution is improvable. As soon as a non improvable valid solution is found, the algorithm returns it and stops.

Θ bits t β β ′ β ′′ β : σ = 1 β ′ : σ = 1.5 β ′′ : σ = 2 Θ ′ Θ ′′
QuantumMin function (line 9) implements a binary search. It applies the WCTT analysis in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] on values not greater than Q, until it gets the smallest value with no deadline miss.

In the next section, we illustrate Algorithm 2 on the example in Figure 1 and give some more details on the computation.

QUANTUM ASSIGNMENT EXAMPLE

The flows are divided into n = 3 classes based on their delay constrains. C 1 and C 2 are critical flow classes with delay constraint 3100 µsec and 3200 µsec, respectively, and C 3 is non-critical flow class with no constraint on delay (see Table 1). The maximum service rate at each output port is R = 100 Mb/s.

Initially, we assume a sum of quanta Q = V alInit = 4550 bytes (line 1). First critical class is C 1 (line 4). For the given sum of quanta, the minimum quantum value Q i (i = 1 and 2) for each class is computed (line 8-18). The function QuantumMin(i,Q) computes the minimum quantum required to respect the deadline in class C i given the quantum sum Q. This computation is based on the maximum end-to-end delay in the class, obtained thanks to the WCTT analysis in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF].

The whole process is shown in Table 2 for each class of the network in Figure 1. For each class, the process is based on a binary search. In the first step, the maximum quantum is assigned to Q 1 (4550 in our case). With this quantum, the worst-case end-to-end delay for C 1 obtained by NC approach in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] is 1007.87 µsec. Since, this computed delay is less than the delay constraint on C 1 (3100 delays are computed for all the flows, using the classical network calculus approach for FIFO [START_REF] Bauer | Improving the Worst-Case Delay Analysis of an AFDX Network Using an Optimized Trajectory Approach[END_REF]. Obtained results are shown in Figure 5. In Figure 5, each unit on x-axis represents a flow path and y-axis represents the worst-case end-to-end delay corresponding to this path. The paths are sorted in increasing order of delays in each class. The maximum delays computed in the network is 12572.6 µsec. Therefore flow deadlines are met. Indeed deadlines for C 1 flows are 12573 µs, while deadlines for class C 2 flows are 50292 µs.

Counter: i (Integer) 1 Q ← V alInit ; 2 Fini ← f alse ; 3 while not Fini do 4 i ← 1 ; 5 QResid ← Q ; 6 valid ← true ; 7 min ← Q ; 8 while i < n and valid do 9 Q i ← QuantumMin(i, Q) ; 10 if Q i > QResid then 11 valid ← f alse ; 12 else 13 QResid ← QResid -Q i ; 14 if min > Q i Max i then 15 min ← Q i Max i ; 16 i ← i + 1 ;
Next, we arbitrarily introduce some additional flows into this configuration. Actually, we consider a set of 40 C 1 like flows. The idea is to interfere with the critical flows and evaluate the impact on worst-case end-to-end delay in the network. The added flows are considered as non-critical (best-effort) flows characterised by class C 3 shown in Table 3.

The impact of additional flows on the critical ones is shown in Figure 6. Not surprisingly, the delay is increased for critical flows as they share waiting queues with non-critical flows. Moreover, there are 9 flows of C 1 which exceed their deadlines. The maximum delay in C 2 is still much lower than the delay constraint. Now, we consider DRR scheduling at each switch output port in the given network. The DRR scheduler configuration is given in Table 4. The quantum for each class is optimised using the Algorithm 2 such that no critical flow (in C 1 and C 2 ) misses its deadline while maximising the percentage of bandwidth assigned to non-critical flows (C 3 ). Based on WCTT analysis in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF], worst-case end-to-end delays are shown in Figure 7. Quantum assignment insures that critical flows are within their expected constraints and reducing one quantum for a critical class would lead to exceeded deadlines. Finally we compare the delays observed on the additional flows (C 3 ) in both cases (FIFO and DRR). Worst-case delays for each flow are shown in Figure 8 and summarised in Table 5. On this specific example, DRR globally leads to smaller worst-case delays for C 3 flows than FIFO. This is due to the fact that DRR reserves bandwidth to these flows while, with FIFO, they are transmitted only when there are no pending critical frames. It would be interesting to evaluate average delays for C 3 flows, for instance by simulation. We can guess that DRR would still be better than FIFO.

Discussion

The NC approach for WCTT analysis used in this paper (from [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]) can be very pessimistic as it assumes that the competing classes are always active and the traffic from each class is maximum. This The problem of pessimism in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] was addressed in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] by quantifying the maximum amount of traffic of each competing class within the delay bound computed by [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]. However, the optimised NC approach in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] cannot be used with the quantum assignment algorithm presented in this paper as it does not respect Lemma 3.1. Indeed the optimisation in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] depends on the quantum allocated to each competing class. Therefore the resulting WCTT analysis depends, not only on the sum of the quanta of competing classes, but also on each quantum value. Thus the algorithm proposed in this paper cannot be used.

The delay bounds computed in this paper, using [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF], can be pessimistic which means that the actual delays are much lower. We evaluate the difference between both bounds on the case study. We take the optimised quanta computed earlier (Table 4) and use these quanta values in the optimised NC approach given in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. The results are shown in Figure 9. The maximum delay in C 1 and C 2 are 10016.9 and 24669.2 µsec respectively, which are clearly much less than what was computed by the pessimistic approach. It means that we can increase the percentage of bandwidth assigned to non critical flows without compromising the constraints of critical ones.

CONCLUSION

In this paper we show how the available bandwidth of an AFDX network can be efficiently shared between critical avionics flows and non critical ones. We consider a Deficit Round Robin scheduling in switch output ports. We assume a set of critical flow classes and one non critical flow class. We propose an algorithm that assign the minimum quanta to critical classes that insure that no deadlines will be missed. Thus it maximises the percentage of bandwidth assigned to non critical flows. We show that such a strategy leads to smaller worst-case delays for non critical flows. It would be interesting to show that the trend is the same for average delays. This could be done by simulation. The other advantage of the proposed solution is to take into account the different deadlines of critical flows.

In the proposed approach, the WCTT analysis in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] is used. It is known to be potentially very pessimistic and a much less pessimistic solution has been proposed in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. This optimised solution is not compatible with the algorithm proposed in this paper. Therefore one future work is to adapt the algorithm to the optimised WCTT analysis. Our intuition is that it might significantly increase the algorithm complexity.

Other scheduling policies are envisioned for QoS-aware AFDX networks, such as Weighted Round Robin [START_REF] Soni | WCTT analysis of avionics Switched Ethernet Network with WRR Scheduling[END_REF]. Another future work is to develop a similar assignment algorithm for this scheduling policy.

Figure 1 :

 1 Figure 1: AFDX Network Example

Figure 2 :

 2 Figure 2: DRR rounds at S 4 output port

  bits

Figure 3 :

 3 Figure 3: Arrival and Service Curves

Figure 4 :

 4 Figure 4: Service curves

Algorithm 2 :

 2 Quantum assignment algorithm input : Initial sum of quanta: ValInit (Integer) input : Per class maximum frame size: Max 1 . . . Max n (Integer) input : Improvement level: ϵ (Float) output : Valid solution found: valid (Boolean) output : Per class quantum: Q 1 . . . Q n (Integer) Data: Remaining quantum: QResid Data: Relative distance to a non improvable solution: min (Float) Data: End of the process: Fini (boolean) Data:

  Max n ; 25 if min < 1 or min > 1 + ϵ then 26

Figure 5 :

 5 Figure 5: End-to-end delay bounds in C 1 and C 2 flows under FIFO scheduling

Figure 6 :

 6 Figure 6: End-to-end delay bounds in C 1 and C 2 flows under FIFO scheduling in presence of additional flows

Figure 7 :

 7 Figure 7: End-to-end delay bounds in C 1 and C 2 flows under DRR scheduling in presence of additional flows

Figure 8 :

 8 Figure 8: Comparison of end-to-end delay bounds in C 3 flows under FIFO and DRR scheduling

Figure 9 :

 9 Figure 9: End-to-end delay bounds in C 1 and C 2 flows under DRR scheduling in presence of additional flows (computed by optimised NC approach)

Table 1 :

 1 VL parameters in network example (Figure1)

	Flow	BAG i (msec)	l max i (byt es)	l min i (byt es)	Delay (µsec) constraint	Class
	v 1 , v 2 , v 3	8	1500	800	3100	Critical
	v 4 , v 5	8	990	800		(C 1 )
	v 12 , v 13 , v 18	16	1000	800	3200	Critical
	v 20 , v 15 , v 19	16	990	800		(C 2 )
	v 17 , v 14 , v 6 , v 7	32	1000	800		Non
	v 8 , v 9 , v 10 , v 11 , v 16	32	990	800	-	critical (C 3 )
	2.2 Overview of DRR scheduler
	DRR scheduler was designed in [10] to achieve a better quality of
	service by fair sharing of available network bandwidth among the
	flows. Basically DRR is a variation of Weighted Round Robin (WRR)
	which allows fair sharing of bandwidth among variable length flow
	packets. DRR service is divided into rounds. In each scheduling
	round, active classes are served sequentially. A class is said to be
	active when it has some pending frames in its queue. Algorithm
	1 shows DRR implementation at a switch output port h serving n
	traffic classes.
	DRR scheduler assigns quantum Q

i to each active class C i .

Table 4 :

 4 DRR configuration

		Delay	Optimized
	Class	constraints	Quantum
		(µsec)	(bytes)
	Critical		3581
	C 1	12573	(Bandwidth = 56.02%)
	Less-Critical C 2	4 × 12573	1535 (Bandwidth = 24.01%)
	Best-effort		1276
	C 3	-	(Bandwidth = 19.97%)

Table 5 :

 5 Performance comparison: FIFO Vs DRR scheduling

		Max delay (µsec)
		C 1	C 2	C 3	Deadlines
					missed
	FIFO	12572.6 12572.6	-
	FIFO
	(with added flows) 13659.9 11535.4 11535.4	9
	DRR
	(with added flows) 12549.2 50215.7 7082.42	0
	Deadlines	12573	50292	-
	pessimism also affects the optimised quantum computed by the
	algorithm presented in this paper, since it over-estimate worst-case
	delay.

µsec), Q 1 can be reduced. It will increase the worst-case delay for C 1 flows.

The delay computation in NC is based on the convergence of overall arrival curve and the service curve. Thus, the service rate ρ x must be more than the arrival rate r x = vi ∈C x l max i BAG i of the cumulative flows in C x . In C 1 , the maximum traffic arrival rate is observed at output port of switch S 4 as 6.48 bits/µsec. If the minimum bandwidth provided to C 1 is 7.48 bits/µsec, the corresponding quantum value is 340 bytes.

The next value assumed in binary search is the mid value between 4550 and 340, thus, Q 1 = 2445. The corresponding maximum end-to-end delay is 2138.72 µsec. Then Q 1 can be further decreased, since, the computed delay is less than the delay constraint on C 1 . This process is repeated until the computed delay is close to the C 1 delay constraint (and smaller). The value returned by

The residual quantum is QResid = 4550 -1524 = 3026 bytes (line 13 in Algorithm 2) which can be distributed among the other classes. min is the smallest factor which is obtained from the ratio of the quantum assigned to a class and its maximum frame length. This factor will be used to optimise the quantum sum (line 26). From class C 1 , min = 1.016 (line 14-16).

Next, critical class is C 2 . The minimum quantum obtained from 2). Thus, the residual quantum is QResid = 3026 -1337 = 1689 bytes. Since, the minimum quantum is successfully computed for critical classes, next class is non-critical class C 3 (line 21-30). The residual quantum can be assigned to C 3 (line 22).

Based on Lemma 3.2, the goal is to find the smallest valid value of Q, which we call a non improvable value.

The factor min represents the convergence towards a non improvable value of sum Q of quanta. If min < 1, then Q is lower than the expected value and if min > 1, then Q is higher than the expected value. Thus, the non improvable sum of quanta can be obtained by the Q min = 4479 (line 26). The distribution of this new sum of quanta among each class can be done by repeating the whole process with Q = 4479. The corresponding values of quantum for each class is given in Table 2.

EVALUATION

In this section, we evaluate the proposed quantum assignment algorithm on an industrial-size network.

First, we perform a WCTT analysis using Network Calculus on the original industrial configuration assuming that each switch output port is controlled by a FIFO scheduler.

Then, we introduce some additional non-critical flows to this configuration and analyse the impact on the worst-case end-to-end delays of the critical flows, still considering FIFO scheduling.

Next, we assume a DRR scheduler at each switch output port. We show how the constraints on end-to-end delays for critical flows can be guaranteed while minimising the delay for non-critical flows with DRR scheduling in presence of optimised quantum values.

Table 2: Quantum assignment in the network (Figure 1).

(bytes)

(µsec)

Industrial Case Study

We consider an industrial-size configuration. It includes 96 endsystems, 8 switches, 984 flows, and 6276 paths (multi-cast VL) [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. We arbitrarily distribute flows between 2 critical classes: a class C 1 for flows with small BAGs (up to 16 ms) and a class C 2 for flows with larger BAGs. Table 3 summarises the features of these classes. In the first step, this network is assumed to use FIFO scheduling in switch output ports (classes are not considered). Worst-case


Aakash Soni
email: aakash.soni@irit.fr

Jean-Luc Scharbarg
email: jean-luc.scharbarg@enseeiht.fr

Jérôme Ermont
email: jerome.ermont@enseeiht.fr

Efficient configuration of a QoS-aware AFDX network with Deficit Round Robin

Keywords: Quantum Allocation, Deficit Round Robin, WCTT analysis, AFDX, Switched Ethernet, Quality of Service

AFDX is the de facto communication standard in avionics domain. It is primarily used for the transmission of critical avionic flows. The mandatory certification process requires to upper bound the end-to-end transmission delay for each critical flow. Therefore, worst-case traversal time analysis has been implemented. However, it leads to a very lightly loaded network (up to 10%) as it considers very rare worst-case situations. Introducing a QoS mechanism is often a good solution to improve network utilisation since it allows differentiating critical flows based on their constraints as well as the transmission of less/noncritical flows with bounded impact on critical ones. Deficit Round Robin is such a mechanism and it is envisioned for future avionic networks. Using this mechanism, we propose to share the bandwidth between n -1 classes for critical flows and one class for non-critical ones. Therefore the contributions of this paper are (1) to propose a quantum assignment that ensures that critical flows always respect their deadlines and maximises the bandwidth for non-critical ones and (2) to propose a heuristic for the distribution of the flows among different classes.

I. INTRODUCTION

Avionics Full DupleX switched Ethernet (AFDX) [START_REF]1,2,7 Aeronotical Radio Inc[END_REF] has become the de facto standard for the transmission of (critical) avionic flows. It has been tailored to meet avionic constraints and a Worst-Case Traversal Time analysis (WCTT) allows the computation of an upper bound for the end-to-end delay of each flow. This analysis is based on Network Calculus (NC) for the certification of A380 and A350 backbones. It makes pessimistic assumptions that leads to a very lightly loaded network. Typically, less than 10% of the available bandwidth is used for the transmission of avionic flows on an AFDX network embedded in an aircraft. A classical solution to improve utilisation of the network is to introduce Qualityof-Service (QoS) mechanisms. First, it can decrease worst-case delay for the most constrained avionic flows. Second, less/noncritical additional flows can be transmitted on the network with bounded impact on avionic ones. Existing AFDX switches implement Fixed Priority service discipline with two priority levels. Up to now, they are rarely used. Thus avionic flows are transmitted, following a FIFO service discipline.

It has been shown [START_REF] Hamza | Priority assignment on an avionics switched Ethernet Network (QoS AFDX)[END_REF] that distributing avionic flows between these two priority levels can significantly decrease the highest end-to-end delay that any flow can experience. These preliminary results are promising. Further studies have shown that Deficit Round Robin (DRR) allows an efficient and safe bandwidth sharing between critical avionic flows and noncritical additional ones [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF].

DRR [START_REF] Shreedhar | Efficient fair queuing using deficit round-robin[END_REF] achieves fair sharing of the capacity of a server among several flow classes, thanks to quanta which are allocated to classes per round. Several papers address the analysis of DRR latency bound [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]- [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. In particular, the analysis of a server with DRR scheduler based on NC is proposed in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] and optimised in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF].

The work in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] is based on the WCTT analysis of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]. It considers a switched Ethernet network with DRR scheduler, shared by critical and non-critical flows. It considers n -1 classes for critical flows and one for non-critical ones. [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] assumes that flows have been assigned to classes. It determines a quantum assignment which guarantees that critical flows respect their deadlines (valid assignment) and maximises the bandwidth allocated to non-critical flows. A similar problem has been addressed in the context of non-critical flows with Weighted Round Robin (WRR) [START_REF] Noda | Approach to optimal wrr weight assignment method in delay-limited environment[END_REF]. To the best of our knowledge, the only work that addresses this problem is [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. It suffers from two main limitations.

• First, it does not benefit from the optimised NC WCTT analysis for DRR presented in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. Indeed it is based on assumptions that do not hold for this optimised analysis. • Second, it does not propose an assignment of flows to classes. Such an assignment makes sense for avionic flows. The goal is to find the best valid assignment in terms of bandwidth for non-critical flows. This paper integrates both aspects in the approach in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. First, we redesign the quantum assignment algorithm in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] so that it can cope with the WCTT analysis in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. Second, we propose a heuristic for the allocation of critical flows to classes.

Section II presents the context of the study and states the problem. An improved quantum assignment is proposed in Section III. Flow distribution among classes is addressed in Section IV. The proposed solution is evaluated on a realistic case study in Section V. Section VI concludes the paper and gives some directions for future works.

II. CONTEXT OF THE STUDY

AFDX network interconnects a set of end-systems by switches via full-duplex links. End-systems are the sources and destinations of flows statically defined as virtual links (VL). Each flow v i is constrained by a minimum interval BAG i between any two consecutive frames at end system level, a maximum (l max i ) and a minimum (l min i ) frame length. The path P i followed by v i is statically defined with a bounded switching latency sl in each switch. Unlike TSN, AFDX is an asynchronous network: it doesn't provide a global clock to avionics systems in order to mitigate certification issue.

Critical avionic flows consume a small part of the available bandwidth. Thus it is envisioned to use the free bandwidth to transmit additional less/non-critical flows which are presently transmitted on other networks. Obviously, the impact of these additional flows on the critical ones must be bounded in order to guarantee that critical flows never miss deadlines.

Fixed priority service discipline with two priority levels is implemented in existing AFDX switches and it can be used to that purpose. Critical flows are assigned the high priority and non-critical flows the low one. However, this solution presents limitations [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. First, non critical flows have to wait as long as there are high priority ones to be served. It can lead to long delays in case of bursts of high priority frames. However, the constraint is to transmit critical flows within their deadlines. Thus critical frames could be delayed by noncritical ones, provided that it does not jeopardise the respect of their deadlines. Second, assigning all critical flows to the same priority means that they are not differentiated. It can be quite inefficient [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]: critical flows should be treated differently, depending on their deadlines.

DRR scheduler is promising to mitigate these limitations [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. It is an approximation of fair queuing technique that allows each flow passing through a network device to get a fair share of network bandwidth at a very low implementation complexity. Therefore, an enhanced switch implementing DRR policy is under consideration, leading to a QoS aware AFDX network. In such a network, a set of n queues is associated with each output port h. Each queue stores the frames of a given traffic class.

Let us illustrate the operation of DRR scheduling on the network example in Figure 1. Two switches (S 1 and S 2 ) interconnect eight end-systems (e 1 to e 8 ). Twenty one (critical) avionic flows (v 1 to v 21 ) and one (non-critical) additional flow (v 22 ) are transmitted on this network. Each switch output port implements a DRR scheduler. The maximum link bandwidth is R = 100 Mbits/s. Flow features are given in Table I. An arbitrary distribution of these flows is presented in Table II where the deadline in each class is limited to its smallest flow deadline (i.e. v 1 (300µsec) for C 1 , v 6 (600µsec) for C 2 and v 14 (900µsec) for C 3 ).

.. One possible scenario for DRR scheduling at S 2 is shown in Figure 2 where frames of critical flows v 1 , v 2 , v 3 , v 7 , v 6 , v 8 , v 9 , v 14 , v 16 , v 15 , v 17 arrive at the output port of S 2 simultaneously and they are arbitrarily buffered in this order. For all flows l min = 80 bytes. DRR scheduler serves the classes in rounds. Each class C i is allocated a quantum of Q Ci bytes. In Figure 2, a quantum of 198 bytes is considered for each class. DRR scheduler maintains a deficit counter per class, that represents the number of bytes (a.k.a credit) that an active class is allowed to transmit each time it is selected by the scheduler. Initially, the deficit ∆ Ci for all the classes is 0. Each time a class C i is selected, its credit is set to ∆ Ci + Q Ci . Then, C i can transmit frames as long as its queue is not empty and its credit is larger than the head-of-line frame in its queue. On each transmission of a frame, the credit is reduced by the frame size. If the queue becomes empty, the remaining credit is discarded, otherwise, it is preserved in ∆ Ci . Then the next class is selected to be served.

v 12 v 13 v 1 v 17 v 21 v 2 v 14 v 18 v 20 v 6 v 3 v 7 v 9 v 10 v 4 v 8 v 11 v 5 v 16 v 1 ...v 21 S 2 v 15 v 19 ..
In Figure 2, we assume that C 1 is selected first. It gets a credit of 198 bytes (its quantum value). Frame from v 1 is first in the queue and it is transmitted, since its size (99 bytes) is less than the available credit. Since the remaining credit of 99 bytes is not enough for the transmission of next frame (v 2 ) in C 1 , it is preserved in ∆ C1 to be utilised in the next round. Therefore, the scheduler moves to the next active class C 2 which also gets a credit of 198 bytes. It allows the transmission of v 7 frame but not v 6 one and the deficit is 99 bytes. A similar scenario occurs in C 3 that allows transmission of v 14 . In C BE , the first two frames from v 22 are in total 198 bytes which is equal to its credit. Thus they are transmitted and the deficit is 0. In the next round, C 1 gets a credit of 99 (its deficit) + 198 (its quantum) = 297 bytes. C 1 consumes 199 bytes for the transmission of v 2 and v 3 frames. Since C 1 queue is now empty its deficit is set to 0. Similarly, C 2 and C 3 also get 297 bytes of credit sequentially, which allows transmission of v 6 , v 8 v 16 and v 15 leaving deficit of 98 bytes and so on.

In order to allow a class C x to be served at least once in each round its quantum cannot be less than its maximum frame length l max Cx , so

Q Cx ≥ l max Cx (1)
Therefore each class with critical traffic can be assigned the bandwidth it needs to meet the deadlines of its traffic. The remaining bandwidth (in each round) is available for noncritical flows and they do not have to wait until there is no more pending critical traffic. Several classes can be reserved for critical flows, making it possible to treat differently the flows with different deadlines.

In contrast to WRR [START_REF] Katevenis | Weighted round-robin cell multiplexing in a general-purpose ATM switch chip[END_REF] that shares bandwidth, based on number of frames (without considering their lengths), DRR allows fair sharing of bandwidth among variable length flow frames. Moreover in DRR scheduler, if a flow experiences a deficit of service due to insufficient credit in a given round then this deficit is compensated in the next round.

A WCTT analysis is mandatory in order to guarantee that critical flows always respect their deadline. Such an analysis is presented in the next paragraph.

A. DRR WCTT analysis

The WCTT analysis for DRR was proposed in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] and optimised for AFDX in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. Both approaches are based on NC and are now summarised.

The NC is a mathematical framework, based on the (min, +) algebra, applied to guaranteed service networks in [START_REF] Boudec | Network Calculus: a theory of deterministic queuing systems for the internet (Book)[END_REF] to compute guaranteed backlog and delay bounds. The delay computations are based on piecewise-linear curves. In NC, the traffic and network elements are represented by arrival curves and service curves respectively.

Based on [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF], in a switch deploying DRR scheduler, the worst-case delay D h i for a flow v i of C x at h is upper bounded by the maximum horizontal difference between the cumulative curve (α h Cx ) of the arrival curves of C x flows in h and the service curve β h Cx offered to C x . These curves are shown in Figure 3 (left).

Since a DRR scheduler shares the network bandwidth among all the classes, each class C x gets only a fraction ρ h Cx of the link rate R and experiences a scheduler latency Θ Cx . Thus C x service is a sequence of periods where it is being served at full rate and periods where it is waiting for its turn. It leads to a staircase curve, as shown in Figure 3 (left). Such a staircase curve can lead to high mathematical complexity in delay computation. Therefore, the residual service curve for C x at h is derived in [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] as an under-approximation of this staircase curve which is given as

β h Cx (t) = ρ h Cx × [t -Θ h Cx -sl] + (2)
The bandwidth fraction ρ h Cx depends on the quantum assigned to C x and the sum of quantum assigned to all the classes and is given by: Cx of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] can be too pessimistic as it does not make any assumption on the volume of competing traffic from other classes. It assumes that the competing classes C y (y = x) remain active during the active period of C x flows and they consume their maximum credit in each DRR service round. Hence the residual service for C x is β Cx (which depends only on Q x and sum of quantum assigned to all the classes but not on the distribution of this sum between these classes). It might not be the case. In some cases, the traffic in C y can be too low to remain active and to consume their full credit during the active period of C x . So, the residual service of C x can be much higher (illustrated in Figure 3 (right)) and it is not independent of the quantum distribution between competing classes. Thus [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] optimises the computation by quantifying the maximum amount of traffic of each competing class within the delay bound computed by [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]. Therefore the optimised delay in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] is obtained by subtracting the time required to transmit the overestimated traffic assumed by β h Cx in the duration [0, D h i ]. This optimised delay is given by

ρ h Cx = Q h Cx 1≤j≤n Q h j × R (3) bits t sl α h Cx β h Cx ρ h Cx ≥ ρ h Cx R D h i,opt End of C y service R ρ h Cx bits D h i t sl α h Cx Θ h Cx β h Cx Θ h Cx
D h i,opt = D h i - n h y=1,y =x over-estimated portion of C y traffic R (4
) And the end-to-end delay upper bound of v i can be computed by:

D ET E i,opt = h∈Pi D h i,opt (5)
where P i is the path followed by v i . Since [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] takes into account the volume of traffic from competing classes and not an over-approximated traffic, the obtained delay bound is tighter. For more information on D h i,opt computation, readers may refer to [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF].

B. Problem statement

As briefly explained earlier, DRR scheduling allows to differentiate critical flows with different deadlines by assigning them to different classes. Then the bandwidth assigned to these critical classes can be tailored to the minimum value which guarantees that no deadlines are missed. All the remaining bandwidth is available for non-critical flows. The idea is to maximise the quantity of additional flows that can be served before critical flows such that the delay of critical flows is increased but do not exceed the deadline.

Two points have to be addressed:

• distribute critical flows among critical classes,

• find the best possible quantum assignment for these classes, i.e. one that maximises the bandwidth available for non-critical flows while ensuring no missed deadlines for critical ones. The second point has been addressed in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. However, the proposed solution is based on the basic NC approach of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]. In the next section, we present an extension which is based on the optimised NC approach of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. Such an extension is not trivial, since the quantum assignment in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] is based on assumptions that do not hold for the NC approach of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF].

We address the first point in Section IV. This flow distribution has a big impact on results, as it will be shown with the results in Table V.

III. QUANTUM ASSIGNMENT

First we recall the existing solution proposed in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. Then we show how it can be extended in order to use the optimised WCTT analysis of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. The goal is to significantly increase the residual service of non-critical class C BE .

A. Overview of the existing quantum assignment approach

The algorithm in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] is based on two fundamental properties:

• The worst-case delay computation by NC of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] is independent of the quantum distribution among competing classes (Lemma 3.1 in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]). It means that, in order to compute the end-to-end delay bound in C x , only Q Cx (a portion of Q) and Q (the sum of quantum distributed among all the classes) is needed. • The part of Q available to the non-critical class C BE is higher for the smaller values of Q provided that each critical class is assigned the minimum quantum which guarantees that no deadline is missed, based on the WCTT analysis of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] (Lemma 3.2 in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]). Based on these properties the basic idea of the proposed algorithm is to give minimum (yet sufficient) fraction of quantum sum to critical classes so that the residual quantum of the non-critical class is maximised. The basic parts of this algorithm are presented in Algorithm 1.

The process starts with an initial value InitVal for the sum of quanta Q (line 1). The minimum portion Q Ci (called valid quantum) of Q required by each critical class C i is computed. The constraint is that no C i frame misses its deadline (line 5, function QUANTUMMIN).

The process stops as soon as the unused portion QResid of Q is smaller than the computed Q Ci value (line 6-7) or all the critical classes have been treated (line 4-8). In the latter case, the unused portion QResid is assigned to non-critical class C BE (line 9) and a solution has been obtained. The solution is improvable (line 10) if the quantum in each class is greater than the minimum possible value, i.e. its maximum frame size (equation 1). The improved Q is obtained (line 11) by dividing it by a factor representing the smallest ratio of the quantum of a class to its maximum frame size.

The outcome of this algorithm is the distribution of the smallest Q among all the classes such that every critical flow respects its deadline and the residual service of non-critical frames is maximised.

Algorithm 1: Quantum assignment algorithm in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] input : Initial sum of quanta (ValInit : Integer) output: Let us illustrate the operation of this algorithm on the network example given in Figure 1 with flows divided into 3 critical classes and 1 non-critical class as shown in Table II. The maximum service rate at each output port is R = 100 bits/µsec.

Per class quantum (Q C1 , Q C2 . . . : Integer) Data: Remaining quantum (QResid) 1 Q ← V alInit ; 2 while true do 3 QResid ← Q ; 4 for each critical class C i do 5 Q Ci ← QUANTUMMIN(C i , Q)); 6 if Q Ci > QResid then 7 terminate; 8 QResid ← QResid -Q Ci ; 9 Q C BE ← QResid;
Initially, let us assume a sum of quanta Q = 741 bytes. The process starts with critical class C 1 whose deadline is 300 µsec. The minimum quantum needed by C 1 to meet all its deadline is determined, thanks to a binary search between the maximum possible value (741 bytes) and the maximum C 1 frame size. We get Q 1 = 270 bytes.

The minimum quanta for C 2 and C 3 are determined with a similar process. We get Q C2 = 106 bytes and Q C3 = 100 bytes. Thus, the residual quantum for non-critical class is Q C BE = 741 -(270+106+100) = 265 bytes, which is 265 741 × 100 = 35.76% of Q.

Since a valid quantum distribution for each class is obtained and at least one class (C 3 ) receives a quantum equal to its maximum frame length, the algorithm returns the quantum distribution Q C1 = 270, Q C2 = 106, Q C3 = 100 and Q C BE = 265 as its solution.

B. Improved quantum assignment

As mentioned earlier, [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] relies on WCTT analysis based on NC approach of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] which is shown to be pessimistic and optimised in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF].

Due to this pessimism, the delay bounds computed in Algorithm 1 are much higher than the actual delays in the network. Delay bounds on the example in the previous paragraph are given in Table III. For the quantum distribution Q C1 = 270, Q C2 = 106, Q C3 = 100 and Q C BE = 265 bytes resulting from Algorithm 1 the maximum end-to-end delays, computed by NC of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] D i,opt End-to-end delays (in µsec) obtained by optimised NC from [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] Function QuantumMin in Algorithm 1 stops decreasing the quantum Q Cx for a given critical class C x when its computed delay bound (based on NC of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]) is near (and smaller) to its deadline. Since this delay bound can be pessimistic, there remains a possibility to decrease the quantum share for C x (eventually increasing the residual quantum share for C BE ) while still respecting its deadline.

However, the optimised NC approach cannot be directly integrated in Algorithm 1. As mentioned earlier, the implementation of the function QuantumMin in Algorithm 1 is based on the assumption that the WCTT analysis is carried out independently for each class, i.e. in order to compute the endto-end delay bound in a class C x , only Q Cx (a portion of Q) and Q (the sum of quantum distributed among all the classes) is needed. This assumption does not hold for the optimised NC approach of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. In order to compute tight delay bounds, [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] takes into account the impact from competing classes, which is affected by the distribution of Q in these classes.

Therefore, we propose an extension to Algorithm 1 which takes the quantum distribution result from Algorithm 1 and improves it by deploying the NC approach from [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. The main idea is to improve the quantum share of the non-critical class by decreasing the quantum of critical classes and/or increasing the quantum of non-critical class until the computed delay bound (based on NC in [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]) in critical classes is near (and smaller) to their respective deadlines.

Before giving the algorithm, he process is illustrated on the example in Figure 1 with flow classification in Table II.

1) Process overview: Table IV summarises the steps of the process. It starts with the quantum assignment computed by the algorithm in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. Using the optimised WCTT analysis of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF], the maximum end-to-end delays for critical classes are smaller than those which are considered by the algorithm in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] (as shown in Table III). Therefore there is a margin for each critical class, which is the differences between this optimised end-to-end delay bound and the deadline. These margins are listed in Table IV. For instance, for class C 1 , it is 18.129% (between 245.612 µs and 300 µs). This initial quantum assignment reserves 35.76% of the bandwidth to noncritical flows.

The first step of the process consists in decreasing quanta associated with critical classes as much as possible, keeping the quantum assigned to non-critical class. It comes to find the smallest quanta for critical classes such that, for each critical class, the end-to-end delay bound computed with the optimised WCTT analysis is not greater than the deadline and the quantum is at least the maximum frame size. For the considered example, quanta for C 1 and C 2 are reduced to 199 and 100 bytes, while quantum for C 3 is not changed. They cannot be further decreased since they correspond to the minimum frame size (for classes C 2 and C 3 ) or it would lead to a delay bound greater than the deadline (class C 1 ). Now the non-critical class gets 39.91% of the bandwidth.

The second step consists in increasing, as much as possible, the quantum assigned to the non-critical class while keeping the quanta assigned to critical ones. This step gives a quantum of 311 bytes which leads to 43.8% of the bandwidth.

At this point, the critical class quanta cannot be decreased. However, margins for class C 2 and C 3 are large (around 29% and 41%). Therefore, in the third step, the quantum of class C 1 (the one with no margin) is increased in order to be able to increase the quantum for non-critical class. It gives 398 bytes for C 1 quantum. Now, the bandwidth for the non-critical class is decreased to 34.21%. However, since no critical class has a margin close to 0, the second step can be applied again (as a fourth step). It gives 554 bytes for non-critical class quantum, corresponding to 48.09% of bandwidth. These steps (second to forth) gives a gain of around 5% by increasing quanta of classes C 1 and C BE .

A similar process can be applied again, i.e. increase the quantum of class C 2 (the critical class with the smallest margin) to 125 and then the quantum of C BE to 624. The new bandwidth for non-critical class is 50.04%.

Since all margins are small, there is no point to apply the same process again. However, the quanta for the critical classes can still be decreased, down to the situation where decreasing them more would lead to a delay bound greater than the deadline or a quantum smaller than the maximum frame size. At the end, the bandwidth for the non-critical flows is 54.97%.

The improvement from the existing approach in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] is significant (from 35.76% to 54.97%). We argue that the obtained quantum assignment should be close to optimum, assuming the WCTT analysis of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. Indeed, margins for critical classes are small (less than 5%) and the quantum cannot be smaller for class C 3 (largest margin), since it is the maximum frame size. We recall that it has been shown in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] that smaller values of sum of quanta Q lead to a higher bandwidth for C BE .

2) Algorithm: Algorithm 2 implements the process described in the previous paragraph. Every WCTT computation is based on the optimised NC approach of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. Three operations have to be executed one or several times.

• REDUCETOMIN(Q Ci ) decreases quantum assigned to critical class C i as much as possible, while keeping the quantum of the non-critical class. The implementation is based on a binary search between the current value of Q Ci and its minimum possible value, i.e. the maximum frame size of C i traffic. • INCREASETOMAX(Q Cn )) increases the quantum associated with the non-critical class as much as possible while keeping the quanta assigned to critical classes. The value of Q Cn is doubled as long as it does not lead to missed deadlines for critical classes. As soon as it is the case, a binary search is implemented between the reached value and the previous one. • INCREMENTSMALLESTDIFFERENCE() increases the quantum assigned to the critical class with the smallest margin (so that the quantum associated with the noncritical class can be increased furhter). The quantum of the critical class C i with minimum margin is doubled. If it does not lead to missed deadlines for other critical classes, the new value is kept as quantum for C i . Otherwise, a binary search is implemented between the new value and the initial one. The algorithm takes the quantum distribution from Algorithm 1, i.e. Q C1 , . . . Q Cn , as input.

First, the quantum Q Ci for each critical class C i (i = n) is reduced so that the corresponding end-to-end delay bound remains less than the delay constraint in C i and the quantum is at least the maximum frame size (line 2-3). The resulting quantum values are stored in res.

Next, the maximum quantum Q Cn for non-critical class C n is computed (line 6-11). This step is divided in two parts. In the first part, the quantum Q Cn is increased while the end-toend delay bounds in all the critical classes remain less than their respective delay constraint in C i . In the second part, the quantum of the critical class with the smallest margin is increased.

Both parts are repeated until the margin for each critical class is reduced below a value (line 8-9). The whole process is repeated until Q Cn reaches a value which cannot be further improved (line 12-13).

IV. FLOW DISTRIBUTION Up to now it has been considered that critical flows have been distributed in classes and the proposed quantum assignment maximises the bandwidth available for non-critical flows with no missed deadlines for critical ones. In this section, we show that the distribution of critical flows in classes has a significant impact on achievable bandwidth for non-critical ones. Finding an optimal distribution by exhaustive search is intractable, even for configurations with limited number of flows (e.g. configuration in Figure 1 with 21 critical flows). Thus we identify flow features which have to be taken into account in order to propose a flow distribution heuristic.

Let's come back to the network configuration in Figure 1 flows in different classes is not always beneficial. Indeed, F D 1 (one critical class) leads to 32.2% of bandwidth for non-critical flows and is better than F D 2 (two critical classes, 29.65% of bandwidth for non-critical flows), but worse than F D 3 (three critical classes, 45.58% of bandwidth for non-critical flows). Actually, two main factors impact the results:

• the difference between flow deadlines within each class: the overall deadline of a class (input of quantum assignment) is the smallest deadline among all the flows in the class. It comes to consider that all the flows in the class have to respect this smallest deadline. As soon as some flows in the class have a much higher deadline, the result is to significantly increase the required bandwidth for the class, leading to a reduction of the bandwidth available to non-critical flows. Thus, the difference between flow deadlines within a class should be as small as possible.

• the number of classes: increasing the number of classes increases the scheduler latency computed by NC approach, since this computation considers the worst case for the deficit of competing classes (quantum plus maximum frame size minus one byte). Moreover, the residual bandwidth that can be provided to any class decreases since the total bandwidth has to be shared among more classes in each DRR scheduling round. These impacts can be illustrated on the results in Table V. Class C 1 in F D 1 includes flows with very different deadlines (from 300 µs to 950 µs). Deadline variations are similar for F D 2 (from 300 µs to 890 µs for C 1 , from 310 µs to 950 µs for C 2 ). Therefore F D 2 is mainly impacted by the increased scheduler latency induced by the additional critical class, leading to a reduced bandwidth for non-critical flows. Conversely, the deadline variation within classes is smaller for F D 3 (from 300 µs to 620 µs for C 1 , from 390 µs to 910 µs for C 2 , from 600 µs to 950 µs for C 3 ) and the benefit more than compensate for the increased scheduler latency induced by the additional critical classes. In general, the impact of deadline variation within classes is much higher that the cost of scheduler latency. This is the case for F D 3 and the same trend has been observed in all conducted experiments.

Based on this observation, we propose the following heuristic to efficiently distribute these flows in different classes so that their bandwidth requirement is reduced and the residual bandwidth for non-critical class is increased. The principle is to group the flows with similar delay constraints in the same class so that they can be assigned a quantum which allows them to be served in a delay not far from their deadlines.

• Critical flows are sorted by increasing deadlines,

• We assume that the maximal number of classes is known. This is a reasonable assumption, since each output port of the QoS aware AFDX switch implementing DRR will have a fixed number of queues, thus classes. Let us illustrate this algorithm on the network example in Figure 1, assuming four classes (n = 4). Critical flows (v 1 to v 21 ) are sorted by increasing deadlines (actually the order in Table I). The n -2 most significant increment in deadlines (i.e. potential class boundaries) are determined by decreasing values and corresponding potential class boundaries are stored in BList (line 2): in the example, between v 12 and v 13 (890-660 = 230 µs), then between v 4 and v 5 (590-390 = 200 µs). Then each potential boundary is considered (line 5-13). In the first iteration, the boundary between v 12 and v 13 is considered. It distributes flows in two classes: C 1 gets v 1 to v 12 and C 2 gets v 13 to v 21 (line 8). Quanta for the classes are computed by our improved quantum assignment algorithm (line 9). It gives a first solution with two critical classes. In the next iteration, the same process is applied with the boundary between v 4 and v 5 leading to three classes (C 1 gets v 1 to v 4 , C 2 gets v 5 to v 12 and C 3 gets v 13 to v 21 ). It leads to a second solution with three critical classes, which, in the example, gives more bandwidth for non-critical flows than the first solution. Therefore, this second solution is kept (line 10-13). The process stops, since we assume no more than three critical classes in our example.

The resulting flow distribution F D 4 is shown in Table V. It clearly outperforms previous flow distributions F D 1 , F D 2 and F D 3 with more than 56% of bandwidth for non-critical flows. For instance we have 32% of this bandwidth when there is a single critical class (F D 1 ).

V. EVALUATION In this section, the two solutions proposed above are evaluated on an Airbus A380 aircraft "like" industrial network configuration. The gain introduced by Algorithm 2 is also compared to the existing solution of [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF].

The given network configuration includes 96 end-systems interconnected by 8 switches forwarding 984 flows on 6276 paths (multi-cast VL). Frame lengths are between 84 and 1535 bytes and BAGs are between 2 and 128 ms.

These flows are distributed in 3 critical classes (C 1 -C 3 ), based on the solution proposed in Section IV, as shown in Table VI. Ten additional flows are arbitrarily introduced, characterised by non-critical class C BE , which share the path with each critical flow on at least one switch output port. The quanta computed by Algorithm 2 as well as the algorithm in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF])) are shown in Table VI, where Initial corresponds to [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. These quanta are then used to compute the worst-case end-to-end delays based on optimised NC approach of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]. For comparison, the results are plotted in increasing delay order (per class) in Figure 4. It can be observed from Figure 4 that the improved quanta (by Algorithm 2) bring the delay bounds in all the critical classes closer to their respective deadlines, which allows the residual quantum share for non-critical class to increase to 30.89% as compared to the initial value of 9.87% (Table VI).

VI. CONCLUSION

In this paper, a QoS-aware AFDX network is considered where each output port is managed by a DRR scheduler. This network is shared between critical (avionic) and non-critical (additional) flows. We address the problem of distributing flows among traffic classes (n-1 critical classes, 1 non-critical one) and compute the quanta which ensure the delays less than the deadlines in critical flows and maximise the bandwidth for the non-critical flow. The approach of [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] is improved in two ways. First, the quantum assignment algorithm is redesigned to exploit the optimised WCTT analysis of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] ( [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] uses the basic WCTT analysis of [START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF], since it makes assumptions which do not hold with the WCTT analysis of [START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF]). Second, a heuristic is proposed for the distribution of critical flows in classes.

The solution presented in this paper outperforms the one in [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF]. On a realistic case study, the bandwidth for non-critical flows guaranteed by [START_REF] Soni | Quantum assignment for QoSaware AFDX network with deficit round robin[END_REF] is less than 10% and it is more than 30% with the new approach.

For future work, other policies are envisioned for AFDX, e.g. WRR [START_REF] Soni | WCTT analysis of avionics switched Ethernet network with WRR scheduling[END_REF], that also requires a configuration solution.

Fig. 1 .

 1 Fig. 1. AFDX Network Example

Fig. 3 .

 3 Fig. 3. Delay upper bound computation in NCIt has been shown in[START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] that the computation of delay D h i based on β hCx of[START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF] can be too pessimistic as it does not make any assumption on the volume of competing traffic from other classes. It assumes that the competing classes C y (y = x) remain active during the active period of C x flows and they consume their maximum credit in each DRR service round. Hence the residual service for C x is β Cx (which depends only on Q x and sum of quantum assigned to all the classes but not on the distribution of this sum between these classes). It might not be the case. In some cases, the traffic in C y can be too low to remain active and to consume their full credit during the active period of C x . So, the residual service of C x can be much higher (illustrated in Figure3(right)) and it is not independent of the quantum distribution between competing classes. Thus[START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] optimises the computation by quantifying the maximum amount of traffic of each competing class within the delay bound computed by[START_REF] Boyer | Deficit Round Robin with Network Calculus[END_REF]. Therefore the optimised delay in[START_REF] Soni | Optimizing Network Calculus for Switched Ethernet Network with Deficit Round Robin[END_REF] is obtained by subtracting the time required to transmit the overestimated traffic assumed by β h Cx in the duration [0, D h i ]. This optimised delay is given by

Algorithm 2 : 5 previousQ 7 INCREASETOMAX

 257 Improved quantum assignment algorithm input : Quantum distribution from Algorithm in [3] : Q C1 . . . Q Cn (Integer) output: Per class quantum: res{Q C1 . . . Q Cn } (array) 1 while true do 2 for i = 1 to (n -1) do // Minimise C i service 3 REDUCETOMIN(Q Ci ); 4 res ← {Q C1 . . . Q Cn }; Cn ← Q Cn ; 6 while true do // Maximise Cn service

Fig. 4 .

 4 Fig. 4. Results on industrial AFDX configuration

  and consider the three following flow distributions for critical flows (v 1 to v 21 ): FD 1 : a single critical class C 1 with flows v 1 . . . v 21 , FD 2 : two critical classes C 1 and C 2 with v 1 , v 6 , v 12 , v 13 in C 1 and the other critical flows in C 2 , FD 3 : three critical classes C 1 , C 2 andC 3 with v 1 , v 2 , v 3 , v 8 , v 9 in C 1 , v 4 , v 5 , v 7 , v 10 , v 11 , v 12 , v 15 , v 16 in C 2and the other critical flows in C 3 . In each flow distribution case, our improved quantum assignment algorithm is applied and the corresponding results are shown in TableV. These results show that distributed critical

  , v 5 , v 7 , v 10 , v 11 , v 12 , v 15 , v 16

			TABLE V
	FLOW DISTRIBUTION IN CRITICAL CLASSES AND THE RESULTS OF
			QUANTUM ASSIGNMENT ALGORITHM
			Flows	DL	Q C i	Q C BE
	FD 1	C 1	v 1 -v 21	300	219 (67.8%)	104 (32.2%)
	2 FD	C 1 C 2	v 1 , v 6 , v 12 , v 13 v 2 -v 5 , v 7 -v 11 , v 14 -v 21	300 310	100 (12.84%) 448 (57.51%)	231 (29.65%)
		C 1	v 1 , v 2 , v 3 , v 8 , v 9	300	199 (24.12%)
	FD 3	C 2	v 4 390	150 (18.18%)	376 (45.58%)
		C 3	v 6 , v 13 , v 14 , v 17 , v 18 , v 19 , v 20 , v 21	600	100 (12.12%)
		C 1	v 1 -v 4	300	249 (23.29%)
	FD 4	C 2	v 5 -v 12	590	112 (10.48%)	608 (56.88%)
		C 3	v 13 -v 21	890	100 (9.35%)
	Units: Deadline (DL) in µsec. Quantum distribution in bytes

•

  Based on the number n -1 of critical classes, the n -2 most significant increments in the flow deadlines are identified as the boundaries of the classes. The process is implemented by Algorithm 3.

	Algorithm 3: Flow distribution
	2 BList ← GETSIGNIFICANTINCREMENTS(VL);
	3 previousQL ← empty;
	4 i ← 0;
	5 while size(res) < n-2 and i < size(BList) do
	6	i ← i + 1;
	7	res.append(BList[i]);
	8	DISTRIBUTEFLOWS(res, VL);
	9	QL ← COMPUTEQUANTUMDISTRIBUTION();
	10	if ISIMPROVED(QL, previousQL) then
	11	previousQL ← QL
	12	else
	13	res.remove(BList[i]);

input : Maximum number of classes : n output: List of critical class boundaries : res Data: Critical Flows : VL (list), Qunatum distribution QL (list), Critical class boundaries : BList (list) 1 SORTFLOWS(VL);

  BAG in msec. Frame lengths in bytes. Deadline in µsec.

			TABLE VI
	FLOW DISTRIBUTION AND QUANTUM ASSIGNMENT
		C 1	C 2	C 3	C BE
	Flows	280	229	475	10
	(paths)	(1681)	(1488)	(3107)	(501)
	BAG	2-16	32	64-128	-
	Frame lengths	84-1497	84-1371	84-1535	84-934
	Deadline	13000	39000	52000	-
	Quantum distribution (in bytes)
	Initial	6057	1640	1535	1012 (9.87%)
	Algo 2	8130	1943	1535	5190 (30.89%)
	Units: