Sheikh • Ahmad Al

Olivier Brun
email: brun@laas.fr

Maxime Chéramy
email: mcheramy@laas.fr

Pierre-Emmanuel E Hladik
email: pehladik@laas.fr

A Al Sheikh
email: aalsheik@laas.fr

Optimal Design of Virtual Links in AFDX Networks

Keywords: AFDX, Virtual Link, Bandwidth consumption, Route optimization

The Avionics Full Duplex Switched Ethernet (AFDX) backbone constitutes one of the major technological breakthroughs in modern avionic architectures. This network is based on routing Ethernet frames through isolated data tunnels referred to as Virtual Links (VL). VLs can be thought of as multicast trees, each serving for data transmission between one and only one end of the network to several others. Multiple VLs are deployed for exchanging data between avionic systems with a reserved amount of bandwith.

In this paper, we propose different methods to define VL characteristics and to route VLs in the network while minimizing the maximum utilization rate of the links. The proposed methods provide the basis for a more efficient design of the VLs, and have to be completed later on by the verification of the worstcase network latencies. The industrial applicability is shown on experimental results and on a representative benchmark.

Resource Allocation Problems in IMA Architectures

Nowadays, aircrafts have to maintain high standards of safety and reliability in a high stress environment whilst integrating many computers, sensors, actuators, and control and display units [START_REF] Spitzer | Digital avionics systems[END_REF][START_REF] Spitzer | The avionics handbook[END_REF][START_REF] Authority | Software considerations in airbornes y s t e m sa n de q u i p m e n tc e r t ification[END_REF][START_REF]Certification considerations for highly-integrated or complex aircraft systems[END_REF]. Traditional avionic systems have been built according to a federated architecture ("one function -one computer"), which leads to numerous equipment boxes, one for each subsystem.

With the ever increasing number of embedded avionic functions, the avionic industry has had to abandon this design approach in favor of the Integrated Modular Avionics (IMA) [START_REF] Watkins | Transitioning from federated avionics architectures to Integrated Modular Avionics[END_REF]. IMA architectures allow the execution of avionic functions using shared computing and communication resources while respecting hard segregation constraints in order to avoid fault-propagation between applications.

At the computing level, the processing units, called modules, can host several avionic applications of different criticalities and execute them independently. Segregation constraints are enforced using complete partitioning, not only on a functional basis, but also with respect to space (spatial partitioning) and time (temporal partitioning). A partition is therefore a program unit of an application that can execute only within strictly periodic time intervals and that can only access a statically allocated memory space.

At the communication level, the Avionics Full-Duplex Switched Ethernet (AFDX) network enforces the segregation constraints by replacing the pointto-point cabling used in federated architectures with Virtual Links (VL) [START_REF]Aircraft data network, Part 7: Avionics Full Duplex Switched Ethernet (AFDX) Network[END_REF]. Each VL is dedicated to a single communication flow between a source partition and multiple receivers and uses a statically configured route in then e twork. It can be thought as a permanently defined virtual circuit between the source and the receivers with guaranteed timing and bandwidth allocation on the network. Traffic-shaping is used to regulate the time between two consecutive transmissions on the network by the same VL, thus controlling the bandwidth it uses, and providing traffic at a constant and deterministic rate.

Primary benefits of IMA include reduction of the weight, the power consumption and the overall complexity of the physical architecture, as well as providing greater flexibility in software design and shortened design-cycle times. However, the transition from federated to IMA architectures has given rise to complex resource allocation problems. We can distinguish two main types of resource allocation problems:

-The first is related to the multiprocessor scheduling of the strictly periodic partitions on the processing modules. Indeed, as partitions allocated to the same module share the overall execution time, the system designer has to ensure the temporal segregation of these partitions by designing ap r o p e r periodic schedule. -The second is related to the design of the Virtual Links. Indeed, data exchanges between partitions located on different modules have to be tunneled through VLs, and thus a dedicated VL has to be configured fore a c h communication flow. This amounts to selecting some transmission parameters, which have an impact on the timing properties and on the bandwdith allocation of the VL, in addition to finding a multicast path between the source and the receivers.

In a previous work [START_REF] Al-Sheikh | Strictly Periodic Scheduling in IMAbased Architectures[END_REF], we have exposed a method to allocate and schedule partitions on the processing modules. The present paper is the logical progression from this previous work and is focused on the design of VLs in AFDX networks, assuming a predefined multiprocessor scheduling of the avionic partitions.

Design of Virtual Links

Due to the complexity of the overall problem, the design of an IMA platform usually follows a (suboptimal) decomposition approach (refer to Figure 1). In this approach, the design of the virtual links is performed once the avionic partitions have been scheduled on the processing modules of the platform. A dedicated VL implementing its own traffic shaper has to be configured for each data exchange between partitions located on different modules. This basically requires that the system integrator answers the following questions:

-What are the VLs to be configured ? -How to set the transmission parameters of the VLs ? -How to route the VLs in the AFDX Interconnect ? Let us first consider the second question. Two key parameters areu s e dt o configure a VL. The first one is the Bandwidth Allocation Gap (BAG), i.e, the minimum time interval between the starting bits of two successiveA F D X frames, assuming zero jitter. In other words, the BAG defines the maximum frequency at which frames are sent in a VL. This parameter can take only discrete values that are powers of 2 from 1 to 128 ms. The second parameter is the Maximum Frame Size (MFS), i.e, the maximum size, in bytes, of the transmitted Ethernet frames for the VL. MFS is in the range from 64t o1 5 1 8 bytes. Together, these parameters allow to limit the transmission rate of a VL in order to prevent its traffic from interfering with the traffic of other VLs.

!"#$%&'()&*+),&'+%&'()-.&$#"'/)+(01'2-$2"* 3.."1&$()&*+)01,(+4.()-&'$2$2"*0)"*)/"
For each message sent by a partition to receivers on other modules,t h e system integrator has to set the BAG and MFS values of the VL dedicated to this message, taking into account application-level requirements in the form of a maximum delivery time and a message size. Note that a major difficulty to guarantee the delivery time of a message is that it depends on the network traversal time, which in turn depends on the number of configured VLs, on their transmission parameters and on how they are routed in the network. However, as observed by Lauer et al. in [START_REF] Lauer | Latency and freshness analysis on IMA systems[END_REF], "the upper bounds on worst-case traversal time [...] are small compared to periods and duration of the functions" (the experimental results on industrial systems reported in [START_REF] Charara | évaluation des performances temps réel de réseaux embarqués avioniques[END_REF][START_REF] Scharbarg | A Probabilistic Analysis of End-To-End Delays on an AFDX Avionic Network[END_REF] lead to the same observation). In practice, the worst-case network traversal time is in the order of few ms, whereas the maximum delivery times of the messagesa r e comparable to partition periods, and are thus in the order of several tens or hundreds of ms. A pragmatic approach to VL design is therefore to assume an upper bound ∆ on the worst-case network traversal time, to design the VL using maximum delivery times decreased by ∆,an dt h ent oc h ec kap o s t e r i o r i that this bound is satisfied.

There are usually several feasible values of the BAG and MFS parameters that allow to guarantee the message delivery time. It is therefore convenient to use the feasible BAG and MFS values minimizing the bandwidth consumption since this will give more flexibility to add future VLs. For instance, to transmit a 100 bytes message within a maximum delivery time of 50 ms, it is possible to use a VL with (1) BAG=8 ms and MFS=64 bytes (17 bytes payload), or with (2) BAG = 32 ms and MFS=147 bytes (100 bytes payload). In these two options the temporal requirement is respected, but the bandwidth is 64 Kbps for the first option and 36.75 Kbps for the second. Although trivial, this example clearly shows the influence of the VL transmission parameters on the quality of a design.

We now turn to the question of what VLs have to be created. A dedicated VL has to be created whenever a source partition sends a message to receivers located on other modules. It may however occur that a source partition sends several messages to the same set of receivers. In this case, the system integrator can choose to use a separate VL for each message, or to aggregate all data into a single message and thus to use a single VL, and he can even choose to use an intermediate strategy. As we show in Section 3, the choice made by the system integrator can have a strong influence on the bandwidth consumption.

Finally, once the VLs are defined, the system integrator has to route them in the AFDX network. The routing problem amounts to finding one and only one multicast tree between the source and the destinations of each VL whilst guaranteeing that the amount of reserved bandwidth on each link is lower than its capacity. Since an upper-bound on the worst-case network traversal time has been assumed, message delivery times are guaranteed by design and it is therefore not suitable to minimize the network latency. A more appropriate design goal is to maximize the minimum residual capacity of the network links since ensuring a fair load distribution among network links eases the introduction of new VLs, or the modification of existing ones.

Related work

Although many works have been devoted to the design of avionic architectures, the problems addressed in this paper have been largely overlooked. To the extend of our knowledge, there is no previous work on how to define the VLs. All previous works regarding VLs focus on the analysis of the time required to transmit a frame through the network. Different methodsh a v ebe e n proposed, such as Network Calculus [START_REF] Charara | Methods for bounding end-to-end delays on an AFDX network[END_REF], probabilistic analysis [START_REF] Scharbarg | A Probabilistic Analysis of End-To-End Delays on an AFDX Avionic Network[END_REF], trajectory approach [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF], ILP [START_REF] Lauer | Latency and freshness analysis on IMA systems[END_REF], etc.

Although it seems that there is no previous work on the VL routing problem, similar problems have been considered for telecommunication networks. In the special case where we only have one VL, the problem becomes related to the computation of a minimum cost tree, known as a Steiner tree [START_REF] Gilbert | Steiner minimal trees[END_REF][START_REF] Hwang | Steiner tree problems[END_REF]. This Steiner tree problem is NP-complete [START_REF] Seok | Explicit multicast routing algorithms for constrained traffic engineering[END_REF]. Another special case is obtained when each VL has a single destination, yielding a single-path routing problem. This problem is also known to be NP-complete [START_REF] Pióro | Routing, flow, and capacity design in communication and computer networks[END_REF]. Not much propositions can be found for routing several multicast demands ato n c e .T h e authors in [START_REF] Seok | Explicit multicast routing algorithms for constrained traffic engineering[END_REF] look into finding multicast trees for multicast traffic requests that arrive one-by-one, while minimizing the maximum link utilization. Many others also propose multiobjective multicast routing algorithms for a single multicast traffic request in an already loaded network [START_REF] Crichigno | A multicast routing algorithm using multiobjective optimization[END_REF][START_REF] Zitzler | Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. evolutionary computation[END_REF].

Contribution

Our contribution is threefold. We first show how to set the BAG and MFS parameters of a VL so as to minimize the reserved bandwidth while transmitting the data within their maximum delivery time. We next consider the case where a source partition has to send multiple messages to the same set of receivers. We present several closed-form results and efficient numerical algorithms for aggregating messages into super-messages so as to minimize the bandwidth consumption. Finally, we propose an exact integer-linear programming formulation of the routing problem that can be used to route thousands ofV L ss o as to maximize the minimal residual capacity of the links. All the proposed approaches allow to reduce the bandwidth consumption and thus to get more flexibility for adding new VLs or modifying existing ones. We illustrate the benefits of the proposed design approaches on a benchmark inspired from an industrial case study.

Organization

The paper is organized as follows. Section 2 is devoted to the analysis of the optimal transmission parameters to send a single message through aV L .I n Section 3, we consider the case where a source partition has to send multiple messages to the same set of receivers and analyze the optimal strategy to minimize the bandwidth consumption. Section 4 presents an exact integerlinear programming formulation to solve the routing problem. Experimental results are presented in Section 5 and some conclusions are drawn in Section 6.

2O p t i m a lT r a n s m i s s i o nP a r a m e t e r so faV L

Problem statement

We consider the transmission of a message from a source partition toas e t of destinations (located on modules other than that of the source's). Let s denote the size of the message in bytes. The message can be fragmented into n frames, each having a header of size c bytes. The maximum size of the frame's payload is f ∈ IN bytes, and it is assumed that f min ≤ f ≤ f max .I nA F D X networks, the values of these parameters are c =47b ytes,f min =17bytesand f max = 1471 bytes, so the minimum frame size is 64 bytes and the maximum one is 1518 bytes. The payload size f and the number of frames n have to be such that nf ≥ s.

The delay between the transmision of two consecutive frames is bag = 2 k ms, where k ∈{0, 1,...,7}, so that the total delay between the transmission of the first frame and that of the last frame is (n -1) bag ms. Let ∆ denote an upper bound on the time required to transmit a frame of size 1518 bytes from one point of the netwok to another. Then the total delay between the transmission of the first frame of the message by the source partition and the reception of the last frame by the destinations is upper bounded by (n-1) bag+ ∆. It is assumed that this total delay has to be lower than a given constant δ + ∆,s ot h ep a r a m e t e r sn and k have to be chosen such that (n -1) 2 k ≤ δ.

Since at most c + f bytes are transmitted in bag seconds, the total bandwidth to be reserved for this communication is bw =( c + f )/bag.T h ep r o blem amounts to finding the parameters n, f and bag such that the reserved bandwidth is minimized, while ensuring the end-to-end delay constraintofthe message delivery. The problem can thus be stated as follows,

minimize f + c 2 k (OPT) subject to (n -1) 2 k ≤ δ, nf ≥ s, f min ≤ f ≤ f max , k ∈{0, 1,...,7}, n, f ∈ IN .

Derivation of the optimal parameters

In what follows, we introduce important Lemmas and Propositions that help in deriving the optimal parameters.

Lemma 1 Problem (OPT) has a solution if and only if

s fmax ≤ 1+δ.
Proof See Appendix A.1.

In the following, we let n min = s fmax and n max =1+δ. We shall assume that n min ≤ n max and thus that the set Ω = {n min ,n min +1,...,n max } of all feasible values of n is non empty. The following proposition shows how to find the optimal parameters for the Virtual Link.

Proposition 1 Let f (n)=m a x ( s n ,f min ), k(n) = min(7, log 2 δ n-1
),

and bw(n)=(f (n)+c)2 -k(n) for n ∈ Ω.L e tn * be a minimum in Ω of bw(n), i.e., bw(n) ≥ bw(n * ) for all integers n ∈ Ω.T h e n ,(n * ,f(n * ),k(n * )) is an optimal solution of Problem (OPT). Proof See Appendix A.2.
Proposition 1 implies that finding the optimal solution of problem (OPT) reduces to finding the minimum of bw(n)o v e rt h es e tΩ. To this end, let us introduce the sequence {n q } q∈IN defined by

n q =1+ 2 -q δ ,q ∈ IN , (1)
and note that n q >n q+1 for all for q ∈ IN. These numbers will play a key role in determining the optimal solution, as will be shown below.

As an example on the above, Figure 2 shows the function bw(n)fors=2000 bytes and δ=100 ms. Note that n min =2 ,n max =1 0 1a n dn 6 =2 .T h e minimum of bw(n) is 16.36 and is obtained for n = n 6 = 2. The frame size is f (n 6 )=1000 bytes and the bag is 2 6 ms.

Figure 3 shows the function bw(n)f o rs=2000 bytes and δ=400 ms. Here we have n min =2 ,n max =4 0 1a n dn 7 = 4. The minimum of bw(n) is 4.27 and is obtained for n = n 7 = 4. The frame size is f (n 7 )=500 bytes and the bag is 2 7 ms.

We shall first state several properties of the functions f (n)a n dk(n)t h a t will be helpful in determining the optimal strategy. Lemma 2 For al l integers n ≥ 1 and all integers q ∈{ 0,...,6},w eh a v e k(n)=q if and only if n q+1 <n≤ n q .M o r e o v e rk(n)=7if and only if n ≤ n 7 .

Proof See Appendix A.3. We now study the minimum of bw(n)o v erΩ. We proceed in two steps. We show (a) that the minimum of bw(n) is attained at a point n * in {n 0 ,n 1 ,...,n 7 }, and (b) that n * is the minimum value of the sequence {n q } q∈IN in Ω.T op ro v e (a), we first prove that this function is piecewise non-increasing.

Lemma 5 For al l n ≤ n 7 we have bw(n) ≥ bw(n 7 ).M o r e o v e r ,f o ra l lq ∈ {0, 1,...,6} and for all n ∈ (n q+1 ,n q ], bw(n) ≥ bw(n q ). Proof See Appendix A.6.

Using the piecewise monotonic behaviour of bw(n), Lemma 6 below proves that the minimum of bw(n)o v e rΩ is necessarily attained at a point of the sequence {n q } q∈IN .

Lemma 6 Let J = Ω ∩{ n 0 ,n 1 ,...,n 7 }.T h e r ee x i s t sn * ∈J such that bw(n * ) ≤ bw(n) for all integers n ∈ Ω.

Proof See Appendix A.7.

Since the minimum of bw(n) is in {n 0 ,n 1 ,...,n 7 }, we will now compare the values of this function at these points. Lemma 7 shows that bw(n q ) > bw(n q+1 ).

Lemma 7 For al l integers q ∈{0, 1,...,6},i th o l d st h a tbw(n q ) >bw(n q+1 ).

Proof See Appendix A.8.

We can now prove that the minimum of bw(n) is attained by the smallest value of the sequence {n q } q∈IN belonging to the set Ω. This is formally stated in the following proposition. Proof See Appendix A.9.

We are now in position to state our main result.

Theorem 1 If s ≤ f max ,t h e nn * = n 7 , f * = f (n 7 ) and k * =7is an optimal strategy. Otherwise, k * = min 7, log 2 δ nmin-1 , n * =1+ 2 -k * δ and f * = f (n * ) is an optimal strategy.
Proof From Proposition 2, an optimal strategy is obtained by choosing the largest value of k in {0,...,7} such that

n k =1+ 2 -k δ ≥ n min .Ifn min =1, this value of k is clearly k = 7. Otherwise, k ≤ log 2 δ nmin-1 , that is k = min 7, log 2 δ nmin-1 .
To summarize, the above results prove that an optimal strategy for sending the message is always obtained by sending n 7 frames and choosing k =7when the message size is lower than or equal to f max . Otherwise, an optimal strategy is obtained by setting k = min 7, log 2 δ nmin-1

, with n min = s fmax , and fragmenting the message into n k frames of size f (n k ) that are transmitted one after the other, separated by 2 k ms.

Before concluding this section, we present below two basic properties of the optimal solution that will be used in the following. The next lemma provides bounds on the optimal number of frames.

Lemma 8 If s>f max and if δ ≤ 2 7 (n min -1), n min ≤ n * ≤ 2[ n min -1]. Proof See Appendix A.10.
It is worthwhile noticing that the above lemma implies that if f max <s< 2f max , i.e., if n min =2 ,t h e nn * = 2. The following lemma is concerned with the optimal size of the frames.

Lemma 9 If s>f max and if δ ≤ 2 7 (n min -1),t h e nf * >f min .

Proof See Appendix A.11. 3O p t i m a ls t r a t e g yf o rs e n d i n gm u l t i p l em e s s a g e s

Problem statement

We now consider the situation where the source partition (applicationprogram unit) has to send multiple messages to the destinations. Let M>1b et h e number of messages and assume that they are numbered from 1 to M .W e let M = {1,...,M} denote the set of messages. Message i ∈Mhas a size equal to s i bytes and has to be delivered before δ i ms after the first bit has been transmitted1 . In the rest of this section, the term partition is used in the set-theoretic sense and, unless indicated otherwise, is not to be confused with the previous description of application program units.

When we consider the transmission of multiple messages, several strategies are possible. The system designer can choose to use a separate VL for each message, or he can choose to aggregate all data into a single message and thus to use a single VL. Of course, intermediate strategies are also possible, i.e., the system designer can choose to partition the set M into K ∈{ 2,...,M -1} subsets A 1 ,...,A K such that A i ∩A j = ∅ for i = j and ∪ i A i = M,a n dt o send all the messages belonging to each subset A i as a single super-message of size s(A i )= m∈Ai s m . Note that in this case the upper bound on the delivery time of the super-message i is δ(A i ) = min m∈Ai δ m .

The question we want to answer here is that of the strategy that minimizes the reserved bandwidth. For any subset A⊂M , let bw(A)d e n o t et h e minimum bandwidth to send a super-message of size s(A)= m∈A s m with a delivery time lower than δ(A) = min m∈A δ m . Note that the optimal parameters k(A), n(A)a n df (A) for the associated Virtual Link are given in Theorem 1. We let also P(A) denote the set of all partitions of a subset A of M. The problem amounts to finding a partition {A i } i=1,...,K of M minimizing the total bandwidth

K i=1 bw(A i ). Formally, minimize K i=1 bw(A i )( P A R T ) subject to {A i } i=1,...,K ∈P(M) K ∈{1,..

.,M}

A solution to problem PART is thus a partition of the set M of all messages. Note that the number of solutions correspond to the cardinality of P(M)and that it is given by the Bell number of order M :

|P(M)| = 1 e ∞ k=0 k M k! , (2)
which implies that we cannot hope finding the optimal solution by an exhaustive enumeration of all solutions for large values of M . We thus first consider some simple special cases for which closed-form results can be obtained in Section 3.2, before presenting general numerical approaches in Section 3.3 and 3.4.

Some simple special cases

In the following, we will focus on the case where the message sizes are lower than or equal to f max and the upper bound on the delivery time of the supermessage is strictly below 128 ms. This is formally stated in the following assumption.

Assumption 2 For each message m ∈M,w eh a v ef min ≤ s(m) ≤ f max and δ(m) < 2 7 .

Throughout this section, this assumption is adopted. This is clearly the most interesting case, and it is also the most tractable as indicated byt h e following lemma. Lemma 10 Let A⊂Mand {A i } i=1,...,K be a partition of A such that s(A i ) ≤ f max for all i.I th o l d st h a tk(A i )=7 , n(A i )=1for all i,a n d

K i=1 bw(A i )=2 -7 (s(A)+Kc). Proof See Appendix B.1.
Note that Lemma 10 implies that the total reserved bandwidth depends on the particular partition that is considered only through the number K of super-messages, as long as the size of each one is below f max . We immediatly get the following corollary.

Corollary 1 We have bw(A) K i=1 bw(A i ) =2 7-k(A) f (A)+c s(A)+Kc , (3)
for any subset A⊂Mand any partition {A i } i=1,...,K of A such that s(A i ) ≤ f max for all i.

Using Corollary 1 we first show that as long as s(A) ≤ f max ,t h et o t a l reserved bandwidth is minimized by sending all messages of A in a single Virtual Link.

Proposition 3 For A⊂Msuch that s(A) ≤ f max and a partition {A i } i=1,...,K of A,i th o l d st h a t bw(A)

K i=1 bw(A i ) =1-(K -1) c s(A)+Kc , (4)
which implies that bw(A) <

K i=1 bw(A i ) if K ≥ 2.
Proof Since s(A) ≤ f max , Lemma 10 implies that k(A)=7 ,n(A)=1a n d bw(A)=2 -7 (s(A)+c). Thus, with Corollary 1 we obtain bw(A)

K i=1 bw(Ai) = s(A)+c s(A)+Kc .
Note that in practice, most partitions (program units) send a small number of short messages with a maximum delivery time that is smaller than 128 ms. In this case, we can directly apply the above proposition and assert that the total reserved bandwidth is minimized by aggregating all messages into a single super-message.

Example 1 Assume that there are M =6m e s s a g e st ob es e n ta n dt h a tt h e sum of their sizes is 148 bytes. According to formula (4), we can reduce by about 55% the total reserved bandwidth by sending all messages as a single super-message instead of sending each one in a separate Virtual Link.

Is it always optimal to aggregate the messages? The answer is no, as indicated by the following proposition which considers the case where a partition (program unit) has to send two messages satisfying the assumptions of Lemma 10, and proves that it is optimal to send each message separately if the sum of their sizes is greater than f max .

Proposition 4 Let A⊂Mbe such n min (A)=2and {A 1 , A 2 } be a partition of A such that s(A i ) ≤ f max , i =1, 2.T h e nbw(A) ≥ bw(A 1 )+bw(A 2 ). Proof See Appendix B.2.
Example 2 Assume that there are two messages to be sent with the following parameters : s 1 = s 2 =1024bytesandδ 1 = δ 2 = 30 ms. In this case, we obtain bw({1})+bw({2})=2 1024+47 . Aggregating the messages thus requires four times more bandwidth than sending them separately. Proposition 4 implies that aggregating messages of relatively small sizes, under Assumption 2 that is, in one super-message is not trivial if its size exceeds f max . In addition, solving PART for general cases, especially when Assumption 2 does not hold, is not an easy task. Resorting to numerical algorithms becomes hence inevitable to determine optimal strategies. For this purpose, an exact branch-and-bound algorithm is first introduced in Section 3.3, then followed by a greedy one in Section 3.4.

Branch-and-bound algorithm

Problem PART can be solved using the branch-and-bound algorithm 1.A sa reminder, a branch-and-bound algorithm works in two steps: the branching step consists of splitting the problem in two or more sub-problems whereas the bounding step defines a lower and an upper bound for the current subproblem. When the lower bound meets the upper bound, it is not necessary to continue exploring from this state. The recursive algorithm 1 takes as input the current partial solution which is defined by a set of super-messages and a set of messages not yet handled. The initial state is defined by an empty set of super-messages. Starting from a partial solution, the algorithmg e n e r a t e s another partial solution by taking a message that is not present in any supermessage and merging it to a super-message or putting it alone.

In the following, we describe the details of this algorithm.

Initial upper bound

The branch-and-bound algorithm is started with an initial value of theu p p e r bound. In our implementation, we have used the cost returned by the greedy algorithm described in Section 3.4. As will be shown later, this heuristic often provides near-optimal solutions. As described in Algorithm 1, the upper bound is updated each time an improving complete solution is discovered. for i ← 1 to |S| do 7:

C←S Let C = C j represent the set of super-messages. 8:

C i ←C i ∪{N 1 }
Merge N 1 to the existing super-message C i . 9:

BandB(C, N\{ N 1 }) 10:

end for 11:

S←S∪{ { N 1 }} Add the message alone. 12:

BandB(S, N\{ N 1 }) Run the Branch and Bound.

Lower bound

A lower bound on the optimal cost-to-go is generated in each node oft h e search tree. This lower bound is based on the following conjecture.

Conjecture 1 It holds that

K i=1 bw(A i ) > m∈A s(m) n(m) 2 -k(m) (5)
∀{A i } i=1,...,K ∈P(A), ∀A ⊂ M

We show below that this conjecture holds true in an important specialcase. The proof is based on the following lemma.

Lemma 11 Under assumption 2, Conjecture 1 is equivalent to bw(A) > 2 -7 s(A) ∀A ⊂ M. ( 6
)
Proof See Appendix C.1.

The interest of Lemma 11 is that it provides an equivalent formulation of Conjecture 1 that is independent of a particular solution: it depends only on the sum of the sizes of the messages in the set A and on the minimum of their delivery times. This allows to obtain the following Proposition. Proof See Appendix C.2

Variable ordering

As in most cases, ordering plays an important role in ameliorating the performance of a branch-and-bound algorithm. In our work, messages were sorted following a decreased order of sizes. Implementing this ordering scheme had a great impact on resolution times as it helped in obtaining greater lower bounds faster and hence pruning the search tree earlier (due to starting with messages of larger size).

Greedy algorithm

An initial upper bound is determined using a greedy algorithm that selects the state with the best lower bound until no messages are left (Algorithm 2). This greedy algorithm performs in O(M 2 ) so it can be used for large-scale problems.

Algorithm 2

1: function greedy(M :t h es e to fm e s s a g e s ) 2:

S←{ } The super-messages of the partial solution.

3:

for ∀m ∈Mdo 4:

Q ←{} 5:

for i ← 1 to |S| do 6:

C←S Let C = C j represent the set of super-messages. 7:

C i ←C i ∪{m} Merge m to the existing super-message C i . 8:

Q ← Q ∪{C} 9:
end for 10:

S←S∪{ { m}} Message alone. 11:

Q ← Q ∪{S} 12:
S←argmin Qx∈Q (bw(Qx)) Best partial solution. 13: end for 14:

return S 15: end function

4O p t i m a lR o u t i n go ft h eV L s

As illustrated in Figure 4, let N = {1,...,N} be a set of N nodes representing the AFDX network (n ∈Nmay correspond to an AFDX switch or End System). Here an End System corresponds to a processing module.DenotebyE the set of directed edges (links) between nodes such that no edge exists between As the VLs need to be routed in the AFDX network, the problem amounts to finding one and only one Steiner tree for each VL, thereby indicating the links that shall be traversed.

In order to ensure an increased residual capacity in the network, the optimization associated to the VL routing problem is taken to be the minimization of the maximum link load (links actually represent switch interfaces), that is,

Minimize ρ =max e∈E y e c e ,
where y e represents the total reserved bandwidth on link e.

In this paper, we opted for an exact node-link formulation [START_REF] Ahuja | Network flows: theory, algorithms, and applications[END_REF] based on Mixed Integer Linear Programming (MILP). Thus, for every node n ∈N, let Γ + (n) ⊆E denote the set of incoming links to n and Γ -(n) ⊆E the set of outgoing links from n as can be seen in Figure 5.

e∈Γ + (n) x e v - e∈Γ -(n) x e v = h n,v , ∀n, v, (7)
y e v M ≥ x e v , ∀v, e, (8)
y e v ≤ x e v , ∀v, e, (9)
e∈Γ + (n)

y e v ≤ 1 , ∀n, v, (10)
y e = v∈V y e v b v , ∀e, (11)
y e ≤ c e ρ, ∀e, (12)
y e v ∈{0, 1} , ∀v, e, (13)
x e v ∈{0,...,K v } , ∀v, e, (14)
where x e v can be thought of as the number of destinations VL v is addressing via link e (cf. Figure 6). The equality in constraint [START_REF] Crichigno | A multicast routing algorithm using multiobjective optimization[END_REF] indicates that the difference in the number of addressed destinations by VL v between before and after entering a node n should be equivalent to h n,v where,

h n,v =    -K v if n = src(v), 1 if n ∈ dst(v), 0 otherwise.
Evidently the source node (End System) should address all of the destinations. A destination node (End System) should be the last in the chain as it cannot re-route information, and only receives what is addressed to it from VL v and hence the value of h n,v = 1. Finally, an intermediate node (switch) should transfer whatever is addressed by the VLs from its input links to its output links.

The constant value M in ( 8) is considered as a large number, e.g., a value greater than the maximum number of destinations in the VLs. Consequently, Fig. 6: An example on the number of destinations x e v addressed by a VL v on the links, following a given multicast tree between End System 1 (source) and End Systems 2 and 3 (destintations).

the boolean y e v indicates whether link e is traversed by VL v or not, i.e. if x e v > 0t h e ny e v = 1 indicating the passage of v in this link, otherwise it can be either 0 or 1 but be set to 0 due to constraint [START_REF] Hwang | Steiner tree problems[END_REF]. Constraint [START_REF]ILOG CPLEX[END_REF] ensures that each VL is routed along a tree where no node is visited more than once. Constraints ( 11) and ( 12) define the total reserverd bandwidths and the maximum utilization rates on the links, respectively. Constraints ( 13)and( 14) represent the domains for the decision variables y e v and x e v , respectively. As a result of the preceding node-link formulation, Steiner trees fort h e various VLs can be assigned based on the decision variables y e v .

5R e s u l t s

Message Aggregation

The optimal strategy for sending multiple messages (cf. Section 3) was first compared to the strategy which consists of sending each message separately in a different VL ("1/VL"). In addition, the strategy of grouping all messages together and defining one unique VL was also considered ("All in 1"). Furthermore, the results of the greedy algorithm from Section 3.4 are presented to demonstrate the efficiency of this algorithm.

To compare these different strategies, several experiment sets, with 100 instances each, were considered. Each instance consisted of n randomly generated messages, defined by their sizes (in bytes) and their maximum delivery times δ (in ms). The message sizes were chosen uniformly from the set {16, 32, 64, 128, 256, 512, 1024} bytes, thereby favoring small sizes (as the mean is at 290 bytes). As observed in [START_REF] Scharbarg | A Probabilistic Analysis of End-To-End Delays on an AFDX Avionic Network[END_REF], adopting small sizes is more representative for messages in real-world instances. In addition, values for maximum delivery times (δ) were chosen to respect assumption 2. Tables 1 and2 demonstrate the relative gap, in percentage, between the optimal solution of PART and the various strategies, while varying δ and n respectively.

We observe that the strategy of placing all messages in a single VL gives severly unoptimized solutions, unless the maximum delivery time is large enough. Indeed, with an average message size of 290 bytes, instances with only 5 messages can have a total size which exceeds f max . Hence, in most cases and similar to proposition 4, it is not optimal to aggregate the messages in a single VL. This is also verified in Table 2, where the relative gap to the optimal solution exceeds 170% when grouping all messages in a single VL, so as to repect the maximum delivery times. As the total size exceeds f max and the minimum value of the maximum delivery times has to be respected, it becomes favorable to choose a small bag value, which maximizes the bandwidth in the process.

We can also observe that the strategy of sending each message separately in different VLs has a better performance at average, where the total bandwidth consumption is approximatively 12% greater than the optimal solution. However, as shown in Figure 7, the relative gap between the solution obtained by sending one message per VL and the optimal one highly depends on the set of messages considered. A closer look at the extreme cases shows that using a separate VL for each single message leads to acceptable performances when the message sizes are close to f max , but that it leads to a significant waste of bandwidth when message sizes are small. Finally, the greedy algorithm performs very well in all cases. The worst solution obtained, among all the tested instances (1400 instances in all, including ones with a greater number of messages and not presented in this paper), is only 2.6% above the optimal solution. Thus, this algorithm could replace the optimal algorithm when the number of messages becomes large (> 20-25 messages). Fig. 7: Relative gap to the optimal solution in % when using one VL per message.

Routing

Assuming that the messages have been aggregated, and the VLs have been defined, we hereafter demonstrate the performance of the node-link formulation presented in Section 4 for routing the different VLs in the network. For solving the associated MILPs, the linear program solver CPLEX [START_REF]ILOG CPLEX[END_REF] from IBM ILOG was used. As for the topology, and for depicting as much as possible the AFDX network found on board aircrafts, the one shown in Figure 8 was considered. This topology consists of 7 AFDX switches and 6 End Systems. The End Systems represent the group of sources and destinations (e.g. partitions) for VLs.

All links are full duplex at 100Mbps. Given nbV L VLs, all End Systems were evenly attributed a number of VLs in which they act as a source (e.g. if nbV L = 12 then each End System in our topology would act as source for 2 VLs). For each VL, the destinations were chosen so that 1 to 5 End Systems (other than the source) would be uniformly selected. Bandwidth requirements were chosen based on an exponential distribution with an average of1 2 5 K b p s (so that for large examples link capacities are not exceeded). Several examples were generated with nbV L = {100, 300, 500, 700, 1000}.

For each case of nbV L, 100 instances were generated and solved following the exact node-link formulation. In all of the cases, optimal solutions for routing the VLs where obtained under 10 seconds.

Benchmark

In order to validate the benefit of both the message aggregation and routing approaches in industrial applications, a benchmark was generated. The topology was considered similar to that of Figure 8, except that each End System was replaced with 12 separate ones depicting different processing modules, and connected to the same switch. Each module itself hosted a set of 12 partitions (application program units), giving a total of 864 partitions in the system.

Messages were first generated in such a way that each partition would be a source to a number of messages uniformly chosen from 2 to 9. Each message was destined to partitions uniformly chosen among all possible partitions (the number of destinations was limited between 1 and 43). Message sizes and maximum delivery times were chosen from the sets {16, 32, 64, 128, 256, 512, 1024}bytes and {30, 60, 100}ms respectively. All these considerations lead to a total number of 5305 messages.

The optimal strategy for message aggregation lead to the definitionof1568 distinct super-messages, and hence VLs, in a couple of seconds. This reduction in the total number of VLs as compared to sending each of the 5305 messages in a separate VL, reduced the total demand in the network by about10%from 114.3Mbps to 103.5Mbps.

Furthermore, routing the arising VLs using the exact node-link formulation, with an objective of minimizing the maximum link utilization rates, gave a solution at about 39% maximum utilization in a couple of minutes. To demonstrate the importance of obtained results, we need to consider the strategy that might be followed in avionics. The messages would be first placed in separate VLs, which are then routed to obtain a feasible solution while minimizing route lengths, for example. Doing so will not only give an increased total bandwidth requirement (aforementioned 10%), but also a routing scheme with a maximum link utilization rate of about 53%.

This clearly shows that, using our strategies (aggregation and link utilization rate minimization) leads to more flexibility in the network. That is, residual capacities are increased in the network so as to allow any future evolution, that is the introdution of new messages or VLs. In worst-case scenarios this might not be possible if messages are not efficiently aggregated and link utilization rates are not decreased.

6C o n c l u s i o n

In AFDX networks, bandwidth is a valuable resource that should not be wasted. We have shown how to compute the optimal transmission parameters of a VL so as to minimize the bandwidth consumption while transmitting the data within their maximum delivery times. We have also shown that the aggregation of messages destined to the same set of receivers can lead to significant bandwidth savings, and we have presented efficient algorithms to compute the optimal aggregation strategy. Finally, we have also proposed an exact integer-linear programming formulation of the VL routing problem allowing to maximize the residual capacity of the network links, thereby providing more flexibility for adding new VLs or modifying existing ones. The proposed methods provide the basis for a more efficient design of theVLs,and have to be completed later on by the verification of the worst-case network latencies. ). Thus, the minimum bandwidth for this fixed value of n is bw(n). The optimal value of n is the value n * which minimizes bw(n) in the interval Ω.

A.3 Proof of Lemma 2

Assume first that k(n)=q<7. We have q ≤ log 2 δ n-1 <q+ 1 if and only if 2 q ≤ δ n-1 < 2 q+1 . This is equivalent to n>1+2 -(q+1) δ and n ≤ 1+2 -q δ. Since n is integer, this is equivalent to n q+1 <n≤ n q .A s s u m en o wt h a t

k(n)=7.Notethat7≤ log 2 δ n-1 is equivalent to 2 7 ≤ δ n-1 , which holds if and only if n ≤ 1+ 2 -7 δ = n 7 .

A.4 Proof of Lemma 3

From the definition of n q+1 ,w eh a v e2 -(q+1) δ<n q+1 ≤ 1+2 -(q+1) δ, which yields 2 -q δ<2n q+1 ≤ 2+2 -q δ. But since 2n q+1 ∈ IN , 2 n q+1 > 2 -q δ implies that 2n q+1 ≥ 1+ 2 -q δ = n q . Moreover, since 2n q+1 ∈ IN , 2 n q+1 ≤ 2+2 -q δ implies that 2n q+1 ≤ 1+(1+ 2 -q δ )=1+n q , i.e., n q ≥ 2n q+1 -1.

A.5 Proof of Lemma 4

To prove (a), observe that s n ≤ f min if and only if s fmin ≤ n, which is equivalent to n ≥ Let us now consider n such that n q+1 <n≤ n q with q ∈{ 0, 1,...,6}. According to Lemma 2, k(n)=q for n q+1 <n≤ n q .M o r e o v e r ,f (n) is a non-increasing function of n. Therefore, bw(n) is non-increasing on (n q+1 ,n q ]a n dt h u sbw(n) ≥ bw(n q )f o r all integers n such that n q+1 <n≤ n q .

A.7 Proof of Lemma 6 Observe first that J = ∅ since n 0 = n max ∈ Ω.L e tn qmax = min{x : x ∈J} and assume on the contrary that there exists m ∈ Ω such that bw(m) <bw(x) for all x ∈J. We have either m ∈ [n min ,n qmax ]o rn qmax <m≤ n max .I f m ≤ n qmax , then, according to Lemma 5, we have bw(m) ≥ bw(n qmax ), i.e., a contradiction. Thus m>n qmax , which is possible if and only if q max > 0. However, this implies that there exists q ∈{ 0, 1,...,q max -1} such that m ∈ (n q+1 ,n q ]. From Lemma 5, we then have bw(m) ≥ bw(n q ) which is again a contradiction. Hence, there exists n * ∈J such that bw(n * ) ≤ bw(m) for all integers m ∈ Ω.

A.8 Proof of Lemma 7

According to Lemma 2, k(n q )=q and k(n q+1 )=q +1. We thus have to show that (f (n q )+c)2 -q > (f (n q+1 )+c)2 -(q+1) , i.e., 2f (n q )+c>f(n q+1 ).

(

) 15
Assume n q+1 ≥ s fmin . Since n q ≥ n q+1 , Lemma 4.(a) states that f (n q )= f (n q+1 )=f min . In this case, equation ( 15 where the last inequality is a direct consequence of Lemma 3. We thus get 2f (n q )+c ≥ s nq+1 + c and since the left-hand side is an integer value this implies that 2f (n q )+c ≥ s nq+1 + c. Since f (n q+1 )= s nq+1 , it yields 2f (n q )+c>f(n q+1 ). Thus equation ( 15) also holds in this case, which proves the result.

A.9 Proof of Proposition 2 From Lemma 7, we have bw(y) >b w (z) for all y, z ∈J such that y>z . Hence, bw(n * ) <bw(y) for all y ∈J \{n * }. However, according to Lemma 6 there exists x ∈J such that bw(x) ≤ bw(n) for all n ∈ Ω, which is possible if and only if x = n * .W et h u sh a v ebw(n * ) ≤ bw(n) for all n ∈ Ω. According to Proposition 1, this implies that (n * ,f(n * ),k(n * )) is an optimal solution of Problem (OPT).

Fig. 1 :

 1 Fig.1: Decomposition approach for the design process on IMA.

Fig. 2 :

 2 Fig. 2: Function bw(n)f o rδ=100 ms and s=2000 bytes.

Fig. 3 :Lemma 3 Lemma 4

 334 Fig. 3: Function bw(n)f o rδ=400 ms and s=2000 bytes.

Proposition 2

 2 Let n * = min{x : x ∈J } .T h e n ,(n * ,f(n * ),k(n * )) is an optimal solution of Problem (OPT).

6 .

 6 However, since n min ({1, 2})=2we obtain k({1, 2})= log 2 (30) =4andn({1, 2}) = 2, which yields bw({1, 2})= 1024+47 2 4

Algorithm 1 1 :

 1 procedure BandB(S:s e to fs u p e r -m e s s a g e s ,N :s e to fr e m a i n i n gm e s s a g e s ) 2:if |N | > 0 then 3:if lowerbound(N )+bw(S) ≥ bw(sol) then 4

Proposition 5

 5 Under Assumption 2, Conjecture 1 holds true for all A⊂M.

Fig. 4 :

 4 Fig. 4: Notations for modeling an AFDX network.

Fig. 5 :

 5 Fig. 5: Links to and from node n.

Fig. 8 :

 8 Fig. 8: Topology considered for experimentations. Set of 7 AFDX switches and 6E n dS y s t e m s .

1 A. 1

 11 AP r oo f so ft h er e s u l t si nS e c t i o n2 . Proof of Lemma 1 Assume that n is fixed. Then there exists at least one value of f ∈ IN s u c h that max f min , s n ≤ f ≤ f max if and only if s n ≤ f max , i.e., n ≥ s fmax . Similarly, there exists at least one value of k ∈{ 0, 1,...,7} such that (n -1)2 k ≤ δ if and only if n ≤ 1+δ. We conclude that the problem has a solution (n, f, k) if and only if we can find at least one value of n ∈ IN s u c h t h a t b o t h conditions are satisfied, i.e., s fmax ≤ 1+δ holds. A.2 Proof of Proposition 1 Assume that the value of n ∈ Ω is fixed. The minimum value of f is f (n)= max(f min , s n ) and the maximum value of k is k(n) = min(7, log 2 δ n-1

  s fmin . Statement (b) is just the contrapositive of (a). Finally, statement (b) implies that f (n) is strictly decreasing on the interval 1, s fmin , while statement (a) implies that f (n) is constant for n ≥ s fmin . A.6 Proof of Lemma 5 Let n ≤ n 7 .F r o mL e m m a2 ,k(n) = 7. Since f (n) is non-increasing on the interval [1,n 7 ], it yields bw(n) ≥ bw(n 7 ), as claimed.

  ) clearly holds, which proves the result. Assume on the contrary that n q+1 < s fmin which, according to Lemma 4.(b), implies that f (n q+1 )= s nq+1 . By definition, f(n q ) ≥ s nq ,a n dt h u s 2f (n q )+c ≥ 2 s n q + c ≥ 2 s n q + c ≥ 2s 2n q+1 + c,

A. 10 1 .F r o m log 2 δ n min - 1 - 1

 10111 Proof of Lemma 8Assume s>f max and thus n min > 1. Using Lemma 8, we get n * ≤ 2[ n min -1inequality is obtained using f min =1 7<1 2 f max = 1471 2 .A ccording to Lemma 4, we can conclude that that f * >f min .A.11 Proof of Lemma 9The assumptions imply thatk * = log 2 δ nmin-<k * ≤ log 2 δ n min -1 , we get n min -1 ≤ 2 -k * δ<2[ n min -1], and this implies thatn min ≤ n * = 1+ 2 -k * δ ≤ 2[ n min -1], as claimed.BP r oo f so ft h er e s u l t si nS e c t i o n3B.1 Proof of Lemma 10According to Theorem 1, n min(A i ) = 1 implies that k(A i )=7 .M o r e o v e r , since δ(A i ) < 2 7 ,w eh a v en(A i )=1+ 2 -7 δ(A i ) =1a n dt h u sf (A i )= s(Ai) 1 = s(A i ) ≥ f min . It yields i )+Kc =2 -7 (s(A)+Kc) .(16)B.2 Proof of Proposition 4 Note first that δ(A) < 2 7 and n min (A) = 2 implies that k(A) ≤ 6. Moreover, we have n(A)=2andf (A)= s(A) 2 >f min according to Lemmata 8 and 9. With Corollary 1, and the fact that x ≥x, we thus obtain bw(A) 2 i=1 bw(A i ) ≥ 2 7-k(A) s(A)/2+c s(A)+2c =2 6-k(A) s(A)+2c s(A)+2c ≥ 1. (17)

Table 1 :

 1 Average relative gap in % to the optimal solution, for n =1 0a n dδ variable.

	δ	{30, 60, 100}	{60, 100, 120}	30	60	100
	1/VL	12.12	11.58	12.19	10.54	10.69
	Greedy	.06	.31	<.01	<.01	.01
	All in 1	282.62	96.93	293.57	98.98	.90

Table 2 :

 2 Average relative gap in % to the optimal solution, for δ ∈{30, 60, 100} and n variable.

	n	5	10	15
	1/VL	10.35	12.12	11.64
	Greedy	.03	.06	.06
	All in 1	176.81	282.62	301.61

In practice, all messages sent by a partition share the same maximum delivery time. The analysis presented here does not rely on this assumption,b u ti to fc o u r s ea l s oa p p l i e s in this case. The numerical results presented in this articlec o n s i d e rbo t ht h ec a s ew h e r et h e δ i are equal and the case where they are different.

Acknowledgements The work presented in this paper was conducted under the research project SATRIMMAP (SAfety and Time Critical Middleware for future Modular Avionics Platforms) which is supported by the French National Agency for Research (ANR).

CP r oo f so ft h er e s u l t si nS e c t i o n3 . 3 C.1 Proof of Lemma 11 We first show that the conjecture is equivalent to the following condition:

Indeed, if Conjecture 1 holds true, then clearly, since {A} is a partition of A, assertion (18) also holds true. Conversely, if [START_REF] Spitzer | The avionics handbook[END_REF] holds true, then for any partition {A i } i=1,...,K of A, it holds that

However, since we have assumed that n min (m)=1 ,w eh a v ek(m)= 7 and since δ(m) < 2 7 this implies that n(m) = 1 for all m ∈M .T h u s , under Assumption 2, condition ( 18) can be equivalently written as bw(A) > 2 -7 s(A), ∀A ⊂ M.

C.2 Proof of Proposition 5

According to Theorem 1, Condition 6 is trivialy satisfied if s(A) ≤ f max . Assume therefore that s(A) >f max , i.e., n min (A) ≥ 2. Together with δ(A) < 2 7 , this implies that k(A) ≤ 6. Thus, with Lemma 9, we obtain bw(A)=

Assume first that k(A) = 6. Since n(A)a n dk(A) are solutions of problem OPT, the constraint (n(A) -1) 2 k(A) ≤ δ(A) < 2 7 has to be satisfied, which is only possible if n(A) = 2. In this case, [START_REF] Watkins | Transitioning from federated avionics architectures to Integrated Modular Avionics[END_REF] which proves that the conjecture also holds true in this case.