Christian Fraboul -Jean-Luc Scharbarg

Laurent George -Ye-Qiong

Song Présentée

Xiaoting Li

Laurent George

Henri Bauer

Emilie Fabian

Michaël, Nesrine, Raoul Florian

Tony Razvan

Victor

Titre : Worst-case delay analysis of real-time switched Ethernet networks with flow local synchronization

La présente étude n'aurait pas été possible sans le bienveillant soutien de certaines personnes.

Et je ne suis pas non plus capable de dire dans les mots qui conviennent, le rôle qu'elles ont pu jouer à mes côtés pour en arriver là. En premier lieu, je tiens à remercier mes directeurs de thèse, Christian Fraboul et Jean-Luc Scharbarg, professeurs à l'INP-ENSEEIHT et chercheurs à l'Institut de Recherche en Informatique de Toulouse (IRIT, UMR 5505 du CNRS), pour m'avoir guidée, encouragée, conseillée, fait beaucoup voyager pendant quatre ans tout en me laissant une grande liberté. Au travers de nos discussions, ils m'ont apporté une compréhension plus approfondie des divers aspects du sujet.

Yvon Trinquet m'a fait l'honneur de présider le jury, qu'il soit remercié pour son intérêt pour mon travail. J'adresse mes sincères remerciements à

List of Abbreviations and Symbols

Abbreviations: the delay of flow τ i generated by flows in δ i due to FIFO with non-preemptive effect ∆ h i a factor considering the frame serialization with reachable frame sequences in the pessimism analysis ∆ h i,t the frame serialization factor f i one frame of flow τ i f i,j the j th frame of flow τ i f (h) the first frame of the busy period bp h f irst i the source node of flow τ i f irst j,i the first output port where a competing flow τ j crosses the flow τ i f irst F P j,i the first shared FP output port of flow τ i and flow τ j along the path P i in a heterogeneous network G x the x th subset containing dependent flows h a node of a network h (α, β) the maximum horizontal deviation between α and β hp i a set of flows having higher priorities than flow τ i IP h k the set of flows crossing the k th input link of h j i the release jitter of flow τ i J i the maximum release jitter of flow τ i J compx i the maximum release jitter of flow τ i at the component comp x in a heterogeneous network l h k the duration of sequence seq h k without its first frame l max the maximum frame length of a Ethernet frame l min the minimum frame length of a Ethernet frame last F IF O i,j the last share FIFO output port of flow τ i and flow τ j along the path P i in a heterogeneous network last i the last visited output port of flow τ i lp i a set of flows having lower priorities than flow τ i L max the maximum processing delay when a frame crosses a link L min the minimum processing delay when a frame crosses a link LD i the transmission delay on links of flow τ i along the path P i M h i the earliest possible starting instant of bp h for the flow τ i M D h i,j the minimum duration from τ i to τ j at the output port h n B the number of bridges visited by a studied flow in a heterogeneous network n Bout the number of bridg ourpur ports connceting Ethernet visited by flow τ i in a heterogeneous network n S the number of switches visited by a studied flow in a heterogeneous network N i an end node of a real-time switched Ethernet N B the maximum number of CAN frames encapsulated within an Ethernet frame at a bridge in a heterogeneous network O i the offset of flow τ i OP h the output port link of h p i the priority of flow τ i p compx i the priority of flow τ i at the component comp x in a heterogeneous network p(h) the last frame of the busy period bp h P CF last i i,t the pessimism upper bound of the delay of flow τ i generated by competing flows in the pessimism analysis P CT last i i the pessimism upper bound of the delay of flow τ i generated by busy period transition in the pessimism analysis P S last i i,t the upper bounded pessimism introduced by the computation of frame serialization for flow τ i in the pessimism analysis P i the path of flow τ i |P i | the length of path P i rl h k a reachable duration of a frame sequence seq h k without its first frame in the pessimism analysis R the transmission rate of the network R c the total constant cost in switches and in bridges a studied flow in a heterogeneous network R CAN the bandwidth of a CAN bus in a heterogeneous network R ET H the bandwidth of the Ethernet backbone in a heterogeneous network R i the end-to-end delay of flow τ i R trs the tranmission cost of a studied flow along its path in a heterogeneous network R(t) input function of flow traffic over time t R * (t) output function of flow traffic over time t RS i,t,x the maximum workload generated by the interference set G x seq h k the frame sequence of IP h k shp i j ∈ shp i if p j > p i and τ j shares pure FP or both FP and FIFO scheduling policies with τ i in a heterogeneous network slp i j ∈ slp i if p j < p i and f irst j,i is with FP scheduling in a heterogeneous network ssp i j ∈ ssp i if p j = p i ; or if p j < p i and f irst j,i is with FIFO scheduling in a heterogeneous network sl the switching latency delay of a switch slow i the slowest node visited by τ i on its path P i slow j,i the slowest node visited by τ j on the path P i sp i a set of flows having the same priority as flow τ i S h max i the maximum delay experienced by a frame of flow τ i from its source node f irst i to output port h S h min i the minimum delay experienced by a frame of flow τ i from its source node f irst i to output port h S ET H the maximum size of an Ethernet frame encapsulating CAN frames in a heterogeneous network SD i the total switching lantency delay of flow τ i along the path P i τ i a real-time switched Ethernet flow τ compx i the input flow of flow τ i at the component comp x in a heterogeneous network T B a constant cost used in a brigde for frame encapsulation/decapsulation in a heterogeneous network T i the period of flow τ i T compx i the period of flow τ i at the component comp x in a heterogeneous network U P i the pessimism upper bounds of the worst-case ETE delay computation of the flow τ i using the Trajectory approach U R i the underestimation of the worst-case ETE delay of flow τ i using the classical Trajectory approach U R CF last i i the lower bounded delay of flow τ i generated by competing flows in the pessimism analysis U R CT last i i the lower bounded delay of flow τ i generated by busy period transition in the pessimism analysis U R S last i i a reachable value of frame serialization effect in the pessimism analysis v i a VL in the AFDX network

W last i i,t
the latest starting time of a frame f i of τ i at its last visited output port last i W D the maximum waiting delay of a CAN frame pending in a bridge output port in a heterogeneous network W D i the total waiting delay in the output buffers of flow τ i along the path P i

Mathematics Symbols:

(a) + = max(a, 0) 1, n an integer set {1, 2, ..., n}

List of Figures

General Introduction

Due to a limited bandwidth, the fieldbus technologies cannot cope with the increasing demand of data exchange of the industrial applications. Ethernet technology therefore becomes a promising candidate since it provides large bandwidth of data transmission and steadily decreasing cost. Since vintage Ethernet is not able to reach the real-time requirements, one solution considered in this thesis is based on a full-duplex switched Ethernet with traffic assumptions on incoming flows (traffic shaping).

One important real-time requirement is the worst-case end-to-end (ETE) communication delay. For a full-duplex switched Ethernet network, the end-to-end communication delay of a flow transmitted in the network is the time elapsed between the generation time of one frame of the flow at its source node and the reception time of this frame at its destination node. Then the end-to-end delay is the sum of the transmission delay on each crossed link and the delay generated at each crossed switch along the path. The worst-case end-to-end delay considers the most unfavorable scenario along the path. It depends on the generation times of other flows crossing the path, and therefore it is difficult to compute the worst-case end-to-end delays of large-scale networks. One solution is to guarantee the upper bounds of the worst-case delays by worst-case delay analysis, and efforts have been dedicated to solve this problem.

There exist several end-to-end delay analysis methods for real-time switched Ethernet networks. Simulation approach is based on the model of the network and it provides valuable informations about the delay distribution. However, worst-case delay is often a rare event that is missed by the simulation approach. Model-Checking performs an exhaustive exploration of the possible scenarios in order to calculate an exact worst-case end-to-end delay. However, it is limited to small networks due to the huge combinatorial explosion problem for large configuration. Network Calculus approach is a powerful method that uses arrival curves, which upper bound the arriving traffic, to describe arriving flows. It computes the maximum delay of a flow generated at each crossed switch and therefore leads to the worst-case end-to-end delay upper bound along the path. This approach is classical although it accumulates pessimism at each hop. The Trajectory approach allows a direct analysis on the worst-case scenario that can happen to a frame along its trajectory. It has been shown that this approach improves the computation of end-to-end delay upper bounds for an industrial avionics switched Ethernet network [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF]. Therefore, the Trajectory approach attracts increasing attention in the worst-case delay analysis.

All the worst-case delay analysis methods mentioned above consider that flows transmitted over the network are independent. This is true with flows emitted by different source nodes since there is no global clock to synchronize flows. However, each source node does have a local clock which can synchronize its flows. It means that local flows (emitted by the same source node) can be synchronized and that periodic flows can have known offsets. Thus offset assumptions increase the knowledge about the frame arrivals of periodic flows emitted by the same source node. They help to build a more precise flow model and eliminate some impossible scenarios which lead to pessimistic computation. Hence, the study of offset constraints is an important issue which needs to be addressed in the worst-case delay analysis of switched Ethernet networks.

The subject of this thesis is to integrate the offset constraints in the worst-case delay analysis of switched-Ethernet networks. This problem is of great interest since improved worst-case delay analysis can be obtained on large scale industrial switched Ethernet network. In the first step, we identify the offset constraints among a set of periodic flows emitted by the same source node and illustrate the offset constraint and its impacts on worst-case delay computation. In the second step, two approaches, the Network Calculus approach and the Trajectory approach, are proposed to integrate these offset constraints. Therefore, these two approaches allow us to compute the worst-case delay upper bounds of a real-time switched Ethernet network with offset assumption. As a real example of real-time switched Ethernet network, the Avionics Full-DupleX switched Ethernet network (AFDX) is introduced. The two proposed approaches are applied on an industrial AFDX configuration to show the improvement of the computed end-to-end delay upper bounds. Since the proposed approaches provide us a tool to evaluate a network with offsets, we are interested in the offset assignment algorithm that leads to minimum computed end-to-end delay upper bounds for the industrial AFDX network. An optimal scenario is introduced which minimizes the worst-case delays for all the flows. The existing offset assignments are presented and evaluated by comparing the results to those obtained based on the optimal scenario. The worst-case delay analysis leads to pessimistic delay upper bound computation. In order to investigate how pessimistic the proposed approaches are, an analytical pessimism analysis is developed based on the Trajectory approach and an upper bound of the introduced pessimism is obtained by measuring the maximum gap of a computed worst-case delay upper bound and an underestimated value of the worst-case delay.

As a future direction, a heterogeneous network architecture which combines existing field buses and a switched Ethernet is then studied. A worst-case delay analysis is tricky in such an architecture due to its heterogeneity nature (different bandwidths, scheduling policies, etc.). Two approaches are proposed to solve this problem. One is component-based approach which preserves the network properties but introduces pessimism at each component level; the other one is an adjusted Trajectory approach which unifies the heterogeneities along each path.

Main contributions of this thesis are summarized below.

• Integration of offset constraints in the Network Calculus approach and in the

Trajectory approach applied to the real-time switched Ethernet network.

Each source node in the switched Ethernet network has a local clock based on which the transmissions of periodic flows are not independent. Indeed, periodic flows with known offsets emitted by the same source node are dependent. A benefit of knowing the offsets is to improve the worst-case delay analysis for a switched Ethernet network since it can eliminate some impossible scenarios. Existing approaches of worst-case delay analysis do not consider the offsets. In this work, we show how to integrate the offset constraints in two approaches: the Network Calculus approach [LSF10b, LSF10a, LSF10c] and the Trajectory approach. These two modified approaches allow us to improve the computation of worst-case delay upper bounds of large scale switched Ethernet networks.

• Applications of the modified Network Calculus approach and the modified Trajectory approach on an industrial avionics switched Ethernet network.

The Avionics Full-DupleX switched Ethernet network (AFDX) can be seen as an example of real-time switched Ethernet. The two proposed approaches are applied to an industrial AFDX configuration. The results show that the two modified approaches improve the computation of delay upper bounds. We compare the delay upper bounds computed by these two modified approaches. Such a comparison allows us to know which approach is more suitable for such an industrial configuration. Moreover, an optimal approach is presented by choosing the tighter (smaller) computed worst-case delay between the results of the two modified approaches. Such an optimal approach provides an improved network performance evaluation by combining the two modified approaches.

• Evaluation of offset assignment algorithms for the industrial AFDX network.

In the context of processor and CAN bus, there exist studies about offset assignments which lead to the maximum system performance [START_REF] Goossens | Scheduling of offset free systems[END_REF][START_REF] Grenier | Pushing the limits of CAN -scheduling frames with offsets provides a major performance boost[END_REF]. Since the choice of offset assignment is related to a specific application, in this work, we focus on the industrial AFDX network [START_REF] Li | Existing offset assignments are near optimal for an industrial AFDX network[END_REF]. An optimal scenario is introduced which considers infinitive durantion between frame arrivals for all the flows. The comparison between the offset assignment algorithms and the optimal scenario allows us to know which algorithm leads to better performance (smaller computed delay upper bounds) in this context as well as how far the existing algorithms are from the optimal case.

• Analysis of pessimism introduced by the Trajectory approach and formalization of computation on pessimism upper bound.

The Trajectory approach guarantees the worst-case delay upper bounds of the switched Ethernet network by introducing pessimistic computation. The introduced pessimism directly reflects the reliability of the obtained worst-case delay upper bounds which are overestimated. A pessimism analysis has been proposed in [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF] which is empirical based on an unfavorable scenario. It relies on simulation and needs to build an unfavorable scenario for each network configuration. In this work, an analytical pessimism analysis based on the Trajectory approach is studied [START_REF]Analysis of the pessimism of the Trajectory approach for upper bounding end-to-end delay of sporadic flows sharing a switched Ethernet network[END_REF]. We analyze the factors leading to pessimistic computation in the Trajectory approach which allows us to know where the pessimism comes from. Then we propose an analytical method to calculate an underestimated value of the worst-case delay based on the Trajectory approach. The difference between an underestimated delay and an overestimated delay allows us to upper bound the introduced pessimism.

• Worst-case delay analysis of a real-time heterogeneous network.

With the increasing exchange of information in the real-time application, field buses cannot satisfy the industrial communication demand any more. The heterogeneous network using a backbone network to connect existing networks is considered as a solution to build large scale industrial network. Then, the worst-case delay analysis to guarantee deterministic communication on such a network is crucial. However, due to the heterogeneities existing in such a network, the problem of worst-case delay analysis is complex.

In this work, we propose two approaches to solve this problem [START_REF]Applying Trajectory approach for worst-case delay analysis of a heterogeneous real-time network[END_REF][START_REF]Worst-case delay analysis on a real-time heterogeneous network[END_REF]. The component-based approach divides the network into several components based on its properties and keeps network properties at each component level. This approach is executed at each component level and allows us to build a large scale network with flexibility and scalability. The Trajectory approach integrates heterogeneities by unifying parameters along each path. It allows us to consider for each frame the worst-case scenario along its heterogeneous path and avoid being holistic.

The organization of this thesis is described as follows.

Chapter 1 introduces the basis of the real-time switched Ethernet network context and the worst-case delay analysis. A literature review of existing approaches of worst-case delay analysis is also presented. The offset constraint is illustrated on a network example. It has been shown that for two periodic flows with known offsets emitted by the same source node, there is a minimum duration between their frame arrivals. Thus the scenario where their frames arrive at the same time can be impossible. Then the consequences on the worst-case delay analysis are emphasized.

Chapter 2 first introduces the classical Network Calculus approach applied to the switched Ethernet network. Then a modified Network Calculus is proposed with the integration of constraints of minimum durations. The computation is conducted at each output port along the path. At each output port, dependent flows are first classified into subsets. Any two flows in one subset have minimum duration constraints. Then the integration is implemented in the arrival curve of each subset. The modified approach is illustrated on a small network example.

Chapter 3 first presents the application of the classical Trajectory approach to the switched Ethernet network. We propose a modified Trajectory approach which integrates the constraints of minimum durations. This approach first classifies the dependent flows into subsets. Any two flows in one subset have minimum duration constraints. Then for each subset, its maximum delay is computed with the integration of minimum duration constraints. The modified approach is also illustrated on the same small network example used in the second chapter.

Chapter 4 introduces the Avionics Full-DupleX switched Ethernet network (AFDX) as a real-time switched Ethernet example. The evaluations on an industrial AFDX configuration for the modified Network Calculus approach and the modified Trajectory approach are conducted. The comparison between the two approaches in terms of worst-case delay upper bound is shown. This chapter also evaluates different offset assignment algorithms for the industrial AFDX configuration based on a proposed optimal scenario. The obtained results show how far the different offset assignment algorithms are from the optimal case. Chapter 5 analyzes the factors of the Trajectory approach which introduce pessimism in the computation. Based on each factor, an analytical method to calculate an underestimated value of the worst-case delay is developed. The difference between an underestimated value of the worst-case delay and a worst-case delay upper bound gives an analytical measurement of maximum introduced pessimism. The pessimism analysis is further developed accounting for the offset constraints and applied on the industrial AFDX network.

Chapter 6 gives a look at a future research direction. A heterogeneous network architecture where a switched Ethernet backbone interconnects existing CAN buses through bridges is presented. In the context of such architectures, two approaches are proposed for the worstcase delay analysis. The component-based approach is applied in this context by defining the interface of each network component. The Trajectory approach is adjusted and modified for the heterogeneous network by unifying heterogeneities along each path. The two proposed approaches are compared based on a middle scale network example. However, fieldbus technologies offer a limited bandwidth (up to 1 M bit/s) which cannot cope with the increasing demand of data exchange of the industrial applications. In the context of avionics, the mono-emitter feature of the ARINC 429 leads to a huge number of buses which is unacceptable in terms of weight and wiring complexity. Ethernet is a very popular communication technology in the context of non real-time applications. It provides large bandwidth for data transmission (from 10 M bit/s to 10 Gbit/s). It is a cost-effective solution due to its steadily decreasing cost brought by mass production. However, vintage Ethernet is not suitable for real-time applications. Indeed, it is based on CSMA/CD which is not deterministic. Thus, it is impossible to bound the time needed for a successful transmission of a given frame.

Chapter 1

Worst-case delay analysis of switched Ethernet networks

Many solutions have been proposed in order to make Ethernet real-time. In this thesis, such a solution is considered . It is based on a full-duplex switched Ethernet with traffic assumptions on the incoming flows. Such assumptions have been made in the context of avionics networks [ACC08]. As we will see, the end-to-end delay of a frame transmitted on this network highly depends on the generation time of the other frames in the network. Fortunately, it has been shown that this end-to-end delay can be upper bounded [SKS02, Son01, FJJ09, CEL05, LH04a, LH04b, BSF09, BSF10, BSF12].

The aim of this chapter is to summarize the evolution of Ethernet toward more or less realtime solutions , to present the network solution which is considered in this thesis, to present the existing approaches for the end-to-end delay analysis of such networks and to justify the contribution of the thesis.

In this Chapter, Section 1.2 first presents the Ethernet evolution and its real-time solutions. Section 1.3 defines network and traffic model of a real-time switched Ethernet network. Section 1.4 defines the end-to-end delay of a real-time flow and illustrates its best and worst cases. Section 1.5 introduces existing approaches for the worst-case delay analysis. Section 1.6 illustrates minimum duration constraints existing between dependent flows and derives its computation. Section 1.7 concludes this chapter.

Context of real-time Ethernet

Evolution

The first "Ethernet" was proposed by Metcalfe and his Xerox PARC colleagues in 1972. It is based on the use of a shared media and an access algorithm called Carrier Sense Multiple Access with Collision Detection (CSMA/CD). Coax cables were used in baseband mode, thus allowing only unicast transmissions. Each coax cable constitutes one collision domain, where only one station may send at the same time, and one broadcast domain, where any station receives the current frame sent. Coax cables can be connected by repeaters in order to extend the Ethernet segment. Early Ethernet topology is shared bus, such as 10Base2 and 10Base5.

The disadvantages of the early bus topology are: 1) if there is a break or a fault happening, it impacts several nodes in the network, even the whole network; 2) Any adding/removing node disrupts network; 3) It is inconvenient to locate the break of the coax cables.

Therefore, a new Ethernet topology was proposed which is called a star topology. Nodes are interconnected by a hub device (basically multi-port repeater) using cheap unshielded twistedpair (UTP) cable, like 10BaseT. This is also known as "CSMA/CD in a box". One advantage of such a topology is that it allows the reuse of the structured cabling already installed in the building. Another advantage is that single cable break/fault effects only one node. However, such a topology still leads to one single collision and broadcast domain, which is a logical bus.

For performance reasons, bridging was created to communicate at the data link layer while isolating the physical layer. Bridges are store and forward devices which introduce significant delay. It can filter traffic based on the addresses associated with each port and it forwards network traffic only to the necessary segments to avoid unnecessary flooding of frames to certain segments. It also checks frames which means that only well-formed Ethernet frames are forwarded from one Ethernet segment to another; therefore collisions and frame errors are isolated. Thus, bridges segment the network into several collision domains. However, broadcast traffic is still forwarded to all network segments (one single broadcast domain).

The switch has been introduced in order to satisfy increasing data exchanging demand. A switched Ethernet is based on star topology. The full-duplex communication on twisted pair cables allows a collision-free Ethernet (no collision domain). Such a technique allows simultaneous transmissions between different nodes. A switch supports different transmission rates on different ports, special forwarding techniques (cut through or store and forward) etc.. Thus switched Ethernet is a collision-free plug and play scalable Ethernet. Moreover, Virtual LANs allows to split the network into several broadcast domains.

Full duplex switched Ethernet networks have received increasing attention in the industrial domain since it can offer a higher bandwidth for data transmission and a steadily decreasing cost of components. In the following paragraphs, we will introduce the characteristics of switched Ethernet designed for industrial real-time applications.

Real-time Ethernet solutions

Nowadays, Ethernet is the fastest growing segment of industrial networking due to its increased bandwidth plus its decreased product costs which can satisfy the timing requirement of realtime applications. Demand for Ethernet as a real-time control network is therefore increased. Since standard Ethernet is not able to reach the requirements of the real-time Ethernet, different solutions to modify the Ethernet have been proposed. Some of the material in this chapter are taken from [START_REF] Felser | Real-time Ethernet -industry prospective[END_REF][START_REF] Decotignie | Ethernet-based real-time and industrial communications[END_REF], to which the reader is referred for a more detailed overview of this subject. There are in principle three different approaches [START_REF] Felser | Real-time Ethernet -industry prospective[END_REF] for a real-time Ethernet solution:

• Top of TCP/IP approach builds real-time modification over unchanged TCP/UDP/IP protocols. Such an approach simply uses a real-time protocol over TCP/UDP/IP protocols without any special modification. Existing propositions include Modbus/TCP [Aut],

EtherNet/IP [START_REF] Schiffer | The CIP family of fieldbus protocols and its newest member-Ethernet/IP[END_REF], P-NET on IP [START_REF]P-NET on IP: Proposal for a publicly available specification for real-time Ethernet[END_REF] etc.. Such a solution provides only soft real-time communications due to the adoption of TCP/UDP/IP protocols.

• Top of Ethernet approach bypasses the TCP/UDP/IP protocols and accesses directly to the Ethernet functionality. It realizes real-time protocol directly over the Ethernet without altering its hardware. This approach enhances real-time guarantees by using master-slave system and/or time slicing mechanism. Some real-time applications, for example the real-time avionics application, demands hard real-time constraints and fully distributed network solution without a global clock (no global synchronization). In that case, the Top of TCP/IP approach cannot satisfy the stringent timing constraint, while the Top of Ethernet approach which is built on a master-slave scheduling and the Modified Ethernet approach which requires network synchronization cannot provide the required network architecture.

Real-time switched Ethernet network

A real-time switched Ethernet network is a network able to provide a determined data transmission service. The full-duplex communication eliminates the collision domains, but it shifts the problem to the switch level. Main assumption of the network is that the end-to-end delay of each flow should be upper bounded. Several works [LH04a, GRD02, JNTW02, FJJ09] have studied the real-time communication over a switched Ethernet network having the following features:

• full-duplex communication, which eliminates collisions on links;

• static routing mechanism, which uses a static routing table in each switch to avoid dynamic mechanisms such as a spanning tree.

-Real-time switched Ethernet network

• traffic shaping, which controls at each source node the maximum rate at which the traffic is sent. More precisely, the traffic shaping technique guarantees the minimum inter-frame duration between two consecutive frames of a flow. This is a main characteristic of a realtime switched Ethernet network since without a shaped traffic entering the network, it would be impossible to upper bound the end-to-end delays.

In our work, we consider the same network model which is described in the following paragraphs.

Network model

The real-time switched Ethernet network architecture is composed of a set of nodes interconnected by a full duplex switched Ethernet. It is a homogeneous single network.

The inputs and outputs of the network are nodes. Each node manages a set of flows and emits flows through an output port with a buffer supporting a scheduling strategy (First In First Out, FIFO for short, as an example). It can be connected to only one port of a switch and each port of a switch can be connected at most to one node.

Each switch uses a classical IEEE 802.1d store and forward policy. It has one buffer at each output port which supports a scheduling strategy. It receives frames from input ports and forwards them to the corresponding output ports based on a static routing table. There is a switching latency to deal with the frame forwarding between an input port and an output port of a given switch and it is upper bounded by a known value sl.

Links between switches are full-duplex defined by IEEE 803.1e. The full duplex characteristic guarantees that there are no collisions on links. The bandwidth (transmission rate) of the network is denoted by R (100M bit/s for example).

The nodes and the switches are not synchronized due to the lack of a global clock. A sample network architecture is depicted in Figure 1.1. It includes four nodes N 1 , N 2 , N 3 and N 4 interconnected by two switches S 1 and S 2 via full-duplex links.

Flow model

We assume that n flows τ i , i ∈ 1, n are transmitted over the network in order to exchange data. Each flow is unidirectional. It has one emitter and a non empty set of receivers (multicast). Thus n i paths P i,j (j ∈ 1, n i ) are associated to each flow τ i . Each path is defined by a sequence of output ports f irst i , ..., last i,j and a destination node dest i,j . These notations are summarized in Figure 1.2. • the minimum inter-frame duration T i ,

1,1 = {N 1 , S 1 , S 2 , N 4 }. Its source node is f irst 1 = N 1 . Its last visited output port is last 1,1 = S 2 and its destination node is dest 1,1 = N 4 .
• the maximum transmission time of one frame C i ,

• the maximum release jitter J i which is the maximum delay between the generation time of a frame and its arrival at the output port of the source node, and

• the offset O i which is the generation time of the first frame of τ i .

Figure 1.4 summarizes these temporal features for both a sporadic and a periodic flow. f i,j denotes the j th frame of τ i . The generation times are represented by ↓ and the frame arrivals in the first output port are represented by ↑. Each frame arrives within an interval of J i after its corresponding generation time. The generation time of the first frame of τ i at its source node is the offset O i . The offset of a given flow can be known or not.

Classically, the inter-frame duration is always exactly T i for a periodic flow τ i . It is at least T i for a sporadic flow. In a typical industrial application, up to 80% of the flows are periodic [START_REF] Jasperneite | Deterministic real-time communication with switched Ethernet[END_REF]. A periodic flow with a strict period and an offset leads to an exact knowledge of frame generation times at the source node.

f i,1 i O T i J i f i,1 T i J i f i,2 i C i C i C f i,2 f i,3 f i,3 i C i C i C T i J i T i J i i O 0 0 t t a periodic flow J i J i a sporadic flow

A real-time switched Ethernet example: AFDX network

Avionics Full DupleX Switched Ethernet (AFDX) [ACC08] is a typical real-time switched Ethernet network. It has been defined in the context of avionics and developed for modern aircraft such as Airbus A380. It interconnects a set of end systems (ES) by a full-duplex switched Ethernet network. Each flow transmitted on this network is called a V irtual Link (V L). It is a multicast sporadic flow with static routing (Actually many VLs are periodic). The minimum inter-frame duration T i is called the Bandwidth Allocation Gap (BAG i ). Possible values range in powers of 2 from 1 ms to 128 ms. The transmission time of a frame depends on the frame length and on the rate R of the link. Each VL v i defines a minimum frame length and a maximum frame length (l min i and l max i ) which respect the standard Ethernet frame. Thus, the maximum transmission time C i of one frame of VL v i is computed by:

C i = l max i * 8 R J i and O i follow the definitions in Section 1.3.2.

End-to-end delay analysis on a real-time switched Ethernet

The following paragraphs characterize the end-to-end delay of a frame transmitted on a realtime switched Ethernet.

End-to-end delay

Let us consider one frame of a flow τ i . For the sake of simplicity, this frame is denoted f i . This frame follows one of the paths of τ i . For the sake of simplicity, this path is denoted

P i = [f irst i , .
.., last i , dest i ] (We omit the index of the path).

The end-to-end (ETE) delay of a flow τ i is the time elapsed between the generation time of f i at its source node f irst i and the reception time of f i at its destination node dest i . The ETE delay R i of f i is given by:

R i = j i + LD i + SD i + W D i (1.1)
where j i is the release jitter of f i ; LD i is the transmission time on links along the considered path P i ; SD i is the delay caused by switching latency sl of all the visited switches; W D i is the waiting delay caused by competitions with other frames in the output buffers.

The propagation delay is not considered in this work since it is considered negligible. For a twisted pair cable of 100 meter, the maximum length for a cable segment per TIA/EIA 568-5-A [START_REF]The Evolution of Copper Cabling Systems from Cat5 to Cat5e to Cat6[END_REF], the propagation delay is about 560 nanoseconds. Therefore, the propagation delay is not taken into account in the end-to-end delay computation.

Let us consider the end-to-end delay of the first frame f 1 of flow τ 1 in Figure 1.3. It follows the path P 1 = {N 1 , S 1 , S 2 , N 4 }. One possible scenario is depicted in Figure 1.5. f 1 is generated at its source node N 1 at its offset time O 1 . It experiences a release jitter j 1 (0 ≤ j 1 ≤ J 1 ) and arrives at the output port of N 1 at time a N 1 f 1 . Since another frame f 2 of flow τ 2 arrives at the same output port earlier than f 1 and does not finish its transmission when f 1 arrives, f 1 waits in the buffer till the transmission of f 2 finishes. τ 2 is called an interference (or a competing) flow of τ 1 since it shares an output port with τ 1 .

f 1 arrives at the switch S 1 where it first experiences an upper bounded switching latency sl. Then f 1 waits in the buffer of the output port of S 1 due to the transmission of f 2 which was delayed by a frame f 3 of τ 3 . Similarly, at the switch S 2 , f 1 experiences a switching latency sl and delays caused by the transmissions of other frames (f 3 , f 5 and f 2 ). Finally, f 1 arrives at its destination node N 4 . In Figure 1.5, the transmission delay LD 1 and the waiting delay W D 1 of f 1 are indicated by blocks with different patterns. The release jitter j 1 and switching latency at each visited switch are also marked in Figure 1.5. The end-to-end delay R 1 of f 1 is shown by a shadow block in Figure 1.5.

Minimum end-to-end delay

The minimum end-to-end delay of a flow τ i happens when τ i does not experience release jitter or competition with other frames for the output ports along its path. The lowest possible value of end-to-end delay is obtained when j i = 0 and W D i = 0 (no waiting delay in output buffers). Thus, the minimum ETE delay of a frame is the sum of LD i and SD i . The minimum delay of flow τ 1 is illustrated in Figure 1.6. LD i is obtained by considering that one frame of τ i with minimum length l min i is transmitted. |P i | is the number of nodes in the path P i . Then the frame of τ i crosses |P i | -1 links, and we have:

LD i = (|P i | -1) × l min i R Since τ i crosses |P i | - 2
switches, we have:

SD i = (|P i | -2) × sl
Thus the minimum end-to-end delay of a flow can be easily computed.

Maximum end-to-end delay

The maximum end-to-end delay is obtained when each term in Formula 1.1 is upper bounded. Let us examine each of those terms:

• The release jitter j i has a maximum value J i which is a feature of the flow.

• The transmission delay on links is maximized when a frame with maximum transmission time C i is transmitted. Thus we have:

LD i = (|P i | -1) × C i
• The switching latency is upper bounded. Thus we have:

SD i = (|P i | -2) × sl
• The waiting delay W D i in output buffers depends on the arrival times of competing frames at each output port crossing τ i . This is illustrated in Figure 1. We can conclude that in order to get the maximum end-to-end delay, we have to determine the maximum possible value of W D i . Up to now, this is still an open problem. Some approaches have been proposed in order to solve this problem. They are summarized in the following section.

Existing approaches for worst-case delay analysis

Three groups of approaches have been investigated for the worst-case delay analysis of a realtime switched Ethernet network.

• The goal of the first group is to calculate the end-to-end delay on a set of scenarios. It leads to a distribution of the delay. The highest delay of this distribution is an observed worst-case delay. The typical approach of this group is the simulation approach.

• The goal of the second group is to calculate an exact worst-case end-to-end delay. This is achieved by an exhaustive exploration of the possible scenarios. This group of approaches is based on Model-Checking (MC) and they are not scalable.

• The goal of the last group is to compute a sure upper bound of the end-to-end delay. These approaches (mainly the holistic approach [TC94, TBW95a], the Network Calculus approach ,NC for short, and the Trajectory approach) upper bound all the parts of the delay. Most of the time, they are scalable.

Figure 1.8 summarizes these different groups of approaches. When possible, the Model-Checking approach gives the exact worst-case end-to-end delay. Otherwise, the other approaches give an interval where these worst-case delays are. The following paragraphs give a short overview of the existing calculations for all the approaches.

Simulation

A simulation approach is based on a model of the system. The goal is to get informations concerning the typical behaviors of the system. These informations are accurate as long as the model captures the features of the systems. A simulation approach has been proposed for the temporal analysis of a switched Ethernet network [GRD02, CSEF06, SRF09, DH03, SF07, MFF07]. The goal was to obtain the end-to-end delay distribution of a given flow. The main issue is to cope with the huge set of possible scenarios when an industrial network configuration is considered. One solution has been proposed in [START_REF] Scharbarg | Simulation for end-to-end delays distribution on a switched Ethernet[END_REF][START_REF] Scharbarg | A probabilistic analysis of endto-end delays on an AFDX avionic network[END_REF]. It consists in focusing the simulation on the part of the network configuration which has an influence on the distribution of the considered flow. With this approach, it is possible to analyze most of the flows of a typical avionics configuration. [START_REF] Georges | Evaluation of switched Ethernet in an industrial context by using the network calculus[END_REF] considers a switched Ethernet network with shaped traffic, while [START_REF] Dolejs | Simulation of Ethernet for real-time applications[END_REF] analyzes a similar network with a time-division scheme. The simulation approach gives valuable informations concerning the delay distribution and a maximum observed delay of each flow. However, this maximum observed delay is most of the time smaller than the exact worst-case delay, since this worst-case is often a rare event which is missed by the approach. This approach is not considered in the rest of this thesis.

Model-checking

Model-checking [BBF + 10] allows the automatic verification of software and reactive systems. It performs a reachability analysis on a model of the system. There exist different formalisms for the modeling of the system. Timed automata [START_REF] Alur | A theory of timed automata[END_REF] is one of the most popular among these formalisms. These automata describe the system behaviors with times. A model is composed of a set of finite automata with a set of clocks (real and possible variables increasing uniformly with time). Preliminary approaches have been proposed in the context of a mixed TTCAN/switched Ethernet architecture [START_REF] Ermont | Worst-case analysis of a mixed CAN/switched Ethernet architecture[END_REF] and an avionics switched Ethernet [START_REF] Charara | Method for bounding end-to-end delays on an AFDX network[END_REF]. The later one cannot cope with more than 8 flows due to the well-known combinatorial explosion problem.

A promising idea to miligate this problem is to drastically limit the research space. It consists in considering only the scenarios which are candidates to the worst-case. In [START_REF] Adnan | Minimizing the search space for computing exact worst-case delays of AFDX periodic flows[END_REF][START_REF] Adnan | An improved timed automata approach for computing exact worst-case delays of AFDX sporadic flows[END_REF], properties of such scenarios have been established. Thanks to these properties, it is possible to get the exact worst-case delay for network configurations with up to 60 flows, which is a significant improvement. However, up to now, this approach cannot cope with industrial configurations with 1000 flows. Thus it will not be considered in the rest of this thesis.

Network Calculus

Network Calculus was first proposed by Cruz [START_REF] Cruz | A calculus for network delay, part 2[END_REF], and then applied to guaranteed service networks by Le Boudec et al. [START_REF] Boudec | Application of network calculus to guaranteed service networks[END_REF][START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]. This approach is considered as a holistic approach. The holistic approach considers the worst-case scenario on each node visited by a flow, accounting for the maximum possible jitter introduced by the previous visited nodes.

A generation of the Network Calculus approach has been applied to the switched Ethernet network in order to guarantee its real-time communication [START_REF] Loeser | Low-latency hard real-time communication over switched Ethernet[END_REF] by using firmware offloading to lower the CPU utilization. [START_REF] Cholvi | On the feasible scenarios at the output of a FIFO server[END_REF] focuses on the scenarios at the output port of a FIFO multiplexer. It demonstrates that iteratively applying the "optimal" output bounds when flows pass through several FIFO nodes does not guarantee the overall tight bound. [START_REF] Lenzini | Delay bounds for FIFO aggregates: a case study[END_REF] refines the service curves of the Network Calculus to improve end-to-end delay bounds for FIFO aggregates. [START_REF] Fan | Guaranteed real-time communication in packet-switched networks with FCFS queuing[END_REF] improves the delay bounds of a packet-switched network by refining the Network Calculus for the source node and the switch connected to the source node. In [START_REF] Frances | Using network calculus to optimize the AFDX network[END_REF], this approach has been improved by considering serialization effect, which refers to the fact that frames transmitted by the same input link are serialized and cannot arrive at the output port at the same time. The Network Calculus provides delay upper bounds with pessimistic computation. Then these upper bounds can be larger than the exact worst-case delays, as shown in Figure 1.8.

Network Calculus approach provides a theoretical framework to analyze performance guarantees (backlog bound, delay bound and output flow) in a network. It computes the delay upper bound at a node h by considering a maximum arriving flow traffic and a minimum service capacity provided by node h. The maximum arriving traffic is modeled by the arrival curve α(t) for t ≥ 0, which limits the traffic sent by source nodes by an upper bounded curve. It means that on any time window of width τ , the number of bits for the flow is limited by α(τ ). The minimum service provided by node h is modeled by the service curve β(t) for t ≥ 0 which guarantees that on any time window of width τ , the traffic of at least β(τ ) can be served. Therefore, the delay upper bound is determined by considering the maximum time interval between the arrival of an amount of traffic till its departure (being served) at node h, which is the maximum horizontal distance between the arrival curve α(t) and the service curve β(t), and presented by h(α, β). For several flows multiplexed at a node h, the overall arrival curve is the sum of the arrival curve of each arriving flow, which corresponds to the case where a frame of each arriving flow arrives at the same time at the node h. The details of the approach can be found in Appendix A, and a brief review of the approach applied on a switched Ethernet can be found in Chapter 2.

Trajectory approach

Trajectory approach was first proposed in [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF] to cope with worst-case response time of flow with FIFO scheduling, and it was expended for the Fixed Priority (FP) scheduling in [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF] and for the Non-preemptive Fixed Priority/Earliest Deadline First (FP/EDF) scheduling in [START_REF]The Trajectory approach for the end-to-end response times with nonpreemptive FP/EDF*[END_REF]. It is further applied to an avionics switched Ethernet network with FIFO scheduling in [START_REF] Bauer | Applying and optimizing trajectory approach for performance evaluation of AFDX avionics network[END_REF][START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF] as well as with FP scheduling in [START_REF]Applying Trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF] with an integration of frame serialization. In [START_REF] Martin | End-to-end response time with fixed priority scheduling: Trajectory approach versus holistic approach[END_REF], it has been shown that the Trajectory approach is less pessimistic than the holistic approach for a distributed system. In [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF], it has shown interesting properties of worst-case delay analysis on the avionics application as it can bring tighter delay upper bounds than the Network Calculus approach. Therefore it is interesting to consider the Trajectory approach for the delay upper bound computation. The Trajectory approach calculates pessimistic delay upper bounds which can be larger than the exact worst-case delays, as shown in Figure 1.8.

The Trajectory approach considers the worst-case scenario that can happen to a frame along its trajectory instead of considering the worst-case scenario on each node visited by a flow. Therefore it is not holistic. The approach computes the delay upper bounds by maximizing each part of delay generated along the considered path as illustrated in Figure 1.7. The release jitter of a considered flow is upper bounded by the maximum value. The switching latency is upper bounded by the value sl and the number of switches visited by the considered flow. The transmission delay can be maximized by considering the largest frame transmission at each visited node. The waiting delay generated by other competing flows is maximized by considering the maximum possible number of frames of each competing flow that can delay the considered flow. Therefore, the computed delay upper bound is the sum of the upper bound of each part of delay. The details of the approach can be found in Appendix B, and a brief review of the approach applied on a switched Ethernet can be found in Chapter 3.

Temporal constraints of dependent flows 1.6.1 Minimum duration

The three approaches for the worst-case delay analysis on a real-time switched Ethernet network make no assumptions on the generation instants of the frames (except that they are shaped). This is realistic when flows are generated by different nodes since these nodes do not have a common clock. This is not always the case for flows generated by the same node. Indeed periodic flows are constrained by their offsets and periods. Then periodic flows emitted by the same source node are scheduled based on the same local clock, and therefore they are called locally synchronized and they are dependent. The dependencies lead to a limitation on the number of possible scenarios at the output ports. We will show in the following chapters that integrating this limitation in the worst-case delay analysis can significantly reduce the obtained upper bounds on the delays.

Let us illustrate the impact of offsets and periods for periodic flows generated by the same node. We consider a reference network example in Figure 1.9. This network example supports FIFO scheduling. The transmission rate is R = 100 M bit/s and the switching latency is sl = 10 µs.

Five flows are transmitted over the network example. There are two periodic flows τ 1 and τ 2 generated at node N 1 , and two periodic flows τ 3 and τ 4 generated at node N 2 . Flow τ 5 is an independent flow emitted by node N 3 . They have parameters listed in Table 1.1:

The hyper-period of a flow τ i and a flow τ j is the Least Common Multiple of periods T i and T j , i.e., lcm(T i , T j ). Since the hyper-period lcm(T i , T j ) is the multiple of both T i and T j , t4 t5 t6 t7 t1 t2 t3 t5 t7 t6 t4 t4 t5 t6 t7 t8 t8 t9 t10 t11

Figure 1.9: A reference network example the frame generation sequence of these two flows infinitely repeats since flows are periodic. Therefore, we consider the frame generation sequence in one hyper-period. We focus on flows τ 1 and τ 2 in Figure 1.9. Figure 1.10 depicts the sequence of frame generations of τ 1 and τ 2 on a hyper-period (lcm(T 1 , T 2 ) = 4000 µs).

τ i T i (µs) C i (µs) O i (µs) J i (
Based on the periods and offsets, frames of τ 1 are ready at the time instant k * 2000 µs, while frames of τ 2 are ready at the time instant 3500 + l * 4000 µs. Thus there is a minimum duration of 1500 µs from the arrival time of a frame of τ 1 to the arrival time of a frame of τ 2 at the output port of N 1 . The minimum duration is 500 µs in the reverse order. Release jitters are null in Table 1.1 and in Figure 1.10. We consider release jitters of flows as shown in Table 1.2.

Integrating these release jitters leads to the sequence in Figure 1.11. ↓ represents the frame generations and ↑ represents the frame arrivals. Each frame can be delayed and is ready at any time instant of an interval (maximum release jitter) after its generation. Frames of τ 1 are ready in the intervals [k * 2000, 500 + k * 2000], while frames of τ 2 are ready in the intervals [3500 + l * 4000, 3600 + l * 4000]. Thus there is a minimum duration of 1000 µs from the arrival time of a frame of τ 1 to the arrival time of a frame of τ 2 at the output port of N 1 . This For the purpose of simplicity, we consider Table 1.1 as the flow parameters in the rest of the thesis. Such a duration can be determined for any couple of flows at one shared output port. This minimum duration is null as soon as one of the two flows is not periodic or when the two flows are not generated by the same node.

τ i T i (µs) C i (µs) O i (µs) J i (
More formally, the minimum duration from any frame f i of τ i to any frame f j of τ j transmitted after f i at the output port h is denoted M D h i,j . M D h i,j is null as soon as τ i or τ j is not periodic or when the τ i and τ j are not generated by the same node.

The minimum duration propagates along the path followed by the flows. However, it can decrease from one node to the following one. This is illustrated in Figure 1.12 considering flow τ 1 in the example in Figure 1.9. It shows that the scheduling of the flows along their path and the evolution of the minimum duration from one frame arrival of τ 1 to one frame arrival of τ 2 . The computations of M D N 1 1,2 , M D S 1 1,2 and M D S 2 1,2 are detailed in the following paragraphs.

Computation of minimum duration

In order to compute the minimum duration M D f irst i i,j from one frame arrival of flow τ i to one frame arrival of flow τ j in their source node f irst i , we have to consider all the frame generations of τ 1 and τ 2 during one hyper-period. We illustrate the computation on flows τ 1 and τ 2 in the example in Figure 1.9. Figure 1.13 shows frame arrivals of τ 1 and τ 2 . Since the hyper-period of τ 1 and τ 2 is 4000 µs, for the computation of M D N 1 1,2 , we consider frame arrivals in the time interval [O 1 , O 1 + 4000) = [0, 4000) during which there are the first two frame arrivals of τ 1 and the first frame arrival of τ 2 . The duration from the first frame arrival of τ 1 to the first frame arrival of τ 2 is 3500 µs, and the duration from the second frame arrival of τ 1 to the first frame arrival of τ 2 is 1500 µs. Therefore the minimum duration from a frame arrival of τ 1 to a frame arrival of τ 2 is 1500 µs. In the reverse order, we consider frame arrivals in the time interval [O 2 , O 2 + 4000) = [3500, 7500). Similarly, the minimum duration from a frame arrival of τ 2 to a frame arrival of τ 1 is 500 µs. The computation of the minimum duration at the source node can be formalized in the following way. Two periodic flows τ i and τ j are emitted by their source node f irst i . They have known offsets O i and O j . Let us denote M D f irst i i,j (k, l) the time interval from the k th frame generation of τ i to the l th frame generation of τ j . It is computed by

M D f irst i i,j (k, l) = (T j • l + O j ) -(T i • k + O i ) (1.2)
We consider frame generations in a hyper-period lcm(T i , T j ) during which the frame generations are repeated. The first frame generation of τ i is at time O i , then we consider frame generations in a time interval [O i , O i + lcm(T i , T j )). Since all the frame generations of τ i are ready at time instant O i + T i * k, we have:

O i ≤ O i + T i * k < O i + lcm(T i , T j )
Then it leads to the computation range of k as follows:

k ∈ 0, lcm(T i , T j ) T i -1
Similarly, all the frame generations of τ j are ready at time instant O j + T j * l, and then we have:

O i ≤ O j + T j * l < O i + lcm(T i , T j )
which leads to the computation range of l as follows:

l ∈ O i -O j T j , O i -O j + lcm(T i , T j ) T j -1
Let us consider the computation of M D N 1 1,2 (k, l). The computation range of k is 0, 1 , and the computation range of l is 0, 0 . Then we have all the possible values of

M D N 1 1,2 (k, l) as listed in Table 1.3. M D N 1 1,2 (k, l) k 0 1 l 0 3500 µs 1500 µs Table 1.3: All the possible values of M D N 1 1,2 (k, l)
Similarly for the computation of M D N 1 2,1 (k, l), all the possible values are listed in Table 1. [START_REF]An illustrative industrial AFDX network architecture The network is composed of 123 end systems, 8 switches per network[END_REF].

Since M D f irst i i,j
is achieved only if the frame of τ i experiences maximum release jitter J i and the frame of τ j does not experience any release jitter, the minimum duration

M D f irst i i,j
is the maximum value between 0 and the smallest possible non negative value of

M D f irst i i,j (k, l) minus J i : M D f irst i i,j = ( min M D f irst i i,j (k,l)≥0 (M D f irst i i,j (k, l)) -J i ) + (1.3) M D N 1 2,1 (k, l) k 0 l 2 500 µs 3 2500 µs Table 1.4: All the possible values of M D N 1 2,1 (k, l)
for any k and j in the computation ranges:

k ∈ 0, lcm(T i , T j ) T i -1 , l ∈ O i -O j T j , O i -O j + lcm(T i , T j ) T j -1
For

N 1 = f irst 1 in Figure 1.9, M D N 1 1,2 (k, l) = (4000 × l + 3500) -(2000 × k + 0). Then M D N 1 1,2 = 1500 µs when k = 1, l = 0. Similarly, the minimum duration from τ 2 to τ 1 at N 1 is M D N 1
2,1 = 500 µs when k = 0, l = 2. They are illustrated in Figure 1.13. For two flows τ i and τ j emitted by the same source node f irst i and sharing the output ports from f irst i till h, the minimum duration from τ i to τ j propagates at each switch output port of their shared path. The general case is depicted in Figure 1.14. The frame f i of τ i and the frame f j of τ j are separated by M D f irst i i,j at their source node f irst i , which can be determined by Equation 1.3. When f i and f j arrive at the output port h, one possible scenario is shown in Figure 1.15.

Frames f i and f j experience different delays from f irst i to h as they can be delayed by different competing flows. Since the minimum duration M D h i,j from τ i to τ j at h is the minimum possible time interval, then it is obtained when the delay experienced by f i from f irst i to h is maximized and the delay experienced by f j from f irst i to h is minimized. It may not be equal to M D f irst i i,j as illustrated in Figure 1.15. Hence, it is necessary to compute the minimum duration at each shared switch output port. t2 t3 t2 t3 t1 t4 t5 t6

Figure 1.14: General case The maximum delay of f i from f irst i to h is denoted S h max i , and occurs when f i is delayed by all possible competing flows at each crossed switch between f irst i and h. This delay can be computed by worst-case delay computations which will be introduced in Chapter 2 and in Chapter 3. The minimum delay of frame f j from f irst i to h is denoted S h min j and occurs when f j is not delayed by any competing flows. Provided that the transmission rate of switched Ethernet is R, there are n h links between f irst i and h, and the switching latency is sl, the

S h min j = ( l min j R × n h ) + sl × (n h -1) (1.4)
Therefore, M D h i,j is a non negative value and determined by:

M D h i,j = (M D f irst i i,j + S h min j -S h max i ) + (1.5)
The computation of the propagated minimum duration is illustrated by the reference example where M D N 1 1,2 = 1500 µs. Since τ 1 and τ 2 are not delayed by any other flow at N 1 , when they arrive at S 1 , they experience the maximum delays S S 1 max 1 = S S 1 max 2 = 40 µs. Assuming that these flows have a constant frame length, the minimum delays of τ 1 and τ 2 are S S 1 min 1 = S S 1 min 2 = 40 µs. Then M D S 1 1,2 (illustrated in Figure 1.12) is computed by Equation 1.5:

M D S 1 1,2 = (M D N 1 1,2 + S S 1 min 2 -S S 1 max 1 ) + = 1500 + 40 -40 = 1500 µs
This computation propagates to the output port of S 2 . Since τ 1 is delayed by flow τ 3 at the output port S 1 (the reason will be explained in the following chapters) while τ 2 is not delayed by any other flows at S 1 , when they arrive at S 2 , τ 1 experiences a maximum delay S S 2 max 1 = 120 µs while τ 2 experiences a minimum delay S S 2 min 2 = 80 µs. Then M D S 2 1,2 (illustrated in Figure 1.12) is computed by Equation 1.5:

M D S 2 1,2 = (M D N 1 1,2 + S S 2 min 2 -S S 2 max 1 ) + = 1500 + 80 -120 = 1460 µs
Similarly, the minimum durations from τ 2 to τ 1 along the path {N 1 , S 1 , S 2 , N 4 } as well as the minimum durations from τ 3 to τ 4 and from τ 4 to τ 3 along the path {N 2 , S 1 , S 2 , N 4 } can be determined by Equation 1.3 and Equation 1.5, and they are listed in Table 1.5. Since N 1 and N 2 do not share one common clock, τ 1 and τ 2 are not synchronized with τ 3 and τ 4 . Then the temporal constraints between flows of N 1 (τ 1 , τ 2 ) and flows of N 2 (τ 3 , τ 4 ) are not considered.

h M D h 1,2 (µs) M D h 2,1 (µs) M D h 3,4 (µs) M D h 4,3 (µs) N 1 1500 500 - - N 2 - - 1000
These minimum duration constraints should be introduced in the worst-case delay analysis. In the following chapters, we propose such an introduction in both the Network Calculus approach and the Trajectory approach.

Conclusion

In this chapter, we presented main characteristics of real-time full-duplex switched Ethernet networks using traffic shaping at each source node. The analysis of worst-case end-to-end delay has been illustrated. The state of the practice related to our work has been shortly recalled, as well as the Network Calculus approach and the Trajectory approach that are taken into account in our work.

The existing worst-case delay analysis considers only independent flows exchanged in the network. In this chapter, it has been shown that periodic flows with known offsets emitted by the same source node are dependent. There is a minimum duration between two frames of two dependent flows. These constraints of minimum duration can eliminate some pessimistic scenarios and therefore should be integrated in the worst-case delay analysis. In the following chapters, the integration of the minimum durations in the Network Calculus approach and in the Trajectory approach are implemented.

Introduction

The existing Network Calculus approach allows the computation of an upper bound on the delay of flows transmitted on a switched Ethernet network with traffic shaping at each source node. This approach does not make any further assumptions on the generation instants of the frames. We have shown in Chapter 1 that, for periodic flows with known offsets emitted by the same source node, minimum duration constraints exist for the generation instants of the flows. The goal of Chapter 2 is to propose the integration of these minimum duration constraints in the Network Calculus approach.

32Chapter 2 -Modified Network Calculus approach integrating minimum duration constraints Section 2.2 briefly reviews the classical Network Calculus approach applied on a real-time switched Ethernet network. Section 2.3 shows the integration of the minimum duration constraints in the Network Calculus approach. Section 2.4 compares the classical Network Calculus approach with the enhanced one on an example configuration. Section 2.5 concludes this chapter.

Classical Network Calculus approach

The existing Network Calculus approach for FIFO scheduling applied to a real-time switched Ethernet network is summarized in this section. A detailed presentation of the Network Calculus approach can be found in Appendix A.

We use the example in Figure 1.9 to illustrate the classical Network Calculus approach. This example is recalled in Figure 2.1. The transmission rate is R = 100 M bit/s and the switching latency is sl = 10 µs. t4 t5 t6 t7 t1 t2 t3 t5 t7 t6 t4 t4 t5 t6 t7 t8 t8 t9 t10 t11 Five flows are transmitted over the network example. There are two periodic flows τ 1 and τ 2 generated at node N 1 , and two periodic flows τ 3 and τ 4 generated at node N 2 . Flow τ 5 is an independent flow emitted by node N 3 . They have parameters recalled in Table 2.1.

τ i T i (µs) C i (µs) O i (µs) J i (

Arrival curves

We consider real time flows shaped by leaky buckets. Each flow τ i has a maximum frame size l max i and a minimum inter-frame distance T i . Thus each flow is classically modeled by the arrival curve α i defined by:

α i (t) = r i t + b i = l max i T i × t + l max i
This arrival curve upper bounds the traffic generated by τ i .

At each output port, the overall arrival curve is obtained by adding the arrival curves of all the input traffics. More precisely, when there are n input flows with arrival curves α 1 , α 2 , ..., α n entering an output port, the arrival curve of the aggregated traffic is:

α = i∈ 1,n α i
As an example, let us consider the output port of N 1 in the example in Figure 2.1. It is crossed by two flows τ 1 and τ 2 with parameters: l max 1 = 4000 bits, T 1 = 2000 µs, l max 2 = 4000 bits, T 2 = 4000 µs. Thus, their arrival curves are:

α 1 (t) = 2t + 4000, α 2 (t) = t +
α(t) = α 1 (t) + α 2 (t) = 3t + 8000 It is shown in Figure 2.2.

Service curves

An output port of a source node transmits the arriving traffic with a transmission rate R. Thus it provides a service curve β(t) = R(t) + . An output port of a switch transmits the arriving traffic with a transmission rate R after an upper bounded switching latency sl. Then it provides a service curve β(t) = R(t -sl) + . 34Chapter 2 -Modified Network Calculus approach integrating minimum duration constraints As an example, the output port of N 1 in the example in Figure 2.1 has a service curve β(t) = 100(t) + , while the output port of switch S 1 has a service curve β(t) = 100(t -10) + .

Delay computation

According to the Network Calculus approach, for an output port with an arrival curve α and providing a service curve β, the maximum delay generated at the output port is computed by h(α, β), which is the maximum horizontal distance between α and β.

For the output port of N 1 , its arrival curve is α(t) = 3t + 8000 and its service curve is β(t) = 100(t) + , then the maximum delay is obtained by h(α, β) = 80 µs, as depicted in The end-to-end delay upper bound of τ i computed by the Network Calculus approach is the sum of the maximum delays computed at each output port visited by τ i along its path P i . Then the computation has to be propagated from the source node to the following output port till the last visited output port.

The worst-case end-to-end delay R 1 of τ 1 in the example in Figure 2.1 is the sum of the maximum delays at the output ports of N 1 , S 1 and S 2 .

The propagation is done in the following manner. At each output port h -1 on the path of the considered flow, the output port curve α h is computed from the overall arrival curve α h-1 and the service curve β h-1 of the output port. It is illustrated in Figure 2.4.

According to [START_REF] Grieu | Analyse et évaluation de techniques de commutation Ethernet pour interconnexion des systèmes avioniques[END_REF], the arrival curve of τ i at the output port h is constrained by:

α h i = α h-1 i (t + J h-1 i ) (2.1)
where J h-1 i is the maximum delay jitter encountered by τ i in the output port h -1.

This output curve becomes an arrival curve for the next output port h on the path of the t1 t2 t4 t3 We illustrate this propagation of arrival curve of flow τ 1 in the example in Figure 2.1. Its arrival curve at its source node is α N 1 1 (t) = α 1 (t) = 2t + 4000. As we have shown, it experiences a maximum delay 80 µs in the output port of N 1 . Since its transmission delay is C 1 = 40 µs, its maximum delay jitter in the output port of N 1 is J N 1 1 = 80 -40 = 40 µs. Then its arrival curve at the following output port of S 1 is: Similarly, for flows τ 2 , τ 3 and τ 4 arriving at the output port of S 1 we have:

α S 1 1 (t) = α N 1 1 (t + J N 1 1 ) = 2(t +
α S 1 2 (t) = t + 4040, α S 1 3 (t) = t + 4040, α S 1 4 (t) = 0.5t + 4020

Frame serialization

Frames coming from the same input link are serialized and they cannot arrive at the output port at the same time. This frame serialization is integrated in the approach by constraining the maximum traffic of each input link with the peak arriving rate R of link and the burst workload which is the maximum workload arriving at one time.

For example, at the output port of S 1 in Figure 2.1, frames of τ 1 and τ 2 are transmitted by the same input link from N 1 and they are serialized. They cannot arrive at the same time at the output port of S 1 and their transmission rate is limited by the link rate R. Therefore, the sum of α S 1 1 and α S 1 2 is constrained by the burst workload max(b S 1 1 , b S 1 2 ) = 4080 bits and by the link rate R as shown in Figure 2.6. Similarly, the frame serialization of α S 1 3 and α S 1 4 at the output port of S 1 is illustrated in

Limitation of the approach

The existing Network Calculus approach does not put any constraints between the flows. Typically, it assumes that frames of any two different flows can be generated at the same time. It has been shown in Section 1.6 that such a scenario might be impossible when the two flows are periodic and generated by the same node. Indeed, there can be a minimum duration between the frames of two such flows. In the rest of this chapter, we show how these minimum durations can be integrated in the Network Calculus approach.

A modified approach considering minimum duration constraints 2.3.1 General idea

The approach summarized in the previous section considers that all the flows are independent. Thus the arrival curves of all the flows crossing an output port are simply added in order to obtain the overall arrival curve at this port. It corresponds to the case where frames from each flow arrive at the output port at the same time. This is illustrated in Figure 2.8 on flows τ 1 and τ 2 at the output port of N 1 in the example in The burst 8000 bits at time t = 0 corresponds to arrivals of one frame of τ 1 and one frame of τ 2 at the same time. However, it has been shown in Section 1.6 that there is at least 1500 µs from one frame of τ 1 to one frame of τ 2 and 500 µs from one frame of τ 2 to one frame of τ 1 . Consequently, there will never be such a burst. Thus the idea of the approach is to build, for each set of dependent flows (i.e. flows with minimum durations between them), an aggregated arrival curve which takes into account these minimum durations.

Computation overview

Since the Network Calculus approach propagates the computation port by port along the considered path, the computation is presented for one output port h. Let us consider an output port where n flows compete. The computation of the overall arrival curve at port h processes in the following steps:

1. The n flows are classified in n g subsets G x , x ∈ 1, n g . Any two flows in a given subset have minimum duration constraints between them. Conversely, any two flows in different subsets have no minimum duration constraints between them.

An arrival curve α h

Gx is computed for each subset G x , x ∈ 1, n g . When the subset G x includes one single flow, α h Gx is directly the arrival curve of this flow. When the subset G x includes more than one flow, α h

Gx is an aggregation of the arrival curves of these flows.

38Chapter 2 -Modified Network Calculus approach integrating minimum duration constraints 3. The overall arrival curve at h which is obtained by adding the arrival curves of the n g subsets:

α h = x∈ 1,ng α h Gx 4.
The maximum delay at h is the maximum horizontal distance h(α h , β h ) between the overall arrival curve α h at h and the service curve β h at h.

Thus, the difference with the approach presented in Section 2.2 is the computation of an aggregated arrival curve for a set of dependent flows. This computation is detailed in the following sections.

Computation of the arrival curve of dependent flows

In order to compute the worst-case delay upper bound, we need to upper bound the arrival traffic of each subset at each output port. For a subset G x , since the arrival traffic is the sum of all the flows in the subset, there can be a huge number of possibilities. The arrival curve α h Gx constrains the maximum arrival traffic of all the flows in subset G x , and it is determined by the worst-case scenario of the subset G x at the output port h. The number of possible arrival curves can be reduced by the following Lemma.

Lemma 1 A source node has a subset G x of dependent flows. The worst-case scenario of the arrival curve α h

Gx of this subset happens when at least one frame of any flow τ i (i ∈ G x ) arrives at h at time t = 0.

Proof: For a subset G x , if its arrival curve at h happens when there is no frame of any flow τ i (i ∈ G x ) arriving at h at time t = 0, its burst workload is 0 at time t = 0. This burst workload is smaller than any case where there is one frame of any flow τ i (i ∈ G x ) arriving at h at time t = 0 which gives a burst workload of the size of the arriving frame. Since the arrival curve constrains the maximum arriving traffic, the case where there is no frame of any flow τ i (i ∈ G x ) arriving at time t = 0 cannot constrain the maximum arrival traffic, and therefore it is not the worst-case scenario for the set G x . Then the worst-case scenario of the arrival curve α h

Gx happens when at least one frame of flow τ i (i ∈ G x ) arrives at h at time t = 0.

Based on the Lemma 1, we compute the aggregated arrival curve α h Gx at the output port h. We first consider two flows τ i and τ j generated by the same source node and classified in a subset G x = {i, j}. Their arrival curves at the output port h are illustrated in Figure 2.9. There are minimum durations M D h i,j from τ i to τ j and M D h j,i from τ j to τ i . According to the Lemma 1, there is at least one frame from τ i or τ j arriving at h at time t = 0. We first consider the case when there is a frame of τ i arriving at t = 0. Due to the minimum duration M D h i,j , the first frame arrival of τ j is delayed to t = M D h i,j , which means 40Chapter 2 -Modified Network Calculus approach integrating minimum duration constraints that the arrival curve of τ j is delayed by t = M D h i,j , as illustrated in Figure 2.10(a). This delayed arrival curve is given by:

α h j (t -M D h i,j )
The sum of these two arrival curves is denoted α h Gx,τ i . It indicates that it is the sum of the arrival curves of all the flows in the set G x when considering that τ i has a frame arriving at t = 0. Since τ i and τ j are the only flows in G x , we have:

α h Gx,τ i (t) = α h i (t) + α h j (t -M D h i,j )
Similarly, as illustrated in Figure 2.10(b), when we consider that there is a frame of τ j arriving at h at time t = 0, we have a delayed arrival curve

α h i (t -M D h j,i ) of τ i ,

and there is another arrival curve α h

Gx,τ j which is the sum of α h j and α h i (t -M D h j,i ).

The arrival curve α h

Gx of set G x has to upper bound the traffic of all the flows in G x . Thus it has to upper bound all the sum arrival curves built in the previous steps (α h Gx,τ i and α h Gx,τ j in the example). It is obtained by taking the piecewise maximum of the sum arrival curves. It is called a Safe Arrival Curve (SAC) and denoted α h Gx . Considering the subset G x = {i, j}, its Safe Arrival Curve is:

α h Gx (t) = max(α h Gx,τ i (t), α h Gx,τ j (t))
The illustration is given in Figure 2.11.

When there are more than two flows in one subset, we have to explore all the possible sum arrival curves in order to build the Safe Arrival Curve. For example, there are three flows τ i , τ j and τ k emitted by one source node. These three flows are in one subset G x = {i, j, k}. One possibility is that a frame of τ i arrives at time t = 0 at the output port h, and the earliest frame arrival of τ j is at time M D h i,j , and then the following earliest frame arrival of τ k is at time M D h j,k . In this case, the frame arrival order is {τ i , τ j , τ k } and it gives one possible sum arrival curve with the integration of M D h i,j and M D h j,k . Similarly, the frame arrival order can also be

{τ i , τ k , τ j }, {τ j , τ i , τ k }, {τ j , τ k , τ i }, {τ k , τ i , τ j } and {τ k , τ j , τ i }. There are 3! = 6 possibilities.
Therefore, for a subset G x having n flows, there are n! possible sum arrival curves and the Safe Arrival Curve is the piecewise max of all these curves. The computation time becomes prohibitive for large value of n. Thus, we propose that each time when we consider a frame arrival of τ i at time t = 0, we consider the earliest frame arrival of any other flow τ j in the subset arrives at time M D h i,j , and we ignore the minimum duration constraints between any other two flows. It means that the other flows in this set are considered independent to each other. Thus, for a subset G x having n flows, there are n possible sum arrival curves. This simplified computation is pessimistic but it reduces the computation complexity.

More formally, for a subset G x with n flows, n cases are considered. For the case where τ i has a frame arrival at time t = 0, the arrival curve adds α h i (t) and other

α h j (t -M D h i,j ) t1 t3 t6 t8 t7 t9 t5 t4 t2 Figure 2.11: The Safe Arrival Curve of subset G x (j ∈ G x /{i}) constrained by M D h i,j .
It is given by:

α h Gx,τ i (t) = α h i (t) + j∈Gx/{i} α h j (t -M D h i,j )
Then the Safe Arrival Curve α h Gx is computed by:

α h Gx (t) = max i∈Gx α h Gx,τ i (t) (2.2)

Application on a small network example

In the following paragraphs, the proposed approach is illustrated on the example in Figure 2.1. Based on the flow parameters in Table 2.1, the arrival curves of τ 1 , τ 2 , τ 3 , τ 4 and τ 5 are: First we consider the classical Network Calculus approach. We illustrate the computation at the output port of S 1 . Then the results of all the flows are given. Second, we do the same considering the modified Network Calculus approach.

α 1 (t) = 2t + 4000, α 2 (t) = t + 4000, α 3 (t) = t + 4000,

Classical Network Calculus approach

In order to compute the worst-case delay at the output port of S 1 , we first have to determine the arrival curves of flows τ 1 , τ 2 , τ 3 and τ 4 at S 1 (these flows compete at this port). It has been shown in Section 2.2.3 that:

α S 1 1 (t) = 2t + 4080, α S 1 2 (t) = t + 4040, α S 1 3 (t) = t + 4040, α S 1 4 (t) = 0.5t + 4020
Since frames are serialized on links N 1 -S 1 and N 2 -S 1 , the overall arrival curve α S 1 is the sum of the arrival curve in Figure 2.6 and the curve in Figure 2.7, as illustrated in Figure 2.13. The output port of S 1 provides a service curve: β S 1 = 100(t -10) + . Then the maximum delay generated at the output port of S 1 is h(α S 1 , β S 1 ) = 132.02 µs, which is illustrated in Figure 2.13.

Similarly, we can derive the arrival curve of the output port of S 2 , and the maximum delay generated at the output port of S 2 is h(α S 2 , β S 2 ) = 92.51 µs. For flow τ 1 crossing the output ports of N 1 , S 1 and S 2 , its worst-case end-to-end delay upper bound R 1 computed by the classical Network Calculus approach is the sum of the maximum delays generated at each Results of all the flows of the example are given in Table 2.2 (column NC ).

Modified Network Calculus approach

Two sets of flows are competing at the output port of S 1 . G 1 includes flows τ 1 and τ 2 which are generated by N 1 , while G 2 includes flows τ 3 and τ 4 which are generated by N 2 . Indeed, these flows are periodic. In order to compute the aggregated arrival curves of these two sets at S 1 , we have to determine the arrival curve of the flows they include. Due to the minimum duration constraints (M D N 1 1,2 = 1500 µs and M D N 1 2,1 = 500 µs) at N 1 , τ 1 and τ 2 do not suffer any delay jitter at N 1 . Thus they have the same arrival curves as at N 1 :

α S 1 1 (t) = 2t + 4000, α S 1 2 (t) = t + 4000
It is the same for flows τ 3 and τ 4 :

α S 1 3 (t) = t + 4000, α S 1 4 (t) = 0.5t + 4000
The aggregated arrival curve of the set G 1 = {1, 2} is built from two sum arrival curves. The first one considers that a frame of τ 1 arrives at S 1 at time t = 0. Due to the minimum duration M D S 1 1,2 from τ 1 to τ 2 , the delayed arrival curve of τ 2 is α S 1 2 (t -M D S 1 1,2 ), which is depicted in Figure 2.15(a). The corresponding sum arrival curve α S 1 G 1 ,τ 1 is also shown in Figure 2.15(a). The second one considers the scenario when a frame of τ 2 arrives at S 1 at time t = 0. Then another sum arrival curve α S 1 G 1 ,τ 2 of G 1 is obtained by the sum of α S 1 2 and α S 1 1 (t -M D S 1 2,1 ) as depicted in Figure 2.15(b). Finally the Safe Arrival Curve of G 1 , shown in Figure 2.16, is obtained by: Then by adding α S 1 G 1 and α S 1 G 2 , the overall arrival curve α S 1 at the output port of S 1 is obtained:

t1 t2 t6 t5 t7 t3 t4 (a) α S 1 G 1 ,τ 1 t1 t2 t4 t13 t14 t12 t11 (b) α S 1 G 1 ,τ 2
α S 1 G 1 (t) = max(α S 1 G 1 ,τ 1 (t), α S 1 G 1 ,τ 2 (t)) t3 t6 t2 t1 t7 t8 t4 t5
α S 1 = α S 1 G 1 + α S 1 G 2
It is also depicted in Figure 2.17.

Figure 2.18 compares the overall arrival curve obtained by the sum of the Safe Arrival Curves in Figure 2.17 with the overall arrival curve considered by classical Network Calculus approach which does not take into account the minimum duration constraints.

α S 1 in Figure 2.18 represents the overall arrival curve at S 1 obtained by the modified Network Calculus approach, while α S 1 is the overall arrival curve obtained by the classical Network Calculus approach. The upper bounded delay at this port is given by the maximum horizontal distance between the overall arrival curve and the service curve, which for α S 1 is: As presented in Section 2.4.1, it is 132.02 µs for the classical Network Calculus approach. Thus the improvement is significant on this port for the considered example.

h(α S 1 , β S 1 ) = 90.0 µs
Similarly, we can derive the arrival curve α S 2 of flows τ 1 , τ 2 , τ 3 , τ 4 and τ 5 at the output port of S 2 . There are three subsets

G 1 = {1, 2}, G 2 = {3, 4} and G 3 = {5}. The computation of α S 2
G 1 and α S 2 G 2 are similar to those at S 1 , and therefore they are not detailed. Since the subset G 3 has only one flow τ 5 , α S 2 G 3 = α S 2 5 = α 5 . Since the flows of τ 1 , τ 2 , τ 3 and τ 4 are transmitted from S 1 through one input link, their frame transmissions are serialized, and they cannot arrive at the output port of S 2 at the same time. These four flows are classified into two subsets, and then the sum of α S 2 G 1 and α S 2 G 2 are constrained by the frame serialization. Therefore the burst workload of the sum of the two arrival curves is the maximum burst workload among the four flows, i.e. b S 2 1 = 4100 bits, and the peak arriving rate is constrained by the link rate R. The constrained sum of arrival curves is obtained by:

min(α S 2 G 1 + α S 2 G 2 , Rt + 4100)
Therefore the overall arrival curve α S 2 is obtained by:

α S 2 = min(α S 2 G 1 + α S 2 G 2 , Rt + 4100) + α S 2 5
The maximum delay generated at S 2 is computed by h(α S 2 , β S 2 ) = 90.81 µs, as illustrated in Figure 2.19. The results for all the flows of the configuration are given in Table 2.2 (column ModifNC ). The column Reduction is the percentage of reduction when the results of ModifNC compared to that of NC. On this example, taking into account the minimum duration constraints brings a significant improvement on the delay upper bound (up to 27.5%). A more realistic case study will be presented in Chapter 4.

τ i NC (

Conclusion

In this chapter, it has been illustrated that the classical Network Calculus approach leads to pessimistic computed delays without taking into account the constraints of minimum durations. Therefore, in this chapter a modified Network Calculus approach has been developed. This approach integrates the constraints of minimum duration at each output port along the considered path.

The proposed approach is illustrated on a small example of network. Each flow in the network example is computed and the results show that the modified Network Calculus approach brings significant improvements for four flows out of five on worst-case delay upper bounds compared to the classical Network Calculus approach. Further results of the modified Network

Introduction

The Trajectory approach allows the computation of the worst-case delay of a flow transmitted on a switched Ethernet network. It has been first proposed for First In First Out (FIFO) scheduling in [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF], and expended for Fixed Priority (FP) scheduling in [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF]. This approach is not holistic since it considers the worst-case scenario that can happen to a frame along its trajectory. It has shown interesting properties of worst-case delay analysis on an avionics network as it can bring tighter delay upper bounds than the Network Calculus approach [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF].

The classical Trajectory approach does not consider the minimum duration constraints presented in Section 1.6. The goal of this chapter is to propose a modified Trajectory approach with the integration of these minimum duration constraints. Section 3.2 summarizes the classical Trajectory approach applied on a real-time switched Ethernet network. Section 3.3 proposes a modified Trajectory approach which integrates the 52Chapter 3 -Modified Trajectory approach integrating minimum duration constraints minimum duration constraints. Section 3.4 applies the modified Trajectory approach to a network example. Section 3.5 concludes this chapter.

Classical Trajectory approach

This section gives a short overview of the approach. A more detailed presentation can be found in Appendix B.

The Trajectory approach has been proposed for the computation of worst-case response time in the context of distributed systems [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF]. It has been adapted and optimized for the computation of a worst-case delay on an avionics switched Ethernet network [START_REF] Bauer | Applying and optimizing trajectory approach for performance evaluation of AFDX avionics network[END_REF][START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF]. Both FIFO and FP schedulings have been considered. In this section, we focus on FIFO scheduling.

Let us consider flow τ 1 in the example in Figure 1.9. This example is recalled in Figure 3.1. The transmission rate is R = 100 M bit/s and the switching latency is sl = 10 µs. t4 t5 t6 t7 t1 t2 t3 t5 t7 t6 t4 t4 t5 t6 t7 t8 t8 t9 t10 t11 Five flows are transmitted over the network example. There are two periodic flows τ 1 and τ 2 generated at node N 1 , and two periodic flows τ 3 and τ 4 generated at node N 2 . Flow τ 5 is an independent flow emitted by node N 3 . They have parameters recalled in Table 3.1.

τ i T i (µs) C i (µs) O i (µs) J i (
P 1 = {N 1 , S 1 , S 2 , N 4 }.
One possible scenario of one frame f 1 of flow τ 1 generated at time t = 0 is depicted in Figure 3.2. In this figure ,a h f 1 is the arrival time of frame f 1 at the output port h.

Actually, the scenario in Figure 3.2 is the worst-case scenario for f 1 . The delay of f 1 includes several parts (see Appendix B for details):

• The delay generated by frames competing with f 1 (the workload delay, blocks with oblique lines in Figure 3.2).

• The transition cost (one frame for each link, shadow blocks in Figure 3.2). The switching latency depends on the number of switches crossed by the frame and the latency in each switch. Since the latency in a switch is bounded by sl, the overall switching latency is:

(|P i | -2) • sl
The transition cost at one output port corresponds to the time needed to reach the following output port of the path. The largest competing frame is considered at each output port in order to avoid optimism in the computation. Thus the overall transition cost is:

h∈P i /{last i ,dest i } ( max j∈ 1,n h∈P j (C j ))
The output port last i does not have a following output port and dest i is the input port of the destination node.

In the example in Figure 3.2, f 2 is considered as the transition cost. Actually, any frame can be considered, since they all have the same frame size.

The last part of the delay (the workload delay) is more complex to determine. Indeed, this workload includes all the frames which can delay the frame under study. In order to do that, 54Chapter 3 -Modified Trajectory approach integrating minimum duration constraints we have to upper bound, for each flow τ j competing with the flow under study, the number of frames which can delay the frame under study. This is achieved in two steps.

In the first step, the output port where flows τ i and τ j join is considered. This output port is denoted f irst j,i . It has been shown in [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF] that a frame of τ j can delay f i only if it arrives at f irst j,i during the busy period when f i is transmitted and no later than the arrival of f i at f irst j,i . Thus the earliest possible starting time of this busy period has to be determined. In [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF] an underestimation M f irst j,i i of this earliest possible starting time is proposed. It considers the earliest instant when a frame generated at time 0 at the source node of τ i can reach the output port f irst j,i . It is obtained by considering the transmission of the smallest possible frame at each output port between the source node of τ i and f irst j,i .

Figure 3.3 depicts the obtained time interval at f irst j,i . It starts at M f irst j,i i and finishes at the latest possible arrival time of f i at f irst j,i , i.e. its generation time t plus its maximum delay S f irst j,i max i between its source and f irst j,i . In the second step, the maximum number of frames of τ j which can join f irst j,i during this interval is determined. The delay of a frame of τ j from its source node f irst j to f irst j,i is in the interval [S f irst j,i min j , S f irst j,i max j ]. Thus a frame of τ j has a chance to arrive at f irst j,i in the right interval only if it arrives at f irst j no earlier than M f irst j,i i -S f irst j,i max j and on later than Considering that the earliest possible frame arrival f j can experience a maximum release jitter J j , then the workload interval which maximizes the number of frame generations of τ j is t + A i,j with:

a f irst j,i f i - f irst j,i
A i,j = S f irst j,i max i -S f irst j,i min j -M f irst j,i i + S f irst j,i max j + J j (3.1)
Based on this workload interval for τ j , the maximum number of frames which can delay f i is:

(1 + t + A i,j T j ) +
It leads to a maximum workload of:

(1 + t + A i,j T j ) + • C j
Thus the overall competing workload of n competing flows is:

j∈ 1,n P i ∩P j =∅ (1 + t + A i,j T j ) + • C j
It has been shown in [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF] that, for some configurations, a part of this workload cannot delay f i due to the serialization effect. This part is denoted ∆ h i,t and its computation is detailed in Appendix B.3. Now the whole computation of the Trajectory approach can be summarized. The latest starting time W last i i,t of frame f i from a flow τ i at its last visited output port last i is given by:

W last i i,t = j∈ 1,n P i ∩P j =∅ (1 + t + A i,j T j ) + • C j (3.2) + h∈P i /{last i ,dest i } ( max j∈ 1,n h∈P j (C j )) (3.3) +(|P i | -2) • sl (3.4) - h∈P i /{f irst i ,dest i } (∆ h i,t ) (3.5) -C i (3.6)
Term 3.6 means that the transmission time C i of f i at the last visited output port is subtracted because

W last i i,t
is the latest starting time.

56Chapter 3 -Modified Trajectory approach integrating minimum duration constraints

The worst-case end-to-end delay upper bound of the flow τ i is obtained by:

R i = max -J i +B i ≥t≥-J i {W last i i,t + C i -t} (3.7)
where

B i = j∈ 1,n P i ∩P j =∅ B i T j • C j .
Let us illustrate the whole computation process on a frame f 1 of τ 1 of the example in Figure 3.1. The switching latency is 2 * sl = 20 µs since f 1 crosses two switches. The transition cost includes one frame of maximum size for the output ports of N 1 and S 1 . Frame f 2 is taken in this example. Any competing frame can be chosen since they all have the same size. Thus the transition cost is:

C 2 + C 2 = 40 + 40 = 80 µs
The computation of the workload delay considers all the flows competing with τ 1 : τ 2 , τ 3 , τ 4 , τ 5 and τ 1 itself. Figure 3.5 illustrates the computation of the workload generated by τ 3 . The earliest starting of the busy period at S 1 is the time when the first frame (smallest one) transmitted from N 1 arrives. It is the sum of the transmission time of the smallest frame and a switching latency sl = 10 µs. Since N 1 emits flows τ 1 and τ 2 , the earliest starting time is

M S 1 1 = min(C 1 , C 2 ) + sl = 50 µs.
Frame f 1 is delayed by frame f 2 at the output port of N 1 and it experiences a switching latency sl = 10 µs when it crosses switch S 1 . Thus, the maximum delay of

f 1 from N 1 to S 1 is S S 1 max 1 = C 1 + C 2 + sl = 90 µs. The latest arrival time of f 1 at the output port of S 1 is a S 1 f 1 = t + S S 1 max 1 .
Similarly, flow τ 3 can be delayed by flow τ 4 at the output port of N 2 . Thus the maximum delay of flow τ 3 from N 2 to S 1 is S S 1 max 3 = C 3 + C 4 + sl = 90 µs, while the minimum delay is S S 1 min 3 = C 3 + sl = 50 µs. Therefore, we have:

A 1,3 = S S 1 max 1 -S S 1 min 3 -M S 1 1 + S S 1 max 3 + J 3 = 90 -50 -50 + 90 + 0 = 80 µs
Similarly, the workload intervals of the other flows are computed:

A 1,1 = A 1,2 = 0, A 1,4 = 80 µs, A 1,5 = 120 µs
Then the latest starting time W S 2 1,t of f 1 at its last visited output port S 2 is:

W S 2 1,t = j∈ 1,5 (1 + t + A 1,j T j ) + • C j + C 2 + C 2 + 2 * sl -C 1 = (1 + t 2000 ) + • 40 + (1 + t 4000 ) + • 40 + (1 + t + 80 4000 ) + • 40 +(1 + t + 80 8000 ) + • 40 + (1 + t + 120 16000 ) + • 40 + 60
Finally, the worst-case ETE delay of τ 1 is then bound by

R 1 = max -J 1 +B 1 ≥t≥-J 1 (W S 2 1,t + C 1 -t)
and it is obtained when t = 0, which is R 1 = 300 µs as illustrated in Figure 3.2. The results of other flows will be given in Table 3.3 (column Traj).

We illustrate the worst-case delay R 1 by showing the maximum vertical distance between W S 2 1,t + C 1 and t, as depicted in Figure 3.6. The Trajectory approach does not consider the minimum duration constraints. It has been shown in Section 1.6 that for two periodic flows emitted by the same source node, there is a minimum duration between their frame arrivals. This constraint has been integrated in the Network Calculus approach in Chapter 2, and it improves the computation. In the following paragraphs, we show how the minimum duration constraints can be integrated in the Trajectory approach.

A modified approach considering minimum duration constraints

General idea

The classical Trajectory approach considers for the studied flow τ i the maximum number of frames of each competing flow τ j generated during the workload interval t + A i,j . It leads to a worst-case scenario with each competing flow τ j having a frame generation at the beginning of its workload interval t+A i,j . For example, consider flows τ 3 and τ 4 in the example in Figure 3.1. These two flows delay flow τ 1 at the output port of S 1 . In the previous section, it has been shown that for a frame f 1 of τ 1 generated at time t = 0, we have M S 1 1 = 50 µs, a S 1 f 1 = 90 µs, S max 3 = S max 4 = 90 µs and S min 3 = S min 4 = 50 µs. Therefore A 1,3 = A 1,4 = 80 µs. It is illustrated in Figure 3.7. It corresponds to the scenario when a frame of τ 3 and a frame τ 4 arrive at the output port of N 2 at the same time. However as shown in Section 1.6, there is a minimum duration from a frame of τ 3 to a frame of τ 4 , which is 1000 µs and 3000 µs in the reverse order. Therefore, such a scenario will never happen. Thus the idea is to integrate the minimum duration constraints in the workload intervals for all the dependent flows of each subset.

Computation overview

We consider a frame f i of flow τ i generated at time t. There are n flows crossing the path P i of τ i . The computation of the latest starting time

W last i i,t
of f i at its last visited output port last i processes in the following steps:

1. The n flows are classified in n g subsets G x , x ∈ 1, n g . Any two flows in a given subset have minimum duration constraints between them. Conversely, any two flows in different subsets have no minimum duration constraints between them.

2. For the flows in a subset G x , we build all the combinations of their workload intervals which integrate the minimum duration constraints. When the subset G x includes one single flow, the workload interval of the subset is obtained as in the classical Trajectory approach.

3. The maximum workload RS i,t,x for each subset G x is obtained by the envelope of all the combinations of workload intervals.

The latest starting time

W last i i,t
of f i at its last visited output port is:

W last i i,t = x∈ 1,ng RS i,t,x + h∈P i /{last i ,dest i } ( max j∈ 1,n h∈P j (C j )) +(|P i | -2) • sl - h∈P i /{f irst i ,dest i } (∆ h i,t ) -C i (3.8)
5. The worst-case end-to-end delay upper bound R i of flow τ i is computed by Equation 3.7.

Thus, the difference with the approach presented in Section 3.2 is the computation of workload RS i,t,x for a set of dependent flows. This computation is detailed in the following sections.

Computation of the maximum workload of dependent flows

The computation is illustrated using the example in Figure 3.8. Flow τ i is the only flow emitted by f irst i , then it is the only flow in one subset. Flows τ j and τ k are periodic with known offsets 60Chapter 3 -Modified Trajectory approach integrating minimum duration constraints and emitted by their source node f irst j = f irst k . There is a minimum duration M D f irst k j,k from a frame arrival of τ j to a frame arrival of τ k and a minimum duration M D f irst k k,j in the reverse order. These two flows are classified in one subset. We consider a frame f i of flow τ i generated at time t. Flows τ j and τ k delay flow τ i at the output port h. Each subset G x generates a maximum workload RS i,t,x to delay τ i . This maximum workload has to be determined. For the example in Figure 3.8, a subset of two flows:

G x = {j, k} is considered.
The delay of a frame f i of flow τ i includes a workload delay. In the classical Trajectory approach the workload intervals of flows τ j and τ k are determined independently. Such intervals are shown in Figure 3.9. In order to take into account the minimum duration constraints, we consider two combinations of intervals. In the first combination, we consider that one frame f j from τ j is generated at the beginning of the workload interval of τ j , and ready at time W S j . Then no frames of flow τ k can be ready before

W S j + M D f irst k j,k
. Indeed the minimum duration from one frame arrival of τ j to one frame arrival of

τ k is M D f irst k j,k
. Thus in this case, the workload interval of

τ k cannot start before W S j +M D f irst k j,k
. This combination of intervals is illustrated in Figure 3.10. The constrained workload interval of τ k is denoted A i,j,k .

The second combination is built in a similar manner, considering that a frame f k of flow τ k Taking into account these two combinations is sufficient for a subset of two flows, since it captures the worst-case workload of τ j and τ k . A scenario where a frame f j of flow τ j is not generated at the beginning of its workload interval cannot provide more workload. This scenario is illustrated in Figure 3.12. In this scenario, the release jitter J j is null. The starting time of the workload interval t+A i,j is W S j . The first frame f j of flow τ j arrives at its workload interval at time W S j + I j . Due to the minimum duration M D f irst k j,k , the constrained workload 62Chapter 3 -Modified Trajectory approach integrating minimum duration constraints Now we shift all the frame arrivals of flows τ j and τ k during their corresponding workload intervals to the left by temporal distance I j . Thus the first frame arrival f j of flow τ j is at time W S j , which is the beginning of its workload interval. The first frame

interval t + A i,j,k of flow τ k starts at time W S j + M D f irst k j,k
f k of flow τ k is moved to time W S j + M D f irst k j,k
, which is the beginning of its constrained workload interval. This scenario is illustrated in Figure 3.13. There is no frame moved out of its corresponding workload interval, thus the overall workload of flows τ j and τ k is not reduced. Therefore, a scenario where a frame is not generated at the beginning of its workload interval will not bring more workload than the scenario where a frame is generated at the beginning of its workload interval. Now let us formalize the computation. First let us consider the case where τ j has a frame generated at the beginning of its workload interval t + A i,j . Thus, the workload generated by τ j is computed by:

(1 + t + A i,j T j ) + • C j
As illustrated in Figure 3.10, since there exists a minimum duration

M D f irst k j,k
, the workload interval t + A i,j,k is lower bounded by:

M f irst k,i i -S f irst k,i max j + M D f irst k j,k
We do not know if the modified lower bound is lower than the classical one M

f irst k,i i - S f irst k,i
max k -J k (without minimum duration constraint). In order to avoid pessimism, the larger value is taken between them. Then the lower bound of the constrained workload interval t + A i,j,k is:

max(M f irst k,i i -S f irst k,i max j + M D f irst k j,k , M f irst k,i i -S f irst k,i max k -J k )
The upper bound of the constrained workload interval is not related to

M D f irst k j,k
. It is the same as the one in the classical workload interval, which is:

t + S f irst k,i max i -S f irst k,i min k
Therefore this constrained workload interval t + A i,j,k of τ k is determined with:

A i,j,k = S f irst k,i max i -S f irst k,i min k -max(M f irst k,i i -S f irst k,i max j +M D f irst k j,k , M f irst k,i i -S f irst k,i max k -J k ) (3.9)
With the constrained workload interval, the maximum workload of flow τ k to delay τ i is computed by:

(1 + t + A i,j,k T k ) + • C k
Thus, the maximum workload of one combination of the subset G x is the sum of the the maximum workloads of τ j and τ k . It is denoted by RS j i,t,x which indicates the scenario where flow τ j has a frame generated at the beginning of its workload interval t + A i,j , and flow τ k has a constrained workload interval t + A i,j,k . Thus RS j i,t,x is computed by:

RS j i,t,x = (1 + t + A i,j T j ) + • C j + (1 + t + A i,j,k T k ) + • C k
There is another scenario where flow τ k has a frame generated at the beginning of its 64Chapter 3 -Modified Trajectory approach integrating minimum duration constraints workload interval A i,k . This scenario is illustrated in Figure 3.11. Similarly, for flow τ j there is a constrained workload interval t + A i,k,j where:

A i,k,j = S f irst j,i max i -S f irst j,i min j -max(M f irst j,i i -S f irst j,i max k + M D f irst j k,j , M f irst j,i i -S f irst j,i max j -J j )
With the constrained workload interval, the maximum delay of flow τ j to delay τ i is computed by:

(1 + t + A i,k,j T j ) + • C j
Correspondingly, accounting for the scenario where τ k has a frame generated at the beginning of its workload interval t + A i,k , and flow τ j has a constrained workload interval t + A i,k,j , the maximum workload RS k i,t,x of the subset G x is obtained by:

RS k i,t,x = (1 + t + A i,k T k ) + • C k + (1 + t + A i,k,j T j ) + • C j
As illustrated before, there are two possible maximum workloads (RS j i,t,x and RS k i,t,x ) generated by the subset G x corresponding to two scenarios of combinations. The maximum workload generated by the subset G x is denoted RS i,t,x . It considers the envelope of the two scenarios of combinations above. It is then obtained by:

RS i,t,x = max(RS j i,t,x , RS k i,t,x )
When there are more than two competing flows in one subset G x , each time one case where τ j , j ∈ G x has a frame at the beginning of its workload interval is considered. As we have shown in Section 2.3.3, in order to avoid the problem of prohibitive computation time, only the minimum duration constraints between flow τ j and any other flow τ k in G x /{j} are considered. The minimum duration constraints between any other two flows in the subset are ignored. Then for a subset G x having n flows, the computation goes through n times.

Thus the maximum workload RS j i,t,x for one scenario of combination where flow τ j has a frame generated at the beginning of its workload interval is computed by:

RS j i,t,x = (1 + t + A i,j T j ) + • C j + k∈Gx/{j} ((1 + t + A i,j,k T k ) + • C k )
And the maximum workload of the subset G x is obtained by taking the maximum values of all the combinations:

RS i,t,x = max j∈Gx (RS j i,t,x ) (3.10)

Illustration on a small network example

The approach proposed in Section 3.3 is illustrated on the same example we used in Chapter 2. This example is depicted in Figure 3.1.

Flow τ 1 which follows the path P 1 = {N 1 , S 1 , S 2 , N 4 } is under study. Based on the configuration of the example, there are three subsets which are

G 1 = {1, 2}, G 2 = {3, 4} and G 3 = {5}.
The minimum durations between any couple of dependent flows have been computed in Section 1.6 and recalled in Table 3.2.

M D N 1 1,2 M D N 1 2,1 M D N 2 3,4 M D N 2 4,3
1500 µs 500 µs 1000 µs 3000 µs Table 3.2: Minimum durations of flows τ 1 , τ 2 , τ 3 and τ 4 at their source nodes

Classical Trajectory approach

For the purpose of comparison, the classical Trajectory approach is first applied to the example. The computation has been detailed in Section 3.2. And the worst-case ETE delay of τ 1 is then bounded by R 1 = 300 µs, which is recalled in Figure 3 The classical Trajectory approach does not consider the minimum duration constraints listed in Table 3.2, and therefore it considers that a frame f 1 is delayed by a frame f 2 of τ 2 at N 1 , by a frame f 3 of τ 3 and a frame f 4 of τ 4 at S 1 and by a frame f 5 of τ 5 at S 2 . This corresponds to the worst case depicted in Figure 3.2.

Modified Trajectory approach

Now the modified Trajectory approach is applied to the example with the integrations of the minimum duration constraints. The delay generated by each subset is computed. Let us take the subset G 2 = {3, 4} as an illustration. Since there are two flows in this set, two scenarios are considered. One scenario is when flow τ 3 has a frame generation at the beginning of its workload interval t + A 1,3 . The other scenario is when flow τ 4 has a frame generation at the beginning of its workload interval t + A 1,4 .

Due to the minimum duration constraints (M D N 2 3,4 = 1000 µs and M D N 2 4,3 = 3000 µs) at N 2 , flows τ 3 and τ 4 do not suffer any delay jitter at N 2 . They cross the switch S 1 and experience a switching latency sl = 10 µs. Thus, we have:

S S 1 max 3 = S S 1 min 3 = 50 µs, S S 1 max 4 = S S 1 min 4 = 50 µs
The earliest starting time of the busy period at the output port of S 1 is the time when the first frame (smallest one) transmitted from N 1 arrives. The source node N 1 emits two flows τ 1 and τ 2 to the output port of S 1 . This frame suffers a minimum transmission delay of min(C 1 , C 2 ) = 40 µs and a switching latency of 10 µs. Thus M S 1 1 = 50 µs. Due to the minimum duration M D N 1 1,2 = 1500 µs, frame f 1 of flow τ 1 is not delayed by a frame f 2 of flow τ 2 . It experiences a switching latency of 10µs when it crosses the switch S 1 . Thus its maximum delay from N 1 to S 1 is S S 1 max 1 = 50 µs. Its latest arrival time at the output port of S 1 is a S 1 f 1 = t + S S 1 max 1 = t + 50 µs. Let us first consider the scenario where τ 3 has a frame generation at the beginning of its workload interval. The workload interval of flow τ 3 is computed by:

A 1,3 = S S 1 max 1 -S S 1 min 3 -M S 1 1 + S S 1 max 3 + J 3 = 50 -50 -50 + 50 + 0 = 0 For τ 4 which is constrained by M D N 2 3,4
, its workload interval is t + A 1,3,4 with:

A 1,3,4 = S S 1 max 1 -S S 1 min 4 -max(M S 1 1 -S S 1 max 3 + M D N 2 3,4 , M S 1 1 -S S 1 max 4 -J 4 ) = 50 -50 -50 + 50 -max(1000, -40) = -1000
Then the maximum workload generated by the subset G 2 when τ 3 has a frame generation at the beginning of its workload interval is:

RS 3 1,t,2 = (1 + t + A 1,3 T 3 ) + • C 3 + (1 + t + A 1,3,4 T 4 ) + • C 4 = (1 + t 4000 ) + • 40 + (1 + t -1000 8000 ) + • 40
It is illustrated in Figure 3.16.

Similarly, when τ 4 has a frame generation at the beginning of its jitter, τ 3 has a constrained workload interval t + A 1,4,3 = t -3000, and the maximum workload generated by the subset G 2 in this scenario is:

RS 4 1,t,2 = (1 + t + A 1,4 T 4 ) + • C 4 + (1 + t + A 1,4,3 T 3 ) + • C 3 = (1 + t 8000 ) + • 40 + (1 + t -3000 4000 ) + • 40
It is illustrated in Figure 3.16.

In order to guarantee the worst case, the maximum workload generated by the subset G 2 is determined by:

RS 1,t,2 = max(RS 3 1,t,2 , RS 4 1,t,2 )
It is illustrated in Figure 3.16. In a similar process, the maximum workload generated by the subset G 1 is determined by:

RS 1,t,1 = max(RS 1 1,t,1 , RS 2 1,t,1 )
It is illustrated in Figure 3.17. The subset G 3 has one single flow τ 5 . Thus the maximum workload generated by this set is obtained by:

RS 1,t,3 = (1 + t + A 1,5 T 5 ) + • C 5 = (1 + t + 40 16000 ) + • 40
It is illustrated in Figure 3.18.

Since all the flows have the same frame size, any frame can be chosen as the transition cost at the output ports of N 1 and S 1 . In the example frame f 1 is taken, thus the transition cost is:

C 1 + C 1 = 40 + 40 = 80 µs
Since frame f 1 crosses two switches, the switching latency is 2 * sl = 20 µs.

Hence, based on the modified Trajectory approach of Equation 3.8, the latest starting time of frame f 1 of τ 1 at its last visited output port of S 2 is: The worst-case end-to-end delay upper bound of τ 1 is then bounded by Equation 3.7 and equal to R 1 = 220 µs when t = 0. We illustrate the delay by considering the maximum vertical distance from curve W S 2 1,t + C 1 to curve t, which is shown in Figure 3.15. The corresponding worst-case scenario is shown in Figure 3.19. Compared to the computed result obtained by the classical Trajectory approach, there is a clear reduction of R 1 from 300 µs to 220 µs. The difference 80 µs between two computed results are contributed by the minimum duration constraints. Actually, due to the existing M D N 1 1,2 , f 1 is not delayed by f 2 at N 1 . Similarly, due to the existing M D N 2 3,4 (M D N 2 4,3 ), at the output port of S 1 only one frame (lager one) of f 3 and f 4 can arrive during the busy period bp S 1 and delay f 1 . f 3 is taken as an illustration in Figure 3.19. A different of 80 µs is the transmission time of f 2 and f 4 which do not delay f 1 but are taken into account in the classical approach.

W S 2 1,t = RS 1,t,1 + RS 1,t,2 + RS 1,t,3 + C 1 + C 1 -2 * sl -C 1 = RS 1,t,1 + RS 1,t,2 + RS 1,t,3 + 60
The results for all the flows of the configuration are given in Table 3.3 (column ModifTraj). The column Reduction is the percentage of reduction when the results of ModifTraj compared to that of Traj. On this example, taking into account the minimum duration constraints brings a significant improvement on the delay upper bound (up to 26.7%). A more realistic case study will be presented in Chapter 4.

τ i Traj (

Conclusion

In this chapter, it has been illustrated that the classical Trajectory approach, which does not consider the constraints of minimum duration, introduces pessimistic computation of end-toend delay upper bounds. Indeed, there exist minimum durations between two frames of two periodic flows emitted by the same source node. Therefore, a modified Trajectory approach has been developed which integrates the constraints of minimum duration in this chapter.

The proposed approach is applied to a network example. The results show that the modified Trajectory approach brings improvement (up to 26.7%) on worst-case delay upper bounds compared to the classical Trajectory approach. Further results of the modified Trajectory approach applied on an industrial avionics switched Ethernet network can be found in Chapter 4. Moreover, the comparison of the two modified approaches, the Network Calculus approach and the Trajectory approach, will be conducted on this industrial avionics switched Ethernet network in Chapter 4.

Introduction

In previous chapters, two approaches, a modified Network Calculus approach and a modified Trajectory approach, have been proposed to upper bound the end-to-end delays of a real-time switched Ethernet network with dependent flows. The evaluation of these two modified approaches on an industrial application is important in order to demonstrate the improvement brought by considering the minimum duration constraints. In this chapter, an industrial realtime switched Ethernet (Avionic Full DupleX Switched Ethernet, AFDX [ACC08]) is presented. AFDX has been proposed to satisfy the growing requirements of avionics application and developed for modern aircraft such as Airbus A380. This chapter concentrates on the evaluations on an industrial AFDX configuration of both modified approaches presented in the previous two chapters.

Different offset assignments of flows can lead to different combinations of flow arrival times at one source node. Therefore, it is interesting to find out which offset assignment leads to tighter delay upper bounds of a given configuration. This issue has been addressed in the context of uniprocessor in [START_REF] Goossens | Scheduling of offset free systems[END_REF][START_REF] Grenier | Near-optimal fixed priority preemptive scheduling of offset free systems[END_REF] as well as in the context of automotive network in [START_REF] Grenier | Pushing the limits of CAN -scheduling frames with offsets provides a major performance boost[END_REF]. Therefore, it is interesting to consider existing offset assignment methods to find an algorithm that minimizes the delay upper bounds of the industrial AFDX network. Moreover, the existing algorithms can be adapted in order to take into account specific characteristics of an AFDX network.

In this chapter, we evaluate offset assignment algorithms for industrial AFDX network. The goal of the evaluation is to measure the gap between offset assignments based on heuristics and the optimal assignment. For a given flow, this gap can be defined as the difference between the worst-case ETE delays obtained by, on one hand, the Optimal offset assignment, and on the other hand, the offset assignment based on a heuristic. Since the optimal scenario is intractable on the industrial AFDX network, it is impossible to obtain the exact gap between the Optimal offset assignment and each offset assignment heuristic. In order to evaluate it, one way is to upper bound the gap from an underestimated delay (a reachable value) to an overestimated delay (a worst-case delay upper bound). An underestimated delay is achieved by an optimal scenario. This chapter is organized as follows. Section 4.2 introduces the AFDX network model and an illustrative industrial configuration. Section 4.3 presents an offset assignment example for the purpose of evaluation. Section 4.4 shows the evaluation on the AFDX industrial configuration with the modified Network Calculus approach. Section 4.5 shows the evaluation on the AFDX industrial configuration with the modified Trajectory approach. Section 4.6 compares the results obtained by the two modified approaches. Section 4.7 introduces the existing offset assignments and proposes new heuristics integrating the avionics characteristics. The offset assignments are compared to an optimal assignment for the AFDX industrial configuration. Section 4.8 concludes this chapter.

AFDX context

Avionics Full DupleX Switched Ethernet (AFDX) [ACC08] is a switched Ethernet network which has been defined for the avionics context and developed for modern aircraft such as Airbus A380. AFDX is one of the industrial applications of real-time switched Ethernet networks, since this network is based on full-duplex switched Ethernet architecture. In this architecture, a static routing at each switch is implemented and flow shaping at each source node is provided by the concept of V irtual Link (V L). The descriptions of the network and its industrial configuration are given in the following paragraphs.

Network and flow model

The inputs and outputs of the networks are called end systems (ES). All the end systems are interconnected by switches. Each end system is connected to exactly one port of an AFDX switch and each port of an AFDX switch can be connected at most to one end system. All the output ports of end systems and switches support a scheduling strategy. All the links in the network are full-duplex.

A V irtual Link (V L) standardized by ARINC-664 is a concept of virtual communication channel, which is the basis of AFDX flows (mono-emitter and multi-receivers). A Virtual Link is characterized by the Bandwidth Allocation Gap (BAG), which is the minimum delay between two consecutive frames of the corresponding VL, as well as l min and l max , which are the minimum and maximum frame lengths. As shown in Section 1.3.3, each VL v i can be described by {BAG i , C i , J i , O i }, where the BAG i value corresponds to its period, C i is the frame transmission time, J i is the maximum release jitter and O i is the offset.

A connection defined by a Virtual Link is unidirectional, including one source end system and one or more paths leading to different destination end systems (multicast). For the purpose of determinism, Virtual Links are statically defined.

There is no synchronization between the end systems. Each end system transmits frames on a set of VLs. Thus each end system has to schedule the transmissions of all its emitting VLs since they are multiplexed on the same physical Ethernet link.

An AFDX industrial configuration

The industrial AFDX network interconnects aircraft functions in the avionics domain. It is a large scale network and composed of two redundant networks. A typical industrial AFDX network architecture is illustrated in Figure 4

Example of an offset assignment algorithm

To evaluate an industrial AFDX configuration, an offset assignment to model flow behaviors is required. Therefore, an algorithm proposed for automotive CAN networks in [START_REF] Grenier | Pushing the limits of CAN -scheduling frames with offsets provides a major performance boost[END_REF] is to provide an offset allocation example. The aim of this algorithm is to separate frames of one flow as far as possible from the frames of the other flows emitted by the same source node.

This algorithm considers a discrete time system based on a time interval granularity gran.

A periodic flow τ i has a period T i . For n periodic flows emitted by the same source node, the offsets are distributed over time interval [0, Tmax gran ), where T max = max i∈ 1,n (T i ), and the offset for each flow τ i is chosen in the interval [0, T i ). The sequence of frame transmissions is stored in an ordered array R, which has Tmax gran elements. The n flows are numbered by increasing value of their periods and proceeded from τ 1 to τ n . The first flow τ 1 is assigned with the offset O 1 = 0. The offset assignment of τ i (i ∈ 2, n ) is achieved by the following steps:

1. look for one of the longest idle interval in [0, T i ). The first and last possible release time of the interval are noted by B i and E i respectively.

2. then set the offset O i in the middle of the selected interval. The corresponding possible release time is r i .

3. finally store the frames of τ i in the array R in the following way:

∀k ∈ N and r i + k • T i gran ≤ T max gran , do R[r i + k • T i gran ] = R[r i + k • T i gran ] ∪ f i,k+1
This algorithm is illustrated by the following small example. Four periodic flows τ 1 , τ 2 , τ 3 , τ 4

P RT i 1 2 3 4 5 6 7 8 R[i] f 1,1 f 2,1 f 1,2 f 3,1 f 1,3 f 2,2 f 1,4 f 4

Worst-case delay analysis based on the modified Network

Calculus approach

The industrial avionics network in Figure 4.1 is configured with the example offset assignment presented in 4.3. We assume that all the VLs are periodic. The worst-case end-to-end delay upper bound of each VL path is computed by the classical Network Calculus approach and the modified Network Calculus approach. A normalization is used for the purpose of comparison.

For two computed results of one path P x , one is considered as the reference value (denoted rf x ) and normalized as 100, while the other (denoted cp x ) is taken as the comparison value and normalized as N cp x :

N cp x = 100 + ( cp x -rf x rf x × 100) (4.1)
The delay upper bound computed by classical Network Calculus approach is taken as the reference value rf x . The delay upper bound computed by modified Network Calculus approach is taken as the comparison value cp x . Both rf x and N cp x are shown in The average improvement brought by modified Network Calculus approach in terms of ETE delay upper bound is of 49.7%, which reveals the gain of integrating the minimum duration constraints of flows at AFDX end systems. The maximum improvement is up to 83.3%. The main reason of this improvement is that the flows are separated by the minimum durations at each source node, and therefore lead to a reduction of burst workload at the output ports.

Since these minimum duration constraints propagate along the path, they also lead to more even workload at the output ports of switches.

Besides the case that all the flows transmitted in the network are constrained by minimum durations, it is also possible that only part of the flows are dependent while the other flows are independent. It means that only part of the flows are periodic and with known offsets. In order to evaluate this case, it is assumed that 2964 randomly chosen VL paths (almost half of the total VL paths) in the industrial AFDX network are periodic with known offsets. The other 3448 VL paths are either sporadic or periodic with unknown offsets, and they are considered independent. The delay upper bound of each flow is computed by both the classical Network Calculus approach (rf x ) and the modified Network Calculus approach (cp x ). The comparison is shown in offsets brings improvement on end-to-end delay upper bounds. The average improvement for dependent flows is of 17.23% which is slightly higher than the 16.15% for independent flows.

Worst-case delay analysis based on the modified Trajectory approach

In this evaluation, the improvement brought by the integration of the minimum duration constraints is measured for the modified Trajectory approach. The worst-case end-to-end delay upper bound of each VL path is computed by the classical Trajectory approach and the modified Trajectory approach. The normalization presented by Equation 4 The gap between the obtained N cp x and the reference reflects the improvement for each VL path. There is a clear improvement of computed end-to-end delay upper bounds as minimum duration constraints are considered. The maximum improvement is up to 82% and the average improvement is about 50%. The main reason of this improvement is that the flows are separated by the minimum durations at each source node, and therefore lead to a reduction of burst workload at the output ports, not only of source nodes, but also of switches. The following table Table 4.4 shows the distribution of improvements on output port burst workload of both end systems and switches. This improvement means the percentage of burst workload reduction when considering offsets compared to the case where no offsets are accounted for. This result complies with the results obtained by the modified Network Calculus approach.

Similarly, the improvements on dependent flows and on independent flows are evaluated 4.6 -A comparison of the two modified approaches and depicted in Figure 4.8 and in Figure 4.9, respectively. The average improvement on dependent flows is 17.72% which is slightly higher than the 15.99% of independent flows. Thus, these results are in line with the results obtained by the modified Network Calculus approach.

Integrating the temporal constraints imposed by the offsets, even partially, in the computation improves the results on end-to-end delay upper bounds as well.

A comparison of the two modified approaches

The modified Network Calculus approach takes into account the frame serialization effect on link. It is still holistic since the computation considers the worst case scenario for a frame at each output port it visits. The computation of the proposed Trajectory approach, which integrates offsets, considers the worst case scenario of a frame along its path. In previous paragraphs, both approaches are applied to the industrial AFDX network. This section compares the results of the modified Network Calculus approach to the ones of the proposed Trajectory approach.

The same normalization method is adopted with the reference value rf x chosen as the endto-end delay upper bounds computed by the modified Network Calculus approach, while the comparison value cp x chosen as the end-to-end delay upper bounds computed by the proposed Trajectory approach. Since both two modified approaches are pessimistic computations, an optimized approach (denoted Opt) can be achieved by taking the tighter (smaller) value of the two approaches for each VL path. The result is shown in Figure 4.10.

The modified Trajectory approach brings tighter end-to-end delay upper bounds than the modified Network Calculus approach to 5956 VL paths which takes up 92% of the VL path total number and correspondingly it brings looser upper bounds to 456 VL paths. The maximum The modified Trajectory approach works better than the modified Network Calculus approach on this network for the bigger portion of VL paths. The optimized approach provides a further improved worst-case delay analysis. It brings on average 50.2% improvement on end-to-end delay upper bounds which is slightly better than the modified Trajectory approach.

Near-optimal offset assignment for the industrial AFDX network

Each source node of the switched network emits its flows according to a local clock. It assigns an offset to each flow. It means that different offset assignments of flows can lead to different combinations of flow arrival times at one source node. Therefore, it is interesting to find out which offset assignment leads to a tighter delay upper bound for a given system. This issue has been addressed in the context of uniprocessor task scheduling in [START_REF] Goossens | Scheduling of offset free systems[END_REF][START_REF] Grenier | Near-optimal fixed priority preemptive scheduling of offset free systems[END_REF] as well as in the context of automotive networking in [START_REF] Grenier | Pushing the limits of CAN -scheduling frames with offsets provides a major performance boost[END_REF]. In previous paragraphs, only the offset assignment originally designed for the CAN network in [START_REF] Grenier | Pushing the limits of CAN -scheduling frames with offsets provides a major performance boost[END_REF] has been applied to the industrial AFDX network. It is interesting to consider other existing offset assignment algorithms [START_REF] Goossens | Scheduling of offset free systems[END_REF][START_REF] Grenier | Near-optimal fixed priority preemptive scheduling of offset free systems[END_REF] in order to find the algorithm that minimizes the delay upper bounds of flows in the industrial AFDX network. Moreover, the existing algorithms can be adapted in order to take into account specific characteristics of an AFDX network.

Existing offset assignments

The offset assignment has been studied in [START_REF] Goossens | Scheduling of offset free systems[END_REF] in the context of periodic task sets executed on a unique processor. Each task τ i is characterized by a period T i , a hard deadline D i , a processing time C i and an offset O i . In the context of uniprocessor, the systems can be classified into three classes with respect of their offsets:

• Synchronous system: all the tasks have the same fixed offsets O i = 0, i.e., at time 0, all the tasks generate one request;

• Asynchronous system: a different offset is allocated to each task due to application constraints;

• Offset free system: any offset can be allocated to each task in order to improve the system schedulability.

A key point of an offset free system is the choice of an offset assignment. However, the number of possible offset assignments is exponential.

In [START_REF] Goossens | Scheduling of offset free systems[END_REF], an Optimal offset assignment is proposed to exhaust all possible non-equivalent offset assignments. Although this method reduces significantly the number of combinations, the number remains exponential. Therefore this offset algorithm is intractable for large scale network.

Dissimilar offset assignment is then defined in [START_REF] Goossens | Scheduling of offset free systems[END_REF] in order to reduce computational complexity in the comparison with the Optimal offset assignment by providing a single offset assignment for a task set. This method tries to move from the synchronous case as much as possible. It considers a set of pairs of tasks. Each pair has two tasks (τ i , τ j ). Then it orders task pairs (τ i , τ j ) by decreasing value of gcd(T i , T j ), where gcd(T i , T j ) is the greatest common divisor of T i and T j . When O i is known, this algorithm assigns an offset O j to τ j by separating τ j from τ i by a minimal distance gcd(T i ,T j ) 2 between two requests of τ i and τ j . Dissimilar offset assignment is denoted GCD in this chapter.

Near-optimal offset assignment heuristics are derived in [START_REF] Grenier | Near-optimal fixed priority preemptive scheduling of offset free systems[END_REF] based on the study of GCD. When GCD fails to generate a schedulable asynchronous situation, this algorithm orders task pairs by considering one of four alternative criteria:

• RateAdd: C i T i + C j T j ,
• RAGCD:

( C i T i + C j T j ) × gcd(T i , T j ),
• RM GCD: max(

C i T i , C j T j ) × gcd(T i , T j );
• GCDM inus: -gcd(T i , T j ).

Then it assigns offsets to each task pair in the same way as GCD. Since both Dissimilar offset assignment and Near-optimal offset assignment heuristics assign offsets to tasks pair by pair, they are called PairAssign in this Chapter.

In [START_REF] Grenier | Pushing the limits of CAN -scheduling frames with offsets provides a major performance boost[END_REF], the authors show that the offset assignments mentioned above are not efficient when applied to the scheduling of automotive message, and an offset assignment algorithm is tailored for automotive CAN networks. This algorithm aims at choosing offsets to maximize the distance between frames. It is presented in 4.3, and it is denoted SingleAssign and recalled briefly here. For n flows emitted by one source node, sort them by increasing value of their periods and calculate T max = max i∈ 1,n (T i ). The assignment starts with the flow having the smallest period and processes one flow after the other. The first flow is assigned with the offset 0. For a flow τ i (i ∈ 2, n ), its offset O i is derived as follows:

• first, search for the longest idle interval in [0, T i );

• then set O i in the middle of this interval;

• finally record all the frames of τ i released in [0, T max ).

It is noted that different network applications have various temporal characteristics, then the efficiency of an offset assignment highly depends on the specific network application. In this chapter, we specially consider the industrial AFDX configuration presented in Section 4.2.

In the following paragraphs, an optimal scenario is developed and different offset assignments are then evaluated based on the optimal offset scenario for the industrial AFDX configuration.

Optimal scenario of dependent flows over the AFDX network

Considering the industrial AFDX configuration (presented in Section 4.2) with about 1000 flows, the Optimal offset assignment proposed in [START_REF] Goossens | Scheduling of offset free systems[END_REF] is intractable. Thus other offset assignment algorithms have to be used. Then, the evaluation of the gap between the Optimal offset assignment and the assignment generated by each heuristic is an important issue. For a given flow, this gap is the difference between the worst-case ETE delay obtained by Optimal offset assignment and the one obtained by a chosen offset assignment algorithm. On a whole configuration, the gap is the average of the gaps obtained for all the flows. Indeed, it is not possible to compute such a gap for an industrial AFDX configuration, since Optimal offset assignment is intractable. Then, a first idea is to compute an upper bound on this gap.

This upper bound can be obtained by considering an ideal offset assignment, which minimizes the worst-case ETE delay for all the flows. This ideal assignment may not exist for a

given configuration, but it is sure that it gives worst-case delays which are not higher than the ones obtained by the Optimal offset assignment. This ideal assignment, denoted IdealAssign, minimizes the maximum waiting delay of every frame in each output port that it crosses by considering that all the frames emitted by the same end system are separated by an infinite distance. It corresponds to the following scenario:

• At a source ES, a frame f i of a VL v i is not delayed by any other frames emitted by the same ES, i.e., the frame f i is transmitted immediately after its release;

• At each switch output port of its path, the frame f i encounters frames generated by several ESs. f i can be delayed by exactly one frame coming from each of these ESs. The frame with the largest size is considered. The delay experienced by f i at each switch output port takes into account the serialization effect (i.e., two frames cannot be received at the same time from an input link).

Indeed, since there is no common clock among the end systems, there is no relationship between the releases of two frames from different end systems. Consequently, there exist scenarios where the two frames arrive at their first common switch output port at the same time.

Let us illustrate this scenario on Example 1 depicted in Figure 4.11.

Example 1 There are four flows transmitted: v 1 and v 2 emitted by the end system e 1 as well as v 3 and v 4 emitted by the end system e 2 . The temporal characteristics of each VL are listed in Table 4.5 The sample AFDX network works at 100 M bit/s. The technological latency is null.

We first focus on VL v 1 . The IdealAssign leads to the scenario illustrated in Figure 4.12, where a h f i is the arrival time of frame f i on the output port h. At e 1 , the frame f 1 is transmitted as soon as it is released due to the separation from v 2 . Since the ESs are not synchronized, at the output port of the switch S 1 , the frame f 1 of v 1 can arrive at the same time as the frame f 3 of v 3 and it is delayed by f 3 , i.e. a S 1 f 1 = a S 1 f 3 . Only one frame from e 2 delays the frame f 1 at the output port of S 1 since v 3 and v 4 are separated far away from each other, and f 3 is considered due to the frame size l max 3 > l max 4 . IdealAssign gives an upper bound on the delay reduction which can be obtained by an offset assignment algorithm. The following paragraphs propose some offset assignment heuristics tailored for the AFDX network.

Offset assignment algorithms in the context of AFDX network

In the context of a uniprocessor, a set of tasks shares a unique resource, i.e., the processor. The situation is different in the context of a switched Ethernet network, like the AFDX network, where a set of flows shares a set of output ports. Actually, each port is shared by a subset of all the flows. Consequently, the load can be different for each output port. The worst-case waiting time of a frame in an output port increases when the load of the output port increases. Then, it could be interesting to take into account the load of the output port in the offset assignment. This is illustrated on Example 2 in Figure 4.13, Example 2 There are six flows transmitted: v 1 , v 2 and v 3 emitted by the end system e 1 as well as v 4 , v 5 and v 6 emitted by the end system e 2 . The temporal characteristics of each VL are listed in Table 4 The offset assignment SingleAssign is applied to this example network. The three VLs emitted by e 1 are considered. Since SingleAssign assigns offsets to VLs in the order of increasing BAG values and BAG 1 = BAG 3 < BAG 2 , the offsets are assigned to these three VLs in order:

O 1 = 0 µs, O 3 =
l max 1 = l max 4 = 6000 bits (C 1 = C 4 = 60 µs)
According to SingleAssign, the release of frames at e 1 and e 2 is depicted in Figure 4.15 (same as in Figure 4.14). One possible scenario at the output port of S 1 is exhibited for the chronogram of S 1 in Figure 4.15, where the studied frame f 2 finishes its transmission at time 300 µs. The delay of the frame f 2 is: R 2 = 300 -100 = 200 µs This delay is higher than the one obtained in the case of Figure 4.14 (180 µs). It increases due to the fact that when the frame f 2 arrives at S 1 at time a S 1 f 2 = 160 µs, the transmission of frame f 4 , delayed by the transmission of frame f 1 , is not completed. It thus delays the transmission of frame f 2 . For this case SingleAssign could not separate frames at an output port of a switch.

U e 1 = {v 1 ,v 2 ,v 3 } ( C 1 BAG 1 + C 2 BAG 2 + C 3 BAG 3 ) = 0.375
The upper output port of S 1 is shared by VLs v 1 , v 2 , v 4 and v 5 , creating a utilization of:

U S 1 = {v 1 ,v 2 ,v 4 ,v 5 } ( C 1 BAG 1 + C 2 BAG 2 + C 4 BAG 4 + C 5 BAG 5 ) = 0.45
The lower output port of S 1 is shared by VLs v 3 and v 6 , creating a utilization of:

U S 1 = {v 3 ,v 6 } ( C 3 BAG 3 + C 6 BAG 6 ) = 0.3
Consequently, for these three VLs, the most loaded port is the upper output port of S 1 , followed by e 1 and the lower output port of S 1 . We could first assign offsets to v 1 and v 2 For the PairAssign, a similar heuristic is proposed to consider the load of the output ports.

This heuristic, denoted M ostLoad, sorts the VL pairs (v i , v j ) by decreasing values of Ld i +Ld j ,

where Ld i is the workload (utilization) of most loaded output port crossed by v i . We illustrate this offset assignment using the same example shown in Figure 4.13 and Table 4.6, except that we consider C 1 = C 4 = 60 µs. Three VL pairs are considered for v 1 , v 2 and v 3 emitted by e 1 :

(v 1 , v 2 ), (v 1 , v 3 ) and (v 2 , v 3 ). For the first pair (v 1 , v 2 ), the most loaded output port crossed by v 1 and v 2 is the upper output port of S 1 , and then Ld 1 + Ld 2 = 0.45 + 0.45 = 0.9. Then, for the second pair (v 1 , v 3 ), the most loaded output ports crossed by v 1 and v 3 are the upper output port of S 1 and the output port of e 1 respectively, and then Ld 1 + Ld 3 = 0.45 + 0.375 = 0.825.

Similarly, for the third pair (v 2 , v 3 ), we have Ld 2 + Ld 3 = 0.45 + 0.375 = 0.825. emitted by e 1 all cross one switch output port, then they are assigned offsets in the order of v 1 , v 2 and v 3 . Similar process happens for v 4 , v 5 and v 6 emitted by e 2 . The assigned offsets are listed in Table 4.7. For the PairAssign, a similar heuristic, denoted CrossedS, is proposed.

It sorts the VL pairs (v i , v j ) by decreasing values of cs(v i , v j ), where cs(v i , v j ) is the number of common switch output ports crossed by v i and v j . For the same example, three VL pairs are considered for v 1 , v 2 and v 3 emitted by e 1 : (v 1 , v 2 ), (v 1 , v 3 ) and (v 2 , v 3 ). For the first pair (v 1 , v 2 ), v 1 and v 2 share one switch output port of S 1 . For the second pair (v 1 , v 3 ), v 1 and v 3 do not share any switch output port. For the third pair (v 2 , v 3 ), v 2 and v 3 do not share any switch output port. Therefore, offsets are assigned to v 1 and v 2 , and then to v 3 , which are also listed in Table 4.7.

Besides the four new proposed heuristics, the existing offset assignment heuristics presented in Section 4.7.1 are applied to the AFDX network with the value of BAG as the period. The evaluation on each offset assignment is presented in the next section.

Results

The existing and proposed offset assignments introduced in Section 4.7.3 are applied to the industrial AFDX network presented in 4.2. In this evaluation, all the VLs are assumed to be periodic. The computation is processed using the modified Network Calculus approach integrating the offsets.

O 3 = O 1 + gcd(BAG 1 ,BAG 3 ) 2 = 2 ms (O 2 = O 3 ).
The releases of the first frames for both v 2 and v 3 overlap, and the frames have to wait in the queue. This case is depicted in Figure 4.18.

t1 t2 t3 t4 t6 t7 t3 t4 t6 t5 t5 In this way, no frame has to wait in the output queue of e 1 .

The analyzed problem of GCD for the industrial AFDX network exists for all the PairAssign based heuristics because the computation of offsets mainly concerns the value of gcd(BAG i , BAG j ) even if the order of pairs varies based on different criteria.

The results are further studied by the normalized method in Equation 4.1. For one path Further evaluations have been conducted, leading to the same conclusions. They consider the same industrial AFDX architecture and a same overall workload of 10%. For each VL, the l min and l max are randomly chosen from 72 bytes to 1526 bytes, and the BAG value is randomly chosen from 1 ms to 128 ms as the powers of 2. The results show that the average ETE delay reduction brought by the IdealAssign is 45%. The P airAssign heuristics bring average reductions ranging from 24% to 31%, which are far from the IdealAssign. The algorithms based on the SingleAssign bring average reductions ranging from 39% to 40%, which are closer to the IdealAssign.

Conclusion

In this chapter, we have presented the AFDX network as a real-time switched Ethernet network example. An AFDX industrial configuration which contains about 1000 flows is introduced.

Evaluations on such an industrial configuration have been conducted for the modified Network

Calculus approach and for the modified Trajectory approach. The results have shown that considering the minimum duration constraints improves significantly the computed worst-case delay upper bounds by 49.7% for the modified Network Calculus approach and by 50% for the modified Trajectory approach. The comparison of results obtained by both approaches has shown that the modified Trajectory approach brings improvement for 92% of flows compared to the modified Network Calculus approach. An optimized approach based on both two modified approaches has been proposed which further improves the computation on end-to-end delay upper bounds.

The offset assignments for the industrial AFDX network have also been studied in this chapter. Since the Optimal offset assignment is intractable in this context, an optimal scenario has been built based on a presumed optimal assignment in order to upper bound the gap between the Optimal offset assignment and each offset assignment heuristic. New heuristics considering the AFDX characteristics have been proposed. Using the Network Calculus approach, the improvement on ETE delay upper bound bought by each heuristic has been compared to the optimal algorithm. It is demonstrated that PairAssign heuristics are not efficient when applied to the industrial AFDX network due to the limited amount of different BAG values.

The SingleAssign turns out to be a near optimal algorithm in the studied context. Although the heuristics integrating specific AFDX characteristics bring slight improvements in contrast to the SingleAssign, they are of increased complexity.

Introduction

In previous chapters, two approaches, a modified Network Calculus approach and a modified Trajectory approach, are proposed for the worst-case delay analysis of real-time switched Ethernet networks considering minimum duration constraints. In order to guarantee the delay upper bounds on real-time switched Ethernet networks, some pessimism is introduced in the worstcase delay analysis. The introduced pessimism of a computed delay upper bound is the gap between the exact worst-case delay and the computed value. The percentage of the introduced pessimism out of the computed delay upper bound indicates how pessimistic the computation is. Thus, an evaluation of this pessimism is an importance issue. Since the exact worst-case delay is unknown, the difference between an underestimated value of worst-case delay and an upper bounded delay (overestimated) is considered. The maximum difference between the underestimated delay and the overestimated delay gives a metric of the introduced pessimism.

The pessimism analysis is an essential part of worst-case delay analysis, since it evaluates the credibility of the computed delay upper bounds.

Similar work about pessimism analysis includes [START_REF] Baruah | Quantifying the sub-optimality of uniprocessor fixedpriority scheduling[END_REF][START_REF] Fan | Guaranteed real-time communication in packet-switched networks with FCFS queuing[END_REF][START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF]. In [START_REF] Baruah | Quantifying the sub-optimality of uniprocessor fixedpriority scheduling[END_REF], a quantitative metric is proposed to compare the deviation between a given scheduling algorithm and an optimal scheduling in the context of uniprocessor with FP scheduling. In [START_REF] Fan | Guaranteed real-time communication in packet-switched networks with FCFS queuing[END_REF], a Network Calculus based approach is proposed to guarantee real-time communication of a switched network with FIFO scheduling. The pessimism introduced by such an approach is measured by the difference between the computed worst-case delay and a simulated worst-case delay which is obtained by simulation. However, no further details about how to build the simulation is provided.

In [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF] an empirical pessimism analysis based on an unfavorable scenario was built in the context of avionics switched Ethernet with FIFO scheduling. In this unfavorable scenario, only one frame for each sporadic flow is considered and all the considered frames are sorted based on the following criteria:

• At one output port, the frames are sorted first based on their arrival times according to FIFO scheduling;

• If they have the same arrival time, they are sorted by increasing number of shared output ports along the path of the considered flow from the current output port;

• If they have the same number of shared output ports, they are sorted by decreasing frame size.

Pessimism can be obtained only based on a simulation since the first criterion is the frame arrival times which are decided by simulation. Therefore, such a pessimism analysis is empirical, which means that a scenario corresponding to each configuration has to be built. Recently, this work has been extended for FP/FIFO scheduling policies for the avionics switched Ethernet network in [START_REF]Applying Trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]. This chapter proposes an analytical approach, which is based on the Trajectory approach, to evaluate the maximum potential pessimism introduced by the worst-case delay analysis of real-time switched Ethernet supporting FIFO scheduling. Therefore it is first necessary to identify the sources of pessimism of the proposed Trajectory approach, and then to derive an analytical approach to evaluate the maximum potential pessimism by integrating minimum duration constraints for periodic flows with known offsets. The pessimism introduced by both modified Network Calculus approach and modified Trajectory approach is evaluated on the industrial AFDX configuration. This chapter is organized as follows. Section 5.2 presents the pessimism analysis of a realtime switched Ethernet network based on the classical Trajectory approach. It first identifies all the possible sources of pessimism and then gives an analytical method to upper bound the maximum potential pessimism. Section 5.3 integrates the minimum duration constraints and develops a pessimism analysis based on the modified Trajectory approach. Section 5.4 applies the developed pessimism analysis on the industrial avionics switched Ethernet network. Section 5.5 concludes this chapter.

Pessimism analysis based on the classical Trajectory approach

Review of the classical Trajectory approach

The Trajectory approach considers for a frame f i of flow τ i the worst-case scenario along its trajectory. According to Chapter 3, for frame f i generated at time t, the latest starting time W last i i,t at its last visited output port last i is computed by Term 3.2, Term 3.3, Term 3.4, Term 3.5 and Term 3.6 for FIFO scheduling. The computation is recalled by Term 5.1, Term 5.2, Term 5.3, Term 5.4 and Term 5.5:

W last i i,t = j∈ 1,n P i ∩P j =∅ (1 + t + A i,j T j ) + • C j (5.1) + h∈P i /{last i ,dest i } ( max j∈ 1,n h∈P j (C j )) (5.2) +(|P i | -2) • sl (5.3) - h∈P i /{f irst i ,dest i } (∆ h i,t ) (5.4)
-C i (5.5)

• Term 5.1 is the delay generated by competing flows which delay τ i along its trajectory as well as the transmission delay generated by τ i itself.

• Term 5.2 is the transition cost from one busy period to the next one.

• Term 5.3 is the switching latencies along the considered path.

• Term 5.4 considers the frame serialization effect.

• Term 5.5 is subtracted because

W last i i,t
is the latest starting time at last i , but not the delay.

Then the delay upper bound of τ i is computed by Equation 3.7, and recalled by Equation 5.6:

R i = max -J i +B i ≥t≥-J i {W last i i,t + C i -t} (5.6)
Thus, the delay of the considered flow τ i is composed of several parts. This pessimism will be analyzed in this Chapter.

Besides the demonstration of potential pessimism introduced by the three terms of the classical Trajectory approach computation, a key issue is to evaluate this pessimism. Such an evaluation has been conducted in [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF], based on the generation of a reachable unfavorable scenario. The difference between the guaranteed delay upper bound and the delay experienced with the unfavorable scenario gives an estimation of the pessimism (maximum potential pessimism). Nevertheless, this unfavorable scenario must be established for each analyzed configuration. Therefore, a formula is proposed which underestimates the worst-case ETE delay. This underestimation is obtained by modifying pessimistic terms (Term 5.1, 5.2, 5.4) in the Trajectory approach computation. An analytical method for underestimated delays is developed based on these new terms which are never pessimistic (they can be optimistic).

Therefore an analytical method for maximum potential pessimism is the discrepancy between the classical Trajectory approach and the analytical method for underestimated delays.

Pessimism analysis of computing flows

Overestimation of competing flows

For a flow τ i following its path P i , its frame f i generated at time t is considered. At each node along its path P i , there are competing flows from other input links which could delay the frame The arrival time of a frame f i of flow τ i at the output port h is denoted a h f i . The worst case scenario of a frame f 1 of flow τ 1 at the source node N 1 occurs when each competing flow τ j (j ∈ 2, 11 ) has a frame arriving at the source node N 1 at the same time as the frame f 1 (critical time) and the frame f 1 is the last one transmitted. For the sake of simplicity, this arrival time is considered as the time origin, i.e., t = a N 1 f 1 = ... = a N 1 f 11 = 0 µs. This scenario is depicted in Figure 5.2. Then S S 1 max 1 = 110 µs and M S 1 1 = 10 µs. Since τ 12 is the only flow emitted by the source node N 2 , S S 1 max 12 = S S 1 min 12 = C 12 = 10 µs.

f i . Thus,
According to the Equation 3.1 , the maximum workload interval of flow τ 12 at node S 1 is:

A 1,12 = S S 1 max 1 -S S 1 min 12 -M S 1 1 + S S 1 max 12 + J 12 =
(1 + t + A 1,12 T 12 ) + • C 12 = (1 + t + 100 100 ) + • 10 = 20 µs when t = 0 µs.
It means that there are at most two frames, denoted by f 12 and f 12 , of flow τ 12 delaying the studied frame f 1 at node S 1 .

Specifically, the k th frame of flow τ j is represented by f j,k . The minimum temporal interarrival time between the arrival times of two consecutive frames f j,k , f j,k+1 from the same flow τ j at the output port h is achieved when frame f j,k is delayed as much as possible and frame f j,k+1 is not delayed by any other frame, as illustrated in Figure 5.3.

T j -S h max j + S h min j -J j
Back to Example 3, the minimum inter-arrival time between f 12 and f 12 at the node S 1 is 100 -10 + 10 -0 = 100 µs. In order to delay f 1 , f 12 and f 12 arrive at S 1 no earlier than M S 1 1 = 10 µs and no later than t + S S 1 max 1 = 110 µs with a minimum interval 100 µs between their arrivals. Thus f 12 and f 12 arrive at 110 µs and 10 µs, respectively. This scenario is also depicted in Figure 5.2. The computed delay of flow τ 1 is then 140 µs.

Note that it is the interval lower bounded by M S 1 1 and upper bounded by t + S S 1 max 1 which determines the maximum number of frames of flows τ 12 delaying the studied frame f 1 . However, the length of this interval could be overestimated. Let us consider the Example 4 drawn in The worst case scenario for the frame f 1 at the output port of source node N 1 is shown in Figure 5.5 (the same as that in the Example 3 in Figure 5.2), which gives S S 1 max 1 = 110 µs and M S 1 1 = 10 µs. The interval [M S 1 1 , t + S S 1 max 1 ] decides that two frames f 12 and f 12 of flow τ 12 could arrive at the node S 1 during this interval. As analyzed in the previous paragraphs, these two frames arrive at M S 1 1 = 10 µs and t + S S 1 max 1 = 110 µs respectively, which is depicted in Figure 5.5. The computed delay of the frame f 1 is 140 µs which is the same as that in delaying any frame in the busy period bp S 1 .

Maximum potential pessimism of competing flows

In order to evaluate the introduced pessimism of an overestimated delay, it is necessary to calculate an underestimated value of the delay generated by competing flows. We focus on a frame f i of flow τ i which is generated at time t. According to the Term 5.1, the pessimism comes from the overestimated number of frames for each competing flow. Thus the potential pessimism can be removed by considering that there is only one frame per flow. It can be optimistic. Then the lower bounded delay generated by competing flows is denoted U R CF last i i and computed by:

U R CF last i i = j∈ 1,n P i ∩P j =∅ (C j ) (5.7)
The upper bound of the pessimism caused by the computation of this delay is denoted by

P CF last i i,t
. It is the difference between Term 5.1 and Term 5.7, which is:

P CF last i i,t = j∈ 1,n P i ∩P j =∅ ( t + A i,j T j ) + • C j (5.8)
For Example 4 in Figure 5.4, a reachable delay of τ 1 computed by Term 5.7 is 130 µs which is the exact worst-case delay of τ 1 in this example.

The maximum pessimism introduced by the classical Trajectory approach for τ 1 is computed by Term 5.8, which is 10 µs.

Pessimism analysis of busy period transition

Overestimation of busy period transition

Based on the classical Trajectory approach, the transmission time of the first frame of a busy period is counted twice as the busy period transition. In order to be safe, the largest frame crossing each output port of nodes is counted. This can be pessimistic. Let us consider the Example 5 depicted in Figure 5.6.

Example 5 Flows τ 1 and τ 2 are emitted by the source node N 1 , and flows τ 3 and τ 4 are emitted by the source node N 2 . The parameters of the flows are as follows: The worst-case ETE delay of flow τ 1 is computed using the classical Trajectory approach and it equals to 500 µs which corresponds to the worst-case scenario depicted in Figure 5.7.

C 1 = C 2 = C 3 = C 4 = 100 µs, T 1 = T 2 = T 3 = T 4 = 8000 µs, J 1 = J 2 = J 3 = J 4 =
Note that in this scenario all the frames are counted once except the frame f 2 which is the first and largest frame coming from the busy period bp N 1 to the busy period bp S 1 . Indeed, the transmission time of the frame f 2 (marked as a shadow block in Figure 5.7) is the transition cost from the busy period bp N 1 to the busy period bp S 1 which corresponds to the Term 5.2. However, Term 5.2 could introduce some pessimism in the computation when the first frame of the busy period is not the largest frame transmitted from the previous busy period. Let According to the Trajectory approach, Term 5.2 is equal to

max(C 1 , C 2 ) = max(100, 40) = 100 µs
The latest starting time of a frame f 1 of flow τ 1 at node S 1 is computed as W S 1 1,t = 340 µs. Therefore, the ETE delay upper bound of the flow τ 1 is obtained by: R 1 = max

-J 1 +B 1 ≥t≥-J 1 (W S 1 1,t + C 1 -t) = 440 µs when t = 0.
In this computation, the frame f 1 is counted twice since C 1 > C 2 . However, this result is pessimistic.

The worst-case scenario of the frame f 1 at the source node N 1 is identified in Figure 5.8.

Based on the computation, a frame f 3 of flow τ 3 and a frame f 4 of flow τ 4 can arrive at node S 1 no earlier than the time M S 1 1 = 40 µs and no later than the time t + S S 1 max 1 = 140 µs. Since both f 3 and f 4 come from the same input link, their transmissions are constrained by the serialization. It means that the temporal interval between their arrivals is at least min(C 4 , C 5 ) = 100 µs. Assume that f 3 arrives earlier than f 4 (it is the same if f 4 arrives earlier since f 3 and f 4 have exactly the same parameters). In order to guarantee the worst case, the arrival time of f 4 is delayed till the arrival of the considered frame f 1 , which is 140 µs. Therefore, the latest arrival time of f 3 is 40 µs.

One possible scenario giving the worst-case delay in the node S 1 is that a S 1 f 2 = a S 1 f 3 and a S 1 f 1 = a S 1 f 4 as shown in Figure 5.8. In this scenario, frame f 2 which delays the frame f 1 is the first frame transmitted in the busy period bp S 1 . It means that the frame f 2 should be counted twice in the computation and counting twice the frame f 1 actually incurs pessimism.

The tight ETE delay of the flow τ 1 is then 380 µs. Compared to the delay 440 µs computed by the classical Trajectory approach, there is a pessimism of 60 µs, which corresponds to the difference between the transmission times of C 1 and C 2 . The computation is pessimistic because the frame f 2 is not the largest frame transmitted from the busy period bp N 1 . It indicates that since the order of frames transmitted in the busy period is not arbitrary, the assumption that the first frame coming from the previous busy period is the largest one can bring some pessimism into the computation.

Maximum potential pessimism of busy period transition

Term 5.2 considers that first frame transmitted in the busy period bp h is the largest frame coming from the previous busy period bp h-1 and it is counted twice as the busy period transition. As shown in Example 6 in Figure 5.8, Term 5.2 can introduce pessimism due to the non-arbitrary frame transmission order. It is sure that the transition cost is equal to or larger than the minimum frame transmitted from the previous busy period. Then the lower bounded delay of busy period transition is denoted U R CT last i i and computed by:

U R CT last i i = h∈P i /{last i ,dest i } ( min j∈ 1,n h∈P j (C j ))
(5.9)

Chapter 5 -Pessimism analysis

The upper bound of the pessimism caused by the twice counted frame is denoted

P CT last i i .
It is the difference between Term 5.2 and Term 5.9, which is:

P CT last i i = h∈P i /{last i ,dest i } ( max j∈ 1,n h∈P j (C j ) -min j∈ 1,n h∈P j (C j )) (5.10)
For Example 6 in Figure 5.6, a reachable delay of τ 1 computed by Term 5.9 is 380 µs which is the exact worst-case delay of τ 1 in this example.

The maximum pessimism introduced by the classical Trajectory approach for τ 1 is computed by Term 5.10, which is 60 µs.

Pessimism analysis of serialization effect

Underestimation of serialization effect

As an optimization in [BSF10], Term 5.4 considers the frame serialization of input link, which refers to the fact that the frames coming from the same input link cannot arrive at the output port at the same time due to the physical constraint. The flows crossing the output port h are coming from k h + 1 input links. For the studied flow τ i , at each visited output port h in the path P i , IP h 0 represents the input link of the flow τ i . There are k h others input links, denoted by IP h k (k ∈ 1, k h ). For each input link IP h k , there is a frame sequence seq h k composed of continuous frame transmissions of each competing flow from the input link IP h k . The duration of sequence seq h k without its first frame is denoted

l h k (k ∈ 0, k h ).
According to [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF], the serialization factor ∆ h i,t at the output port h is the maximum value between 0 and: The ETE delay upper bound of the flow τ 1 computed by the Trajectory approach is 320 µs.

max k∈ 1,k h (min(l h k )) -max(l h 0 ) (5.
The computation of ∆ S 1 1,t is illustrated in Figure 5.9. According to [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF], ∆ S 1 1,t is calculated by:

∆ S 1 1,t = max(0, min(l S 1 1 ) -max(l S 1 0 )) = max(0, C 4 -C 1 ) = max(0, -60) = 0 t1 t2 t8 t7 t9 t10 t3 t4 t6 t5 Figure 5.9: Illustration of ∆ S 1 1,t
The worst-case scenario of frame f 1 at the source node N 1 is identified in Figure 5.10. When f 1 arrives at the output port of S 1 , the interval during which the other competing frames can

delay f 1 is [M S 1 1 , a S 1 f 1 ] = [40, 140
]. Since frames f 3 and f 4 are transmitted by the same link from N 2 to S 1 , they are serialized which means that their inter-arrival time at S 1 is at least one frame transmission time 40 µs. Suppose that frame f 4 arrives at the output port of S 1 at the same time as frame f 1 , i.e., a S 1 f 4 = a S 1 f 1 = 140 µs, and frame f 3 is transmitted before frame f 4 . Thus in order to delay f 1 , f 3 arrives at S 1 no earlier than t = 40 µs and no later than t = 100 µs due to the serialization.

If f 3 arrives as early as at time t = 40 µs (the same arrival time as f 2 ), the transmission of these two frames is finished at time 40 + C 2 + C 3 = 120 µs which is before the arrival of f 1 . Thus f 3 does not delay f 1 . This case is illustrated in the chronogram of S 1 (a) in Figure 5.10.

If f 3 arrives as late as at time t = 100 µs, the transmission of f 3 is finished at time 140 µs before the arrival of f 1 , and f 3 does not delay f 1 . This case is depicted in the chronogram of S 1 (b) in Figure 5 Frame f 3 does not delay frame f 1 because it has been transmitted during the idle time generated between the arrivals of frames f 2 and f 1 (indicated by a shadow block in Figure 5.10). This idle time can not be ignored due to the different transmission times of the serialized frames f 1 and f 2 . Indeed, the busy period bp S 1 starts at time a S 1 f 1 instead of the time a S 1 f 2 , which is different from the case presented in Figure 5.8 where the busy period bp S 1 starts at time

a S 1 f 2 = M S 1 1 .
Then in Example 7, if frame f 2 is still considered in the frame sequence seq S 1 0 , it leads to an overestimated workload of seq S 1 0 . Therefore, f 2 should not be counted in seq S 1 0 in Example 7, which results in l S 1 0 = 0 and the serialization factor is computed by:

∆ S 1 1,t = min(l S 1 1 ) -max(l S 1 0 ) = C 4 -0 =

Maximum potential pessimism of serialization effect

As illustrated in Example 7, the pessimism of serialization factor is introduced due to the idle time at the output port. In order to avoid the pessimism, one way is to build a reachable scenario at each output port where the frame sequence of each input link will not lead to idle time at the output port. Then a reachable serialization factor is computed based on this scenario. In order to achieve that, first we will show how to build a continuous frame sequence at each input link. Actually, the way to build continuous frame sequences of input links of competing flows and the way to build a continuous frame sequence of the input link of the considered flow are different. They will be presented respectively. Then, the computation of the reachable serialization factor is formalized. The difference between the reachable serialization factor and the one of Term 5.4 leads to the maximum potential pessimism.

We first consider a reachable input frame sequence seq h k (k ∈ 1, k h ) of competing flows crossing the output port h. Since we consider one frame per flow, one reachable continuous frame sequence seq h k is composed of one frame of each competing flow transmitted from the input link IP h k with the largest one at first of the sequence. It is proved by Lemma 2, which is given later, that a continuous frame sequence with the largest frame transmitted first on the input link is still continuous when the frames arrive at the output link. Therefore, such a frame sequence will not lead to idle time at the output port h. Thus, the computation max k∈ 1,k h (min(l h k )) in Formula 5.11 is reachable.

Lemma 2 Given a continuous sequence of frames f 1 , f 2 , ..., f n coming from a single input link in and transmitted on a single output link out, this frame sequence is still continuous on the output link out when f 1 is the largest frame of the sequence.

proof: A continuous frame sequence f 1 , f 2 , ..., f n transmitted on an input link in is illustrated in the upper part in Figure 5.11. Let us assume that frame f 1 is the largest frame of the sequence. Let us also assume that a frame f i in the sequence arrives at the output link out as soon as its transmission is finished on the input link in as illustrated by the dashed lines in Figure 5.11. This arrival time is denoted a out f i .

Without loss of generality, when the frame sequence arrives at the output link out, we assume that there is an idle time t idle between frame f m-1 and frame f m . Before the idle time t idle , the frame sequence from f 1 to f m-1 is continuous. This case is depicted in lower part in Figure 5.11.

On the input link in, since the sequence is continuous, we have:

a out fm = a out f 1 + i∈ 2,m C i
On the output link out, since the sequence is continuous before t idle , we have:

a out fm = a out f 1 + ( i∈ 1,m-1 C i + t idle ) Consequently, i∈∈ 2,m C i = i∈∈ 1,m-1 C i + t idle
Then we have:

C m = C 1 + t idle
Since f 1 is the largest frame in the sequence, C m ≤ C 1 . Then we have:

t idle ≤ 0
Therefore, there is no idle time during the frame sequence on the output link out. Thus, we can conclude that the frame sequence is continuous on the output link out when f 1 is the largest frame of the sequence.

A reachable continuous frame sequence seq h 0 is composed of frames transmitted from input links of previous output port h -1, as illustrated in Figure 5.12. We consider a frame f i of flow τ i transmitted from the input link IP h-1 0 to the output port h -1 and then transmitted from the input link IP h 0 to the output port h. Figure 5.13 illustrates how to build a reachable frame sequence seq h 0 for frame f i . a h f i is the arrival time of frame f i at the output port h. At the output port h -1, there are k h-1 input links transmitting competing flows. For each

input link IP h-1 k (k ∈ 1, k h-1 )
, there is at least one competing frame g h-1 k which can arrive at h -1 at the same time as f i . We consider the smallest frame of each input link. Then at the output port h -1, we can build a continuous frame sequence composed of

g h-1 k (k ∈ 1, k h-1 )
and f i . The largest frame among g h-1 k is transmitted first. In Figure 5.13, the largest frame is

f IP h-1 1
. This frame sequence is the input frame sequence of the output port h.

Two cases are taken into account. The first one is that the first transmitted frame is larger than frame f i , as illustrated in Figure 5.13. According to Lemma 2, when the frame sequence arrives at the output port h, it is still continuous. Then this frame sequence is a reachable frame sequence seq h 0 . It includes the smallest frame of each competing input link of h -1, which is

g h-1 k (k ∈ 1, k h-1 ), and frame f i . The transmission time of frame g h-1 k is denoted C h-1 k (k ∈ 1, k h-1
). Then the length of the reachable frame sequence without its first frame (the largest one among g h-1 k ) is denoted rl h 0 and it is computed by:

min(rl h 0 ) = k∈ 1,k h-1 (C h-1 k ) + C i -max k∈ 1,k h-1 (C h-1 k ) (5.12)
The second case is that the first transmitted frame of the frame sequence is smaller than frame f i . This case is illustrated in Figure 5.14. In this case, when the frame sequence arrives at the output port h, there can exist idle time, as indicated by the shadow block in Figure 5.14.

Therefore, a reachable frame sequence seq h 0 includes only f i itself, and therefore rl h 0 = 0. As we have derived a reachable frame sequence length without its first frame for each input link, a reachable frame serialization factor is computed by: :

∆ h i = max(0, max k∈ 1,k h (min(l h k )) -min(rl h 0 )) (5.
U P i = max -J i +B i ≥t≥-J i (P CF last i i,t + P CT last i i + P S last i i,t
) (5.16)

Integration of the minimum duration constraints

It has been shown in Section 1.6 that for two periodic flows with known offsets emitted by the same source node, there is a minimum duration between them. In Chapter 3, a modified

Trajectory approach has been proposed in order to take into account these dependencies. This proposed method introduces pessimistic computation so as to guarantee the delay upper bounds (overestimated delay). One way to evaluate this pessimism is to consider the gap between an upper bounded delay (overestimated delay) and an underestimated value of worst-case delay.

In previous section, a pessimism analysis has been developed based on the classical Trajectory approach. This analysis provides a computation of underestimated worst-case delays. However, it does not consider the minimum duration constraints. Thus it cannot be applied to the flows with minimum duration constraints since it might provide a worst-case delay lower bound which is not reachable. Therefore, according to Section 1.6, there is a minimum duration of 1000 µs from a frame arrival of τ 1 to a frame arrival of τ 2 , and the duration is 3000 µs in the reverse order. This is illustrated in Figure 5.15. Thus a frame of τ 1 will never be delayed by a frame of τ 2 and a reachable delay of τ 1 is C 1 = 40 µs. According to the pessimism analysis in the previous section, one frame per flow is taken into account and frames of different flows can arrive at the same time since there is no assumptions on their frame arrivals. Thus a reachable delay for

τ 1 is C 1 + C 2 =
80 µs which corresponds to a scenario where a frame of τ 2 delays a frame of τ 1 . However due to the minimum duration constraint, this scenario will never happen and this delay is not reachable for flow τ 1 .

The following paragraphs present how to compute an underestimated delay considering the minimum duration constraints based on the modified Trajectory approach developed in Chapter 3.

Review of the modified Trajectory approach

The classical approach considers that each flow is independent. The modified approach developed in Chapter 3 classifies flows into subsets G x (x ∈ 1, n g ). Any couple of flows in one subset has minimum duration constraints. The maximum workload generated by the subset G x to delay flow τ i is RS i,t,x . Therefore, in order to obtain an underestimated worst-case delay, we have to compute an underestimated value of RS i,t,x for each subset G x .

In the following paragraphs, the pessimism introduced by the overestimated workload of subsets is illustrated. Then an underestimated value of the maximum workload of each subset is developed and the pessimism is computed by the gap of the underestimated value to the overestimated value.

Illustration on the overestimation of dependent flows

Let us first illustrate the pessimism introduced by the overestimated workload of subsets. Since the frames of τ 1 , τ 2 , τ 3 and τ 4 are released at the same time, at the output port of switch S 1 , frame f 1 is delayed by frame f 2 , and at the output port of switch S 1 , frame f 1 is delayed by frames f 3 and f 4 . At the output port of S 2 , any frame of τ 5 and τ 6 can delay f 1 if it arrives later than M S 2 1 = 1000 µs and earlier than the arrival of f 1 : a S 2 f 1 = 2500 µs. The length of this workload interval at S 2 is 1500 µs which happens to be equal to the minimum duration M D N 1 5,6 . It means that both a frame f 5 from τ 5 and a frame f 6 from τ 6 can delay f 1 , as shown in Figure 5.18. The worst-case delay computed by the modified Trajectory approach is 4000 µs which is the exact worst-case delay in this example. The worst-case scenario of f 1 is illustrated in Figure 5.18. However, sometimes due to the overestimation of workload interval, the workload of a subset could be overestimated in the computation. Consider a frame f 1 of flow τ 1 in Example 9 in Therefore, the computation considers the same workload interval 1500 µs at S 2 , which equals to the minimum duration M D N 1 5,6 . Thus it leads to the same computed delay 4000 µs of flow τ 1 .

The worst-case scenario for τ 1 in Figure 5.19 is illustrated in Figure 5.20 which indicates that the exact worst-case delay is 3500 µs. Compared to the computed delay 4000 µs, there is an introduced pessimism of 500 µs. Indeed, in order to delay f 1 , the frame f 6 arrives at the same time as f 1 at the output port of S 2 (a S 2 f 1 = a S 2 f 6 = 2500 µs). Due to the minimum duration M D N 1 5,6 = 1500 µs (shadow block in Figure 5.20), the latest possible arrival time of f 5 before f 6 is 1000 µs. As illustrated in Figure 5.20, f 5 is transmitted immediately after its arrival at S 2 and cannot delay f 1 . Then only f 6 delays f 1 at S 2 , and τ 5 does not delay τ 1 in this example.

In this case, the workload of the subset G 3 = {5, 6} is overestimated. In order to evaluate the introduced pessimism of the workload for each subset, in the following paragraphs we develop first a method to compute an underestimated value for each subset and then the pessimism which is the difference between the overestimated value and the underestimated value.

Pessimism analysis of the workload of dependent flows

It has been shown that the introduced pessimism is due to an overestimated workload of one subset. One way to obtain an underestimated worst-case delay for each subset is to consider the following assumptions:

• Assumption 1 : only one frame per competing flow delays the considered frame;

• Assumption 2 : all the frames generated by a subset are totally separated.

Assumption 1 is obviously optimistic by considering for each competing flow an infinite period. Assumption 2 means that only one frame out of all the frames of one subset delays the considered frame and the largest frame is taken into account. It indicates that the minimum duration between any two flows is infinite and it is obviously optimistic. Thus, these two assumptions lead to the case where only one frame of flows in one subset can delay the considered frame, and the largest frame is considered in the computation. Back to the Example 9 in Figure 5.19, since frames f 5 and f 6 are both from one subset, then only the larger one between f 5 and f 6 is considered to delay frame f 1 at the output port of S 2 .

Based on the two assumptions, an underestimated workload U R CF last i i generated by n g subsets delaying τ i is obtained by:

U R CF last i i = x∈ 1,ng max j∈Gx (C j )
(5.17)

The upper bound of this pessimism is denoted

P CF last i i,t
. It is the difference between Term 3.10 and Term 5.17, which is:

P CF last i i,t = x∈ 1,ng (RS i,t,x -max j∈Gx (C j ))
Then the underestimation of the worst-case end-to-end delay upper bound of flow τ i is computed by Equation 5.15 and the maximum introduced pessimism is upper bounded by Equation 5.16.

Application on the AFDX network

An application of the proposed approach on the industrial Avionic Full DupleX (AFDX) switched Ethernet network configuration (see 4.2) is presented. The modified Network Calculus approach and the modified Trajectory approach have been applied to this industrial AFDX network in Chapter 4. In this part, the introduced pessimism by both the classical and the modified Network Calculus approach as well as the classical and the modified Trajectory approach on such a network is computed by the analytical method developed in this Chapter. The offsets are assigned according to the real-time automotive CAN network [START_REF] Grenier | Pushing the limits of CAN -scheduling frames with offsets provides a major performance boost[END_REF] presented in 4.3.

Upper bounding the pessimism of the Network Calculus approach

Although the pessimism analysis is not directly developed from the Network Calculus approach, it does provide an analytical computation of the underestimated worst-case delays (lower bounds). The formulas are given in Section 5.2.5 and Section 5.3.3. Therefore, by measuring the difference between a worst-case delay upper bound computed by the Network Calculus approach and an underestimated value of the worst-case delay given by pessimism analysis, we can upper bound the pessimism introduced by the Network Calculus approach in the worst-case delay upper bound computation. The percentages of pessimism upper bound out of the overestimated delay (worst-case delay upper bound) of each path P i of VL v i for both classical Network Calculus approach and modified Network Calculus approach are calculated.

The percentage is computed by the following term:

R i -RD i R i %
where R i is the worst-case delay upper bound of v i computed by the classical/modified Network Calculus approach and RD i is the underestimated value of the worst-case delay of v i obtained by the analytical pessimism approaches.

The results are shown in Figure 5.21 where N C stands for the Network Calculus approach.

From these results, we deduce that the average percentages of pessimism for the classical Network Calculus approach and for the modified Network Calculus approach are of 18% and 17%, respectively.

Upper bounding the pessimism of the Trajectory approach

In order to evaluate the pessimism introduced by the Trajectory approach, a pessimism upper bound of each path is computed by the analytical method developed in this Chapter. The percentages of pessimism upper bounds out of the overestimated delays (upper bounds) of each path for both classical Trajectory approach and modified Trajectory approach are calculated. The results are shown in Figure 5.22 where T raj stands for the Trajectory approach.

The average percentages of pessimism for the classical Trajectory approach and for the modified Trajectory approach are of 12% and 14%, respectively. The Trajectory approach introduces less pessimism than the Network Calculus approach for both the classical and the modified cases. The reason is obvious since it has been shown in Chapter 4 that the Trajectory approach gives tighter computed worst-case delay upper bounds than the Network Calculus approach.

It is noticed that the classical Trajectory approach has slightly lower pessimism upper bounds than the modified Trajectory approach. This is due to Assumption 2 in 5.3.3. This assumption considers that all the frames generated by one subset are totally separated and it takes the maximum frame out of a set of dependent flows in the computation instead of the maximum frame out of each flow. This assumption introduces more optimism compared to the classical approach. Therefore the pessimism analysis for the modified Trajectory approach leads to a lower (more optimistic) underestimated value of the worst-case delay and therefore a larger estimated maximum pessimism.

In Chapter 4, an optimized approach Opt is proposed which considers always the tighter computed ETE delay upper bounds between the modified Network Calculus approach and the modified Trajectory approach. The percentages of upper bounded pessimism of the optimized approach Opt are as well evaluated and its results are shown in Figure 5 approach has a slight improvement on upper bounded pessimism (average percentage of 13%) than modified Trajectory approach because it takes tighter delay upper bounds of both the modified Network Calculus and the modified Trajectory approach, and therefore further eliminates some pessimism.

For several paths, the pessimism percentage is 0%. It means that for each of these flows, the computed delay upper bound is equal to its corresponding underestimated worst-case delay, which is the exact worst-case delay of the flow. The numbers of paths with exact worst-case delays provided by each evaluated approach and their percentages to the total number of paths (6412) are listed in Table 5

Conclusion

In the context of real-time switched Ethernet networks, the worst-case delay analysis introduces a pessimistic computation so as to guarantee an end-to-end delay upper bound. In order to evaluate the potential pessimism, a pessimism analysis is developed based on the Trajectory approach. It first analyzes each source of possible pessimism. Then an underestimation of worst-case delay is developed. The maximum difference between the underestimation (lower bound) and the overestimation (upper bound) of the end-to-end delay gives a metric of the maximum potential pessimism. This pessimism analysis is developed for both the classical Trajectory approach and the modified Trajectory approach which takes into account the minimum duration constraints of periodic flows.

This proposed pessimism analysis is applied to the industrial AFDX network. The classical Network Calculus approach and the modified one with minimum duration constraints are taken into account in the evaluations. The difference between the computed worst-case delay upper bounds and the underestimated worst-case delays given by the proposed pessimism analysis shows the pessimism introduced by the Network Calculus approach. The percentages of pessimism out of the computed delay upper bounds for the classical method and the modified method are of 18% and 17%, respectively. The proposed pessimism analysis provides a direct analytical pessimism computation for the Trajectory approach. Both the classical Trajectory approach and the modified one with minimum duration constraints are evaluated.

The results show that there is on average of about 12% introduced pessimism of the computed end-to-end delay upper bounds for the classical Trajectory approach as well as 14% introduced pessimism for the modified Trajectory approach. Clearly, the Trajectory approach introduces less pessimism than the Network Calculus approach since it gives tighter computed delay upper bounds.

Chapter 6

Worst-case delay analysis on a heterogeneous network distributed real-time systems by a compositional approach. However, previous works do not consider a heterogeneous network with both FIFO and non-preemptive FP scheduling policies.

In order to deal with heterogeneities of such a network, one possible solution is a componentbased approach which has been discussed in the domain of complex systems. Especially, a hierarchical scheduling frameworks [START_REF]Compositional real-time scheduling framework[END_REF][START_REF] Lorente | A hierarchical scheduling model for component-based real-time systems[END_REF][START_REF] Shin | Periodic resource model for compositional real-time guarantees[END_REF] where components (applications) form a hierarchy has received increasing attention. Such an approach allows each component to be developed and analyzed independently and therefore guarantees temporal isolation among components. Another way is to consider the Trajectory approach, which has been successfully applied to homogeneous switched Ethernet networks [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF][START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF][START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF][START_REF]Applying Trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]. This approach has been introduced in previous chapters. In order to apply this approach, the heterogeneity properties (e.g. heterogeneous scheduling policies) have to be integrated.

The aim of this chapter is to develop two approaches to compute the end-to-end delay upper bounds on such a heterogeneous network. The key issue is the integration of heterogeneous scheduling policies. The first approach is based on a component-based principle which allows each component to keep its own properties. It is holistic and introduces pessimism at each component level. The second one is an adapted Trajectory approach which integrates heterogeneity properties by unifying them since the computation of a given flow is processed on its whole trajectory (path) and does not allow heterogeneity properties along the trajectory. The two approaches are compared on a middle-scale network case study.

In this chapter, pessimism introduced by the adapted Trajectory approach is also identified.

An improved Trajectory approach is proposed. The results show that the improved Trajectory approach computes tighter delay upper bounds than the component-based approach in the context of a heterogeneous network.

This chapter is organized as follows. Section 6.2 introduces the heterogeneous network architecture considered in this chapter and illustrates the worst-case delay computation on an example. Section 6.3 presents the component-based architecture of the considered network and applies a component-based approach to such a network. Section 6.4 adapts the Trajectory approach by integrating heterogeneity properties of the considered network for the worst-case delay analysis. Section 6.5 applies both proposed approaches to a middle-scale real-time heterogeneous network and analyzes the obtained results of both approaches. Section 6.6 indicates the pessimism introduced by the adapted Trajectory approach and proposes an improved Trajectory approach which provides tighter computation results on case study. Section 6.7 concludes this chapter.

Heterogeneous network architecture

The network architecture considered in this chapter is composed of a set of CAN buses interconnected by a switched Ethernet network. An illustrative example of such a network is depicted in Figure 6.1. It includes three CAN buses interconnected by two switches S 1 and S 2 via bridges.

CAN bus

Each CAN bus is based on the CAN 2.0 A specification (see [CAN] for details) and interconnects a set of Electronic Control Units (ECUs). The scheduling on such a CAN bus is non-preemptive FP scheduling. An identifier on 11 bits is associated to each frame. It defines the priority of the frame: at each time, the pending frame with the highest priority (i.e. the smallest identifier) is transmitted. Each CAN frame includes up to 8 data bytes, leading to a maximum frame size of 135 bits, including bit stuffing. The bandwidth of each CAN bus is R CAN = 1 M bit/s. • Pure Ethernet nodes (N 1 and N 2 in Figure 6.1);

Switched Ethernet backbone

• Bridges connecting CAN and Ethernet (Brdg 1 , Brdg 2 and Brdg 3 in Figure 6.1).

Heterogeneous flows

Three kinds of flows are transmitted over this heterogeneous architecture:

• Pure CAN flows (PC): such a flow concerns a set of ECUs interconnected by the same CAN bus;

• Remote CAN flows (RC): such a flow concerns a set of ECUs which are interconnected by two different CAN buses that must communicate through the Ethernet backbone;

• Pure Ethernet flows (PE): such a flow concerns a set of pure Ethernet stations.

As an example, the flows transmitted over the network architecture in Figure 6.1 are listed in Table 6.1. The type and path of each flow are indicated in this table.

τ i Type Path P i τ 1 RC {CAN 1 , Brdg 1 , S 1 , S 2 , Brdg 2 , CAN 2 } τ 2 RC {CAN 1 , Brdg 1 , S 1 , S 2 , Brdg 2 , CAN 2 } τ 3 PE {N 1 , S 1 , S 2 , N 2 } τ 4 RC {CAN 3 , Brdg 3 , S 1 , S 2 , Brdg 2 , CAN 2 } τ 5 PC {CAN 2 }
Table 6.1: Flows in the example in Figure 6.1

Each flow τ i is characterized by its period T i (minimum inter-arrival time of two consecutive frames), its frame transmission time C i and its maximum release jitter J i . Each CAN flow also has a priority p i which is ignored by the switched Ethernet backbone. The transformation of CAN frames into Ethernet frames has to take into account the differences between CAN and Ethernet (frame sizes, bandwidths, scheduling policies, etc.).

Bridging strategy

One important issue is the encapsulation strategy of CAN frames within Ethernet frames. Due to the very different frame sizes between CAN and Ethernet, different bridging strategies have been proposed in [START_REF] Scharbarg | Interconnecting CAN busses via an Ethernet backbone[END_REF]. The idea is to allow the encapsulation of more than one CAN frame in a single Ethernet frame and to send the encapsulated Ethernet frame withing a certain time.

Thus, the strategy is characterized by two parameters:

• The maximum number N B of CAN frames that can be encapsulated within a single Ethernet frame;

• The maximum waiting delay W D of a CAN frame pending in the bridge output port.

In this chapter, the following bridging strategy is used: a CAN frame arriving at a bridge

S ET H = N B × 135 8 + 18
Therefore, the maximum transmission time of such an Ethernet frame is

C ET H = S ET H × 8 100

End-to-end delay analysis

The delay has to be upper bounded in the context of real-time networks. This can be achieved by a worst-case delay analysis, which has to take into account the heterogeneous properties of the network architecture considered in this chapter.

For example, consider τ 2 in Figure 6 From the point of scheduling policy, τ 2 crosses FP, FIFO and FP schedulings, in this order.

From the point of bandwidth, τ 2 is transmitted under bandwidths 1 M bit/s, 100 M bit/s and 1 M bit/s, in this order. Finally from the point of bridging strategy, τ 2 is encapsulated in an Ethernet flow at Brdg 1 and decapsulated at Brdg 2 . Therefore, the worst-case delay analysis of such a flow has to integrate all these factors. However, existing approaches do not consider these heterogeneities.

In the following paragraphs, two approaches are proposed to deal with the worst-case endto-end delay computation with the integration of heterogeneities of such a network.

Component-based approach for worst-case delay analysis

Component-based architecture

Component-based approach has been widely applied in real-time scheduling. In the context of timing property analysis, a compositional real-time scheduling framework is achieved where global timing properties are built by composing together independently analyzed local timing properties. Such an approach allows each component to be developed and analyzed independently and therefore guarantees temporal isolation among components. Especially, a hierarchical scheduling framework [START_REF]Compositional real-time scheduling framework[END_REF][START_REF] Lorente | A hierarchical scheduling model for component-based real-time systems[END_REF][START_REF] Shin | Periodic resource model for compositional real-time guarantees[END_REF] where components (applications) form a hierarchy, illustrated in Figure 6.3, has received increasing attention. Each component represents a scheduling model and a resource is allocated from a parent component to its children components. The key point of such an approach is to compose independently analyzed local timing properties, called scheduling interface, into a global timing property.

In the context of heterogeneous networks considered in this work, a component is defined as a self-contained network unit or subnetwork that can be used as a building block in the design of a larger network. Each component satisfies some functional properties and it is characterized by a scheduling policy and a set of sporadic flows. The scheduling policy is local to a component. Specifically speaking, for the considered heterogeneous network, three components are considered:

• The Ethernet backbone which exchanges flows using FIFO scheduling;

• Each CAN bus manages a set of pure and remote CAN flows using non-preemptive FP scheduling;

• Each Ethernet source node manages a set of pure Ethernet flows using FIFO scheduling.

Therefore, the component-based approach preserves FP scheduling for each CAN bus and FIFO • the communication between two CAN buses is unidirectional (a CAN bus cannot be the source of a flow and the destination of another flow),

• an Ethernet source node is not allowed to send Ethernet frames to a CAN bus.

Consider the heterogeneous network in

J compm i = J comp m-1 i + D comp m-1 max i -D comp m-1 min i (6.1)
Other temporal characteristics of the output flow τ compm i include:

• T compm i , which is equal to T i , i.e., T compm i = T i ; • C compm i ,
J ET H 2 = J 2 + D CAN 1 max 2 -D CAN 1 min 2 .
where D CAN 1 max 2 is determined by the Network Calculus approach for non-preemptive FP scheduling.

Similarly, from the component ET H to the component CAN

2 , the output flow τ CAN 2 2 is determined by T CAN 2 2 = T 2 , C CAN 2 2 = C 2 , p CAN 2 2 = p 2 and J CAN 2 2
which is:

J CAN 2 2 = J ET H 2 + D ET H max 2 -D ET H min 2 .
where D ET H max 2 is determined by Network Calculus approach for FIFO scheduling. At each network element, the input flows are sorted into n p classes according to priorities.

The arrival traffic of a flow τ i is constrained by an arrival curve α i (t) = r i t + b i , with the burst b i = l max i and the leak rate r i = l max i /T i , where l max i is the maximum frame size of τ i . For class j, j ∈ 1, n p , which has a set J of flows having the same priority, the aggregated arrival curve is the sum of each arrival curve of each flow in this class, i.e. α j = i∈J α i .

Each network element provides a service curve β(t) = R[t -T ] + with full capacity (rate) R and a latency T to flows. Several service curves with full capacity are considered in this paper depending on the specific network element:

• CAN bus: β(t) = R CAN • t; • pure Ethernet node: β(t) = R ET H • t; • switch output port: β(t) = R ET H (t -sl) + ;
• bridge output port towards Ethernet backbone:

β(t) = R ET H (t -T B -W D) + ;
• bridge output port towards a CAN bus:

β(t) = R CAN (t -T B ) + .
The latency value of a service curve includes the switching latency sl, the encapsulation and decapsulation delay T B and the maximum waiting delay W D in the bridge.

It is proved in [START_REF] Schmitt | On average and worst case behaviour in non-preemptive priority queueing[END_REF] that the service curves of lower priority classes are dependent on the arrival curves of higher priority classes. For each class j, the service curve β j is given by:

β j (t) =   Rt - i∈ 1,j-1 α j (t) -C max j   + for j ∈ 1, n p , where C max j = max i∈ j+1,np (C i ).
Therefore, the worst-case delay of a flow belonging to class j with aggregated arrival curve α j in a network element which offers service curve β j for class j is bounded by the horizontal deviation between α j and β j :

h(α j , β j )
The Network Calculus approach, for both FIFO and non-preemptive FP schedulings, is applied to the calculation of the maximum delay D compm max i of τ compm i generated at component comp m .

Trajectory approach for worst-case delay analysis 6.4.1 Classical Trajectory approach for FP/FIFO scheduling applied to a homogeneous network

The classical Trajectory approach for FIFO scheduling is presented in Chapter 3. It is also developed for FP/FIFO scheduling in [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF] and applied to a homogeneous switched Ethernet network in [START_REF]Applying Trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]. It computes the ETE delay upper bound by considering for a frame the worst case scenario on its trajectory. Let us consider a flow τ i following a path P i . The frame f i of flow τ i generated at time t is under study. At each output port h along its path, f i can be delayed by other competing flows. The transmissions of these competing flows before f i compose a busy period bp h at the output port h. Such a busy period bp h is a temporal interval with no idle time. In order to compute the worst-case ETE delay of frame f i , the Trajectory approach considers the longest possible busy period ending with frame f i at each node in its path.

For each flow τ i , we define three sets according to priority:

• hp i : the set of flows having a fixed priority strictly higher than that of τ i ;

• sp i : the set of flows having a fixed priority strictly equal to that of τ i ;

• lp i : the set of flows having a fixed priority strictly lower than that of τ i ;

The following notations are used for the computation:

• n S : the number of switches visited by flow τ i ;

• n B : the number of bridges visited by flow τ i ;

The worst-case delay of a frame f i generated at time t contains several parts.

The first part is the delay generated by the flows in set sp i . This is the same case as the Trajectory approach for FIFO scheduling introduced in Chapter 3. For a flow τ j with the same priority as that of τ i delaying τ i at the node f irst j,i , there is jitter interval A i,j which determines the maximum frame number of τ j delaying f i . This jitter interval is illustrated in Figure 3.4. Then for all flows in set sp i , the competing workload is computed by:

D sp (t, sp i ) = j∈sp i P j ∩P i =∅ (1 + t + S f irst j,i max i -S f irst j,i min j + A i,j T j ) + • C j (6.2) where A i,j = S f irst i,j max j -M f irst i,j i + J j .
The second part is the delay generated by the flows in set hp i . A flow τ j with a higher priority than that of τ i can delay τ i at any shared node (from f irst j,i to last i,j ). The difference from flows with the same priority is that a frame of τ j can delay f i even if it arrives after f i at a shared node, provided it arrives before the start of transmission of f i . Hence for all flows in set hp i , the competing workload is computed by:

D hp (hp i ) = j∈hp i P j ∩P i =∅ (1 + W last i,j i,t -S last i,j min j + A i,j T j ) + • C j (6.3)
where

W last i,j i,t
is the latest starting time of the studied frame f i at its last shared node last i,j with τ j (Figure 6.8).

The third part is the delay caused by a lower priority flow due to non-preemptive effect.

Its computation is detailed by Property 1 in [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF]. For any flow τ i , the delay caused by flows in lp i is denoted δ i (lp i ).

The fourth part represents the transmission cost from one busy period to the next one (explained in [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF][START_REF]Applying Trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]). For a flow τ i , it considers the longest frame for each node (except slow i ) along path P i . Then for any flow τ i , the transmission cost of busy periods along P i is:

. . . . . .

R trs (hp i ∪ sp i ) = h∈P i /{slow i } ( max j∈hp i ∪sp i h∈P j {C h j }) (6.4)
The last part is the sum of the switching latency which is an upper bounded sl per switch as well as the bridging delay which is an upper bounded T B per bridge. For any flow τ i , this cost is:

R c = n S • sl + n B • T B (6.5)
Therefore, for a frame of any flow τ i generated at time t, the latest starting time of its transmission on its last visited node last i is:

W last i i,t = D sp (t, sp i ) + D hp (hp i ) + δ i (lp i ) (6.6) + R trs (hp i ∪ sp i ) + R c (6.7) - h∈P i /{f irst i } (∆ h i,t ) (6.8) -C last i i (6.9)
Each part in Term (6.6) and Term (6.7) corresponds to one part of delay analyzed above.

Term (6.8) considers frame serialization on links. More details on this optimization can be found in [START_REF]Applying Trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]. Term (6.9) is subtracted since

W last i i,t
is not the received time of the considered frame, but its latest starting time on node last i .

Then the worst-case ETE delay upper bound of the flow τ i is obtained by: R i = max

-J i +B slow i >t≥-J i {W last i i,t + C last i i -t} (6.10)
where

B slow i = j∈hp i ∪sp i ∪i B slow i T j • C slow j,i j
. It is proved by Property 2 and Lemma 3 in [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF] and it limits the range of computation.

We illustrate the Trajectory approach for non-preemptive FP scheduling on the network architecture in Figure 6.1. In order to do that, a homogenized version of the network is first considered. It is assumed that all the links have the same bandwidth, and the bridging strategy is characterized by N B = 1 (one CAN frame in one Ethernet frame) and W D = 0. It leads to a homogeneous network. In Section 6.4.2 we will show how the network in Figure 6.1 with heterogeneity properties can be analyzed by the Trajectory approach.

The computation is illustrated on flow τ 2 in the network example in Figure 6.1 which

follows path P 2 = {CAN 1 , Brdg 1 , S 1 , S 2 , Brdg 2 , CAN 2 }.
Along its path, it competes with τ 1

for CAN 1 , with τ 3 and τ 4 for the output port of S 1 as well as with τ 5 for CAN 2 . We assume that p 1 > p 2 = p 3 > p 4 > p 5 , i.e., for τ 2 , hp 2 = {1}, sp 2 = {2, 3} and lp 2 = {4, 5}.

According to Equation (6.2), the delay caused by flows in set sp 2 = {2, 3} is computed by:

D sp (t, sp 2 )= j∈{2,3} (1 + t + S f irst j,2 max 2 -S f irst j,2 min j + A 2,j T j ) + • C j
According to Equation (6.3), the delay caused by flows in set hp 2 = {1} is computed by:

D hp (hp 2 ) = j∈{1} (1 + W last 2,j 2,t -S last 2,j min j + A 2,j T j ) + • C j
The worst-case delay incurred by flows in set lp 2 = {4, 5} due to non-preemptive effect is δ 2 (lp 2 ).

According to Equation (6.4), the transmission cost along path P 2 is:

R trs (hp 2 ∪ sp 2 ) = h∈P 2 h =CAN 1 max j∈{1,2,3} h∈P j {C h j }
Since τ 2 crosses two switches (n S = 2) and two bridges (n B = 2), the cost of the switching latency and the bridging delay is

R c = 2 × sl + 2 × T B .
Thus, the latest starting time of frame transmission of τ 2 on its last visited node CAN 2 is:

W CAN 2 2,t = D sp (t, sp 2 ) + D hp (hp 2 ) + δ 2 (lp 2 ) + R trs (hp 2 ∪ sp 2 ) + R c -C CAN 2 2
Then the worst-case ETE delay of τ 2 is upper bounded by:

R 2 = max t≥0 {W CAN 2 2,t + C CAN 2 2
-t} (6.11)

A modified Trajectory approach adapted to a heterogeneous network

In order to cope with the architecture in Figure 6

Integration of bridging strategy

Let us first focus on the bridging strategy. For the direction CAN to Ethernet, there is an overhead T B to deal with frame encapsulation which is considered in R c . After one CAN frame arrives at the bridge output port connecting Ethernet, it waits at most for a duration W D before encapsulation. This waiting duration W D needs to be added to the computation If flow τ i crosses n Bout bridge output ports connecting Ethernet, thus the total waiting delay is:

n Bout • W D
For the direction Ethernet to CAN, CAN frames are decapsulated from Ethernet frames immediately after a duration T B to handle frame decapsulation.

Integration of different bandwidths

Different bit-rates in the heterogeneous network lead to different transmission durations for a remote CAN flow (e.g. τ 1 or τ 2 in Figure 6.1). For such a remote CAN flow τ i , its transmission time at a CAN bus is C i , and its transmission time at the Ethernet backbone is C ET H as analyzed in Section 6.2.4. In order to guarantee the worst-case delay, the Trajectory approach replaces C i in Equation (6.2), (6.3) with the largest transmission time C slow i i (see [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF] for details). For each remote CAN flow τ i , we have:

C slow i i = max{C i , C ET H }
For a pure Ethernet flow and a pure CAN flow:

C slow i i = C i

Integration of different scheduling policies

The last heterogeneity characteristic which has to be integrated concerns the schedulings of flows: Non-preemptive FP for CAN bus and FIFO for switched Ethernet. When a flow τ j delays a flow τ i and they share output ports with different scheduling policies, the delay upper bound computation of τ i considers the following cases:

• Case 1: p j > p i , then FIFO is replaced by FP along their shared path since FP is less favorable for τ i and can only increase its delay;

• Case 2: p j = p i , then FIFO and FP are equivalent, so FIFO is considered along their shared path (the same as FP/FIFO in [START_REF]Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF]);

• Case 3: p j < p i and f irst j,i is with FP scheduling, then the computation considers FP scheduling along their shared path because τ j cannot have another frame delaying τ i after f irst j,i due to the frame serialization.

• Case 4: p j < p i and f irst j,i is with FIFO scheduling along their shared path, then the computation considers FIFO scheduling because it is pessimistic for τ i by assigning a higher priority p i to τ j .

These cases are illustrated in Figure 6.9.

τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j FP FP FP FP FP FIFO (a) Case 1 τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j FIFO FIFO FIFO τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j FIFO FIFO FP (b) Case 2 τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j FP FP FIFO τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j FP FP FP (c) Case 3 τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j FIFO FIFO FIFO τ iτ j τ i τ j τ i τ j τ iτ j τ i τ j FP FIFO FP (d) Case 4
Figure 6.9: Illustration of heterogeneous scheduling policies integration Three new sets shp i , ssp i and slp i are defined according to the considered scheduling policy:

• shp i : j ∈ shp i if p j > p i and τ j shares pure FP or both FP and FIFO scheduling policies with τ i (Case 1);

• ssp i : j ∈ ssp i if p j = p i ; or if p j < p i and f irst j,i is with FIFO scheduling (Case 2 and Case 4);

• slp i : j ∈ slp i if p j < p i and f irst j,i is with FP scheduling (Case 3).

Computation on a heterogeneous network

With the integration of the three heterogeneity properties, the latest starting time of a frame of flow τ i generated at time t on its last visited node last i is:

W last i i,t = D sp (t, ssp i ) + D hp (shp i ) + δ i (slp i ) + R trs (shp i ∪ ssp i ) + R c + n Bout • W D - h∈P i h =f irst i (∆ h i,t ) -C last i i (6.12)
Then the worst-case delay of τ i can be computed by Equation (6.10).

For τ 2 in Figure 6.1, τ 1 and τ 4 cross heterogeneous schedulings with τ 2 . τ 1 has a higher priority than τ 2 , then the computation of a pessimistic delay caused by τ 1 considers only FP With the integrated heterogeneity characteristics, the latest starting time of frame transmission of τ 2 on CAN 2 is:

W CAN 2 2,t = D sp (t, ssp 2 ) + D hp (shp 2 ) + δ 2 (slp 2 ) + R trs (shp 2 ∪ ssp 2 ) + R c + W D -C CAN 2 2
Then the worst-case ETE delay upper bound of τ 2 can be computed by Equation (6.11).

This adapted Trajectory approach is applied to a case study in the next section. And obtained results are compared to the ones obtained with the component-based approach.

Case study

This evaluation considers a middle-scale heterogeneous network in Figure 6 Consider a frame f 1 of τ 1 generated at time t = 0. Based on the Trajectory approach developed in Section 6.4.2, since τ 2 and τ 3 with lower priorities than that of τ 1 delays τ 1 first at a FIFO output port S 1 , they are considered as with the same priority as τ 1 , as Case 4 in Section 6.4.2. Therefore shp 1 = ∅, ssp 1 = {1, 2, 3}, slp 1 = ∅, and

C slow 2,1 2 = C slow 3,1 3 = 20 µs.
Then, we obtain:

D sp (0, ssp 1 ) = C slow 1 1 + C slow 2,1 2 + C slow 3,1 3 = 60 µs D hp (shp 1 ) = δ 1 (slp 1 ) = 0
R trs (shp 1 ∪ ssp 1 ) = 5 + 5 + 20 = 30 µs According to Equation (6.12) and (6.10), the worst-case delay of τ 1 is computed as R 1 = 90 µs.

The transmission of frame f 1 is illustrated in Figure 6.16, where the arrows represent frame arrivals. At switch S 1 , frame f 1 is delayed by one frame f 2 of τ 2 and one frame f 3 of τ 3 due to the FIFO scheduling. At CAN bus CAN 4 with FP scheduling, frame f 1 is transmitted before frame f 3 due to the higher priority. Therefore, the worst-case delay of τ 1 is 70 µs which is 20 µs less than the computed result R 1 = 90 µs.

The introduced pessimism of τ 1 is due to the integration of different bandwidths where the context of the heterogeneous networks considered in this chapter, CAN bus has a much lower bandwidth than Ethernet backbone. Therefore this pessimism is experienced by flows of Case 4 in Section 6.4.2. In order to reduce the pessimism, for a flow τ j corresponding to Case 4 in Section 6.4.2, its interference on τ i is considered separately by FIFO scheduling and FP scheduling as follows:

• τ j leaves P i after their last shared FIFO output port last F IF O i,j .

• τ j joins P i at their first shared non-preemptive FP output port f irst F P j,i . τ j is modeled by maximum frame density and characterized by

{T j = T j , C j = C j , p j = p j , J j = J j + S f irst F P j,i max j -S f irst F P j,i min j }
This is safe since for FIFO output ports of the shared path, flow τ j is still assigned with a higher priority p i , while for FP output port of the shared path, flow τ j is with its own priority.

We use lpb i to denote the set of these new generated flows. Then δ i (slp i ) in Equation (6.12) is replaced by δ i (slp i ∪ lpb i ).

For τ 1 in Figure 6.15, lpb 1 = {2 , 3 }. Since τ 2 and τ 3 are considered to leave P 1 after S 1 , then C This improved approach is applied to the network in Figure 6.10. The computed results for remote CAN flows are shown in Figure 6.17. Compared to results in Figure 6.13, this improved approach provides tighter delays than the component-based approach for all the remote CAN flows.

Conclusion

In this chapter two approaches for worst-case delay analysis are applied to a real-time heterogeneous network where a switched Ethernet backbone interconnects several CAN buses via bridges. The first presented approach is based on a component-based approach which allows each component to be analyzed independently with a local scheduling and therefore deals with heterogeneity properties at component level. The second introduced approach is an adapted Trajectory approach which integrates heterogeneity properties in the computation by unifying

Conclusions and Perspectives

Real-time switched Ethernet network is a promising candidate for the industrial applications.

It is necessary to demonstrate that worst-case end-to-end delays can be upper bounded since the delay upper bound is a crucial performance to evaluate real-time networks. Fortunately, computation of delay upper bounds can be done by different existing approaches. These existing approaches consider that the flows exchanged in the network are independent. But, periodic flows emitted by the same source node are synchronized based on a local clock. Their offsets can be known, and increase the knowledge about the frame arrival times thus improving the worst-case delay analysis.

This thesis studied the worst-case delay analysis suitable for real-time switched Ethernet networks accounting for the offset constraints.

In the first chapter, we have shown that periodic flows with known offsets emitted by the same source node are dependent since they are scheduled by a common local clock. More precisely, for two periodic flows with known offsets emitted by the same source node, it has been shown that there exist minimum durations between their frame arrivals at the output port of their source node. Therefore, the scenario that these frames arrive at the same time can be impossible. It has been further illustrated that the minimum duration constraints propagate along the shared path of these two flows. Thus, the introduction of minimum duration constraints in the worst-case delay analysis benefit not only the delay computation at the source node but also the delay computation along the whole path.

We proposed two approaches, the Network Calculus approach and the Trajectory approach, to implement the integration of minimum duration constraints in Chapter 2 and Chapter 3. showed that compared to the classical approaches the modified approaches improve significantly the network performance with respect of end-to-end delay upper bounds (49% on average for the Network Calculus approach and 50% on average for the Trajectory approach). Moreover, for a scenario with only less than half of flows with offset constraints, the two modified approaches improved the delay upper bounds by about 17%. Hence, it is important to take into account the offset constraints in the worst-case delay analysis even partially. Since the importance of offset constraints was highlighted, we tried to find out the best offset assignment algorithm leading to the minimum computed end-to-end delay upper bounds for the industrial AFDX configuration (Chapter 4). Several offset assignment algorithms, including existing ones and the ones considering the avionics characteristics, have been evaluated by upper bounding the gap of each assignment and an optimal scenario. It has been demonstrated that heuristics that assign offsets to flows pair by pair are not efficient when applied to the industrial AFDX configuration due to the limited different values of period. A simple algorithm first designed for automotive networks turned out to be a near optimal algorithm. It has also been shown that although the proposed algorithms considering the avionics characteristics slightly outperform the simple algorithm, they increase the computation complexity.

The fifth chapter has investigated the pessimism analysis. The proposed worst-case delay analysis introduce pessimistic computation in order to guarantee the deterministic communication. In order to measure the maximum potential introduced pessimism, an analytical pessimism analysis was developed based on the Trajectory approach. Each possible part of the Trajectory approach computation leading to pessimistic results was analyzed. Then an underestimation of worst-case delay was derived. The maximum difference between the underestimation (lower bound) and the overestimation (upper bound) of end-to-end delay gives a metric of the maximum potential pessimism. This pessimism analysis has been further developed with the integration of offset constraints. It has been applied to the industrial AFDX configuration. The results have showed that there are on average of about 12% introduced pessimism of the computed delay upper bounds for the classical Trajectory approach and of about 14% introduced pessimism for the modified Trajectory approach. Therefore, since the exact worst-case delay upper bounds cannot be calculated for an industrial configuration, the approaches proposed in Chapter 2 and Chapter 3, although introduce some pessimism, are efficient to evaluate the network performance for an industrial configuration.

The last chapter presented a real-time heterogeneous network where a switched Ethernet backbone interconnects several CAN buses via bridges. Such a heterogeneous architecture can serve as the future real-time industrial network. For the purpose of certification, two approaches for worst-case delay analysis have been proposed. The first presented approach is based on a component-based approach which allows each component analyzed independently with a local scheduling policy and therefore deals with heterogeneity properties at component level. The second introduced approach is an adapted Trajectory approach which integrates heterogeneity properties in the computation by unifying the properties along the considered path. The results have showed on a middle scale heterogeneous network case study that the adapted Trajectory approach provides tighter end-to-end delay upper bounds than the component-based approach.

Therefore, a heterogeneous network can be used for real-time industrial applications since its worst-case delay upper bounds can be determined by adapted approaches.

Some perspectives are illustrated as follows.

Fixed priority policy ensures that at any given time, the processor executes the highest priority task of all those tasks that are currently ready to execute. Since the static priority demands added cost and more complicated implementation, many standard switched Ethernet network components only support the FIFO scheduling. Nowadays some real-time applications require guaranteeing the communication of a set of critical flows. For example, an avionics network transmits both avionics flows (higher priority) and non-avionics flows (lower priority), and it needs a worst-case delay analysis for the avionics flows. Such a work has been done in [START_REF]Applying Trajectory approach with static priority queuing for improving the use of available AFDX resources[END_REF]. However, it does not consider the offset constraints. Future work can focus on the integration of fixed priority policy in the approaches proposed in Chapter 2 and Chapter 3 of this thesis in order to provide worst-case delay upper bounds needed for a real-time switched

Ethernet network with offset constraints.

The maximum potential pessimism features a gap from an exact worst-case delay to an overestimated delay (delay upper bound). However, there is no method to obtain an exact worst-case delay for a large scale network. The pessimism analysis presented in Chapter 5 provides a metric to calculate the upper bound of the maximum potential pessimism by measuring the gap from an underestimated worst-case delay, which is smaller than the exact worst-case delay, to an overestimated delay. Therefore, in order to obtain an evaluation on the maximum pessimism, future work focuses on tightening the gap from the underestimation to the upper bound of worst-case delay.

As a future research direction, the heterogeneous network has been introduced and analyzed in Chapter 6. In this work, only CAN buses with non-preemptive FP scheduling are considered.

Other types of field buses, e.g., CAN buses with TDMA scheduling, can be candidates for a heterogeneous network and therefore the corresponding worst-case delay analysis needs to be developed. Moreover, only a middle scale network was evaluated as a case study in this work.

It needs to evaluate more complex large scale industrial networks in future work.

This thesis therefore leaves room for a wide and promising field of research, since the realtime switched Ethernet plays an increasingly important role in the industrial domain. The Network Calculus brings three bounds for lossless networks with service guarantees.

First, the backlog is bounded by the vertical deviation between the arrival and service curves.

A.3 Integration of frame serialization

Flows send frames to a node through different input links. Frames transmitted from different input links can arrive at the output port h at the same time, but they share the same output link and they are transmitted one by one through the output link. It means that they cannot be transmitted at the same time on this link, and it is called that they are serialized. This constraint is considered by Jérôme Grieu [START_REF] Grieu | Analyse et évaluation de techniques de commutation Ethernet pour interconnexion des systèmes avioniques[END_REF].

We illustrate the frame serialization in Figure A.4. There are two input links: IP h 0 transmits a frame f 1 of flow τ 1 to the output port h; and IP h 1 transmits a frame f 2 of flow τ 2 to the output port h. At the output port h, f 1 and f 2 can arrive at the same time a h f 1 = a h f 2 . Then they are serialized at the output port h, which means that they are transmitted by the output link OP h of h one by one. Therefore, they arrive at the following output port h + 1 one after one, which means that they cannot arrive at h + 1 at the same time as illustrated in This arrival curve provides a tighter constraint on input flows, and therefore reducing pessimism of the computed results on worst-case delay.

studied frame f i if they arrive no earlier than M 2 i and no later than a 2 f i . These frames are transmitted before f i and contribute to the busy period bp 2 . This process propagates till the last visited node 4, and the end-to-end delay of f i is marked as shadow bars in Figure B.1. The computation of this delay by the Trajectory approach is explained in the following paragraphs.

Since any frame of a competing flow τ j arriving at the node f irst j,i no earlier than time M f irst i,j i and no later than time a f irst j,i f i can delay f i due to the FIFO scheduling, the maximum waiting delay generated by τ j is obtained by considering maximum frames arriving during a maximized time interval M f irst j,i i , a f irst j,i f i . In order to maximize the length of the busy period, it needs to minimize the value of M h i and maximized the value of a f irst j,i f i .

It has been shown in [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF] that a minimized M h i is achieved by the sum of the transmission time of the smallest frame at each visited node before arriving at node h plus the smallest link cost L min of each crossed link. Therefore M h i is given by:

M h i = h-1 h =f irst i ( min j∈ 1,n f irst j,i =f irst i,j (C h j ) + L min )
where h -1 means the previous node of h along path P i . Then M

f irst i,j i
is the earliest possible starting instant of the busy period bp f irst j,i .

Since S f irst j,i max i is the maximum delay of frame f i generated from its source node to node f irst j,i , the upper bound a f irst j,i f i is maximized by t + S f irst j,i max i , which is the latest possible arrival time of f i at the node f irst j,i .

Therefore, the length of the interval M f irst i,j i , t + S f irst j,i max i is maximized, which is illustrated in Figure B.2 as the shadow bar. As long as the frames of τ j arrive at the node f irst j,i during the maximized interval, they could delay f i .

With the maximized interval M f irst i,j i , t + S f irst j,i max i , it needs to maximize the number of frames of flow τ j which can arrive during this interval. Since the flow model of τ j is known at its source node f irst j , it needs to maximize a workload interval at f irst j . The transmission of a frame of flow τ j from its source node f irst j to the node f irst j,i requires time of at least S f irst j,i min j and at most S f irst j,i max j , then the earliest generation time of a frame of flow τ j at its source node is M f irst i,j i -S f irst j,i max j -J j and the latest generation time is t + S f irst j,i max i -S f irst j,i min j (Figure B.2). This workload interval from the earliest generation time to the latest generation time decides the maximized number of frames which could delay f i at the node f irst j,i , and it is represented by t + A i,j where: With this workload interval, the maximum delay generated by a competing flow τ j can be determined. Due to the FIFO scheduling, a frame can delay the studied frame f i only once. Then its transmission is computed only once. Thus, the waiting delay caused by all the competing flows is maximized by: j∈ 1,n P j ∩P i =∅

(1 + t + A i,j T j ) + • C slow j,i j

In order to ensure the maximum delay, C slow j,i j is considered in the computation since it is the largest transmission time of a frame of τ j along the path P i .

When j = i, it means that frame f i could be delayed by other frames from the same flow τ i if these frames are pending in the output port buffer when f i arrives at the output port. In that case, A i,i = J i and C

slow i,i i = C slow i i .
Besides the delay caused by the competing flows, there are other factors contributing to the end-to-end delay.

According to [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF], the frame f (h + 1) is counted twice as the transition cost from one busy period to the next one (frames f 2 , f 3 and f 4 with shadow blocks in Figure B.1). In order to guarantee the end-to-end delay upper bound, the largest frame of each busy period bp h (except the slow i ) is considered in the computation. Thus, this delay can be computed by: Then the worst-case end-to-end delay upper bound of the flow τ i is obtained by: R i = max

h∈P i /
-J i +B slow i ≥t≥-J i {W last i i,t + C last i i -t} (B.2)
where

B slow i = j∈ 1,n B slow i T j • C slow j,i j
. It is proved by Property 2 and Lemma 3 in [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF] and it limits the range of computation.

B.2 Application on a switched Ethernet network

The Trajectory approach has been applied to and optimized for the switched Ethernet in A link of a switched Ethernet connects an input port and an output port and works in mode full duplex. Therefore, we have:

f irst i,j = f irst j,i , last i,j = last j,i

All the links of the considered switched Ethernet are with the same bandwidth (transmission rate) 100 M bit/s. Therefore there is no slowest node for flows, and we take:

slow i = last i , C h i = C i if h ∈ P i
Therefore, for a frame f i of a flow τ i in a switched Ethernet network, the latest starting time W last i i,t of frame f i at its last visited output port last i is computed: ) is the smallest one of seq h 0 , then the largest minimized l h k (k ∈ 1, k h ) is l h 2 . Therefore ∆ h i,t is given by: ∆ h i,t = l h 2 -l h 0 Therefore, for a frame f i of a flow τ i in a switched Ethernet network, the latest starting time W last i i,t of frame f i at its last visited output port last i is computed by:

1. 1

 1 Example of the network architecture . . . . . . . . . . . . . . . . . . . . . . . . 1.2 An illustration of a static flow path P i,j . . . . . . . . . . . . . . . . . . . . . . 1.3 Example of mapping flows on the network architecture . . . . . . . . . . . . . . 1.4 Temporal characteristics of a sporadic flow and a periodic flow . . . . . . . . . 1.5 Illustration of end-to-end delay of flow τ 1 . . . . . . . . . . . . . . . . . . . . . 1.6 Illustration of minimum end-to-end delay of flow τ 1 . . . . . . . . . . . . . . . . 1.7 Illustration of end-to-end delay of flow τ 1 on a possible scenario . . . . . . . . . 1.8 The end-to-end delay characteristics . . . . . . . . . . . . . . . . . . . . . . . . 1.9 A reference network example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.10 Minimum durations between τ 1 and τ 2 at the output port of N 1 . . . . . . . . . 1.11 Minimum duration between τ 1 and τ 2 at the output port of N 1 with release jitters 1.12 Propagation of the Minimum Duration . . . . . . . . . . . . . . . . . . . . . . . 1.13 Temporal durations from between a frame arrival of τ 1 and a frame arrival of τ 2 1.14 General case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.15 One possible scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Recall of the network example for the Network Calculus approach . . . . . . . 2.2 The arrival curves of flows τ 1 and τ 2 at N 1 . . . . . . . . . . . . . . . . . . . . . 2.3 The maximum delay generated at the output port of N 1 . . . . . . . . . . . . . 2.4 Propagation of the arrival curve . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 The arrival curves of flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Serialization of α S 1 1 and α S 1 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Serialization of α S 1 3 and α S 1 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Illustration of the burst workload at N 1 . . . . . . . . . . . . . . . . . . . . . . 2.9 The arrival curves of α h i and α h j . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Sum arrival curves of G x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 The Safe Arrival Curve of subset G x . . . . . . . . . . . . . . . . . . . . . . . . 2.12 The arrival curves of flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.13 Maximum delay generated at S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 2.14 Worst-case delay of τ 1 with the classical Network Calculus approach . . . . . . 2.15 Sum arrival curves of G 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.16 The Safe Arrival Curve of subset G 1 . . . . . . . . . . . . . . . . . . . . . . . . 2.17 The overall arrival curve α S 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.18 Comparison with the classical Network Calculus approach . . . . . . . . . . . . 2.19 Illustration on the output port of S 2 . . . . . . . . . . . . . . . . . . . . . . . . 2.20 The illustration on R 1 computed by the modified Network Calculus approach . 3.1 Recall of the network example for the Trajectory approach . . . . . . . . . . . .LIST OF FIGURES 3.2 Worst-case scenario corresponding to the classical Trajectory approach . . . . . 3.3 Illustration of the interval at f irst j,i . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Illustration of the interval at f irst j . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Illustration of the workload intervals of τ 3 . . . . . . . . . . . . . . . . . . . . . 3.6 Illustration of the computation of R 1 . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Illustration of the workload intervals of τ 3 and τ 4 . . . . . . . . . . . . . . . . . 3.8 An illustrative example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Illustration of the workload intervals A i,j and A i,k . . . . . . . . . . . . . . . . 3.10 Illustration of the constrained workload intervals A i,j,k . . . . . . . . . . . . . . 3.11 Illustration of the constrained workload intervals A i,k,j . . . . . . . . . . . . . . 3.12 Illustration of a possible scenario of workload interval . . . . . . . . . . . . . . 3.13 Illustration of the frame shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 Classical approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Modified approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.16 Illustration on maximum workload curve RS 1,t,2 . . . . . . . . . . . . . . . . . 3.17 Illustration on maximum workload curve RS 1,t,1 . . . . . . . . . . . . . . . . . 3.18 Illustration on maximum workload curve RS 1,t,3 . . . . . . . . . . . . . . . . . 3.19 Worst-case scenario corresponding to the modified Trajectory approach . . .. 4.1 An illustrative industrial AFDX network architecture . . . . . . . . . . . . . . . 4.2 Improvement of the modified Network Calculus approach . . . . . . . . . . . . 4.3 Improvement of the modified Network Calculus approach with partial dependencies 4.4 Improvement of dependent flows of the modified Network Calculus . . . . . . . 4.5 Improvement of independent flows of the modified Network Calculus . . . . . . 4.6 Improvement of the modified Trajectory approach . . . . . . . . . . . . . . . . 4.7 Improvement of the modified Trajectory approach with partial dependent flows 4.8 Improvement of dependent flows based on the Trajectory approach . . . . . . . 4.9 Improvement of independent flows based on the Trajectory approach . . . . . . 4.10 Comparative results of two approaches . . . . . . . . . . . . . . . . . . . . . . . 4.11 A sample AFDX network of Example 1 . . . . . . . . . . . . . . . . . . . . . . 4.12 Scenarios of the VL v 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.13 A small example of AFDX network of Example 2 . . . . . . . . . . . . . . . . . 4.14 Illustration of the SingleAssign with low workload . . . . . . . . . . . . . . . . 4.15 Illustration of SingleAssign with increased workload . . . . . . . . . . . . . . . 4.16 Illustration of MostLoadSA with high workload . . . . . . . . . . . . . . . . . . 4.17 A small example of AFDX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.18 Comparison of GCD and SingleAssign . . . . . . . . . . . . . . . . . . . . . . . 4.19 Comparative results of IdealAssign, SingleAssign and MostLoadSA . . . . . . . 5.1 Example 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Worst-case scenario for τ 1 of the Example 3 . . . . . . . . . . . . . . . . . . . . 5.3 Illustration on minimum inter-arrival time between two frames of the same flow 5.4 Example 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Worst-case scenario for τ 1 of the Example 4 . . . . . . . . . . . . . . . . . . . . 5.6 Sample network of Example 5, 6, 7 . . . . . . . . . . . . . . . . . . . . . . . . . 5.7 Worst-case scenario for τ 1 of the Example 5 . . . . . . . . . . . . . . . . . . . . 5.8 Worst-case scenario for τ 1 of the Example 6 . . . . . . . . . . . . . . . . . . . . 5.9 Illustration of ∆ S 1 1,t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Worst-case scenario for τ 1 of the Example 7 . . . . . . . . . . . . . . . . . . . . 5.11 Illustration of Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.12 Illustration of seq h 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.13 Illustration of a reachable seq h 0 : Case 1 . . . . . . . . . . . . . . . . . . . . . . . 5.14 Illustration of a reachable seq h 0 : Case 2 . . . . . . . . . . . . . . . . . . . . . . . 5.15 Illustration of a reachable delay of τ 1 . . . . . . . . . . . . . . . . . . . . . . . . 5.16 Example 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.17 Illustration on minimum duration M D N 5 5,6 . . . . . . . . . . . . . . . . . . . . . 5.18 Worst case scenario for τ 1 in Example 8 . . . . . . . . . . . . . . . . . . . . . . 5.19 Example 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.20 Worst case scenario for τ 1 in Example 9 . . . . . . . . . . . . . . . . . . . . . . 5.21 Upper bounded pessimism of the Network Calculus approach . . . . . . . . . . 5.22 Upper bounded pessimism of the Trajectory approach . . . . . . . . . . . . . . 6.1 Heterogeneous network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Heterogeneous path for τ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Hierarchical scheduling framework . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Compositional scheduling framework on an example . . . . . . . . . . . . . . . 6.5 Component-based approach for heterogeneous networks . . . . . . . . . . . . . 6.6 Component and interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Illustration of the component-based approach for flow τ 2 . . . . . . . . . . . . . 6.8 Interval of flow with higher priority . . . . . . . . . . . . . . . . . . . . . . . . . 6.9 Illustration of heterogeneous scheduling policies integration . . . . . . . . . . . 6.10 Heterogeneous network example . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.11 Worst-case ETE delay of pure Ethernet flows . . . . . . . . . . . . . . . . . . . 6.12 Worst-case ETE delay of pure CAN flows . . . . . . . . . . . . . . . . . . . . . 6.13 Worst-case ETE delay of remote CAN flows . . . . . . . . . . . . . . . . . . . . 6.14 Worst-case ETE delay of remote CAN flows according to the path . . . . . . . 6.15 Example network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.16 Illustration on τ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.17 Worst-case ETE delay of remote CAN flows with the improved Trajectory approach153 6.18 Worst-case ETE delay of remote CAN flows of CAN 1 to CAN 3 and CAN 1 to CAN 4 with the improved Trajectory approach . . . . . . . . . . . . . . . . . . A.1 Illustration of Network Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Propagation of Network Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Illustration of Network Calculus applied to real-time switched Ethernet . . . . A.4 Illustration on frame serialization . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 The aggregated flow of one input link IP h k considering the frame serialization . B.1 Illustration of busy period . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Illustration of the workload interval A i,j . . . . . . . . . . . . . . . . . . . . . . B.3 An switched Ethernet network illustration . . . . . . . . . . . . . . . . . . . . . B.4 The transmission process of frame f 1 of flow τ 1 . . . . . . . . . . . . . . . . . . B.5 Illustration on a node h with an output link OP h and k h + 1 input link IP h k . . B.6 Illustration on term ∆ h i,t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .List of Tables1.1 Flow parameters of the reference network example . . . . . . . . . . . . . . . . 1.2 Flow parameters of the reference network example with release jitters . . . . . 1.3 All the possible values of M D N 1 1,2 (k, l) . . . . . . . . . . . . . . . . . . . . . . . . 1.4 All the possible values of M D N 1 2,1 (k, l) . . . . . . . . . . . . . . . . . . . . . . . . 1.5 minimum durations of flows τ 1 , τ 2 , τ 3 and τ 2 . . . . . . . . . . . . . . . . . . . . 2.1 Recall of flow parameters of the network example for the Network Calculus approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 End-to-end delay upper bounds of the reference example . . . . . . . . . . . . . 3.1 Recall of flow parameters of the network example for the Trajectory approach .3.2 Minimum durations of flows τ 1 , τ 2 , τ 3 and τ 4 at their source nodes . . . . . . . 3.3 End-to-end delay upper bounds of the reference example . . . . . . . . . . . . . 4.1 BAGs and frame lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 VL paths lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 The example of offset assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Improvement on burst workload at output ports of ESs and switches . . . . . . 4.5 The Configuration of flows of Example 1 . . . . . . . . . . . . . . . . . . . . . . 4.6 The Configuration of flows of Example 2 . . . . . . . . . . . . . . . . . . . . . . 4.7 The assigned offsets based on different offset assignments . . . . . . . . . . . . 4.8 Statistic reduction on end-to-end delay upper bounds for each offset algorithm 5.1 Number and percentage of paths with exact worst-case delays . . . . . . . . . . 6.1 Flows in the example in Figure 6.1 . . . . . . . . . . . . . . . . . . . . . . . . .

Contents 1 . 1

 11 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Context of real-time Ethernet . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Real-time Ethernet solutions . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Real-time switched Ethernet network . . . . . . . . . . . . . . . . . 10 1.3.1 Network model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Flow model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 A real-time switched Ethernet example: AFDX network . . . . . . . . 1.4 End-to-end delay analysis on a real-time switched Ethernet . . . . 13 1.4.1 End-to-end delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Minimum end-to-end delay . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Maximum end-to-end delay . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Existing approaches for worst-case delay analysis . . . . . . . . . . 19 1.5.1 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2 Model-checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 Network Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.4 Trajectory approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Temporal constraints of dependent flows . . . . . . . . . . . . . . . 22 1.6.1 Minimum duration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.2 Computation of minimum duration . . . . . . . . . . . . . . . . . . . . 1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.1 Introduction During the last three decades, fieldbus technologies have been successively developed and widely used in industrial control system. For instance, technologies such as PROFIBUS [TV99] and WorldFIP [Wor] have been popular in the context of automation while CAN [CAN] is a de facto standard for automotive embedded systems and the ARINC 429 [ACC04] has been developed for avionics systems. These fieldbuses interconnect sensors, actuators and controllers in wide range of applications and support the deterministic industrial communications by ensuring Chapter 1 -Worst-case delay analysis of switched Ethernet networks bounded end-to-end (ETE) communication delays of messages. The guarantees on the end-toend delays are achieved either by the nature of the fieldbus(e.g. ARINC 429 is a mono-emitter bus) or by a worst-case analysis such as the one which has been developed for CAN [TB94, THW94, TBW95b, NS98, HNNP02, DBBL07].

  The switched Ethernet network has been chosen as a solution to some real-time applications, like the Avionics Full-DupleX switched Ethernet (AFDX) network [ACC08]. Such a technology considers a full-duplex switched Ethernet without a global clock. It uses statically defined routing and an upper bounded switching latency in each switch in order to ensure the realtime requirement. The flows emitted at each source node are shaped in order to guarantee the real-time characteristic. The network model and flow model are presented in the following paragraphs.

Figure 1

 1 Figure 1.1: Example of the network architecture

Figure 1

 1 Figure 1.2: An illustration of a static flow path P i,j

Figure 1 . 3 :

 13 Figure 1.3: Example of mapping flows on the network architecture

Figure 1 . 4 :

 14 Figure 1.4: Temporal characteristics of a sporadic flow and a periodic flow

Figure 1 .

 1 Figure 1.5 depicts one possible scenario leading to one possible value of the end-to-end delay. The following paragraphs characterize the minimum and the maximum values of this end-to-end delay.

Figure 1 . 5 :

 15 Figure 1.5: Illustration of end-to-end delay of flow τ 1

Figure 1 . 6 :Figure 1 . 7 :

 1617 Figure 1.6: Illustration of minimum end-to-end delay of flow τ 1

Figure 1

 1 Figure 1.8: The end-to-end delay characteristics

Figure 1

 1 Figure 1.10: Minimum durations between τ 1 and τ 2 at the output port of N 1

Figure 1

 1 Figure 1.11: Minimum duration between τ 1 and τ 2 at the output port of N 1 with release jitters

Figure 1

 1 Figure 1.12: Propagation of the Minimum Duration

Figure 1

 1 Figure 1.13: Temporal durations from between a frame arrival of τ 1 and a frame arrival of τ 2

Chapter 1 -Figure 1

 11 Figure 1.15: One possible scenario

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Classical Network Calculus approach . . . . . . . . . . . . . . . . . 32 2.2.1 Arrival curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Service curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Delay computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Frame serialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.5 Limitation of the approach . . . . . . . . . . . . . . . . . . . . . . . . 2.3 A modified approach considering minimum duration constraints . 36 2.3.1 General idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Computation overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Computation of the arrival curve of dependent flows . . . . . . . . . . 2.4 Application on a small network example . . . . . . . . . . . . . . . 41 2.4.1 Classical Network Calculus approach . . . . . . . . . . . . . . . . . . . 2.4.2 Modified Network Calculus approach . . . . . . . . . . . . . . . . . . . 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Figure 2 . 1 :

 21 Figure 2.1: Recall of the network example for the Network Calculus approach

Figure 2

 2 Figure 2.2: The arrival curves of flows τ 1 and τ 2 at N 1

FigureFigure 2 . 3 :

 23 Figure 2.3: The maximum delay generated at the output port of N 1

Figure 2 . 4 :

 24 Figure 2.4: Propagation of the arrival curve

Figure 2 . 5 :

 25 Figure 2.5: The arrival curves of flows

FigureFigure 2 . 7 :

 27 Figure 2.6: Serialization of α S 1 1 and α S 1 2

4

 4

FigureFigure 2 . 8 :

 28 Figure 2.8: Illustration of the burst workload at N 1

Figure 2 Figure 2

 22 Figure 2.9: The arrival curves of α h i and α h j

α 4 Figure 2

 42 Figure 2.12: The arrival curves of flows

Figure 2 Figure 2

 22 Figure 2.13: Maximum delay generated at S 1

Figure 2 .

 2 Figure 2.15: Sum arrival curves of G 1

Figure 2 .

 2 Figure 2.16: The Safe Arrival Curve of subset G 1

46Chapter 2 -Figure 2 Figure 2

 222 Figure 2.17: The overall arrival curve α S 1

Figure 2 Figure 2

 22 Figure 2.19: Illustration on the output port of S 2

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2 Classical Trajectory approach . . . . . . . . . . . . . . . . . . . . . . 52 3.3 A modified approach considering minimum duration constraints . 58 3.3.1 General idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.2 Computation overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.3.3 Computation of the maximum workload of dependent flows . . . . . . 59 3.4 Illustration on a small network example . . . . . . . . . . . . . . . . 65 3.4.1 Classical Trajectory approach . . . . . . . . . . . . . . . . . . . . . . . 65 3.4.2 Modified Trajectory approach . . . . . . . . . . . . . . . . . . . . . . . 66 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

Figure 3 . 1 :

 31 Figure 3.1: Recall of the network example for the Trajectory approach

Figure 3

 3 Figure 3.2: Worst-case scenario corresponding to the classical Trajectory approach

Figure 3

 3 Figure 3.3: Illustration of the interval at f irst j,i

Figure 3 . 4 :

 34 Figure 3.4: Illustration of the interval at f irst j

Figure 3

 3 Figure 3.5: Illustration of the workload intervals of τ 3

Figure 3

 3 Figure 3.6: Illustration of the computation of R 1

Figure 3

 3 Figure 3.7: Illustration of the workload intervals of τ 3 and τ 4

Figure 3

 3 Figure 3.8: An illustrative example

Figure 3

 3 Figure 3.9: Illustration of the workload intervals A i,j and A i,k

Figure 3 Figure 3

 33 Figure 3.10: Illustration of the constrained workload intervals A i,j,k

,Figure 3

 3 Figure 3.12: Illustration of a possible scenario of workload interval

Figure 3

 3 Figure 3.13: Illustration of the frame shift

  Figure 3.14: Classical approach

Figure 3

 3 Figure 3.16: Illustration on maximum workload curve RS 1,t,2

Figure 3

 3 Figure3.17: Illustration on maximum workload curve RS 1,t,1

Figure 3

 3 Figure 3.18: Illustration on maximum workload curve RS 1,t,3

Figure 3

 3 Figure 3.19: Worst-case scenario corresponding to the modified Trajectory approach

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.2 AFDX context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.3 Example of an offset assignment algorithm . . . . . . . . . . . . . . 74 4.4 Worst-case delay analysis based on the modified Network Calculus approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.5 Worst-case delay analysis based on the modified Trajectory approach 78 4.6 A comparison of the two modified approaches . . . . . . . . . . . . 81 4.7 Near-optimal offset assignment for the industrial AFDX network 82 4.7.1 Existing offset assignments . . . . . . . . . . . . . . . . . . . . . . . . 83 4.7.2 Optimal scenario of dependent flows over the AFDX network . . . . . 84 4.7.3 Offset assignment algorithms in the context of AFDX network . . . . 86 4.7.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

emitted at N 1

 1 with periods of 4 ms, 8 ms, 16 ms, 16 ms respectively are sorted by increasing periods and T max = 16 ms. τ 1 is assigned with offset O 1 = 0 which means R[1] = f 1,1 . According to step 3, R[3] = f 1,2 , R[5] = f 1,3 and R[7] = f 1,4 . Then for τ 2 , B 2 = 2 and E 2 = 3 (step 1), thus r 2 = 2. The array R is updated with R[2] = f 2,1 and R[6] = f 2,2 (step 3). The same process is done for τ 3 and τ 4 . The R array is listed in

Figure 4 .

 4 2, whereClassicalN C refers to the classical Network Calculus approach, and M odif iedN C refers to the modified Network Calculus approach. The VL paths in Figure4.2 are sorted by increasing values of their corresponding normalized N cp x .

Figure 4 . 2 :

 42 Figure 4.2: Improvement of the modified Network Calculus approach

  Figure 4.3 where VL paths are sorted by increasing values of their corresponding normalized N cp x .

Figure 4 . 3 :Figure 4 . 4 :Figure 4 . 5 :

 434445 Figure 4.3: Improvement of the modified Network Calculus approach with partial dependencies

  .1 is used for the purpose of comparison. The results of the comparisons are shown in Figure 4.6, where ClassicalT raj refers to the classical Trajectory approach, and M odif iedT raj refers to the modified Trajectory approach. The VL paths in Figure 4.6 are sorted by increasing values of their corresponding normalized values N cp x .

Figure 4 . 6 :

 46 Figure 4.6: Improvement of the modified Trajectory approach

Figure 4 . 7 :

 47 Figure 4.7: Improvement of the modified Trajectory approach with partial dependent flows

Figure 4

 4 Figure 4.8: Improvement of dependent flows based on the Trajectory approach

Figure 4 . 9 :

 49 Figure 4.9: Improvement of independent flows based on the Trajectory approach

Figure 4 .

 4 Figure 4.10: Comparative results of two approaches

Figure 4 .

 4 Figure 4.12: Scenarios of the VL v 1

  200 µs, O 2 = 100 µsThis case is shown for the chronogram of e 1 in Figure4.14. Similar case at the end system e 2 is depicted for the chronogram of e 2 in Figure4.14. We focus on v 2 whose first frame f 2 is released at O 2 = 100 µs. At the output port of the switch S 1 that v 2 visits, v 4 and v 5 from e 2 join the path of v 2 while v 3 has left. Then one possible scenario at this output port is depicted for the chronogram of S 1 in Figure4.14. It can be seen that when the frames f 1 and f 2 arrive at S 1 , they are still separated long enough to avoid delaying each other. Similarly, the frames f 4 and f 5 from v 4 and v 5 are separated long enough when they arrive at S 1 , consequently only one frame f 5 delays the studied frame f 2 . Since the frame f 2 is released at e 1 at time O 2 = 100 µs and the transmission of frame f 2 is finished at the switch S 1 at time 280 µs, the end-to-end delay (shadow block in Figure 4.14) of the frame f 2 is: R 2 = 280 -100 = 180 µs

Figure 4 .

 4 Figure 4.14: Illustration of the SingleAssign with low workload

Figure 4 .

 4 Figure 4.15: Illustration of SingleAssign with increased workload

  which visit the most loaded port of S 1 , then go on with v 3 , leading to the offsets: O 1 = 0 µs, O 2 = 200 µs and O 3 = 100 µs. This case is illustrated in part e 1 in Figure 4.16. Similar case for the VLs emitted by e 2 is shown for e 2 in Figure 4.16. Then one possible scenario for the frame f 2 at S 1 is identified for S 1 in Figure 4.16, indicating that the delay of this frame is: R 2 = 380 -200 = 180 µs It is smaller than the one obtained by SingleAssign (200 µs). The reason is that at the most loaded output port of S 1 the workload is further evenly distributed to reduce the waiting time in the buffer.

Figure 4 .

 4 Figure 4.16: Illustration of MostLoadSA with high workload

Figure 4

 4 Figure 4.17: A small example of AFDX

Figure 4 .

 4 Figure 4.18: Comparison of GCD and SingleAssign

PFigure 4 .

 4 Figure 4.19: Comparative results of IdealAssign, SingleAssign and MostLoadSA

  Term 5.3 gives a tight delay upper bound since the path length |P i | and the switching latency sl are both constant. Term 5.5 is constant because C i is the transmission time of the considered frame f i . However, Term 5.1, Term 5.2 and Term 5.4 could introduce pessimism in the computation.

  Figure 5.1: Example 3

Figure 5

 5 Figure 5.2: Worst-case scenario for τ 1 of the Example 3

Figure 5 . 3 :

 53 Figure 5.3: Illustration on minimum inter-arrival time between two frames of the same flow

Figure 5. 4 . 4

 44 Figure 5.4.

Figure 5 Figure 5

 55 Figure 5.5. However, since frames f 2 , ..., f 10 have left the path P 1 when frame f 1 arrives at the node S 1 , only frame f 12 arriving at t+S S 1 max 1 = 110 µs can delay frame f 1 , resulting in the delay of flow τ 1 equal to 130 µs (Figure 5.5) which is 10 µs less than the computed delay 140 µs. This 10 µs is exactly the transmission time of frame f 12 which actually does not delay frame f 1 . It indicates that the computation considering two frames of flow τ 12 introduces pessimism. For both Example 3 and Example 4, the results of ETE delay computation for the flow τ i are 140 µs, which is reachable in Example 3 but pessimistic in Example 4. The reason of the introduced pessimism is the idle time between the time M S 11 and the time t + S S 1 max 1 due to the workload that has left the considered path at the output port of S 1 in Example 4. This idle time results in the immediate transmission of frame f 12 just after its arrival at S 1 without

0 .Figure 5

 05 Figure 5.6: Sample network of Example 5, 6, 7

Figure 5 Example 6

 56 Figure 5.7: Worst-case scenario for τ 1 of the Example 5

Figure 5

 5 Figure 5.8: Worst-case scenario for τ 1 of the Example 6

Example 7

 7 11) Details can be found in Appendix B.3. The serialization effect is illustrated using the Example 7 which has the network architecture shown in Figure 5.6. This example has the network architecture shown in Figure 5.6. The parameters of the flows are as follows: C 1 = C 2 = 100 µs, C 3 = C 4 = 40 µs T 1 = T 2 = T 3 = T 4 = 8000 µs, J 1 = J 2 = J 3 = J 4 = 0. The network supports FIFO scheduling and works at R = 100 M bit/s. The switching latency is sl = 0. Compared to Example 6, the transmission times of flows τ 3 and τ 4 are reduced to 40 µs.

Figure 5

 5 Figure 5.10: Worst-case scenario for τ 1 of the Example 7

  40 µs Then ETE delay upper bound of the flow τ 1 is 320 -40 = 280 µs as shown in Figure 5.10. Comparing Example 7 with Example 6, frame f 2 is a part of seq S 1 0 in Example 6 in Figure 5.8, while it does not belong to seq S 1 0 in Example 7 in Figure 5.10. The pessimistic estimation in Example 7 is due to the idle time at the output port of S 1 which separates f 2 from the frame sequence seq S 1 0 .

Figure 5

 5 Figure 5.11: Illustration of Lemma 2

Figure 5

 5 Figure 5.12: Illustration of seq h 0

Figure 5

 5 Figure 5.14: Illustration of a reachable seq h 0 : Case 2

For example, flow τ 1

 1 and flow τ 2 are emitted by the same source node. They are periodic with periods T 1 = T 2 = 4000 µs. The frame transmission times are C 1 = C 2 = 40 µs and the release jitters are null. Flow τ 1 has an offset O 1 = 0 and flow τ 2 has an offset O 2 = 1000 µs.

Figure 5

 5 Figure 5.15: Illustration of a reachable delay of τ 1

Consider a frame f 1 Example 8 Figure 5 Figure 5

 1855 Figure 5.16: Example 8

Figure 5 .Example 9 Figure 5

 595 Figure 5.19, which is similar to Example 8 in Figure 5.16.

Figure 5

 5 Figure 5.20: Worst case scenario for τ 1 in Example 9

Figure 5

 5 Figure 5.21: Upper bounded pessimism of the Network Calculus approach

Figure 5 .

 5 Figure 5.22: Upper bounded pessimism of the Trajectory approach

Figure 6

 6 Figure 6.1: Heterogeneous network

  Each bridge connects a CAN bus to the Ethernet backbone. In the CAN to Ethernet direction, the bridge has to transform the incoming CAN frames into Ethernet frames. In the Ethernet to CAN direction, the bridge releases CAN frames from the incoming Ethernet frames immediately. The frame encapsulation in the CAN to Ethernet direction and frame decapsulation in the Ethernet to CAN direction are modeled by an upper bounded delay T B .

  output port waits at most for a time duration W D; it is transmitted on Ethernet earlier if there are N B pending CAN frames before W D expires. Then the maximum and minimum waiting time for a remote CAN frame generated in a bridge in the CAN to Ethernet direction are T B + W D and T B , respectively. Remote CAN flows have a maximum frame transmission time after their frames are encapsulated in one Ethernet frame. Considering an Ethernet frame with 18 bytes of frame Header and CRC. encapsulating at most N B CAN frames (at most 135 bits for each). The maximum size of the resulting Ethernet frame is

Figure 6

 6 Figure 6.3: Hierarchical scheduling framework

Figure 6 . 4 :Figure 6 Figure 6 . 6 :,.

 64666 Figure 6.4: Compositional scheduling framework on an example

Figure 6 . 8 :

 68 Figure 6.8: Interval of flow with higher priority

  .1, three heterogeneity characteristics are integrated in the Trajectory approach. First, bridging strategies adopt arbitrary values of N B and W D. Second, links have different bandwidths. Last, output ports have different scheduling policies.

scheduling. While τ 4

 4 has a lower priority than τ 2 and f irst 4,2 = S 1 is with FIFO, then the computation of a pessimistic delay caused by τ 4 considers only FIFO scheduling. τ 2 crosses one bridge output port towards Ethernet (Brdg 1 ) where the bridging strategy is with arbitrary values of N B and W D. Therefore, for τ 2 , n Bout = 1 and shp 2 = {1}, ssp 2 = {2, 3, 4} and slp 2 = {5}.

Figure 6

 6 Figure 6.10: Heterogeneous network example

Figure 6 .

 6 Figure 6.11 shows the worst-case ETE delays of all the pure Ethernet flows. They are sorted by increasing delay values. It can be seen from the figure that the adapted Trajectory approach provides tighter computed delays than the component-based approach.

Figure 6 .

 6 Figure 6.13 presents the worst-case ETE delays of all remote CAN flows sorted by increasing values of their identifiers The reason of the sawtooth shape of the curves is that these remote CAN flows cross the Ethernet backbone where they compete with different other flows along

Figure 6 .

 6 Figure 6.13: Worst-case ETE delay of remote CAN flows

4 2= C CAN 4 3Figure 6

 446 Figure 6.16: Illustration on τ 1

=

  C ET H . Based on the improved approach, we obtainD sp (0, ssp 1 ) = C slow 1 1 + C slow 2,1 2 + C slow 3,1 3 = 30 µs δ 1 (slp 1 ∪ lpb 1 ) = 20 µs R trs (shp 1 ∪ ssp 1 ) = 5 + 5 + 20 = 30 µsTherefore the improved result is R 1 = 80 µs, which is still pessimistic but tighter than previous computed result.

  Figure 6.17: Worst-case ETE delay of remote CAN flows with the improved Trajectory approach

  Figure 6.18: Worst-case ETE delay of remote CAN flows of CAN 1 to CAN 3 and CAN 1 to CAN 4 with the improved Trajectory approach

  The idea was to classify dependent flows in groups and compute the maximum delay generated by each group in stead of by each flow in the group. The computation of maximum delay generated by each group took into account the minimum duration constraints of flows in the group. Both two modified approaches have been illustrated on the same network example and the results have shown great improvement on delay upper bounds (27%) compared to the results of classical approaches. As a real-time switched Ethernet application, the Avionics Full-DupleX switched Ethernet (AFDX) network was introduced in Chapter 4. An industrial AFDX configuration was presented and evaluated by the two modified approaches. The results have

Figure A. 1 :

 1 Figure A.1: Illustration of Network Calculus

For a flow withFigure

  Figure A.2: Propagation of Network Calculus

Figure A. 4 .Figure A. 4 :Figure A. 5 :

 445 Figure A.4. Then any scenario considering that f 1 and f 2 arrive at h + 1 at the same time, i.e. a h+1f 1 = a h+1 f 2 is impossible, and introduces pessimism in the delay computation. Therefore, the frame serialization imposed by physical constraint of link should be taken into account in the worst-case delay analysis.

Figure B. 2 :

 2 Figure B.2: Illustration of the workload interval A i,j

[ BSF09 ,

 BSF09 BSF10]. A real-time switched Ethernet network is composed of a set of source nodes and dest 1 = N 2 . The Trajectory approach considers only the output ports of N 1 , S 1 and S 2 as shown in Figure B.4.Each link considered in the Trajectory approach corresponds to a cross of a switch, and the link cost considered in the Trajectory approach is referred to a switching latency. Since the switching latency of the considered switch model is a constant value sl, then the computation for the switched Ethernet considers:L max = L min = slA flow τ i following a path P i which includes f irst i and dest i crosses |P i | -2 switches. Then the total switching latencies experienced by τ i is:(|P i | -2) • sl Flow τ 1 in Figure B.3 crosses two switches, then it experiences the switching latency twice, as sl shown in Figure B.4.

  Figure B.6: Illustration on term ∆ h i,t

  Gxthe Safe Arrival Curve of a flow set G x at the output port h a h f i the arrival time of a frame f i at the output port h A i,j the workload interval for flow τ j delaying flowτ i A i,j,k the constrained workload interval of τ k to delay τ i β the service curve bp h a busy period at the output port h without idle time during it B i,t the sum from Term 3.3 to Term 3.6 BAG i the Bandwidth Allocation Gap value of VL v i B slow i the computation range for the Trajectory approach Brdg i a brigde connecting a CAN bus and the Ethernet backbone in a heterogeneous network γ r i ,b i the arrival curve of a leaky bucket flow model, where r i is the leak rate and b i is the burst comp x a component in a heterogeneous network which has its own bandwidth and manages its flows based on a local scheduling the minimum delay of flow τ i generated in component comp x of a heterogeneous network D sp i the delay of flow τ i generated by interference flows in sp i δ i

	MostLoad Symbols:	an offset assignment considering the load at output port based on
			PairAssign (see PairAssign)
	MostLoadSA	an offset assignment considering the load at output port based on
			SingleAssign (see SingleAssign)
	Opt		an optimal approach based on the modified Network Calculus approach
	α i	and the modified Trajectory approach the arrival curve of flow τ i
	PairAssign α * the arrival curve of output flow offset assignments of near-optimal offset assignment heuristics
	α h	and GCD (see GCD) the arrival curve of the aggregated flow at the output port h
	PC PE PF α IP h k α h	Purely CAN flows in a heterogeneous network Purely Ethernet flows in a heterogeneous network Periodic Flow the arrival curve of the aggregated flow of input link IP h k
	PROFIBUS	Process Field Bus
	PROFINET	Process Field Network
	QoS		Quality of Service
	AFDX RAGCD ARINC BAG RateAdd CAN CPU RC CRC RMGCD CrossedS RT SAC CrossedSSA an offset assignment considering the number of crossed switches a near-optimal offset assignment heuristic considering the rate sum Avionics Full-DupleX Ethernet and the greatest common divisor of periods of a pair of flows Aeronautical Radio, Incorporated a near-optimal offset assignment heuristic considering the rate sum Bandwidth Allocation Gap of a pair of flows Controller Area Network Remote CAN flows in a heterogeneous network Central Processing Unit a near-optimal offset assignment heuristic considering the maximum Cyclic Redundancy Check rate and the greatest common divisor of periods of a pair of flows an offset assignment considering the number of crossed switches Real Time based on PairAssign (see PairAssign) Safe Arrival Curve SF Sporadic Flow based on SingleAssign (see SingleAssign) CSMA/CD Carrier Sense Multiple Access with Collision Detection ECU Electronic Control Unit EDF Earliest Deadline First EPL Ethernet Powerlink ES End System ETE End-To-End ETH Ethernet network EtherCAT Ethernet for Control Automation Technology FCFS First Come First Served FIFO First In First Out SingleAssign an offset assignment oringinally designed for automotive TCnet C ET H the maximum transmission time of an Ethernet frame encapsulating Time-Critical Control Network TCP CAN frames in a heterogeneous network Transmission Control Protocol C i the frame transmission time of flow τ i TCP/UDP/IP Transmission Control Protocol/User Datagram Protocol/Internet Protocol TDMA Time Division Multiple Access TTE C h i the frame transmission time of τ i on node h C compx i the frame transmission time of flow τ i at the component comp x in a Time-Triggered Ethernet UDP heterogeneous network User Datagram Protocol UTP CAN i A CAN bus Unshielded Twisted Pair VL dest i the destination node of flow τ i Virtual Link VLAN Virtual Local Area Network the delay of flow τ i generated by interference flows in hp i D hp i D compx max i the maximum delay of flow τ i generated in component comp x of a
	FIP	Factory Instrumentation Protocol heterogeneous network
	FP D compx min i		Fixed Priority
	FP/EDF		Fixed Priority/Earliest Deadline First
	FP/FIFO	Fixed Priority/First In First Out
	gcd		greatest common divisor
	GCD		dissimilar offset assignment
	GCDMinus a near-optimal offset assignment heuristic considering the minus value
			of the greatest common divisor of periods of a pair of flows
	lcm		least common multiple
	IdealAssign an ideal offset assignment
	IEEE		Institute of Electrical and Electronics Engineers
	IP		Internet Protocol

  Modified Ethernet approach modifies the Ethernet mechanism and infrastructure for realtime performance. It provides real-time services based on modifications in the hardware of the network infrastructures. This approach demands high synchronization guaran-

	Example solutions are Ethernet
	Powerlink (EPL) [EP], Time-Critical Control Network (TCnet) [Eth04d], Time-Triggered
	Ethernet (TTE) [KAGS05] etc..
	•

teed either by master-slave scheduling or by other synchronization protocols, like IEEE 1588

[START_REF] Eidson | IEEE 1588 standard for a precision clock synchronization protocol for networked measurement and control systems[END_REF]

, in order to guarantee hard real-time requirements. CSMA/CDR

[START_REF] Lann | Real-time communications over broadcast networks: the CSMA-DCR and the DOD-CSMA-CD protocols[END_REF]

, SERCOS [C + 95], EtherCAT

[START_REF] Jansen | Real-time Ethernet: the EtherCAT solution[END_REF][START_REF] Ethernet | Ethernet Control Automation Technology (ETHERCAT): Proposal for a publicly available specification for real-time Ethernet[END_REF]

, PROFINET Isochronous RT (IRT)

[START_REF] Feld | PROFINET-scalable factory communication for all applications[END_REF][START_REF]PROFINET IO: Proposal for a publicly available specification for real-time Ethernet[END_REF]

etc. are proposed solutions.

Table 1 .

 1 5: minimum durations of flows τ 1 , τ 2 , τ 3 and τ 2

	3000

Table 2

 2

	µs)

.1: Recall of flow parameters of the network example for the Network Calculus approach

Table 2

 2

		µs) ModifNC (µs) Reduction (%)
	τ 1	304.53	220.81	27.5
	τ 2	304.53	220.81	27.5
	τ 3	304.53	220.81	27.5
	τ 4	304.53	220.81	27.5
	τ 5	132.50	130.81	1.3

.2: End-to-end delay upper bounds of the reference example

Table 3

 3

	µs)

.1: Recall of flow parameters of the network example for the Trajectory approach Flow τ 1 follows path

Table 3

 3

		µs) ModifTraj (µs) Reduction (%)
	τ 1	300	220	26.7
	τ 2	300	220	26.7
	τ 3	300	220	26.7
	τ 4	300	220	26.7
	τ 5	130	130	0

.3: End-to-end delay upper bounds of the reference example

Table 4 .

 4 .1. It supports FIFO scheduling. dispatching of VLs among BAGs. The right part of Table4.1 gives the dispatching of VLs among the maximum frame length values l max . The majority of VLs uses short frames. 1: BAGs and frame lengths Table4.2 shows the number of VL paths per length (i.e. the number of crossed switches).

	BAG Number	Frame length Number
	(ms)	of VL	(bytes)	of VL
	2	20	0-150	561
	4	40	151-300	202
	8	78	301-600	114
	16	142	601-900	57
	32	229	901-1200	12
	64	220	1201-1500	35
	128	255	> 1500	3
	Nb of crossed switches Number of paths
		1	1797
		2	2787
		3	1537
		4	291

Table 4

 4

.2: VL paths lengths This industrial AFDX network works at 100 M bit/s and the technological latency (switching latency) of an AFDX switch is 16 µs. The overall workload (utilization) of the industrial network is about 10%. Actually, the industrial AFDX network is lightly loaded in order to guarantee that buffers will never overflow. Both sporadic VLs and periodic VLs exist on the AFDX network, and offsets can be assigned to periodic VLs. There is no global clock in an AFDX network. Consequently, frame release times at different end systems are independent.

Table 4

 4

	Time	0	2	4	6	8	10	12	14

.3 from which we can see that O 2 = 2 ms, O 3 = 6 ms and O 4 = 14 ms.

Table 4 .

 4 4: Improvement on burst workload at output ports of ESs and switchesFrom the table, we can see that most end systems have a reduced burst workload of 70%-80% due to the offsets. From the viewpoint of switch output ports, even if the input flows

	at the switch output ports come from different end systems which are not synchronized, the
	reduction on burst workload of most switch output ports is still of about 10%. Therefore
	for such an industrial configuration with the average workload of about 10%, accounting for
	minimum duration constraints can effectively reduce burst workload, and therefore gives tighter
	computed end-to-end delay upper bounds.
	The scenario with partial dependent flows presented in the Network Calculus evaluation is
	also presented here for the Trajectory approach. It is assumed that 2964 randomly chosen VL

paths in the industrial AFDX network are dependent and the other 3448 VL paths are considered independent. The delay upper bound of each VL path is computed by both the classical Trajectory approach (rf x ) and the modified Trajectory approach (cp x ). The comparison is shown in Figure

4

.7 where VL paths are sorted by increasing values of their corresponding normalized value N cp x .

Table 4 .

 4

	t1 t2	t3 t5	t4 t6	t7	t3	t4 t5 t6
	Figure 4.11: A sample AFDX network of Example 1
	v i BAG i (µs) l max i (bit) C i (µs) J i (µs)
	v 1		8000	8000		80	0
	v 2		8000	8000		80	0
	v 3		8000	8000		80	0
	v 4		8000	4000		40	0

5: The Configuration of flows of Example 1

Table 4 .

 4 .6. The sample AFDX network supports FIFO scheduling and works at R = 100 M bit/s. The technological latency is null.

	t1 t2	t3 t4 t5 t6 t7 t8	t9	t3 t4 t5	t6 t7 t8
	Figure 4.13: A small example of AFDX network of Example 2
	v 1	400	4000	40	0
	v 2	800	6000	60	0
	v 3	400	6000	60	0
	v 4	400	4000	40	0
	v 5	800	6000	60	0
	v 6	400	6000	60	0

v i BAG i (µs) l max i (bit) C i (µs) J i (

µs) 6: The Configuration of flows of Example 2

Table 4

 4 Therefore, the offsets are first assigned to v 1 and v 2 , i.e., O 1 = 0 µs and O 2 = 200 µs. Then the offset is assigned to v 3 which is O 3 = 100 µs. It is the same process for VLs v 4 , v 5 and v 6 emitted by e 2 . The assigned offsets are listed in Table 4.7.

	VL SingleAssign MostLoadSA MostLoad CrossedSSA CrossedS
	v 1	0 µs	0 µs	0 µs	0 µs	0 µs
	v 2	100 µs	200 µs	200 µs	200 µs	200 µs
	v 3	200 µs	100 µs	100 µs	100 µs	100 µs
	v 4	0 µs	0 µs	0 µs	0 µs	0 µs
	v 5	100 µs	200 µs	200 µs	200 µs	200 µs
	v 6	200 µs	100 µs	100 µs	100 µs	100 µs

.7: The assigned offsets based on different offset assignments Due to the nature of switched Ethernet, flows in one set can share several output ports. When flows share several common output ports of switches, the minimum interval between two frames decreases, which can increase the waiting time of a frame in the output port. Then the number of crossed switches can be considered in the offset assignments. For the SingleAssign, a heuristic, denoted CrossedSSA, is proposed. CrossedSSA first orders the VLs emitted by one end system by decreasing values of maximum number of crossed switch output ports, and then orders the VLs by SingleAssign. Consider the example in previous paragraph. v 1 , v 2 and v 3

Table 4 .

 4 The computed ETE delay upper bounds for each offset assignment are compared with those obtained from the network without offset constraints. The statistic reductions on ETE delay upper bounds of each algorithm are listed in Table 4.8. The columns Average, Max and Min give the average, maximum and minimum reductions, respectively. It is 49% for the SingleAssign and 51% for the SingleAssign based algorithms adapted to the AFDX network. On the considered example, the SingleAssign based algorithms are close to the IdealAssign with an average reduction of 53%. The PairAssign heuristics are not efficient in the studied context due to the limited different values of BAG, which lead to few values of gcd(BAG i , BAG j ) for different VL pairs. It means that different VL pairs can have the same value of gcd(BAG i , BAG

	Heuristics	Average % Max % Min %
	IdealAssign	53.48	83.29	21.00
	GCD	23.00	70.24	4.01
	RateAdd	32.89	73.50	5.08
	RAGCD	32.51	72.99	8.85
	RMGCD	32.29	70.77	9.99
	GCDMinus	32.95	70.06	8.83
	MostLoad	32.12	70.06	8.84
	CrossedS	32.32	73.03	8.90
	SingleAssign	49.67	83.29	18.84
	MostLoadSA	51.32	82.94	18.84
	CrossedSSA	51.29	82.94	18.84

8: Statistic reduction on end-to-end delay upper bounds for each offset algorithm SingleAssign as well as its extended algorithms MostLoadSA and CrossedSSA outperform the PairAssign heuristics. Indeed, the average reductions obtained with the PairAssign heuristics are 23% (GCD) and 32% (RateAdd, RAGCD, RMGCD, GCDMinus, MostLoad and CrossedS). j ). A small example is given in Figure

4

.17. Considering VLs v 1 , v 2 and v 3 with BAG i = 4 ms (i ∈ 1, 3 ) of e 1 , there are three pairs: (v 1 , v 2 ), (v 1 , v 3 ) and (v 2 , v 3 ). They have the same value of gcd(BAG i , BAG j ) = 2 = 2 ms, and

  .1.

		Classical NC Modified NC Classical Traj Modified Traj Opt
	Nb of paths	0	194	234	459	523
	% of paths	0	3.03	3.65	7.16	8.16
	Table 5.1: Number and percentage of paths with exact worst-case delays

Case study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.6 Improved Trajectory approach . . . . . . . . . . . . . . . . . . . . . 150 6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 6.1 Introduction

  CAN bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.2.2 Switched Ethernet backbone . . . . . . . . . . . . . . . . . . . . . . . 129 6.2.3 Heterogeneous flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.2.4 Bridging strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.2.5 End-to-end delay analysis . . . . . . . . . . . . . . . . . . . . . . . . . 132 When using such a heterogeneous network for real-time applications, the computation of end-to-end delay upper bounds is a key issue. A CAN flow received at another CAN bus after crossing a backbone switched Ethernet network experiences bandwidth adaptations, scheduling policies and bridging strategies. The end-to-end communication delay is the sum of delays on its source and destination CAN buses with non-preemptive Fixed Priority (FP) scheduling plus delays on switched Ethernet network with First In First Out (FIFO) scheduling. For such a real-time network, the worst-case delay analysis is mandatory. A similar heterogeneous network has been studied by Scharbarg et al. in [SBF05]. But the network is not deterministic due to the CSMA/CD mechanism. In [AM07], Arjmandi et al. proposed to use switched Ethernet to connect different types of fieldbuses, where a single switch buffers frames in order of their priorities. In [ESMGZ08], an overview of Quality of Service (QoS) paradigms for heterogeneous networks has been discussed. Recently, Rivas et al.

	Contents
	6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
	6.2 Heterogeneous network architecture . . . . . . . . . . . . . . . . . . 129 [RGPH11] discussed heterogeneous Earliest Deadline First (EDF) and Fixed Priority (FP)
	6.2.1 6.3 Component-based approach for worst-case delay analysis . . . . . 133
	6.3.1 Component-based architecture . . . . . . . . . . . . . . . . . . . . . . 133
	6.3.2 Network Calculus approach for Non-preemptive FP Scheduling . . . . 138
	6.4 Trajectory approach for worst-case delay analysis . . . . . . . . . . 139
	6.4.1 Classical Trajectory approach for FP/FIFO scheduling applied to a
	homogeneous network . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
	6.4.2 A modified Trajectory approach adapted to a heterogeneous network . 143
	6.5 Controller Area Network (CAN) has been developed and successfully applied to industrial
	applications during the last two decades. Due to the increasing data exchange needs in the
	industrial environment, CAN bus no longer satisfies huge demand of data exchange. One way
	to build a large network is to use a switched Ethernet network that serves as a backbone
	network interconnecting several CAN buses via bridges [SBF05].

  .1. It is emitted first at a CAN bus CAN 1 which supports non-preemptive FP scheduling with a bandwidth R CAN = 1 M bit/s, then it crosses a bridge Brdg 1 where it is encapsulated in an Ethernet frame which is transmitted on the Ethernet backbone with FIFO scheduling and with a bandwidth R ET H = 100 M bit/s, and finally it is decapsulated from the Ethernet flow at the bridge Brdg 2 and competes for the CAN bus CAN 2 . Such a process is depicted in Figure 6.2.

	FP			FIFO				FP
	CAN 1 CAN frame . 1 Mbps . CAN 2.0 A . FP . 135 bits	TB Brdg 1 . . . frame encapsulation WD	full-duplex FIFO Ethernet frame 64~1518 bytes . 100 Mbps . . . Switched Ethernet Backbone	TB Brdg . . frame decapsulation 2	CAN 2 CAN frame . 1 Mbps . CAN 2.0 A . FP . 135 bits
		CAN frame						CAN frame
	NB	CAN frame CAN frame . . .	CAN frame CAN frame Ethernet frame ...	CAN frame	CAN frame CAN frame Ethernet frame ...	CAN frame	CAN frame CAN frame . . .	NB
			Figure 6.2: Heterogeneous path for τ 2

  which depends on the maximum frame size of τ compm Since the computation of the maximum delay of τ i generated at a component is obtained by the Network Calculus approach, the worst-case delay of τ i is the sum of the worst-case delays generated at each component visited by τ i . This component-based approach is holistic.We illustrate this component-based approach on τ 2 in Figure6.4 crossing a set of components: {CAN 1 , ET H, CAN 2 }. This illustration is depicted in Figure6.7.

	For the maximum delay D compm max i	of τ compm i	generated at component comp m , the Network
	Calculus [BT01] approach is used for the worst-case delay computation. This method for FIFO
	scheduling has been recalled in 2.2, and the method for non-preemptive FP will be reviewed
	in 6.3.2.
	t1	t4	t5	t2		t6	t7	t3	t8
		t9			+	t10	+	t11	=	t12
								i	and the transmission rate
	at comp m ;
	• p compm i	, which complies with the scheduling policy of comp m .
	The minimum delay D compm min i	of τ compm

i generated at the component comp m is the sum of the minimum frame transmission at each link plus bridge cost T B of each visited bridge if there is any in comp m and switching latency sl of each visited switch if there is any in comp m .

Figure 6.7: Illustration of the component-based approach for flow τ 2 From the component CAN 1 to the component ET H, the output flow τ ET H 2 needs to be determined at the interface (Brdg 1 ). Since the following component ET H is with FIFO scheduling, T ET H 2 = T 2 , C ET H 2 = C ET H and p ET H 2 = N one. Based on Equation (6.1), its inherited jitter is:

  {slow i } Due to physical constraint, frame f i crosses |P i | -1 links. The cost to cross each link is between [L min , L max ]. Then it generates an upper bounded link cost:(|P i | -1) • L maxWith the FIFO scheduling, the transmission of a frame can no longer be delayed after it has started. Therefore, the latest starting time W last i i,t of frame f i at its last visited output port last i is computed:

					( max j∈ 1,n	(C h j ))
					h∈P j
	W last i i,t	=	j∈ 1,n	(1 +	t + A i,j T j	) + • C	slow j,i j
			P i ∩P j =∅
			+	h∈P j ( max h∈P i /{slow i } j∈ 1,n	(C h j ))
			+(|P

i | -1) • L max -C last i i The transmission time C last i i of f i at the last visited node is subtracted because W last i i,t

is the latest starting time.

ms (i ∈ 1, 3 ). GCD leads to O 1 = 0 ms, O 2 = O 1 + gcd(BAG 1 ,BAG 2 )

Acknowledgement / Remerciements

Personal Publication List

Journal publications

Calculus approach applied on an industrial avionics switched Ethernet network can be found in Chapter 4.

Chapter 5

Pessimism analysis

A reachable value of serialization factor is denoted U R S last i i and computed by:

Therefore the pessimism introduced by the computation of frame serialization (Term 5. [START_REF]An illustrative industrial AFDX network architecture The network is composed of 123 end systems, 8 switches per network[END_REF])

and upper bounded by:

Consider again the Example 7 in Figure 5.6. For IP N 1 0 , the frame f 2 is smaller than the studied frame f 1 , i.e., C 2 < C 1 . Then the frame f 2 does not contribute to the seq S 1 0 . Therefore when t = 0 we have:

It leads to the maximum introduced pessimism of serialization factor:

Analytical method for underestimated delays

The underestimation of the worst-case ETE delay of flow τ i using the classical Trajectory approach is denoted U R i , which is the sum of U R

Analytical method for maximum potential pessimism

The upper bound of the pessimism of the worst-case end-to-end delay computation of the flow τ i using the Trajectory approach is denoted U P i , which is the maximum value of the sum of to CAN 4 ). The obtained pessimism for remote CAN flows with higher priorities is discussed in the next section and an improved Trajectory approach is proposed.

Improved Trajectory approach

There exists some pessimism introduced by the Trajectory approach on remote CAN flows with higher priorities, as showed in Figure 6.13. This pessimism is illustrated on τ 1 in an example network in Figure 6.15. Each CAN bus of CAN 1 , CAN 2 and CAN 3 sends one remote flow to CAN 4 through an Ethernet backbone (switch S 1 ). For the purpose of simplicity, we consider that N B = 1 and W D = T B = 0 at a bridge as well as sl = 0 at switch S 1 , i.e. R c = 0.

For each flow τ i , T i = 8000 µs, C i = 20 µs, J i = 0 and C ET H = 5 µs. It is assumed that p 1 > p 2 > p 3 , i.e. hp 1 = ∅, sp 1 = {1} and lp 1 = {2, 3}.

-Improved Trajectory approach

Appendix A

Network Calculus

A.1 Network Calculus

For a network element, its input data flows are described by means of the cumulative function R(t), which is defined as the amount of traffic that arrives at the element over time interval [0, t]. The output flows of the network element is described by the output function R * (t) defined as the amount of traffic that departs from the element over time interval [0, t]. Both R(t) and R * (t) are wide-sense increasing functions.

In order to guarantee the data flows, the arrival curve is used to limit the traffic sent by sources. An arrival curve α(t) is a wide-sense increasing function. A flow represented by its input function R is constrained by an arrival curve α if and only if for all s ≤ t

A classical arrival curve is affine function γ r,b (t), which is defined by: A network element offers some guarantees to flows using the concept service curve β(t). A service curve β(t) is a wide-sense increasing function with β(0) = 0. Consider a flow crossing a network element with input and output functions R and R * . It is defined that this network Each flow transmitted over the switched Ethernet network is constrained by such an arrival curve at its source node.

A source node is a network element which emits a set of flows. It guarantees for each emitting flow an arrival curve via a shaper. Each source node has an output port which is equipped with a buffer and supports FIFO scheduling. It transmits frames at rate R. It is represented by a service curve β R,0 = R(t) + (also known as peak rate function). A switch is a device that channels incoming frame from any of multiple input ports to the specific output port that will take the frame toward its intended destination. It supports store and forward mode which means that the switch buffers and verifies each frame before forwarding it. When a frame crosses a switch, there is a switching latency which is used to verify the frame transmission and forward it to the output port toward its destination. The maximum switching latency of a switch is sl, which means that a frame is delayed in a switch at most by time of sl. Each output port of a switch is equipped with a buffer and supports FIFO scheduling. It transmits frames at rate R. Then the service curve provided by a switch is represented by a rate-latency

The worst-case delay of a frame in a network element, such as an output port of a node or of a switch, is determined by the maximum horizontal distance h(α, β) between its arrival curve and the service curve provided by this network element. It is illustrated in

Trajectory approach B.1 Trajectory approach

The Trajectory approach is developed in [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF] for flows scheduled with FIFO. This approach considers a set of n sporadic flows transmitted over a network where neither failures nor frame losses happen. It computes the worst-case end-to-end delay upper bound by considering for a frame the worst case scenario on its trajectory.

A flow τ i (i ∈ 1, n ) following a path P i is considered. The frame f i of flow τ i generated at time t is under study.

In order to present the Trajectory approach, we first introduce some notations:

• C h i : the frame transmission time of τ i on node h;

• f irst i (last i ): the first (resp. last) node visited by τ i on its path P i ;

• slow i : the slowest node visited by τ i on its path P i ;

• slow j,i : the slowest node visited by τ j on the path P i ;

• bp h : a busy period at node h without idle time during it.

• M h i : the starting instant of bp h for the studied flow τ i .

• a h fi : the arrival time of frame f i at node h.

• f irst j,i : the node where a competing flow τ j first crosses the studied flow τ i .

• S h maxi (resp. S h mini ): the maximum (resp. minimum) delay experienced by a frame of flow τ i from its source node f irst i to node h.

• A i,j : the workload interval of a flow τ j to delay flow τ i .

• W lasti i,t

: the latest starting time of frame f i at its last visited output port last i .

• R i : the worst-case end-to-end delay upper bound of flow τ i .

• |P i |: the length of path P i .

• h ∈ P i /{f irst i }: h ∈ P i and h / ∈ {f irst i }.

• L max (L min ): the maximum (resp. minimum) processing delay when a frame crosses a link.

• 1, n : an integer set {1, 2, ..., n}.

• (a) + = max(a, 0).

Along the path P i , τ i can cross several nodes. At each crossed node, τ i can be delayed by different input flows which are transmitted in the busy period of f i . For FIFO scheduling, a busy period of frame f i is a time interval in which there is no idle time and all the frames arriving before the arrival of frame f i are transmitted. In order to compute the worst-case endto-end delay of frame f i , the Trajectory approach considers the longest possible busy period bp h ending with frame f i at each node in its path. This is achieved by considering the maximum number of frames of each competing flow transmitted in the busy period. An illustration of busy periods along the path For a busy period bp h , the first transmitted frame is denoted f (h). The arrival of frame f (h) is the starting instant M h i of the busy period.

At the source node 1, the starting time of bp 1 is taken as the time origin, i.e., M 1 i = 0. At this node, the frame f i could be delayed by frames of competing flows also emitted by the node 1 as long as these frames arrive no earlier than time 0 and no later than the arrival of frame f i .

At the node 2, there are new incoming competing flows to cross P i . The starting time M 2 i is the arrival time of the first frame coming from bp 1 . The new incoming frames delay the interconnected by switches. An illustrative example is given in Figure B.3. A source node manages a set of sporadic flows. Each source node has an input port and an output port. A switch is in charge of forwarding each incoming frame to the output port towards its destination according to a statical routing. There is a constant switching latency sl when a frame crosses a switch. Each switch has a set of input ports and a set of output port. Each input port of a source node or of a switch does not have a buffer, while each output port of a source node or of a switch has a buffer with FIFO scheduling.

An example flow τ 1 following path Each node considered in the Trajectory approach corresponds to an output port crossed by the considered flow, since each output port is equipped with a FIFO buffer. Since the input of destination node is without FIFO buffer, it is not considered in the computation. Then last i is referred to the output pout of last visited switch. For

Then the worst-case end-to-end delay upper bound of the flow τ i is obtained by:

where

B.3 Integration of frame serialization

In [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF] an optimization of the Trajectory approach considering FIFO scheduling is proposed in order to take into account the fact that frames transmitted by the same input link are serialized and they cannot arrive at an output port at the same time.

The frame serialization exists at each switch h as illustrated in Figure B.5. Flows crossing an output port h are transmitted from k h +1 input links IP h k (k ∈ 0, k h . For a frame f i of flow τ i , it crosses h in its path P i from the input link IP h 0 to the output link OP h . Then the input link IP h 0 transmits a frame sequence seq h 0 which contains f i which will be transmitted in the busy period bp h on the output link OP h . There are other k h input links IP h k (k ∈ 1, k h ) which transmits frame sequences seq h k (k ∈ 1, k h ) to the output link OP h . These frames can delay f i in the busy period bp h . The duration of sequence seq h k without its first frame is denoted l h k (k ∈ 0, k h ). The first and last frame arrivals at each busy period bp h are f (h) and p(h). The first frame arrival of each input link IP

The Trajectory approach developed in [START_REF] Martin | Schedulability analysis of flows scheduled with FIFO: application to the expedited forwarding class[END_REF] For flow τ i , the frame serialization does not exist at the source node f irst i and the destination node dest i since f irst i does not have input links and dest i does not have output link.

It does exist for the other visited output ports along the path P i , then each term ∆ h i,t along the path P i /{f irst i , dest i } needs to be subtracted from the delay:

In order to maximize W last i i,t , it needs to minimize term ∆ h i,t . According to [START_REF]Improving the worst-case delay analysis of an AFDX network using an optimized Trajectory approach[END_REF], this is achieved when the first frame of seq h 0 is the smallest one of seq h 0 , which gives max(l h 0 ); while the first frame of each seq h k (k ∈ 1, k h ) is the largest one of the corresponding seq h k , which gives min(l h k ). In order to reduce pessimism in the computation, the largest min(l h k ) (k ∈ 1, k h ) is considered. Then the minimum value of term ∆ h i,t is given by the maximum value between 0