Alexis Duque

Adrien Desportes

Razvan Stanica

Hervé Rivano

Performance Evaluation of LED-to-Camera Communications

Keywords: visible light communications, optical camera communications, Markovmodulated Bernoulli process, simulation

The use of LED-to-camera communication opens the door to a wide range of use cases and applications, with diverse requirements in terms of quality of service. However, while analytical models and simulation tools exist for all the major radio communication technologies, the only way of currently evaluating the performance of a network mechanism over LED-to-camera is to implement and test it. Our work aims to fill this gap by proposing a Markov-modulated Bernoulli process to model the wireless channel in LED-to-camera communications, which is shown to closely match experimental results. Based on this model, we develop and validate CamComSim, the first network simulator for LED-to-camera communications.

INTRODUCTION

Visible-light communication (VLC) is an enabling technology that exploits illumination to provide a short-range wireless communication link. VLC systems take advantage of the license-free light spectrum and their immunity to radio frequency (RF) interference. In such systems, information is often relayed by modulating the output intensity of a light-emitting diode (LED). Any electronic device which can detect the presence or absence of visible light can be utilized as a VLC receiver. While most of the work in the field is focused towards using photo-diodes as receivers, because of their fast response and high bandwidth, some studies demonstrated that smartphone cameras can also be used to detect high-frequency light patterns [START_REF] Danakis | Using a CMOS Camera Sensor for Visible Light Communication[END_REF].

Indeed, nowadays smartphone cameras widely use two types of image sensors, Charge Coupled Devices (CCD) or Complementary Metal Oxide Semiconductors (CMOS). These two technologies have some similarities, but one major distinction is the way each sensor exposes its pixels to light. CCD sensors use the Global Shutter readout mode, where all pixels are exposed simultaneously and then each pixel is read sequentially. This mechanism helps in capturing a still image of a moving object. On the other hand, CMOS sensors use the Rolling Shutter readout mode [START_REF] Nguyen | High-speed Asynchronous Optical Camera Communication using LED and Rolling Shutter Camera[END_REF], where each row is exposed in a row-sequential way with fixed time delay. Due to this mechanism, there is a significant time difference between the beginning of the exposure of the first and the last row, making them no longer simultaneous. When an LED is modulated at a frequency higher than the rolling shutter speed, stripes of different light intensity are captured in the image. A row of pixels appears illuminated when the LED was ON during the row exposure time. On the other hand, a row appears dark when the LED was OFF during the exposure time. The intensity and width of the strip depend on the transmitter modulation frequency, allowing us to encode information in these illuminated and dark bands, similarly to the use of a bar code.

This LED-to-camera communication based on the Rolling Shutter effect opens the door to a wide range of use cases and applications, with diverse requirements in terms of quality of service [START_REF] Pathak | Visible Light Communication, Networking, and Sensing: A Survey, Potential and Challenges[END_REF]. To cite a few examples, both line-of-sight (LOS) [START_REF] Lee | RollingLight: Enabling Line-of-Sight Light-to-Camera Communications[END_REF][START_REF] Hao | CeilingCast: Energy Efficient and Location-bound Broadcast through LED-camera Communication[END_REF] and non-line-of-sight (NLOS) [START_REF] Du | Martian: Message Broadcast via LED Lights to Heterogeneous Smartphones[END_REF][START_REF] Ferrandiz-Lahuerta | A Reliable Asynchronous Protocol for VLC Communications Based on the Rolling Shutter Effect[END_REF] communications have been demonstrated in these settings, as well as ultra-reliable localization solutions [START_REF] Zhang | LiTell: Robust Indoor Localization using Unmodified Light Fixtures[END_REF][START_REF] Zhu | Enabling High-Precision Visible Light Localization in To-dayâĂŹs Buildings[END_REF], sensing [START_REF] Li | Human Sensing Using Visible Light Communication[END_REF], or even scene protection against intrusive photographs [START_REF] Zhu | Automating Visual Privacy Protection Using a Smart LED[END_REF]. However, while analytical models and simulation tools exist for all the major RF technologies, the only way of currently evaluating the performance of a network mechanism over LED-to-camera is to implement and test it. This results in heavy measurement and parameterisation campaigns that need to be repeated anytime a new VLC protocol or feature is imagined. Having access to standard performance evaluation tools in this type of network would certainly accelerate studies in the field, and nicely complement experimental field tests.

The work described in this paper aims to fill this gap by proposing models and tools that help in the assessment of LED-to-camera communication network mechanisms. Our contributions are threefold. First, we propose an analytical model for LED-to-camera communication systems in Sec. 3. Second, we design and implement CamComSim, a LED-to-camera communication simulator in Sec. [START_REF] Hao | CeilingCast: Energy Efficient and Location-bound Broadcast through LED-camera Communication[END_REF]. Finally, the model and the simulator allow us to benchmark several network redundancy mechanisms proposed in the literature. By checking against experimental results, we are able to confirm the correctness of our models in this context.

RELATED WORKS

LED-to-camera communication allows for low-throughput unidirectional message transmission, with a performance in range of a few kbit/s [START_REF] Lee | RollingLight: Enabling Line-of-Sight Light-to-Camera Communications[END_REF][START_REF] Hao | CeilingCast: Energy Efficient and Location-bound Broadcast through LED-camera Communication[END_REF]. Despite this limited throughput, LED-to-camera communication raises a lot of interest because it enables communication with no extra financial cost between any LED-equipped machine or instrument and any regular smartphone. This low cost also explains the fact that practically every study on this topic uses an experimental approach. While experiments are essential in evaluating new protocols and services, running an experimental campaign every time one wishes to evaluate a new idea can become cumbersome.

Designing analytical models and implementing them in simulation tools is standard practice in the wireless networking field in order to accelerate the evaluation of new protocols and mechanisms. Indeed, network simulation has been largely studied in the case of wireless communication [START_REF] Sharif | Ubiquitous Sensor Network Simulation and Emulation Environments: A Survey[END_REF]. Nonetheless, VLC performance evaluation remains poorly investigated and VLC simulation tools are still missing. The main efforts on simulating VLC systems have focused on indoor channel simulation [START_REF] Tagliaferri | Development and Testing of an Indoor VLC Simulator[END_REF], or on the 802.15.7 PHY [START_REF] Aldalbahi | Extending ns3 to Simulate Visible Light Communication at Network-level[END_REF][START_REF] Ley-Bosch | Implementing an IEEE802.15.7 Physical Layer Simulation Model with OMNET++[END_REF] and MAC [START_REF] Musa | The Design and Implementation of IEEE 802.15.7 Module with ns-2 Simulator[END_REF] layers. These approaches rely on classical network simulation frameworks, such as those used for wireless and ad hoc networks, e.g. ns-2 [START_REF] Musa | The Design and Implementation of IEEE 802.15.7 Module with ns-2 Simulator[END_REF], ns-3 [START_REF] Aldalbahi | Extending ns3 to Simulate Visible Light Communication at Network-level[END_REF], OMNET++ [START_REF] Ley-Bosch | Implementing an IEEE802.15.7 Physical Layer Simulation Model with OMNET++[END_REF] or MATLAB [START_REF] Tagliaferri | Development and Testing of an Indoor VLC Simulator[END_REF]. All these works consider LED-to-Photodiode communication, hence LED-to-Camera communication is completely unexplored. Our work is the first effort in LED-to-Camera simulation reported in the literature, making CamComSim the first implementation of a LED-to-Camera VLC simulator.

MODELING LED-TO-CAMERA COMMUNICATION

In this section, we describe, for the first time in the literature from our knowledge, a LED-to-camera communication channel model.

Based on the theory of Markov-modulated Bernoulli processes (MMBP) [START_REF] Ozekici | Markov Modulated Bernoulli Process[END_REF], discussed in Sec.

Model design

In a LED-to-camera system, data is received as a series of dark and illuminated stripes in a picture frame captured by the camera. In the following, we note by f i the i-th frame captured by the camera and by δ f the time between the beginning of two consecutive frames.

Obviously, even at the highest frame rate allowed by the camera, data is not continuously received, as a minimum time δ д exists between two frames. This is denoted as the inter-frame gap (IFG). Moreover, as depicted in Fig. 1, the distance between the LED and the camera also has an impact: when the camera is farther away, the LED transmission is captured for a shorter time, resulting in a smaller ROI.

Gilbert-Elliot model:

A first idea to model LED-to-camera communication would be the Gilbert-Elliot model, which is widely used to model bursty losses [START_REF] Elliott | Estimates of Error Rates for Codes on Burst-Noise Channels[END_REF]. This unique type of channel can intuitively be modeled by a two states Markov chain. In state S 1 , the system is capturing a frame. The camera is receiving packets, and the reception probability is 1 -p e where p e is the packet decoding error probability. In state S 2 , the camera is not capturing any pictures, therefore we consider the reception probability is 0.

The transition probability between S 1 and S 2 (respectively S 2 and S 1 ) is denoted p (respectively q). The model assumes that p, q, p e are independent and constant. In this case, the probability of being in state S 1 under the steadystate regime can be easily computed as p s 1 = p p+q . The probability of being in state S 2 is so p s 2 = q p+q . The values of p and q are function of the duration of the IFG, δ д , the frame duration, δ f , and the camera capture time δ c , depicted in Fig. 1, and linked as the following:

p = 1 -q = δ f -δ д δ f = δ c δ f (1)
3.1.2 MMBP model: If the model introduced just before is straightforward and widely used, it lacks realism in our case, where the transitions between ON and OFF states are almost deterministic. Practically, in our system, the transition probability from a state to another depends on the residence time in this state.

To improve this approach, we model the LED-to-camera channel using a Markov-modulated Bernoulli process (MMBP), represented in Fig. 2. In this figure, we depict a Markov chain with a total number of M +N states. Each of these states represents a reception time slot, i.e. the time duration needed in order to receive one physical layer message (denoted as PHY-SDU in the following). The transition between two states representing successive time slots is automatic, i.e. it happens with a probability of 1. Practically, the M + N states in Fig. 2 represent a δ f time interval, and they are divided in two groups: M states corresponding to the camera capture time δ c (S O N states), and N states corresponding to the inter-frame time δ д (S O F F states). A Bernoulli arrival process is associated with each of these M + N states, representing the reception of a packet.

In S O N states, the camera is receiving packets, and the arrival rate is λ 1 = (1 -p e ), where p e is the packet decoding error probability. In S O F F states, the camera is not capturing any pictures, therefore we consider the arrival rate λ 2 = 0.

We denote as s a state in the Markov chain and we define state s + j as the state reached after j transitions, starting from state s. The probability of being in state s under the steady-state regime can be easily computed as π s = 1 N +M . At the same time, the probability of noticing no arrivals (i.e. no packet reception) in state s is p 0 (s). This can be written as:

p 0 (s) = 1, i f s ∈ N p e , i f s ∈ M (2)
As it can be seen from both models, the relatively high packet loss probability (compared with RF technologies) is an intrinsic property of the LED-to-camera communication channel. To overcome this problem, redundancy mechanisms are needed.

In the following, using classical redundancy mechanisms as an example, we show that the classical Gilbert-Elliot model is inaccurate, which highlights the need to rely on the MMBP theory. Then, we use the MMBP channel model to compare two simple, but widely used redundancy solutions: repeating a packet or repeating a sequence of packets.

Repeat Packet

The first strategy to cope with the inherent losses in the LED-tocamera communication system, used for example by Ferrandiz-Lahuerta et al. [START_REF] Ferrandiz-Lahuerta | A Reliable Asynchronous Protocol for VLC Communications Based on the Rolling Shutter Effect[END_REF], is to send each packet twice in a row, to increase the probability that at least one of the transmissions will be fully captured by the smartphone camera. We generalize this approach in the Repeat Packet (RP) strategy, where each packet is repeated r times, one after the other. In this case, the r value needs to be chosen in order to attain a desired reception probability, its optimal value depending on the inter-frame time and on the packet size.

In the following, we study the probability of receiving a packet at least once when considering the RP strategy, for the two models introduced above.

Gilbert-Elliott Model:

If we consider the Gilbert-Elliott model, the probability of receiving a packet at least once can be written as p RP s = 1 -p RP 0 , where p RP 0 represents the probability of failing to receive a packet r times in a row, written as:

p RP 0 = P S 1 • p e + P S 2 r = p • p e + q q + p r (3)

MMBP Model:

If we consider the MMBP model, the probability of failing to receive a packet r times in a row p RP 0 can be written as:

p RP 0 = s (p 0 (s) • p 0 (s + 1) • p 0 (s + 2) • ... • p 0 (s + r -1)) N + M (4)
The value of p RP 0 will depend on m s , defined as the number of S O N states during the r retransmissions, when the first packet transmission is in state s:

p RP 0 = 1 N + M • M +N s=1 (p e ) m s (5)
Depending on the values of r , M and N , several cases can be distinguished. We present results for the two most current cases: Case 1: r < M, N . This means that the number of retransmissions does not always cover the δ д period (which counts N states). In this case, p RP 0 can be written a follows:

p RP 0 = P [s ∈ N ∧ (s + r ) ∈ N ] + P [s ∈ M ∧ (s + r ) ∈ M] + P [s ∈ M ∧ (s + r ) ∈ N ) + P [s ∈ N ∧ (s + r ) ∈ M] = N -r + 1 M + N + M -r + 1 M + N • p e r + 1 M + N r -1 i=1 p e i + 1 M + N r -1 i=1 p e r -i = N -r + 1 M + N + M -r + 1 M + N • p e r + 2 M + N • p e -p e r 1 -p e (6)
Case 2: N < r < M. . This is the most common case, where the number of repetitions is chosen to cover the entire inter-frame period. However, a reception is still not certain in this case, because of the decoding error p e . In this case: We compare the analytical results given by the two aforesaid models to experimentation results (obtained using our testbed described in [START_REF] Duque | Unleashing the Power of LED-to-Camera Communications for IoT Devices[END_REF]) in Fig. 3. This figure shows the success probability of receiving a message of N p = 50 packets of data, as a function of the number of retransmissions r .

p RP 0 = P [s ∈ M ∧ (s + r ) ∈ M)] + P [s ∈ M ∧ (s + r ) ∈ N ] + P [s ∈ N ∧ (s + r ) ∈ M] = M -r + 1 M + N • p e r + 1 M + N r -1 i=1 p e i + 1 M + N N i=1 p e r -i = M -r + 1 M + N • p e r + 1 M + N • p e -p e r 1 -p e + 1 M + N N i=1 p e r -i = M -r + 1 M + N • p e r + 1 M + N • p e -p e r 1 -p e + 1 M + N • p e r -N (p e -p e N ) 1 -p e (7)
The very different results between the Gilbert-Elliott model and the experimentation confirms that the stochastic transition assumptions of this model are quite far from reality. On the other hand, MMBP approximates quite well the experimental behavior, highlighting the need for this more complex, but finer grained model.

Repeat Sequence

A different approach to improve reliability is the Repeat Sequence (RS) strategy, consisting in the transmission of a sequence of N p packets, repeated r times. In contrast with the previous mechanism, RS does not try to cover the inter frame time at the packet level, and it does not ensure that a packet is received before sending the next one. Instead, the reliability and presumed efficiency is based on the fact that the probability of losing the same packets over different transmitted sequences is low.

In the case of an RS strategy with a sequence of N p packets retransmitted r times, the probability of receiving a packet at least once can be written as p RS s = 1 -p RS 0 . Using the MMBP model, the probability of failing to receive a packet r times in a row, p RS 0 , can be written as:

p RS 0 = 1 M + N . M +N s=1 r -1 j=0 p 0 (s + r N p ) (8)

Evaluation results

We use our MMBP analytical model to study the RP and RS strategies by focusing on the probability of delivering the entire quantity of information in a given number of transmissions. We provide both analytical and experimental results, allowing us to validate the proposed MMBP model. Fig. 4 shows, for the two mechanisms, the probability of integrally receiving N p packets of data as a function of the number of retransmissions r . In this figure, we set M = 5 and N = 2; these values are in line with the packet length, the transmitter frequency and the camera capture interval experimentally observed for a distance of 5 cm between LED and camera. The results show quite a nice fit between the analytical and experimentation results, despite the assumptions required by our MMBP model.

To better understand the performance of the two retransmission strategies, we compare them in Fig. 5. This figure shows that, for the RS strategy, 3 retransmissions are needed to achieve a reception probability higher than 0.9, while this value raises to 6 for the RP strategy. On the right side of the figure, we show that the performance of the two strategies depends on the ratio between the number of S O N and S O F F states, M : N . When this ratio changes from 5 : 2 to 2 : 5, which practically corresponds to increasing the distance between the LED and the camera, RP gives better results than RS. Indeed, for the RS method, the success probability sharply decrease when M < 3 and stays below 0.6 even for 10 retransmission.

Practically, this means that RP is more suitable when the distance between the LED and the camera is higher, while RS is better for short communication distances. This phenomenon was previously unknown in the research community, but it is straightforward to study with our analytical model

ROI MODEL

An important phenomenon in LED-to-camera communications comes as a direct consequence of the distance between the LED and the camera. Indeed, as this distance increases, the size of the region of interest (ROI) in the picture reduces and, as a consequence, cuts down the number of messages that the camera can receive per frame, i.e. the M states in Fig. 1. To include this performance factor into our model, we propose an analytical function that gives the ratio between the ROI and the picture size. In the model discussed in Subsec. 3.1, this is the ratio of M states in the M + N states.

We apply photogrammetry rules to give the ROI ratio as a function of the distance d, the LED size l, the camera CMOS sensor size ss, the image size on the sensor i and the camera focal distance f c. According to the optical system depicted in Fig 6, basic lens optic rules give the following Eq. 9:

i f c = l d ⇐⇒ i = l • f c d (9)
To obtain the ROI as the ratio of the total number of pixels in the picture, we need as input the CMOS sensor size ss. We apply the min function to normalise the ROI ∈ [0, 1] even if the image size on the sensor, i, is larger than the sensor size, ss. The result is given in the following Eq. ( 10):

ROI = min 1, l • f c d • ss (10)
To validate the results given by Eq. 10, we measure the ROI experimentally, using the testbed described in [START_REF] Duque | Unleashing the Power of LED-to-Camera Communications for IoT Devices[END_REF], for distances from 0 to 40 cm. Fig. 7 during our experiments and in green the analytical results computed with a Nexus 5 sensor with the following characteristics: f c = 35, ss = 5.7 and l = 10. This shows that the analytical curve approximates quite well the experimental ROI ratio. However, we notice that the experimental results are better for a distance between 10 and 30 cm, and they become worse than the model at 35 cm. In fact, the light radiance on the camera lens, that our model does not take into account, artificially increases the LED size on the picture when the camera is close to the LED. The difference at larger distance is a consequence of the ambient light which was measured at 650 lux during the experiments, also neglected in Eq. ( 10).

The ROI model described in this section and the MMBP reception model validated in the previous section are the basis of the simulator implementation discussed in the following.

THE CAMCOMSIM SIMULATOR

As discusse in Sec. 2, the simulation of LED-to-camera communication remains completely unexplored in the field. Our work is the first such effort reported in the literature, making CamComSim the first implementation of a LED-to-camera VLC simulator.

Simulator Implementation

5.1.1 Software architecture. CamComSim is an event-driven LEDto-camera simulator developed in Java, which makes it easy to maintain and distribute code, and it provides built-in multi-platform compatibility for systems with a Java Virtual Machine. Fig. 8 shows the CamComSim software architecture that consists of a simulator kernel class and four core packages. The broadcast strategy abstraction is given in the strategy package. Here, the Strategy interface lets the users implement their transmission strategy. This package also contains the straightforward ReapeatPhysduStrategy (RP) implementation that consists in repeating each PHY-SDU r times, one after the other, as described in Sec. 3.2. When the last PHY-SDU of the message is reached, the process is repeated from the beginning. Finally, the scenario package proposes an interface to build a simulation, wiring together the Message , the Channel , the Led , the Camera and the Strategy with the Simulator kernel. Besides, the package utility provides helper classes used to compute the simulation results statistics, format and save the results as a JSON file and load or save the simulation parameters. The ui package contains a command-line interface (CLI) used to run a simulation scenario.

5.1.2 Simulator parameters. Our simulator exposes a set of finely grained parameters to describe the LED-to-camera communication system behavior. Table 1 shows the parameters we use in this work and expose through the CamComSim CLI. The performance of the LED-to-camera communication is significantly affected by the distance d, the IFG noted δ д in Fig. 2, and the LED size l. The values of these parameters should therefore be carefully chosen, according to the available hardware and envisioned scenario.

Further parameters, introduced in Sec. 4, that refer to the CMOS sensor characteristics, are optional but can be considered to refine the channel model, as they impact the ROI. However, smartphone manufacturers rarely provide this information, e.g. regarding the sensor size ss and the focal distance f c.

The PER p e is the consequence of the errors occurring in a M state when a PHY-SDU is well included in a picture but is wrongly decoded by the smartphone. These errors are bits substitutions induced by interference, low SNR, and artifacts on the picture. This value varies from a smartphone to another, but we did not observe major differences in our tests.

The PhysduPayload payload size P and the PhysduPayload header size H configure the data encapsulation mechanism. Given these two settings, the PHY-SDU size is computed as P +H +SY NC + PB, where SY NC is the PHY-SDU delimiter symbol (4 bits in our tests), and PB is the number of parity bits (2 bits in our settings). This PHY-SDU size, along with d, l, δ f and the modulation frequency f , determines the number of the M time slots in Fig. 2.

A transmission strategy among the Strategy interface implementations needs to be chosen as well. For now, we have implemented and considered only the RP strategy, for which the parameters are the size of the message to broadcast, G, and the number of consecutive PHY-SDU emissions, r .

Kernel Implementation.

The CamComSim kernel is implemented in the Simulator class. Its role is to produce PHY-SDU emission events (TX) and manage their result. The number of events, i.e. the number of PHY-SDU sent, is noted c and is updated at runtime. At each clock tick, c is incremented, a TX event is created and processed as follow: (1) the next PHY-SDU in the transmission strategy queue is associated with this event; (2) considering p e , f , P, H , c, the channel response function gives the event result. The result is one among: reception success, reception with errors or loss during IFG; (3) this result is stored in a list to further determine if all the PHY-SDU forming a message are received.

The simulator loops over (1), ( 2) and (3) until the stop condition is met, i.e. c has reached the maximum number of PHY-SDU emissions or the complete message is received. The simulation is repeated n r times using the Java class for multi-threading purpose ThreadPoolExecutor . Finally, the simulations results and statistics are saved in a JSON file for further processing.

CamComSim validation

In this section, we present LED-to-camera simulation results given by CamComSim. To assess the correctness of our simulator, we conduct a series of experiments with the testbed presented in [START_REF] Duque | Unleashing the Power of LED-to-Camera Communications for IoT Devices[END_REF]. We set the emitter symbol rate to 8 kHz and place it in standard indoor illumination conditions, near a window and illuminated with neon lights. The illuminance has been measured with a luxmeter at around 650 lux. We compare the testbed performance with the results given by CamComSim for a set of key parameters: the message size G, the number of consecutive PHY-SDU emissions r , the distance d and the PHY-SDU payload length P.

PHY-SDU Retransmission.

As discussed in Sec. 3.2, to face the IFG bits erasure and ensure that all the packets are well received, a possibility is to transmit consecutively each PHY-SDU r times in a row. The ReapeatPhysduStrategy class in CamComSim implements this retransmission strategy. When each PHY-SDU has been transmitted r times, the message transmission restarts, until the message is completely received. To avoid infinite loops, we stop the simulation when 50000 PHY-SDU are sent, even if the message is not received entirely. In such case, we consider the goodput is 0.

The results highlight that the simulation and testbed goodput follow the same tendency when r varies. The best case is when r = 1, for which the goodput is 1.6 kbit/s according to CamComSim and 1.7 kbit/s for the testbed, an estimation error of only 6%. Based on these results, for all the simulations that follow we use the RP strategy implementation with r = 1.

Message size.

We now consider the impact of the message size G on the goodput at a 5 cm distance, with r = 1 and a 24 bits length PHY-SDU. Fig. 10 shows that CamComSim results are very close to those of the testbed, confirming that the simulator well considers the impact of the message size. The goodput reduces when the message size increases, as the RP strategy leads to a large number of useless transmissions: the simulator gives 1.6 kbit/s of goodput for G = 50 bytes, while this falls to 670 bit/s when G = 1000 bytes. These results differ from the testbed in no more than 7%.

5.2.3

Distance. Fig. 11 shows the goodput and the throughput as a function of the distance, when the LED broadcasts a 50 bytes message. The PHY-SDU payload is set to 24 bits, with P = 19 and H = 5. The results show a good match between the simulation and real life results. At 10 cm, CamComSim gives 2.2 kbit/s of throughput, against 1.94 kbit/s experimentally. The results are closer for the goodput: 0.94 and 1.0 kbit/s respectively for simulation and experimentation, that is only 6% of difference. This section highlights that CamComSim gives results very close to the testbed for all the parameters we have studied. The difference is around 10% and often less. For all the cases we consider, CamCom-Sim respects the behavior of the LED-to-camera communication system implemented by the testbed.

Use case

In this section, we detail a case study for CamComSim, applied to a real life scenario. A common issue with cheap consumer electronics is the lack of diagnostics when a dysfunction happens. Manufacturers often blink the state LED with a pattern and color that match with an error code. Such a mechanism is easy to implement but leads to inaccurate diagnostics. For these cases, we propose to benefit from this LED to perform LED-to-camera communication and broadcast a log file that would include helpful information to diagnose a dysfunction. We consider a worst case file size of 1 kbyte that is large enough for events history or debug traces.

Fig. 12 compares the goodput given by CamComSim with the goodput that our testbed achieved for the transfer of a 1 kbyte log file as a function of the number of PHY-SDU retransmissions r . Note that this is equivalent to G = 1000 bytes in Fig. 10. The transmission restarts until the message is received. The left side plot shows the results when the LED and the smartphone are 5 cm apart, while the distance is 10 cm on the right side figure. At 5 cm, the simulation brings out that, to obtain the higher goodput, the emitter should send each PHY-SDU one or three times consecutively, i.e. r = 1 or r = 3. The goodput is respectively 680 and 720 bit/s in these cases. This finding is similar to the testbed, where the goodput is 570 bit/s when r = 1 and 540 bit/s when r = 3.

Because the ROI decreases with the distance, the behavior is different when the smartphone is 10 cm far from the LED. In this situation, r = 4 stands out clearly to be the best choice both for the simulation and the experiments. The goodput then becomes 620 bit/s on the testbed and 540 bit/s with CamComSim.

Since the results are very close to the reality, using CamComSim highly reduces the search space for the experimental optimization of a system. As shown by these results, the best value for r can be decided using simulations only, removing the need for a lengthy experimental campaign.

CONCLUSION

In this paper, we introduced CamComSim, the first simulator for the design, the prototyping and the development of protocols and applications for LED-to-camera communication. Our event driven simulator is based on an MMBP channel model, and it relies on a standalone Java application that is easily extensible through a set of interfaces. We have validated CamComSim comparing simulation results with the performance reached by a real life testbed. Then, we illustrated with a practical use case the complete usage of CamComSim to tune a broadcast protocol that implements the transmission of a 1 kbyte log file. The results highlight that our simulator is very precise and can predict the performance of a LED-to-camera system with less than 10% of error in most cases. The availability of accurate performance evaluation tools offers a great ease of use and the opportunity to tune protocols without the burden of always realizing experiments on a testbed.

Figure 1 :

 1 Figure 1: Frame capture time and inter-frame interval, and their relation with the MMBP parameters.

Figure 2 :

 2 Figure 2: The MMBP model of the LED-to-camera channel.

  ), Np=50 RP (experimental), Np=50 RP (Gilbert-Elliott), Np=50Retransmissions Success probability

Figure 3 :

 3 Figure 3: Probability to successfully receive N p packets for the RP strategy. Dotted-lines show analytical results for the Gilbert-Elliott and MMBP models, while plain lines represent experimental results.

  RP (experimental), Np=30 RP (experimental), Np=50 RP (experimental), Np=100

Figure 4 :

 4 Figure 4: Probability to successfully receive N p packets for the RS (left) and RP (right) strategies as a function of the number of retransmissions r . Dotted-lines show analytical results while plain lines represent experimental results.

Figure 5 :Figure 6 :

 56 Figure 5: Comparison between RS and RP. On the left, analytical and experimental results for M = 5 and N = 2. On the right, analytical results when M + N = 7, but the M : N ratio changes. In both cases, N p = 50.

Figure 7 :

 7 Figure 7: ROI as a function of distance. The orange line shows experimental results, while the green line represents analytical results given by Eq. 10.

Figure 9 :Figure 10 :

 910 Figure 9: The experimental goodput (blue) compared with the simulation goodput (green) as a function of the number of consecutive PHY-SDU emissions. The bars on top are 95% confidence intervals.

Fig. 9

 9 Fig.9shows the goodput at 5 cm for different values of PHY-SDU consecutive retransmissions r , with G = 50, P = 19, H = 5. When each PHY-SDU has been transmitted r times, the message transmission restarts, until the message is completely received. To avoid infinite loops, we stop the simulation when 50000 PHY-SDU are sent, even if the message is not received entirely. In such case, we consider the goodput is 0.The results highlight that the simulation and testbed goodput follow the same tendency when r varies. The best case is when r = 1, for which the goodput is 1.6 kbit/s according to CamComSim and 1.7 kbit/s for the testbed, an estimation error of only 6%. Based on these results, for all the simulations that follow we use the RP strategy implementation with r = 1.

Figure 11 :

 11 Figure 11: The throughput (red) as a function of the distance, compared with the goodput (green). Dotted-lines show experimental results while plain lines represent simulation results.

Figure 12 :

 12 Figure 12: The experimental goodput (blue) compared with the simulation goodput (green) for the use case as a function of the number of consecutive PHY-SDU emission at 5 cm (left) and 10 cm (right).

  plots in orange the ROI ratio we observed

		1				1
		0.8				0.8
	Success probability	0.2 0.4 0.6			RP, Np=50 RS, Np=50 RP (experimental), Np=50	0.4 0.6 Success probability 0.2						RS, M=5 RP, M=5 RS, M=3 RP, M=3 RS, M=2 RP, M=2
		0	0	2	4 Retransmissions 6 RS (experimental), Np=50 8 10	0	2	4	6	8 Retransmissions 10 12	14	16

Table 1 :

 1 Simulator parameters and default values.

	Param.	Description	Default Value
	d	Distance between camera and LED (cm)	5
	l	LED size (mm)	4
	d д	Camera inter-frame gap ratio	0.1
	p e	Decoder PHY-SDU Error Rate	0.001
	f	Modulation frequency (Hz)	8000
	P	PhysduPayload Header length (bit)	8
	H	PhysduPayload Payload length (bit)	16
	r	PHY-SDU repeat number	1
	G	Message size (bytes)	50

For interested readers, CamComSim is already available as an open-source software under Apache license at http://vlc.project.citi-lab.fr/camcomsim.

Figure 8: The CamComSim software architecture and packages dependency graph.

The topology package groups classes that describe the system components: Led , Camera and Channel . The classes in the data package implement the data encapsulation. For this, a Message is a set of PHY-SDU that encapsulates a PhysduPayload .

A Packet is a PhysduPayload child class, with a sequence number as header and a payload that contains data. Before each simulation, a Message is created according to the user settings. The resulting set of Physdu is initialized with a Packet filled with arbitrary data in the payload (real data could be used if available) and a unique sequence number in the header.


Dr Kai Richter

Dr Marek Jersak

Prof. Dr Rolf Ernst

How OEMs and Suppliers can face the Network Integration Challenges

Keywords: Network Integration, Supply-Chain Communications, Reliability, Timing Analysis 1

Systems integration is a major challenge in many industries. Systematic analysis of the complex integration effects, especially with respect to timing and performance, significantly improves the design process, enables optimizations, and increases the quality and profit of a product. And it helps to improve supply-chain communications. This paper surveys a set of interesting experiments we have conducted on a real-world automotive communication network using our new SymTA/S schedulability analysis technology. We demonstrate that, and how, analysis technology helps answering key integration questions, thereby carefully respecting the established business models.

Introduction

The increasing application complexity, together with a strong time-to-market pressure, require a massively parallel design of systems, whether in automotive, avionics, multimedia, or telecommunications industries. The supply-chain often contains hundreds of companies that design their individual "components" based on requirement definitions from the OEMs or tier-1 suppliers. Systems integration is a major challenge. Dynamic component interactions result in a variety of nonfunctional performance dependencies due to scheduling, arbitration, blocking, buffering etc. These can lead to hard-to-find timing problems, incl. transient overload, buffer under-and over-flows, and missed deadlines. All electronics industries have identified this as a major bottleneck in the design, and have started standardization efforts for components, e.g. AUTOSAR [1] in the automotive area.

We have been researching the role of performance and timing analysis in system-level design in our SymTA/S project [2] for more than five years. We have adopted and extended a host of theoretical contributions to meet industrial requirements, and we have successfully demonstrated our technology in industrial projects. In this paper, we will summarize the application of our technology in the area of automotive network dimensioning, the very center of all integration efforts. We demonstrate how network reliability and the overall integration process can be significantly enhanced, thereby carefully respecting the established business models along the supplychain.

We will start with identifying the challenges that OEMs and suppliers face and provide a quick overview about the foundations of related analysis fields.

The Network Integration Problem

Network integration is carried out by an OEM who determines bus topology, speed, number of nodes and messages, and finally the configuration, e.g. the assignment of priorities or time slots to bus messages. The decision making process typically includes the following questions: Is the network (temporarily) overloaded? Which messages can get lost, and how often? Can more ECUs (and how many) be connected without overloading the bus? How about diagnosis and ECU flashing? Answering these questions requires understanding the sophisticated effects that individual decisions might have on the overall performance and timing. And it requires a systematic procedure including appropriate supply-chain communications in terms of data sheets and requirements specifications.

Interestingly, things look quite different today. Simulation and test is established common practice but suffers from serious corner case coverage problems and is not suitable to reliably detect the bottlenecks. Therefore, architects very often favor less efficient, conservative designs. For instance, conservatively allowing "N out of M" messages to get lost is not an unusual way to "guarantee" that a minimum number of messages gets through. But sending significantly more messages than actually "required" further increases bus load and should be avoided, since this also increases the number of lost messages.

Detecting and reducing such inefficiencies, in turn, requires knowing how message loss can be reliably analyzed and bounded. The lack of systematic procedure currently prevents OEMs from thorough optimizations, and overly conservative approaches are common practice.

3.

Quick Review

Load Analysis is not Enough

Although very simplistic, the bus load model is still among the most popular analytical models for bus analysis in practice. For each message, multiply the frequency of a message (1/period) with its length (incl. protocol overhead), build the sum over all messages, and finally divide it by the network bandwidth. The result is a relative network load, often called utilization, given in percent of the available bandwidth. Such load models are popular but there is, interestingly, much variation among the OEMs in defining a critical bus load limit; some say 40%, others say 60%. Why is that? Clearly, increasing the load means better utilizing resources which translates into promising cost savings. The load model says, however, nothing about if deadlines can be met or buffers overflow and should, therefore, be used with extreme care.

In fact, the correctness of a bus configuration depends on more parameters, especially with respect to the subtle dynamic effects that average load models can not capture.

Dynamic Communication Patterns

Finding bottlenecks requires the complex dynamic communication patterns to by analyzed. A host of sophisticated methods from real-time scheduling theory is available to determine and analyze such patterns automatically [START_REF] Liu | Scheduling algorithms for multiprogramming in a hardreal-time environment[END_REF][START_REF] Joseph | Finding response times in a real-time system[END_REF][START_REF] Kopetz | TTP -a timetriggered protocol for fault-tolerant computing[END_REF][START_REF] Spuri | Analysis of deadline scheduled real-time tasks[END_REF]. The methods directly provide detailed data such as response times that allow answering key design questions.

For instance, to guarantee that a message X will never get lost (overwritten in the sender's buffer), its maximum response time must not exceed its minimum re-arrival time (the deadline). Calculating the response times requires consideration of the protocol-specific behavior of the CAN bus. Higherpriority messages can significantly delay lowerpriority ones, message jitters further distort the timing behavior, the controller type (basicCAN, fullCAN, etc.) influences the order in which messages are sent, and bus errors can lead to additional retransmissions.

Figure 2 Message Jitters, Burst, and Errors Result in Complex Communication Patterns

Figure 2 shows such a complex communication sequence with a variety of influences. Key of such analysis techniques is that they find and evaluate the critical situations automatically without user interaction, provided that the system configuration, i.e. the message IDs (priorities), message length, jitters, the interface queues, and an error model is known. Figure 3 structures this required information into bus-related, ECU-related, and models for error and flashing/diagnosis. Once this data is available, one can select among a host of more or less powerful schedulability analysis techniques, some are available as tools.

Schedulability Analysis in Practice

In practice, however, only part of this data is available to the OEM, usually the CAN K-Matrix, covering only the static part of the system. The gray area of Figure 3 illustrates the "scope" of OEM information. Those important dynamic influences, such as message send jitters, result from ECUs implementation decisions and are often not available in detail. At best, the used CAN controller type is known early. Errors and flashing even have their roots outside the actual design task with little information. So, can such analysis technology really help when data availability is a major concern? In fact, it can, as we will see by the end of the next section.

4.

The Case Study

We have used our SymTA/S tool suite to analyze a real-world power train CAN bus from the automotive industry. Several ECUs (electronic control units) including gateways are attached to that bus, each sending and receiving a total number of more than 50 messages. We automatically imported the length, CAN id (priority), and the period of each message from the K-Matrix. We knew the jitters of only a few messages, typically in the range of 10-30% of the message's period. Other jitters were unknown, as the ECU implementations were not yet completed. Using our tool suite, we conducted a set of experiments, each based on different assumptions on the missing information.

In the first experiment, we assumed zero jitters and verified that all messages will meet their deadlines. In fact, such simplifications (zero jiitters, no errors) have a limited practical relevance. Very important is ,however, the fact that we could do such "what-if" observations within minutes, without any simulation or test equipment.

We proceeded with other experiments, in which we assumed "realistic" jitters for the unknown messages. We also considered different types of bus error models that lead to retransmissions. Practically useful errors models are available for sporadic errors [START_REF] Tindell | Guaranteed message latencies for distributed safetycritical hard real-time control networks[END_REF] that appear once in a given time interval (similar to the MTBF -mean time between failures-model) and for burst errors [START_REF] Punnekkat | Response time analysis under errors for CAN[END_REF].

Sensitivity and Robustness

We repeated these experiments, and within minutes we determined how message response times vary over several jitter and error distributions. We found out that some messages are relatively sensitive [START_REF] Racu | Applying sensitivity analysis in real-time distributed systems[END_REF] to jitters and errors, while others are quite "robust".

Figure 4 illustrates the dependency between the jitter and the response time for few selected messages. A message whose response time increases fast with increasing jitter is considered sensitive, messages with relatively constant response times are considered robust against jitters. Similar results have been obtained for error-sensitivity.

Message Loss

We further detected, for each experiment, how many and which messages already miss their deadlines and could be lost. The dotted lines in Figure 5 illustrate a selected part of the results. The x-axis captures the increasing jitter (in %), while the y-axis shows the number of messages (in % of all messages in the K-Matrix) that will miss their deadlines. When ignoring bus errors (best-case line), no message gets lost until the jitters exceed 25% of the message periods, then loss is slightly increasing.

In the worst case experiment we considered burst bus errors, bit stuffing, and the minimum re-arrival time as a deadline. We can observe deadline violations and message loss starting at very small jitters and increasing rapidly, an undesired behavior.

CAN Optimization

In order to eliminate this message loss we were looking for optimized priority (CAN ID) configurations. We used the automatic optimization feature of our SymTA/S tool suite to find better CAN ID configurations that would exhibit less message loss. The optimizer [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF] also performs "what-if" analysis using genetic algorithms. We configured the optimizer to favor robust configurations over sensitive ones. Quickly, we obtained a system that does not loose a single message at 25% jitter, even in the presence of errors and bit stuffing. Figure 5 allows comparison between the optimized (solid lines) and original (dotted lines) system.

Supply-Chain Considerations

These experiments show that, even when no detailed information is available, "what-if" analyses lets OEMs explore and analyze a huge number of possibilities including a variety of jitter distributions, different error models, and many more not being presented further here. This way, the critical bottlenecks can be foreseen and eliminated systematically and extremely early in the design process, way before ECU prototypes are available for test. The technology further enables OEMs immediate reaction in order to eliminate these bottlenecks. There are several options.

For instance, once the "sensitivity analysis" of Section 4.1 has been conducted, jitter constraints for the most critical (or sensitive) messages can be formulated as requirements for ECU suppliers. In contrast to the seeming "data (un)availability problem" as it was mentioned in Section 3.3, we can obviously turn the tables and use analysis to produce data in the other direction with huge benefits for the supply-chain processes. With established simulation and test procedure, this is virtually impossible.

It is essential that those key requirements are determined early, when the design is still flexible and, for instance, CAN message IDs can still be changed to optimize the overall design. As another example, gatewaying strategies can be optimized. These are usually under the control of the OEMs and provide many parameters that can be tuned such as queue configuration, which is not shown further here.

The Situation of ECU Suppliers

So far, we have mostly concentrated on the situation of OEMs and what they can do to approach the network integration challenges. Interestingly, very similar advantages apply to the suppliers, too. These shall be quickly surveyed.

First of all, ECU suppliers benefit from clear requirements. Having such requirements early when the ECU design is still flexible is key, as late modifications can become extremely time-consuming and expensive for all involved parties.

Furthermore, we can -again-turn the table as ECU suppliers also have requirements on the incoming communication timing. Typical ECU control algorithms rely on new CAN message data arriving in a dedicated timely manner, such that the algorithms always process the most recent numbers. Roughly speaking, the message arrival timing is a property of the bus, so the OEM is in charge of providing such data. Again, the "what-if" analysis allows deriving such data early and ultimately avoids "late surprises". Without further demonstration, we summarize that both OEMs and ECU suppliers can use our SymTA/S technology to a) analyze their system (ECU or bus) based on real data or assumptions, and b) provide the data required by the other party and check if such requirements are met. And they can do so before prototypes are available for test. Besides other components, appropriate analysis methods for CAN as well as operating systems are available as analysis libraries for our SymTA/S tool suite.

Figure 6 illustrates the duality indicated. For the bus dimensioning the OEM requires data about ECU2 sending behavior. Likewise, the ECU3 suppliers requires data from the OEM. What is initially assumed and required, must later be guaranteed, and vice versa. Besides message jitters, which are one of the key dynamic properties of message timing, burst and other info can also be included.

This duality lets OEMs and ECU use a common interface [START_REF] Richter | Event Model Interfaces for Heterogeneous System Analysis[END_REF] for exchanging important design information in terms of data sheets and requirement specifications. The focus on the key integration aspects such as send/receive message jitters, deadlines, etc. allows the intellectual property of either party to be protected, as internal implementation details (e.g. ECU task priorities or gatewaying strategies etc.) need not be disclosed.

Iterative Refinement

With such a clear interface, the analysis can be repeated as new design details become available, incl. sensitivity, exploration, and optimization. Our flexible SymTA/S technology is able to consider TimeTable activation of messages and tasks, typically found in the automotive industry, considers operating system (OSEK) overhead, complex priority schemes with cooperative and preemptive tasks as well as hardware interrupts, and can be adjusted to specific project requirements and system mechanisms. The technical details are, however, not in the scope of this paper and can be found in [START_REF] Richter | Compositional Scheduling Analysis Using Standard Event Models[END_REF][START_REF] Jersak | Compositional Performance Analysis for Complex Embedded Applications[END_REF].

What is key is the practical possibility to perform the analysis at all. Newly appearing bottlenecks can be discovered quickly and immediate reaction is possible. Secondly and not yet mentioned, freezing certain design parameters can result in new flexibility for other decisions and allows trading the timing reserves and budgets for different components against each other. This ensures that, at any given point in time during the entire development process, the remaining flexibility and optimization potential can be controlled and exploited.

Conclusion

From these and other examples that we have studied, we conclude that the availability of timing information and the capability to exploit it, often makes a huge difference. In fact, ECU suppliers can perform analysis and provide all the necessary info, at the same time protecting their essential IP. The other way round, the OEMs can use "what-if" analysis and formulate requirements for the suppliers using the same "language". Furthermore, the experiments did not rely on any simulation or test environment. Quite to the contrary, OEMs can evaluate different network choices upfront and use our SymTA/S technology to dimension optimized and robust buses with known extensibility.

We forecast that the availability of such information will be an important requirement for OEMs when selecting suppliers. The ability to perform "what-if" analysis in rapid cycles even enables a multi-supplier risk-management [START_REF] Kruse | Towards Flexible Systems Engineering by Using Flexible Quantity Contracts[END_REF], possibly in combination with a penalty-reward model, that allows reacting to bottlenecks earlier than ever and in line with the projected road map.

This provides a new quality in the system-level integration process, as component integration along the supply-chain becomes more reliable and more systematic than ever before. The technology is available already now.

Figure 1

 1 Figure 1 Simple Load Analysis ExampleFigure1shows an example. Four ECUs produce bus traffic that accumulates on the shared bus. The resulting total traffic is 180kBit/s which represents a load of 36% on a 500kBit/s CAN bus.

Figure 3

 3 Figure 3 Information Required for Reliable Schedulability Analysis

Figure 4

 4 Figure 4 Jitter-Sensitive and Robust Messages

Figure 5 Message

 5 Figure 5 Message Loss due to Jitter before and after Optimization

Figure 6

 6 Figure 6 Duality of Requirements and Guarantees between OEMs and Suppliers

7.


F Frances

C Fraboul

J Grieu

Using Network Calculus to optimize the AFDX network

Keywords: Christian Fraboul, J AFDX, Network Calculus, optimization, genetic algorithms

Using Network Calculus to optimize the AFDX network

Overview of this paper

This paper sums up our work on the optimization of the latency and queue-size bounds of Airbus' A380's AFDX network, through the use of priorities. More precisely, it deals with the optimization problem of assigning priorities to the thousand traffic flows that are carried by this network, so that the queue-size bounds and the latency bounds calculated by our Network Calculus tool are the smallest possible. Thus, Network Calculus gives the metric that allows to compare two different priority assignments, and we present different techniques we have experimented in order to optimize the setting of priorities to the traffic flows: a variation on a Descent method, a tentative "brute-force" approach helped by Alpha-Beta reduction, and genetic algorithms. Trying to optimize a multi-dimensional problem with a single metric can be misleading, so we have also taken benefit of the multi-criterion capabilities of genetic algorithms to demonstrate how the network traffic designer can trade-off one criterion against another.

In section 2, we present the ARINC 664's deterministic networks and the Virtual Link notion that is at the heart of the AFDX.

In section 3, we give a taste of the deterministic proof methodology we applied to the AFDX, using Network Calculus. We also mention in section 4 how we have improved the bounds calculated by our Network Calculus tool through the notion of "groups" of Virtual Links. Then, section 5 presents the optimization problem and first attempts to address it with classic techniques. Finally, section 6 presents the results we obtained when applying genetic algorithms to this very large optimization problem.

The AFDX network

If Airbus hadn't chosen to have a network technology leap on the A380, the growth of communication needs between the avionics systems would have led to a tremendous amount of ARINC 429 buses [1]. By using a Full-Duplex Switched Ethernet technology for the interconnection of the essential systems (not for the truly critical systems yet, as every new technology has to prove itself first), Airbus knew that they could benefit from a huge decrease of cabling and a much more flexible connection. However, multiplexing all avionics communication flows on standard COTS Switched Ethernet would not have kept the guarantees brought by ARINC 429 buses (in terms of guaranteed bandwidth, segregation, determinism). Actually, traffic confluence inside Ethernet switches lead to variable latency, which we describe by the term of indeterminism. Moreover, without any further assumption on a limitation of the communication flows, the congestions in the switch output ports might lead to an overflow of queues, and thus to frame loss. This is why Airbus, by committing to the process of standardizing Ethernet for aeronautical needs (namely the ARINC 664 standard), proposed "profiled networks", which are entitled to adapt the IEEE 802.3, 802.1D and "IP" (RFC 1122) standards in order to fulfil specific performance or safety needs. For instance, a subset of profiled networks, called "deterministic networks", is defined for those aircraft network domains where quality of service (including timely delivery) is paramount, and AFDX (Avionics Full-Duplex Switched Ethernet [START_REF]ARINC specification 664P7, Aircraft Data Network, Part 7, Avionics Full Duplex Switched Ethernet[END_REF]) is the reference example of such networks. ARINC 664 requires that the guaranteed service is proven; in the case of AFDX, this implies a mathematical proof firmly establishes that:

no frame will be lost (i.e. no switch queue will overflow) the end-to-end delay of any frame is bounded and acceptable As we can see, these assertions don't guarantee absolute behaviour determinism, but only a weaker form of determinism which is sufficient to bring the guaranteed service required by essential avionics systems.

Thanks to the exact bandwidth regulated traffic control of AFDX, expressed by Airbus through the notion of "Virtual Link", we have been able to develop a method for the computation of the required queue size of the switches, and of the maximum latencies suffered by the virtual links at any node of the network [START_REF] Fraboul | Applicability of Network Calculus to the AFDX[END_REF]. This VL concept is described as an example of traffic control in part #7 of the ARINC 664 [START_REF]ARINC specification 664P7, Aircraft Data Network, Part 7, Avionics Full Duplex Switched Ethernet[END_REF]: actually, it can be seen as an analogy of the ARINC 429 bus, virtualized as a multicast traffic flowing through the Ethernet network. A Virtual Link is characterized by a unique identifier, one or more destination addresses, a minimal size of frames (S min ), a maximal size of frames (S max ), and a BAG (Bandwidth Allocation Gap) which defines the minimal time between transmission of two consecutive frames.

Determinism proof methodology

We have modelled the network switches and endsystems into elementary network entities (shapers, multiplexers, de-multiplexers, bounded-latency elements, etc.). For example, the End-System output capability is modelled this way: We then use Network Calculus results [START_REF] Cruz | A calculus for network delay, Part I: Network element in isolation[END_REF] [START_REF] Cruz | A calculus for network delay, Part II: Network analysis[END_REF] to describe VLs by arrival curves, and further Network Calculus studies to describe the minimal service offered by network elements [6] [7] [8] [START_REF] Agrawal | Performance Bounds for Flow Control Protocols[END_REF] [10] [START_REF] Boudec | Network Calculus[END_REF]. The Calculus gives the latency bound of any elementary network entity and for those elements that have a queuing capability, a queue-size bound expressed either in a number of bits or in a number of frames (with a simple majorization using S min ). Given an elementary entity that offers a service curve β to an input flow constrained by an arrival curve α , the calculus also brings the arrival curve α* of the output flow: α* = α ∅ β where α ∅ β is defined by:

( ) { } ) ( ) ( sup 0 u u t t u β α β α - + = ∅ ≥ [1]
We developed a Network Calculus tool that propagates these results on a complete network in a dataflow way, and were thus able to compute the latency and queue-size bounds in every element of the network.

A Calculus optimization: the "Group" concept

In [START_REF] Grieu | Preuve de déterminisme d'un réseau embarqué avionique[END_REF], we improved the Calculus of the AFDX bounds, defining "groups" of VLs that exit from the same multiplexer and enter another multiplexer together, i.e. Virtual Links that share two segments of path at least. The key issue is that the frames of those VLs are serialized once exiting the first multiplexer and thus they don't have to be serialized again in the following multiplexers. This Calculus optimization has been implemented in our tool, and it always gives tighter bounds (up to 40% better), so we never consider the simple Calculus without "groups" in this paper, and all quantitative results are rated against the bounds obtained on a network configuration with no priority assigned to the Virtual Links, but still calculated using this "group" optimization.

Priority Optimizations

In this paragraph, we present how we obtained better (tighter) bounds by studying different optimization techniques applied to the setting of either a low or high priority to each Virtual Link. A first important fact is that giving a priority to a Virtual Link is not supported by real-world arguments: Airbus is not willing to say some types of data are more critical than some others; all Virtual Links should provide the same guarantees. Thus, setting priorities shall only be seen as a mean to balance the load on the network: Virtual Links of "low" priority will still have to satisfy the same jitter and latency constraints. A second point to note is that splitting VLs in two low-and high-priority sets doesn't necessarily bring better bounds than having all VLs in the same high (or low) priority set (the bounds associated to this set will be used as a reference for all comparisons). With random settings of priority, we observed that some switch ports gained a better average bound (i.e. the mean of the two bounds, one for the low-priority VLs and the other for the high-priority VLs), but other ports suffered of a degraded average bound. Moreover, trying to locally optimize the bounds in some part of the network led to overall degradation in other parts of the network.

Network model update

We changed the switch model in order to take into account two priorities. Each switch output port first transmits high-priority frames in FCFS order, and then transmits low-priority frames when all highpriority frames have been transmitted. Two queues in each output port allow implementing this static priority policy, we thus modelled output ports by multiplexers offering different service curves to the high and low priority flows. These service curves have been extensively studied, e.g. in [START_REF] Boudec | Network Calculus[END_REF]: when

) ( * t R H and ) ( * t R L
( ) + - = ) ( . ) ( * t R t C t S L L [2]
From the Network Calculus tool implementation view, we had to change how groups are defined and handled: since flows of different priority are separately queued, a group can only contain flows of the same priority.

The optimization problem

Airbus' AFDX network allows assigning either a high or low priority to each VL in every switch output port. I.e. the switch configuration tables allow different priorities for a single VL in different output ports. However, it is more than likely that the same priority will be associated to a VL in every port of a given switch. We have studied a network consisting of 1008 VLs, and restricted our study to the case a single priority is associated to a Virtual Link, i.e. a given VL always has the same priority everywhere in the network. Thus, this leaves us with "only" 1008 priorities to set; this number would approximately triple is we allowed one priority per switch for each VL. Yet, with a binary choice of low or high priority, this means a discrete optimization problem of size 2 1008 . Of course, computing these 2 1008 ≈ 2.10 303 configurations is not possible in the span of a single human life: if the bounds for each switch port of a given configuration can be calculated in one second, about 10 295 years would be necessary for a brute-force approach. Last but not least, fixing priorities is a highly non-linear problem: changing a single VL's priority might have little or tremendous effect, and the level of this effect doesn't only depend on the considered VL. For example, the Network Calculus improvement we use (the "Group" concept [START_REF] Grieu | Preuve de déterminisme d'un réseau embarqué avionique[END_REF]) is largely affected when the VL priority modification makes it exit a group of VLs and rejoin another group.

Variation on a Descent method

This classic method loops on searching a better configuration than the current one, changing only one priority setting at a time. The algorithm stops when no single-modification leads to a better configuration. The method requires a way to compare the "value" of two configurations: here we use the scalar "maximum queue-size bound" value, i.e. we take the maximum of all queue size bounds. The descent method is known for its ability to find local optima's, but with a single priority modification at each step, it cannot exit these local optima's. We run the method a large number of times from random configurations but since we decided to reduce the time spent at each step (i.e. not to compare the 1007 single-priority modifications, which would imply spending a quarter of an hour in each step), the number of steps required to reach a local optimum was too high, because at each iterative step of the algorithm, the neighbour configuration chosen was only slightly better than the previous one, and thus we had to stop the iterative process before it reached a local optimum. However, when starting from known "good" configurations, the method quickly converged and gave us slightly better configurations, with few priority changes from the starting configuration. Thus this method is still interesting as a "polishing" final step, when a good configuration has been obtained by another method. We think that using a true steepest descent method instead of our variation would not have brought better results; it would only have changed the time spent to reach the local optimum (i.e. more time required in each step, but less steps required).

Sorting configurations in a binary-tree and using Alpha-Beta reduction

Here we assign a sequential number to each VL (how to assign these numbers is an important issue, more on this later), so that every choice of priority leads to two branches in a tree. A full setting of priorities is now represented by a full path from the tree root to one of the 2 1008 leaves. A "brute force" algorithm would require comparing all these leaves: as with the previous descent method, we again use the scalar "maximum queue-size bound" metric. However, the Alpha-Beta algorithm also requires a way to give a "value" to each non-leaf node in the tree. Thus, for non-leaf nodes, we compute the queue-size bounds of a partially loaded network, i.e. a network that only carries those VLs whose priorities have been set along the incomplete path leading from the tree root to the considered node. We then build upon the fact that any node below it will have a higher value (a larger max bound), simply because the corresponding network will carry additional traffic (more VLs have their priorities set). This allows Alpha-Beta to cut large branches of the tree. However, we knew that Alpha-Beta doesn't cut enough branches to allow a complete exploration of the tree in an acceptable time. So, we used Alpha-Beta as an algorithm to explore "small" modifications of priorities, starting from an already "good" configuration (this starting configuration was heuristically build, see paragraph 6.3). As stated earlier, the order of VLs down the tree is of primary importance: if the last VLs (those near the leaves) are such that changing their priorities has little impact, then the algorithm searches better configuration by trying priority changes of these VLs, and the gain is small. On the contrary, if the last VLs are such that their priorities greatly impact the calculated bounds, then the algorithm cut large branches (changing the priority of one of these VLs is quickly identified as giving worse bounds), so that it can quickly state that the setting of these last VLs is optimal, but it is likely it will not bring a better configuration. However, it is difficult to guess if a VL's priority will largely impact the bounds (its impact also depends on the priorities of the other VLs) and thus it is difficult to sort them in "ascending" or "descending" order of influence. In practice, we tried both cases: in a first run, we sorted the VLs in ascending S min order (S min is an important factor in the calculus of bounds on the number of frames). The algorithm found a better configuration than the starting one, by changing the 45 last priorities, but then it didn't find any further improvement (we stopped it after the evaluation of 5 millions of configurations). In a second run, we sorted the VLs in descending S min order, and the algorithm didn't find a better configuration despite evaluating the priority change of the 104 last VLs (thanks to large branch-cuts).

In conclusion, we found that Alpha-Beta is an easily implementable variation of brute-force, but reduction is not enough to explore the full 2 1008 -size tree. However, it allows gaining confidence that a good priority configuration is a local optimum, at least for a subset (a hundred at most) of chosen VLs: contrary to the previous method, this exhaustive exploration of a subset of priorities allows to exit from a local optimum to reach a better configuration.

Optimizing with Genetic Algorithms

Evolutionary algorithms [START_REF] Friedberg | A learning machine:Part II[END_REF][15] [START_REF] Holland | Outline for a logical theory of adaptive systems[END_REF][17] are renowned for their ability to handle very large optimization problems. Among them are Genetic Algorithms ( [START_REF] Holland | Cognitive systems based on adaptive algorithms[END_REF][19] [START_REF] Fogel | On the organization of intellect[END_REF]): these algorithms represent points in the optimization space by individuals, themselves represented by genes, and iterate generations of a population with reproduction and "natural" selection. Many evolution algorithms are available, but most of them are dedicated to a specific application. This is why we chose the PISA architecture [START_REF] Lu | Distributed Scheduling Based on Due Dates and Buffer Priorities[END_REF][22] [START_REF] Zhang | Providing End-to-End Performance Guarantees Using Non-Work-Conserving Disciplines[END_REF], which defines a simple interface that allows coupling an application field with an evolution algorithm. We were thus able to interface our specific Network Calculus tool to SPEA2 [START_REF] Zhang | Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks[END_REF], which is one of the best multi-criterion algorithms according to [START_REF] Zitzler | SPEA2: "Improving the strength pareto evolutionary algorithm for multiobjective optimization[END_REF]. SPEA2 evaluates the quality of an individual j by Sum i {S(i)} for all i in D(j), where D(j) is the set of individuals who dominate j (i.e. who are better than j on all criterions), and S(i) is the number of individuals in the whole population who are dominated by i. The overall algorithm of SPEA2 is given by the following six steps:

Step #1: Initialization, setting of the initial population (P 0 ) and archive initially empty (A 0 Of course we had to define how genetics rule our network priority world:

-An individual represents a priority configuration, i.e. a setting of priorities for all Virtual Links. The DNA sequence of an individual is a 1008-characters long string. The character located at position i reflects the priority of VLi and is either '1' for highpriority or '2' for low-priority.

-Each individual requires a full execution of our Network Calculus tool, in order to compute the queue size bounds and the delay bounds of all network multiplexers. Two criterions are used to identify dominated individuals: the largest queue-size bound and the average delay bound.

-The mutation operator modifies 2% of an individual's DNA, randomly chosen.

-Reproduction consists in concatenating the right part of a parent's DNA to the left part of the other parent's DNA: the cut point is also randomly chosen.

Finally, there are a number of global parameters for the algorithm that have been set as follows:

-Size of the initial population and of the archive: α=1000

-Number of individuals selected for reproduction: µ=100

-Number of children at each generation: λ=10 -Number of individuals in each tournament: P=3

6.1 Results obtained with a single evaluation criterion We first tried the algorithm with a single evaluation criterion, the largest queue-size bound (i.e. the largest of all the queue-size bounds computed by the Network Calculus tool, expressed in number of frames). Figure 4 shows that at generation #10000, the population had converged to individuals having a largest queue-size bound of 727, thus bringing a 6% optimization over the reference configuration (the one with all priorities set at the same level).

Figure 4: Generation convergence with a single evaluation criterion However, as we didn't want that this optimization could be done at the expense of many latency bounds, we decided to exploit the multi-criterion capability of SPEA2 and had it search configurations that minimize both the largest queue-size bound and an average of the latency bounds (each latency bound being weighted by the number of VLs that suffer of this latency bound).

Bi-criterion optimization with a random initial population

Figure 5 shows how the initial random population, the 1000 th generation and the 7000 th generation performed on the two selected criterions: average delay bound (horizontally) and largest queue-size bound (in number of frames, vertically). One can see that the algorithm converges to a better population, both horizontally and vertically. The figure gives a good understanding of the Pareto front: points that are not dominated on both criterions. Thus it gives an idea of the trade-off between the two criterions.

Figure 5: Bi-criterion convergence using a random initial population However, one can notice that despite a large optimization over the initial random population, the optimization is at most only 5% over the reference configuration. We concluded that the optimization problem is of such a big size that neither the random initial population nor the random mutations can cover enough diversity, and that the whole population converges towards "attraction zones", despite the diversity of the individuals inside a single generation. We thus increased the mutation probability and the impact of these mutations, along with a larger number of children per generation. Figure 6 shows the results obtained with these larger parameters.

Unfortunately, the results are not better: it appears that these parameters "boost" the algorithm, in the sense it converges faster, but the individuals of the last generations are not better than those obtained with the first parameters. Our intuition is that small frames are better assigned a high priority, so that large frames do not delay small frames, which would result in a bigger number of delayed frames and thus a larger queue-size (in terms of number of queued frames). The deterministic calculus of the queue-size bounds indeed shows the influence of the S min parameter (minimum size of frames for a given VL): the bound is reciprocally proportional to the minimum of all S min of a given priority. Thus we ordered the VLs in ascending S min order and populated the initial set of individuals with 1008 configurations ranging from the reference one (all VLs set to low-priority) to the equivalent final one (all VLs set to high-priority), each configuration having the next VL in this order set to high-priority. The 2000-sized population was completed with random configurations. Figure 7 shows the evolution of the generations obtained with this partially-chosen initial population.

Clearly, the good properties of a few good initial individuals are propagated to the whole population.

The largest queue-size bound is 25% more optimized than the no-priority setting.

Figure 7: Evolution with a heuristically-good initial population However, in order to better evaluate the added-value of the genetic algorithm, we show the following figure (Figure 8), where only the best individuals of the initial population are depicted, along with the complete last generation. This exhibits two groups of configurations: the first group consists of configurations whose average delay bound is less than 0.00135, and a largest queue-size bound ranging from 780 to 800 frames. At one end of this group, the network integrator can easily gain 41% on the average delay bound (compared to the no-priority configuration) without sacrificing much to the largest queue-size bound (only 4%). One can see that this group contains many of the initial heuristic configurations: this shows that the algorithm didn't found really better configurations. The second group of configurations contains those configurations that are better for the largest queuesize bound criterion (here we can see configurations that have a 31% gain on the largest queue-size bound compared to the reference configuration, and still also optimize the average delay bound by another 30%). Although the algorithm didn't find a really better configuration for the largest queue-size bound criterion, it found configurations with equal value on this criterion and better value on the average delay bound.

Conclusion

Optimizing the deterministic bounds calculated on the AFDX network is a very large optimization problem, offering the opportunity to several research directions. One could try to bring tighter Network Calculus results, but many of the theoretical results we used have already been proved as being optimal, i.e. the bounds can be reached. So, we think there is very little gain to hope from the Network Calculus theory itself. However, there surely are several ways to apply Network Calculus to calculate the bounds of the AFDX network. In [START_REF] Grieu | Preuve de déterminisme d'un réseau embarqué avionique[END_REF], we have gained up to 40% on the bounds, by aggregating segments of flows into groups. In this paper, we have presented another research direction that aims to get benefit from the static priority capability of the AFDX switches. This has turned to a priority setting optimization problem: how to choose either a high or low priority for each of the traffic flows. We have shown that this discrete optimization problem is so large that brute-force cannot handle it (solving it would require about 10 295 years). We have tried classic optimization techniques such as a variation on a descent method and an AlphaBeta search, but this has brought little gain, so we consider these methods can only slightly improve an already good priority configuration. We have also extensively used a Genetic Algorithm to search priority configurations for which our Network Calculus tool calculates tighter bounds, both from a global perspective (all the bounds are reduced in average) and from a focused perspective (the largest bound decreases too). Moreover, the multi-criterion capability of SPEA2 shows the Pareto front of our problem, and thus provides a full range of good priority configurations that help the network traffic designer to trade off one criterion against the other. On our traffic case study, we have thus been able to offer up to 41% gains on the average delay bounds, and up to 31% on the largest queue-size bound. Needless to say, these gains increase the scalability of AFDX, as they raise the potential for future additional traffic.

Glossary

AFDX

Figure 1 :

 1 Figure 1 : End-System output model

S

  are the arrival curves of the high and low priority flows (respectively), then the service curves offered by such a multiplexer to the highpriority flow is a β curve: max the maximum size of the low-priority frames, and C the output rate). And the low-priority flow is offered a service curve S L :

Figure 2 :

 2 Figure 2: Alpha-Beta cuts many branches (example figure shows cuts with diamonds)

Figure 3 :

 3 Figure 3: PISA architure

Figure 6 :

 6 Figure 6: Evolution with bigger diversity

Figure 8 :

 8 Figure 8: Added-value of genetic algorithm

size bound (in frames)

	700 750 800 850 900 950 1000 1050 1100 0.001 0.0012 0.0014 0.0016 0.0018 0.002 Largest queue-Initial gen. gen1000 gen7000	0.0022
		Average delay bound
		1100
		1050
		1000
		950
	Largest queue-	700 750 800 850 900 0.001 0.0011 0.0012 0.0013 0.0014 0.0015 0.0016 0.0017
		Average delay bound

size bound (in frames)

	1200
	1100
	1000
	900
	800
	700
	600
	500
	400
	0.0012	0.0013	0.0014	0.0015	0.0016	0.0017
	init gen1000 gen3000

Average delay bound Largest queue-size bound (in frames)

				initialisation gen2000
		850
	max des bornes (trames)	550 600 650 700 750 800
		500
		0.0012	0.00125	0.0013	0.00135	0.0014	0.00145	0.0015
				espérance du délai
								initial gen.	gen100 gen2000

  Avionics Full-Duplex Switched Ethernet DNA Deoxyribonucleic Acid FCFS First Come First Served ERTS Embedded Real Time Software PISA a Platform and programming language independent Interface for Search Algorithms SPEA Strength Pareto Evolutionary Algorithm VL Virtual Link