Hajime Tazaki

Frédéric Urbani • Emilio Mancini

Mathieu Lacage

Daniel Câmara

Thierry Turletti

Walid Dabbous

Direct Code Execution: Revisiting Library OS Architecture for Reproducible Network Experiments

Keywords: D.4.8 [Operating Systems]: Performance-Simulation, D.2.5 [Software Engineering]: Testing and Debugging-Testing tools Direct Code Execution, Emulation, Experimentation, Linux, Network Stack, Simulation, Software Development

We describe the first capability, to our knowledge, to execute nearly unmodified applications and Linux kernel code in the context of a widely-used open source discrete event networking simulator (ns-3). We propose Direct Code Execution (DCE), a framework that dramatically increases the number of available protocol models and realism available for ns-3 simulations. DCE meets the goals recently proposed for fully reproducible networking research and runnable papers, with the added benefits of 1) the ability of completely deterministic reproducibility, 2) the scalability that simulation time dilation offers, 3) capabilities supporting automated code coverage analysis, and 4) improved debuggability via execution within a single address space. In this paper, we describe in detail DCE, report on packet processing benchmarks and showcase key features of the framework with different use cases. We reproduce a previously published Multipath TCP (MPTCP) experiment and highlight how code coverage testing can be automated by showing results achieving 55-86% coverage of the MPTCP implementation. Then we demonstrate how network stack debugging can be easily performed and reproduced across a distributed system. Our first benchmarks are promising and we believe this framework can benefit the network community by enabling realistic, reproducible experiments and runnable papers.

INTRODUCTION

The need for reproducible research in computational sciences has been expressed many times for decades [START_REF] Buckheit | Wavelab and reproducible research[END_REF][START_REF] Claerbou | Electronic documents give reproducible research a new meaning[END_REF][START_REF] Knuth | Literate programming[END_REF]. However, it was not common for networking researchers to reproduce results shown in the literature because of many reasons: not enough details in papers on scenarios, complexity to reproduce the same scenarios, no access to code and scripts, difficulty to reproduce the same in-field conditions, etc. Only recently networking researchers have started to alleviate the problem, by describing in further details their experimentation scenarios, making their code and scripts available to the network community and sometimes by using tools that improve the repeatability of the experiments [START_REF] Quereilhac | Nepi: An integration framework for network experimentation[END_REF].

Ideally, any researcher should be able to reproduce results shown by her colleague, not only to verify the results published in the paper but also to easily evaluate and debug the protocol on other scenarios with different scales, compare it with other approaches and possibly propose enhancements. In this paper, we define full reproducibility as the ability to provide all the above-mentioned requirements. This would lead to more credible and runnable publications [START_REF] Handigol | Reproducible network experiments using container based emulation[END_REF][START_REF] Jourjon | A portal to support rigorous experimental methodology in networking research[END_REF][START_REF] Tazaki | DCE Cradle: Simulate Network Protocols with Real Stacks for Better Realism[END_REF].

Handigol et al. introduced the following requirements, which are more or less complex to satisfy to ensure experiments reproducibility [START_REF] Handigol | Reproducible network experiments using container based emulation[END_REF]:

Experimentation realism. This requirement is met when the three following properties are provided: functional realism, i.e., the software implementation of the system under test (SUT) is the same than the one used in the real world; timing realism, i.e., the timing behavior of the SUT is similar to real world; and traffic realism, i.e., the traffic sources used in the experiment reflect the ones from the real world.

Topology flexibility. Experimental environments and input parameters of the SUT should be configurable with fine-grained control so that any network topology is possible to evaluate.

Easy and low cost replication. It should be easy and inexpensive to replicate an experiment.

Container-based Emulation (CBE) with fidelity monitoring (Mininet-HiFi [START_REF] Handigol | Reproducible network experiments using container based emulation[END_REF]) has been demonstrated as an efficient tool to address the above requirements. However, this approach has two main concerns 1 . First, it mandates that enough computing resources are available to run the scenario in real time and requires to monitor the CPU load of the emulation machine to ensure that performance results are meaningful. This constraint significantly restricts the range of possible experimentation scenarios that can be evaluated. Second, since each experimental node runs in a distributed way with CBE, identifying and debugging implementation issues of the SUT is a painful task because there is no integrated control of the software execution.

Therefore, we argue that it is important to satisfy the two following requirements in addition to the aforementioned:

Experimentation scalability. The range of possible experimentation scenarios should not be limited by the resources of the machine that run the experiments.

Easy debugging. It should be easy to identify possible issues in the SUT and debug them, in particular in presence of a distributed system running on multiple nodes.

In this paper, we aim to satisfy all of the five abovementioned requirements by proposing Direct Code Execution (DCE), a framework that enables fully reproducible network experimentation. DCE takes the traditional library operating system (LibOS) approach such as Exokernel [START_REF] Kaashoek | Application performance and flexibility on exokernel systems[END_REF] in its core architectural design to enable running and evaluating real network protocol implementations. Since DCE uses a single-process model as a virtualization primitive, the amount of glue code is relatively higher than others (as detailed in Section 2.4). However, tightly integrated design with the ns-3 discrete-event network simulator benefits from a rich network environment allowing fully reproducible experiments.

Our contributions in this paper include:

• The design and implementation of Direct Code Execution 2 , a framework that enables realistic and reproducible network experiments at large scale with debugging facilities by integrating real Linux kernel and application code with the ns-3 network simulator.

2 DCE is available at http://code.nsnam.org/ns-3-dce.

• Packet processing benchmarks to analyze its performance and comparison with the Mininet-HiFi CBE approach.

• Reproducible network experiments with different use cases that demonstrate the benefits of DCE.

The paper is organized as follows: we present the design and implementation of DCE, our proposed framework, in Section 2. Then we present micro-benchmarks obtained with DCE and Mininet-HiFi in Section 3, and showcase features of DCE with different use cases in Section 4. We discuss some future research directions in Section 5. Finally, in Section 6, we review the prior work done to enable reproducible network experiments and conclude the paper.

DCE ARCHITECTURE

The design of DCE takes its core idea from the library operating system (LibOS) architecture [START_REF] Kaashoek | Application performance and flexibility on exokernel systems[END_REF] to satisfy the requirements for reproducible network experimentation. DCE is structured around three separate components as depicted in Figure 1. First, the lowest-level core module handles the virtualization of stacks, heaps, and global memory. Second, the kernel layer takes advantage of these services to provide an execution environment to the Linux network stack within the network simulator. Third, the POSIX layer builds upon the core and kernel layers to re-implement the standard socket APIs used by emulated applications.

Virtualization Core Layer

Contrary to other user space virtualization environments such as UML [START_REF] Dike | User Mode Linux[END_REF], DCE executes every simulated process within the same host process. This single-process model makes it possible to synchronize and schedule each simulated process in turn from the simulator event loop without having to use inter-process synchronization mechanisms. Moreover, it allows users to trace the behavior of an experiment across multiple simulated processes without the need of a distributed and usually complex debugger. One of the downsides of this single-process design is that we cannot rely on the host operating system to release the resources associated with each simulated process. So, it is necessary to carefully track each resource allocated by each process to handle gracefully their termination within a longrunning simulation.

For instance, by default, we manage the stack area and the Program Counter of each simulated process by creating, switching to/from and destroying a host-level thread as necessary. Threads in each simulated process are managed by our task scheduler with the synchronization in simulated host and isolated from the other simulated hosts' threads. This allows the host-level debugger to automatically gain knowledge about the location of our simulated stacks through the list of threads, thus ensuring very reliable backtraces during debugging sessions. Optionally, we provide a more efficient ucontext-based [START_REF] Adya | Cooperative task management without manual stack management[END_REF] stack manager to allocate stack space with mmap and control the Program Counter of each simulated process by saving and restoring CPU registers entirely in user-space.

Similarly, we take great care to track and isolate the heap of each simulated process. In particular, we allocate each heap within large mmaped blocks that can easily be reclaimed as needed and then slice each of these memory blocks with a Kingsley [START_REF] Kingsley | Description of a very fast storage allocator, Documentation of 4[END_REF] allocator to implement the malloc and free functions for simulated applications.

The most challenging aspect of the single-process model, though, is the virtualization of the global memory. Since the objective of the host program loader is to ensure that every process contains no more than one instance of each global variable, we provide a specific loading mechanism to instantiate once the same global variables for each simulated instance.

To do so, each simulated process lazily saves and restores upon context switches its private copy of the global variables to/from the shared data section which was setup by the host ELF loader upon program loading.

Optionally, on a few host systems (Table 1), we provide a replacement ELF loader that is able to avoid these data copies upon context switches by directly allocating a new pair of code and data sections for each instance of the same simulated process. This improves the memory usage of typical experiments very marginally but runtime often improves by a factor of up to 10 [24].

Kernel Layer

On top of these core virtualization primitives, the Kernel layer embeds the network protocol implementations found in the Linux kernel. This layer communicates with ns-3 through two well-defined interfaces. At the bottom of the Linux network stack, MAC-level network packets enter and leave the kernel through a fake struct net_device that communicates directly with the ns-3 C++ equivalent, ns3::NetDevice. At the top of the network stack, applicationlevel payload is exchanged with socket-based applications through the kernel-level socket data structures.

Since most of the network stack configuration happens through netlink sockets, users can benefit from the standard Linux user space command-line tools (ip, iptables) to set up the necessary IP-level configuration (IP addresses, forwarding tables, firewalls, etc.). Other parameters that are only accessible through the sysctl filesystem can also be controlled by specifying path/value pairs. Each pair is set automatically by accessing the sysctl tree of static configuration variables.

Because we have tracked the most recent version of the Linux kernel for almost five years, the support code which provides the execution environment for this Kernel layer has been designed to be robust to kernel version changes. First, we minimized the number of changes to existing kernel code (20 lines across 2 files) and we targeted these changes to files that are stable. Second, we took advantage of the Linux platform abstraction API by integrating the remainder of the support code as a new independent architecture.

POSIX Layer

Given the significant size of the POSIX specifications, our POSIX implementation used to replace the traditional glibc has been developed in an incremental way to provide support for the subset3 of features used by the applications we already tested over DCE. As such, although we do not provide full API coverage, we have made steady progress (see Table 2) towards being able to run most C-based applications of interest out of the box.

Most API implementations are trivial pass-thru to the corresponding function in the host C library except for those which access kernel-level resources. In particular, time-related functions (e.g., gettimeofday( 2 The new socket implementation is similarly un-eventful since it merely acts as a straightforward translator layer between the application and either kernel sockets from the Kernel module or ns-3 sockets that provide access to the ns-3 TCP/IP stack.

One of the most challenging components of this POSIX implementation is the support for the fork() function. Traditionally, single address space-based POSIX implementations provide only the vfork() function because it is not easy to make two processes, sharing the same address space, see different values at the same memory location. By contrast, DCE supports the two above functions to facilitate the integration of a larger set of applications. This feature is implemented by tracking which memory locations are shared by which processes and by lazily saving and restoring these shared locations upon context switches.

Discussion

The LibOS approach that encapsulates kernel network stacks into a user space library, combined with the singleprocess model used in the DCE virtualization core, offers broad capability in code inspection. As a result, our design provides a complete solution for reproducibility, debuggability (through controllability), and experimentation scalability to network experiments.

The essential strengths of the LibOS approach are characterized as follows. First, it uses minimized virtualization, which allows to run multiple instances of a node on a singleprocess to obtain the controllability of experimental entities, as well as fast execution by simplifying the set up and by removing the need for (virtual) hardware initialization, filesystem checking and mounting. This optimization is particularly important when conducting a large number of experiments involving many instances of a node, as they usually take a large amount of time to initialize and execute. This has a significant impact on the easy and low cost replication requirement and represents a clear plus for the DCE framework. Second, the integration with the ns-3 network simulator enables to obtain a deterministic network stack behavior, which is required for reproducible experimentation. This determinism also benefits the experimental scalability, since experimental scenarios are not bound to the real-time constraint of available resources. Moreover, it offers a widely configurable network environment for testing purpose, which is useful to analyze previous work or network experiments using different parameters space to the System Under Test. Finally the single-process model used in DCE facilitates debugging across distributed nodes.

However, DCE suffers from several limitations. First, the use of virtual clock prevents possible interactions with the external world of ns-3 such as real routers in the Internet. Second, contrary to lower-level CPU virtualization technologies, DCE requires API-specific glue code for its POSIX and kernel support. New protocol implementations that at-tempt to use previously un-implemented APIs need extra work. In practice, though, as our coverage of the POSIX API increases, the probability of needing a missing function decreases. Our experience leads us to believe that we have reached sufficient coverage for a wide variety of applications. Finally, in very rare cases, protocol implementations that execute busy loops require modifications to behave correctly within DCE.

One of the concerns of using virtual clock is the timing accuracy with respect to real environments. A previous study [START_REF] Tazaki | DCE Cradle: Simulate Network Protocols with Real Stacks for Better Realism[END_REF] presents a high-level analysis of the TCP performance between DCE-based Linux network stack and real Linux environment, and the result shows some differences between them (25-30% low goodput of DCE), but also gives similarity between them.

Although the single-process model used in DCE brings key features, it is not able to scale with very large simulation scenarios, involving millions of nodes. In such a case, a solution is to use Message Passing Interface (MPI)-based distributed simulation as a built-in service of ns-3 [START_REF] Renard | A performance and scalability evaluation of the ns-3 distributed scheduler[END_REF]. This gives the opportunity to add experimental physical machines when necessary, although it breaks the DCE single-process model, and so, makes debugging more complex.

Integrating a New Protocol

While the details4 of how a new protocol can be integrated within DCE vary a lot, we have observed a few recurring patterns over the past few years. In general, most of the work is relatively minor: it ranges from adding a few passthrough functions for newly-used POSIX functions to adding to the kernel build the files that contain newly-used generic functions. In some cases, extra work might be required to add support for new functionality, especially for POSIXbased protocol implementations. For example, when a new protocol uses a thread synchronization primitive that we do not support yet.

Kernel-based protocols rarely create problems in and of themselves. However, when these protocol implementations are based on ancient versions of the kernel, it can be sometimes necessary to first port them to a more recent Linux kernel before they can be used in DCE.

In the following sections, we evaluate the performance of DCE and compare our approach with other techniques.

PERFORMANCE EVALUATION

To investigate the performance overhead of packet processing that is consumed during transmitting and forwarding at simulated nodes, we measure the maximal packet processing rate that the host machine is able to process. The experiments were performed on an Intel Xeon 2.8 GHz with 8 GB of RAM, and the virtualized network stack from the Linux 2.6.36 kernel. We set up a linear daisy chain topology, where nodes are arranged in a line. Every node, apart from the two nodes at the ends, is connected to two other nodes as depicted in Figure 2. A UDP constant bitrate flow (100 Mbps) is transmitted from the client node to the server node. To avoid congestion issues, the link bandwidth is set to 1 Gbps, higher than the data sending rate.

Emulated network technologies working in real time have their capacity bounded by the host machine processing power and by the size of the emulated topology. DCE, instead, runs in simulated time so it can handle through time dilation all the traffic without data losses, even though the experiment may sometimes take longer to run than the real-time scenario would take. In other words, in DCE only the execution time of the experiment depends on the hardware capacity, while the experiment results are not impacted by the available resources of the machine. Here, we compare DCE with Mininet-HiFi [START_REF] Handigol | Reproducible network experiments using container based emulation[END_REF], which is one of the most promising real time emulation networks tool available. We used Mininet-HiFi Version 2.0.0 over an Ubuntu machine running Linux 2.6.36 kernel, the same used for the DCE tests. clock time decreases as the number of nodes in the network increases. This indicates Mininet-HiFi has lower overhead than DCE to process packets which means that reproducing experiments with DCE might take longer time than with Mininet-HiFi. This is not, however, the most important performance metric when reproducing network experiments.

In order to illustrate the limit beyond which experimental results are not accurate, we report in Figure 4 the maximum throughput that Mininet-HiFi is able to handle. With the machine used to perform the tests, the upper-bound traffic for Mininet-HiFi remains stable when the number of nodes is less or equal to 16. When the number of nodes exceeds 16, we observe the presence of packet loss and that the packet processing capacity starts to decrease. This behavior is expected because the machine used for emulation has limited available hardware resources which may impact the performance of real time emulation of CPU-greedy experiments.

To analyze the relationship between the execution time and the data rate for different number of nodes with DCE, we sent a constant bitrate for 100 simulated seconds. We ran the experiment for different data rates and number of hops. In particular, in Figure 5, the data rates from 5 to 100 Mbps, and for 4 to 32 hops are reported. For less complex experiment scenarios (with lower number of nodes and/or sending rate), DCE runs the experiments faster than it would take to run in the real world (i.e., 100 seconds). As expected, the measured execution time linearly increases with the amount of traffic handled during the simulation, matching closely their linear regression.

DCE USE CASES

This section illustrates key features of the DCE framework with different use cases. First, we replay an existing network experiment found in the literature with the same software over DCE ( § 4.1). Then, we evaluate the degree of configurability of the network environment offered by DCE using the code coverage metric ( § 4.2). Finally, we showcase DCE debugging facilities on distributed nodes ( § 4.3).

Experimentation Reproducibility

In this section, we evaluate the reproducibility of DCE with Linux network stack experimentation by replaying an experiment described in the literature: a Multipath TCP (MPTCP) experiment presented in paper [START_REF] Raiciu | How hard can it be? designing and implementing a deployable multipath tcp[END_REF]. We present 1) the ability of rough reproducibility of an existing experiment by using the same software, and 2) full reproducibility of existing experiments when conducting the experiment with DCE on different versions of the OS.

MPTCP is an extension of the standard TCP allowing to use multiple subflows with different IP addresses without modifying user space applications. Basically, this new transport protocol makes it possible to increase the throughput of an application by running it over multiple links. In this use case, two wireless links (LTE and Wi-Fi) are set up on a simulated host and these two links are simultaneously used to increase the application throughput. Note that in the original scenario [START_REF] Raiciu | How hard can it be? designing and implementing a deployable multipath tcp[END_REF], a 3G connection was used instead of LTE, but we had to replace it with a LTE link of similar characteristics because such a 3G link is not yet available within ns-3.

Figure 6 illustrates the network setup for this experiment along with the plot from the original experiment 6 . We created this topology with ns-3 version 3.17 running over Ubuntu 10.04 x86 64 version. Then we configured DCE to run the MPTCP Linux implementation [START_REF] Barré | Linux Kernel implementation of MultiPath TCP[END_REF], the iproute utility, and iperf without any modification to the original implementations 7 . Our approach, based on simulation virtual time, does not require specific machine setup as it is the case in the original experiment since the CPU and memory re- 7 reports the average received goodput at the right node (Rx) using a single TCP connection over Wi-Fi, a single TCP connection over LTE and an MPTCP connection, along with the 95% confidence interval computed for 30 replications using different random seeds in function of the receive/send buffer size. Unsurprisingly, we note that the goodput obtained with the DCE-based experiment increases when the buffer size increases as the original paper demonstrated, but the performance differs from the original result in the following ways. First, for the two TCP measurements (over LTE and Wi-Fi), no significant goodput improvement is observed when increasing the buffer size, while the impact is more noticeable on the TCP over 3G link experiment of the original paper. Second, the maximum goodput achieved for MPTCP is ranging from 2.2Mbps to 2.9Mbps while it is ranging from 2Mbps to 3.2Mbps in the original paper. The differences observed could be due to different end-to-end delays between the two experiments, as the round-trip-time can have a significant impact on the throughput performance.

Although we observe some differences with the original performance results when using the same software implementations, DCE could reproduce a similar trend of results for the MPTCP goodput. Note that DCE performance results are similar to the ones reported in [START_REF]MPTCP Wireless Performance[END_REF] with Mininet-HiFi, where authors also noticed that link characteristics have a high impact on goodput performance.

In addition to the above experiment and for proof of concept, we conducted the same simulation with four different environments (Ubuntu 12.04 64bits version on physical ma-chine, CentOS6.2 64bits, Ubuntu 12.10 64bits, and Ubuntu 12.04 64bits versions over KVM). Performance results obtained (shown in Table 3) are rigorously identical across all the different environments. This full reproducibility obtained with deterministic performance results is an important asset while [START_REF]MPTCP Wireless Performance[END_REF] reproducing experiments of other researchers, (2) analyzing the impact of some parameters on the performance of the system or (3) comparing different implementations of the same protocol in the same network conditions.

Increasing Code Coverage

The second use case aims to demonstrate DCE flexibility to configure the network environment parameters of experiments by examining the code coverage of the networking protocol stack under test. Code coverage is usually used as a quality metric of software development to measure how thoroughly test programs exercise with the system under test. However, it is also useful to understand how many parameters an experimental system exposes in a specific network experiment since the number of lines, functions, and branches covered by test programs reflect the number of different inputs (i.e., parameters) injected into the system under test with the support of ns-3. Moreover, coverage tests shall be deterministically executed in order to ensure they cover the whole implementation. So, the virtual clock of ns-3 is helpful in such a case.

For this use case, we used the same MPTCP code as in § 4.1 and wrote four test programs by using iproute utility for IPv4 and IPv6 addresses configuration, quagga to set up route information, and iperf as a traffic generator in the experimental topology. We also added an Ethernet type of link with different packet loss ratio and link delay to induce the behaviors of protocols. Then we ran these test programs 4. We do not yet cover 100% code of MPTCP, which requires additional effort to write test scenarios and programs 8 . However, the high code coverage (between 55-86 %) has been achieved with a small amount of effort, with about 1K LoC for four test programs in a couple of days in our case including different network topologies, different traffic patterns, as well as randomized values to link errors such as packet corruptions and losses.

This use case demonstrates that DCE allows one to configure various parameters for network experiments in a flexible way with the interactions of publicly available user space applications (e.g., iperf, quagga, and several Linux command line utilities), and without much effort for writing test programs.

Easy Debugging

This third use case illustrates the fine-grained debuggability feature of DCE by conducting dynamic memory analysis using the valgrind tool, and per-node debugging with gdb. What makes the use of such analysis tools with DCE straightforward is that this framework encapsulates the network stack into a user space library with a single process.

valgrind: valgrind is a dynamic program analysis tool that includes key features for programmers such as memory error detection. DCE jointly used with valgrind allows to investigate, in a reproducible environment, memory errors in a network stack implemented within the kernel space. Furthermore, this functionality is also available for programs that run on multiple distributed nodes using a single valgrind profiler.

Table 5 reports errors detected by valgrind with 2.6.36 version of the Linux kernel running over DCE. Although all tests including IPv4/IPv6 tcp, udp, raw socket, and Mobile IPv6 are passed, we successfully detected two errors related to invalid access of uninitialized memory, which still exist in the latest version of Linux kernel 9 .

gdb: The single-process model used in the DCE virtualization core facilitates debugging of network stacks. For example, it is possible with DCE to inspect a problematic state by putting a breakpoint in the code of a specific node. Although many solutions are available to debug distributed processes in a single debugger front-end, DCE has the specificity to provide full reproducibility of bugs with determinis- 8 The latest result is available at http://ns-3-dce.cloud. wide.ad.jp/jenkins/job/daily-mptcp/cobertura. 9 Linux 3.9.0 (June 2013)

Wi-Fi

Wi-Fi tic behavior of network protocols, which helps a lot in identifying implementation issues.

To demonstrate the following debugging session, we built the basic network topology illustrated in Figure 8. This scenario simulates a node handoff across two Wi-Fi access points along with signaling messages exchanged to provide mobility transparency through the Mobile IPv6 protocol implementation of the Linux network stack. We used the umip [START_REF]UMIP -Mobile IPv6 and NEMO for Linux[END_REF] user space application for Mobile IPv6 signaling over DCE. Figure 9 shows the debugging session corresponding to the bug detected by the Linux kernel community [START_REF] Wakoond | Message corruption with hao and route2 XFRM rules[END_REF]. Basically, we inspect the state of a specific node when a binding registration message transmitted by the mobile node reaches the Home Agent (HA); we put a breakpoint in node number 0 (corresponding to the HA) in order to analyze the change of state triggered by the mobile node movement.

It is worth noting that the memory analysis done with valgrind as well as the sequence obtained with gdb, shown in Figure 9, are deterministic. In particular, possible incorrect memory accesses and message transmission times obtained for the umip application, for the node movement, and for the handoff duration will remain identical to those obtained in different runs. In this manner, bugs can easily be reproduced, which is a key feature while debugging code, especially in distributed systems. Note that it is possible to add randomness into the simulations, such as packet arrival timings, process scheduling timings, random failure injections in a controlled manner thanks to the ns-3 pseudo randomizer. In particular, this may help in identifying bugs dependent on specific timings or conditions.

FUTURE DIRECTIONS

In this section we present some other uses of DCE along with possible future research directions.

On-demand network stack experimentation over public network testbeds. Numerous research activities concern the design of virtualization primitives specific to network emulation testbeds (NET). One of them focuses on how to enable fine-grained privileged access for users on public testbeds such as PlanetLab [START_REF] Bhatia | Vsys: a programmable sudo[END_REF][START_REF] Peterson | A blueprint for introducing disruptive technology into the Internet[END_REF]. In such a network platform, resources are shared among a bunch of users and are controlled by the testbed operator. In particular, it is necessary to prevent conducting experiments that require network stack modifications on testbed nodes. In such a case, DCE is an interesting approach to consider because it enables to run, at user space, a new network stack without requiring root privileges. For instance, this feature is very useful to study the performance of new network protocols implemented in kernel space over shared testbeds such as PlanetLab.

Lightweight virtualization. A user space network stack is similar to a lightweight virtualization primitive that can be used on resource-constrained environments such as smartphones or tiny sensors. It is likely that the need of lightweight virtualization to introduce new network protocols and architectures over resource-limited nodes, without replacing new kernel network stack, will increase over the next few years.

Foreign OS support. DCE is a self-contained entity in user space. It is able to execute network stacks with multiple versions of Linux kernels 10 . This feature enables to evaluate the impact of different operating systems on the performance of the system under test by just replacing the kernel layer part ( § 2.2) with different operating system, for example, a BSD-based OS on Linux host. This is not possible to perform with CBE approaches [START_REF] Bhatia | Trellis: a platform for building flexible, fast virtual networks on commodity hardware[END_REF][START_REF] Handigol | Reproducible network experiments using container based emulation[END_REF][START_REF] Hibler | Large-scale virtualization in the emulab network testbed[END_REF][START_REF] Lantz | A Network in a Laptop: Rapid Prototyping for Software-defined Networks[END_REF][START_REF] Puljiz | IMUNES Based Distributed Network Emulator[END_REF][START_REF] Tripathi | Crossbow virtual wire: network in a box[END_REF] because they should share the kernel image between the hosted operating system and the guest emulated host.

RELATED WORK

Full virtualization provides generic testing environments by running network software prototypes in VMs but suffers from scalability limitation (due to memory and CPU overhead) and non-reproducibility (due to variability introduced by hypervisor scheduling). This section highlights previous research efforts to enhance the evaluation of network experimentation, in particular on virtualization . We classify hereafter the various approaches and discuss if they meet the requirements identified in Section 1, especially the experimentation reproducibility, scalability and easy debuggability.

Container-based emulation (CBE) (CORE [START_REF] Ahrenholz | CORE: A real-time network emulator[END_REF], Trellis [START_REF] Bhatia | Trellis: a platform for building flexible, fast virtual networks on commodity hardware[END_REF], IMUNES [START_REF] Puljiz | IMUNES Based Distributed Network Emulator[END_REF], vEmulab [START_REF] Hibler | Large-scale virtualization in the emulab network testbed[END_REF], Crossbow [START_REF] Tripathi | Crossbow virtual wire: network in a box[END_REF], Mininet [START_REF] Lantz | A Network in a Laptop: Rapid Prototyping for Software-defined Networks[END_REF], Mininet-HiFi [START_REF] Handigol | Reproducible network experiments using container based emulation[END_REF]) is based on lightweight virtualization technologies enabling a large number of VMs to run on the same emulation machine. This approach allows a wide range of network environments to be fed within the ex-periments, without the hurdle of building/maintaining real networks. However, as all containers must run on top of the same kernel, there is no strong separation between the virtual systems. The behavior of the network stacks is therefore not completely reproducible as it depends on the type of virtualized OS scheduler and on the resources available on the emulation machine. Recently, Mininet-HiFi [START_REF] Handigol | Reproducible network experiments using container based emulation[END_REF] has proposed to alleviate this problem by adding resource isolation to reduce variability and monitoring to estimate the performance fidelity obtained from network experiments. However, performance results obtained are only meaningful and reproducible when the CPU resources of the emulation machine are sufficient to run the experiment in real time, which limits the scale of scenarios that can be evaluated with such an approach.

Time Dilation [START_REF] Gupta | To infinity and beyond: time-warped network emulation[END_REF] provides the illusion to an operating system and its applications that time is slower than physical time. Data arriving from a network interface will therefore appear to arrive faster, but the system will experience more cycles per perceived second from the processor and the number of cycles available to each arriving byte remains constant. This approach is proposed mainly to check whether the network is the bottleneck for a given system, providing a low-cost mechanism for determining the potential benefits of higher performance network interconnects before committing an upgrade. The idea is however more general and can be applied to adjust the clocks between network stacks running in the VMs and an underlying emulated network, thus removing the real time operation constraint required to get meaningful results.

SliceTime [START_REF] Weingärtner | SliceTime: a platform for scalable and accurate network emulation[END_REF] provides speed adjustment for a real software prototype running in a VM on top of a simulated network topology. Instead of slowing down the time by a constant factor as done by time dilation, a synchronizer controls the execution of the network simulation and the software prototypes and interrupts the execution of the prototype or the simulation at times to achieve precise clock alignment. To enable this suspension, the software prototypes are hosted inside virtual machines for means of control. This approach allows better scalability and reduces variability. Our approach based on inserting real network or application software in the ns-3 simulator provides implicit synchronization between the software and the simulated network topology as we are only using the simulation time. It also provides 'automatic' time dilation so that a large-scale experiment is run with the minimum slowdown while still providing accurate results.

Time traveling-based virtual machines (TTVM [START_REF] King | Debugging operating systems with time-traveling virtual machines[END_REF]) was proposed to address the difficulties associated with debugging operating systems (as cyclic debugging does not work because of non determinism). By recording enough information to replay a long-term execution of an operating system using ReVirt [START_REF] Dunlap | ReVirt: enabling intrusion analysis through virtual-machine logging and replay[END_REF], TTVM enables a programmer to navigate backward and forward arbitrarily through the execution history of a particular run and to replay arbitrary segments of the past execution, even in the presence of non determinism. This feature can be exploited to provide timing realism in networking experiments even when they are not run in real time. However, the bootstrap time required for each OS instance takes a significant amount of time 11 , which limits the practicality of this technology to repeat experiments. Simics [START_REF] Magnusson | Simics: A full system simulation platform[END_REF] is a full-system simulator used to run unchanged production binaries of the target hardware at high-performance speeds. Simics has the ability to execute a in the forward and reverse direction. Reverse execution can illuminate how an exceptional condition or bug occurred.

User-space network stack implementation (Entrapid [START_REF] Huang | The ENTRAPID protocol development environment[END_REF], Rump [START_REF] Kantee | Rump file systems: Kernel code reborn[END_REF], Alpine [START_REF] Ely | Alpine: a user-level infrastructure for network protocol development[END_REF], nfsim [START_REF] Russell | nfsim: Untested code is buggy code[END_REF]) takes a different approach than DCE to enable easy debug of network protocol stacks. Basically, the network stack kernel code is transformed into a user space library, so that applications can bypass the host network stack in favor of the library. Entrapid [START_REF] Huang | The ENTRAPID protocol development environment[END_REF] reuses BSD 4.4 kernel code and allows multiple instances of the network stack to run in a single process. Rump [START_REF] Kantee | Rump file systems: Kernel code reborn[END_REF], which is already integrated in the NetBSD kernel, extends the latter approach to filesystem code as well as network stacks. While Entrapid and Rump offer debugging facilities and allow reproducing network experiments when enough resources are available on the machine, the use of wall clock time impedes experimentation reproducibility as it is the case with CBE approaches. Alpine [START_REF] Ely | Alpine: a user-level infrastructure for network protocol development[END_REF] and nfsim [START_REF] Russell | nfsim: Untested code is buggy code[END_REF] aim to enable automatic testing of kernel network stacks. By using their own clocks, reproducibility is provided but the per-process virtualization method implemented using the LD_PRELOADed library makes complex the debugging of network stacks between different processes.

Network Simulation Cradle (NSC [START_REF] Jansen | Simulation with real world network stacks[END_REF]) is the ancestor of DCE [START_REF] Lacage | Experimentation Tools for Networking Research[END_REF]. It has been originally developed to provide realistic performance results of existing real-world TCP implementations. NSC parses and transforms different operating system's network stacks (e.g., FreeBSD, Linux, OpenBSD, lwip) into new C files compiled and linked with shared libraries used in network simulators. Both NSC and DCE use the network simulator's virtual time and facilities to provide a wide range of network environments. However, the use of NSC is limited to the validation of TCP protocols as it relies on a language-dependent source-level parser, which is unable to cope with the full set of languages and constructs found in 11 The bootstrap time might be reduced by using snapshots of the VMs after initialization. other network protocol implementations. By contrast, DCE allows to use broader features of the Linux kernel network stack, through carefully designed abstractions of network devices and time-related kernel API (see further details in § 2.2). Table 6 summarizes the discussion of prior work in this section. The DCE approach allows to provide both scalability, as experiments are no longer bound to run in real time, and easy debuggability, which derives from controllability of the single-process model, detailed in Section 2.

CONCLUSION

This paper proposes Direct Code Execution, the first open source framework that allows to integrate real Linux kernel and application code with a leading discrete-event network simulator. DCE provides a realistic, scalable and easy to use environment to reproduce and debug network experiments. We replicated an experiment described in the literature showing reproducible results by using the same protocol implementations over DCE. We also demonstrated a use case on automated code coverage testing that has shown achieving 55-86% coverage of the MPTCP code, and another use case showing easy debugging of a networking stack.

We are confident this framework can help the network community to conduct reproducible experiments and make results more credible by adopting the principle of runnable papers.

Figure 1 :

 1 Figure 1: Architecture of Direct Code Execution. Kernel network devices and timers are synchronized with simulated NetDevice and clock.

  )) return simulation time instead of the wall clock time; signals are checked upon re-turn from every interruptible function; local files are open relative to a node-specific filesystem root to ensure that two different node instances see different data and configuration files, etc.

Figure 2 :

 2 Figure 2: Experimental topology to estimate packet processing rate.

Figure 3 :

 3 Figure 3: Packet processing performance as a function of the number of nodes: Mininet-HiFi has lower overhead than DCE.

Figure 4 :

 4 Figure4: Sent and received packets in function of the number of hops, when running a client/server CBR UDP session for 50s. Note that there is no packet loss in DCE, while Mininet-HiFi starts losing packets when the number of hops exceeds 16.

Figure 5 :

 5 Figure 5: Wall clock time for different sending rates and number of hops with DCE, running a client/server UDP session for 100s.DCE runs slower or faster than real time depending on the scale of scenario but provides accurate results in all cases.

Figure 6 :

 6 Figure 6: Network setup for the MPTCP experiment (left) and the result of original experiment [30] (right).

Figure 7 :

 7 Figure 7: Goodput obtained with MPTCP and TCP over LTE/Wi-Fi using ns-3 DCE in function of receive/send buffer size.

  type of error tcp input.c:3782 touch uninitialized value af key.c:2143 touch uninitialized value to measure and analyze the code coverage of the MPTCP kernel code by gcov tool . The code coverage results are shown in Table

Figure 8 :

 8 Figure 8: Scenario to debug node handoff.

(Figure 9 :

 9 Figure 9: Call stack backtracking of Linux network stack of Mobile IPv6 code with a break condition.

Table 1 :

 1 Supported environment of fast custom ELF loader.

	Version	i386 arch x86 64 arch
	Ubuntu 10.04
	Ubuntu 11.04
	Ubuntu 12.04
	Ubuntu 13.04
	Fedora 14
	Fedora 15
	Fedora 16

Table 2 :

 2 The number of POSIX API functions supported in DCE over time.

	Date	# functions
	2009-09-04	136
	2010-03-10	171
	2011-05-20	232
	2012-01-05	360
	2013-04-09	404

Table 3 :

 3 Measured goodput by different platforms: full reproducible experimental results achieved among different platforms.

	Environment	MPTCP (Mbps) LTE (Mbps) Wi-Fi (Mbps)
	Ubuntu1204-64-Phy	2.67787e+06	1.00382e+06	1.85387e+06
	CentOS6.2-64-KVM	2.67787e+06	1.00382e+06	1.85387e+06
	Ubuntu1210-64-KVM	2.67787e+06	1.00382e+06	1.85387e+06
	Ubuntu1204-64-KVM	2.67787e+06	1.00382e+06	1.85387e+06

Table 4 :

 4 Code coverage of network tests for the MPTCP implementation, where Lines, Functions and Branches are the ratio of declared and tested lines/functions/branches in the code file, respectively.

		Lines Functions Branches
	mptcp ctrl.c	76.3 %	86.7 %	59.9 %
	mptcp input.c	66.9 %	85.0 %	57.9 %
	mptcp ipv4.c	68.0 %	93.3 %	43.8 %
	mptcp ipv6.c	57.4 %	85.0 %	45.2 %
	mptcp ofo queue.c 91.2 %	100.0 %	89.2 %
	mptcp output.c	71.2 %	91.9 %	58.6 %
	mptcp pm.c	54.2 %	71.4 %	40.5 %
	Total	68.0 %	85.9 %	54.8 %

sources will not impact the performance results. The buffer size was configured with the following set of Linux kernel parameters: .net.ipv4.tcp_rmem, .net.ipv4.tcp_wmem, .net.core.rmem_max, and .net.core.wmem_max. Figure

Table 5 :

 5 Memory check obtained with valgrind on Linux (2.6.36).

Table 6 :

 6 Reproducible network experimental tools and their pros/cons.

		Functional	Timing	Topology	Easy	Easy	Experimentation
		realism	realism	Flexibility replication debug	scalability
	Container-based emulation [7] [28] [15] [34] [14] [25] [4]		(only [14])
	Time dilation, traveling
	[13] [21] [36] [26]
	Userspace network stack
	[16] [12] [32] [20]
	Network Simulator Cradle [17]	(limited)
	Direct Code Execution (this paper)

A more detailed description of Mininet-HiFi is provided in Section 6.

The detailed list of supported functions is available at URL http://www.nsnam.org/docs/dce/release/1.0/ manual/html/dce-user-tech.html.

See the DCE manual at http://www.nsnam.org/docs/ dce/manual/html/index.html. Note also that the bake building and integration tool is used to make easier the DCE installation procedure, see http://www.nsnam.org/ docs/bake/tutorial/html/index.html.

In all of the experimental results in this paper, you can click on figures/tables in the PDF to get more information about each result and instruction to reproduce it.

For copyright reasons, we plotted the original data by hand instead of including the original curve from the NSDI paper.

Note that DCE requires a minor modification of iperf when using UDP, but this is not the case in this setup as it uses TCP. See http://www.nsnam.org/docs/dce/release/ 1.1/manual/html/dce-user-newapps.html#example-dcewith-iperf-dce-iperf for more information.

The full list of Linux kernel versions supported by DCE is available at URL https://github.com/thehajime/netnext-sim/branches.

Acknowledgments

This research has been supported by the following projects: (1) the Strategic International Collaborative R&D Promotion Project of the Ministry of Internal Affairs and Communication, Japan, and by the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement No. 608533 (NECOMA); (2) INRIA and the Japanese Society for the Promotion of Science (JSPS) Joint Research Projects program in the context of the Simulbed associated team; (3) the National Institute of Information and Communications Technology (NICT).

The authors thank the anonymous reviewers for their comments and Dejan Kostic, our shepherd, for the guidance in improving the final paper. We also thank Thomas Hen-derson for his insightful comments on this work and Alina Quereilhac for her proofreading on this paper.

Code Availability

The source code described in this paper and the detailed information of each experiment are available at http://yans. pl.sophia.inria.fr/trac/DCE/ If you viewed this paper electronically, click on figures/tables in the PDF to get more information about each result.


Pierre Riedinger
email: pierre.riedinger@ensem.inpl-nancy.fr

Irinel-Constantin Morărescu
email: constantin.morarescu@ensem.inpl-nancy.fr

A numerical framework for optimal control of switched input affine nonlinear systems subject to path constraint

Keywords: Singular optimal control, switched systems, complementarity systems, numerical method

In this paper, we address the problem of numerical implementation of optimal control for switched input affine nonlinear systems subject to path constraint. In order to properly solve the problem, a relaxed system is introduced and the connection between the solution of this system and the solution of the initial one is established. One of the main difficulties is then related to the fact that the optimal solution can be singular. We show that, using slack variables, a set of complementarity constraints can be used to take into account the singular nature of the solution. The optimal control problem is then reformulated as a constraint optimization problem over the Hamiltonian systems and solved via a direct method. This formulation does not require a priori knowledge on the structure (regular/singular) of the solution. In addition, state path constraints are included. Numerical simulations for boost, buck-boost and Flying Capacitor converters, both in continuous and discontinuous conduction mode, illustrate the effectiveness of the proposed methodology.

Introduction

Most of the results related to the optimal control of hybrid systems deal with subsystems sharing zero as common equilibrium. In this paper, we treat the case of switched input affine non linear systems for which generally no common equilibrium can be defined. In this context, the referred targets, named operating points, are defined as the equilibria of a relaxed system -obtained by expanding the control domain to its convex hull. As a result of the applied control strategy, the average value of the state variables computed on a sliding window coincides with the target [START_REF] Hauroigné | Switched affine systems using sampleddata controllers: robust and guaranteed stabilization[END_REF].

It is worth noting that the optimal solution of the relaxed system can be singular as deduced from the Pontryagin Maximum Principle (PMP). Precisely, the necessary conditions provided by PMP are inconclusive on the control value when H u = 0, ∀u. This is a well known [START_REF] Robbins | A generalized legendre-clebsch-condition for the singular cases of optimal control[END_REF][START_REF] Krener | The higher order maximal principle and its application to singular extremals[END_REF][START_REF] Michel | Singular optimal control -the state of the art[END_REF][START_REF] Bonnard | Singular Trajectories and their Role in Control Theory, Series: Mathématiques et Applications[END_REF] difficulty encountered in optimal control field.

The search of analytic solutions is pervasive even for low dimensional systems [START_REF] Patino | Practical optimal state feedback control law for continuous-time switched affine systems with cyclic steady state[END_REF]. In this context only few methods have been proposed to numerically solve such control problems. Indirect shooting method requires a priori knowledge on the structure (regular/singular) of the trajectory [START_REF] Bonnans | Singular arcs in the generalized goddard's problem[END_REF]. This information can be achieved using direct methods [START_REF] Betts | Practical methods for optimal control using nonlinear programming, Advanced design and control[END_REF][START_REF] Riedinger | About solving hybrid control problems[END_REF] but the determination of the control lacks of accuracy. Once the information on the structure of the optimal solution is available, an accurate solution can be obtained if singular arc conditions are imposed for the singular part of the trajectory; see for example the Goddard Rocket Problem in [START_REF] Rao | Algorithm 902: Gpops, a matlab software for solving multiple-phase optimal control problems using the gauss pseudospectral method[END_REF].

In order to overcome this inconvenient, we propose to reformulate the control set inclusion deduced from the necessary conditions of PMP as a set of complementarity constraints and to add them to the Hamiltonian system to form a complementarity system [START_REF] Facchinei | Finite-dimensional Variational Inequalities and Complementarity ProblemsResearch[END_REF]. The multivalued part of the control (corresponding precisely to the singular cases) is then concisely expressed in these complementarity constraints. At this stage, one may view the problem as a Boundary Value Problem (BVP) and try to use a shooting method. Unfortunately, such shooting methods are not appropriate to solve this BVP because of the non uniqueness of the solution.

In this paper we propose to use a direct method [START_REF] Betts | Practical methods for optimal control using nonlinear programming, Advanced design and control[END_REF] to minimize the cost function subject to some complementarity constraints. This approach can be classified as mixed direct-indirect method since it uses both the necessary condition of PMP and a large-scale nonlinear programming problem (NLP) arising from the discretization of the cost and of the resulting complementarity systems. The main advantage of this formulation is that no information on the structure (regular/singular) of the trajectories is a priori required since this feature is implicitly captured by the values of the state and the co-state through a switching function and the set of complementarity constraints.

To improve the accuracy of numerical results, additional constraints concerning the order of the singularity are taken into account. Finally, the method is extended to path constraints case.

The paper is organized as follows. In Section 2 one gives the system description and defines the operating points. Section 3 formulates the optimal control problem derived from PMP. The singular nature of the solution is also detailed and discussed. The complementarity formalism is used to reformulate the optimal control problem in Section 4. To increase the accuracy of the control determination we add constrains related to the order of the singularities. Section 5 contains numerical simulation illustrating the results of the proposed methodology on a variety of power converters.

System Description

The class of constraint switched input affine nonlinear systems under consideration can be described by:

ẋ(t) = f (x(t)) + m i=1 u i (t)g i (x(t)) (1)
x(0) = x 0 (2) c(x(t)) ≤ 0 (3)
where u(t) = (u 1 (t), . . . , u m (t)) ∈ R m is the control law and x(t) ∈ R n represents the state value at time t. The maps f (•) : R n → R n , c(•) : R n → R r and g i (•) : R n → R n , i = 1, . . . , m are supposed sufficiently smooth. A vector is considered positive/negative if all its components are positive/negative. We note that (3) defines the unilateral r-dimension state-path constraints . When u(t) ∈ U = {0, 1} m equation ( 1) describes a class of Switched System (SS) largely used to express the dynamics of nonsmooth mechanical systems (see [START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF][START_REF] Morărescu | Passivity-based tracking control of multiconstraint complementarity lagrangian systems[END_REF] and the reference there in) or electric circuits ( [START_REF] Çamlibe | Stability and controllability of planar bimodal linear complementarity systems[END_REF]). On the other hand when u(t) ∈ co(U ) = [0, 1] m where co(U ) stands for the convex hull, equation (1) describes a Relaxed System (RS). The (SS) belongs to the class of nonsmooth systems for which the notion of solution can be properly defined and generalized in the sense of Fillipov [START_REF] Filippov | Differential equations with discontinuous righthand sides[END_REF]. The link between the solutions of (SS) and (RS) is established by a density theorem in infinite time [START_REF] Ingalls | An infinite-time relaxation theorem for differential inclusions[END_REF]. Let us denote L ∞ ([0, +∞), U ) the set of all essentially bounded measurable functions mapping [0, ∞) to U . Then L ∞ ([0, +∞), U ) equipped with the essential supremum norm (i.e. f ∞ = ess sup|f |) becomes a Banach space. In [START_REF] Ingalls | An infinite-time relaxation theorem for differential inclusions[END_REF] is proven that there exists a switching law u ∈ L ∞ ([0, +∞), U ) such that the trajectory of (RS) is approached as close as desired by the one of (SS). For this reason, the operating points set of (SS) denoted by X ref , is defined as the set of equilibrium points of (RS):

X ref = x ref ∈ R n : f (x ref ) + (4) m i=1 u i,ref g i (x ref ) = 0, u i,ref ∈ [0, 1] . (5)
This set defines the control targets for the state of (SS).

It is worth noting that none of the controls u ref ∈ co(U )\U from (5) corresponding to an equilibrium x ref , is admissible for (SS). The outcome is that (SS) state x cannot be maintained on x ref by a control taking its values in U (unless the time duration between switchings tends towards 0). Consequently, if the target for (SS) is an operating point x ref , the asymptotic behavior of the trajectories is characterized either by a cycle near x ref if a dwell time condition is applied on the switchings (i.e. a lower limit exists for the time duration between switchings) or by an infinite switching sequence with a vanishing time duration between switches as t → ∞.

Optimal control problem formulation

In the sequel, we propose a methodology to numerically solve the following optimal control problem for the system defined by equations ( 1)-(3):

min u(.) T 0 L(x(t), x ref )dt ( 6
)
where L is the continuously differentiable performance function, x ref stands for a chosen equilibrium point in X ref and T refers to the strictly positive final time and is fixed (T ∈ R + ).

When the (RS) has a bang-bang solution (i.e. ∀t, u(t) ∈ {0, 1} m ), (SS) is also solved. Otherwise, it exists a non zero measure set (in the Lebesgue sense) T such that the optimal solution takes values u(t) ∈ co(U )\U for all t ∈ T . Although these solutions are not admissible for (SS), Pulse Wise Modulation (PWM), for example, yields an average approximation by high switching frequency [START_REF] Ingalls | An infinite-time relaxation theorem for differential inclusions[END_REF]. Consequently we relax the optimal control problem for (SS) by searching the optimal solutions of (RS) from which suboptimal solutions for (SS) can be derived.

Suppose in a first time that no constraint are taken into account and let inspect the necessary conditions defined by the Pontryagin Maximum Principle (PMP). The Hamiltonian function H is given by (abnormal case is not taken into account):

H(t) = λ ⊤ (t)(f (x) + g(x)u(t)) + L(x(t), x ref ) (7)
where λ(t) ∈ R n depicts the co-state whose dynamic is given by the Hamiltonian system λ(t) = -H x (t) ( ẋ(t) = H λ (t)).

Optimality condition of PMP that u minimizes the Hamiltonian function leads to the following inclusion,

u i (t) ∈      0 if φ i (t) > 0 [0 1] if φ i (t) = 0 1 if φ i (t) < 0 ∀ i = 1, ..., m (8)
where φ(t) = H u (t) = λ T (t)g(x(t)) defines the switching function. When u i (t) = 0 or 1, the control is called regular. A singularity arises when a component of φ i (t) vanishes identically on a time interval [a, b], b > a. In this case, the PMP is inconclusive concerning the control value

u i (•) on [a, b].
This situation is referred to as singular control [START_REF] Robbins | A generalized legendre-clebsch-condition for the singular cases of optimal control[END_REF][START_REF] Bryson | Applied optimal control[END_REF][START_REF] Bonnard | Singular Trajectories and their Role in Control Theory, Series: Mathématiques et Applications[END_REF] and it corresponds here to the case where u(t) takes values in co(U )\U, t ∈ [a, b]. We can conclude that solution segments for (RS), which are not admissible for (SS), involve a singular control. Nevertheless, there exist generic cases where the necessity to take into account singular arcs can be avoided when a generic property, as defined in [START_REF] Chitour | Singular trajectories of control-affine systems[END_REF], is satisfied by the control-affine system. Indeed, if the system is generic and if m ≥ 2, it is proved that the control system (1) does not admit any singular trajectory. However our paper is focussing on systems that do not satisfy the generic property.

In the sequel, in order to simplify the notation we shall often avoid to emphasize the time dependency of the variables and controller. These arcs are characterized by:

H u (x, λ, u) = 0, ∀u ∈ co(U ), ∀t ∈ (a, b). (9)
To determine these arcs, successive time differentiations:

d q dt q H u (x, λ, u) = 0, (10)
are required. The differentiation has to be done until at least a component of the control appears. The smallest positive integer q * which is always even, such that

∂ ∂u ( d q * dt q * H u (x, λ, u)) = 0, (11)
if it exists, is called the order of singularity [START_REF] Michel | Singular optimal control -the state of the art[END_REF] (or index of the DAE). As we have shown in [START_REF] Patino | Practical optimal state feedback control law for continuous-time switched affine systems with cyclic steady state[END_REF], for low dimensional systems (i.e. n ≤ 3), the analytic expression of u can be explicitly determined by using the set of algebraic equations ( 10) and a second order necessary condition given by the Generalized Legendre-Clebsh Condition [START_REF] Robbins | A generalized legendre-clebsch-condition for the singular cases of optimal control[END_REF][START_REF] Michel | Singular optimal control -the state of the art[END_REF][START_REF] Krener | The higher order maximal principle and its application to singular extremals[END_REF]:

(-1) q * 2 ∂ ∂u ( d q * dt q * H u (x, λ, u)) ≥ 0. ( 12
)
On one hand, to determine analytically the optimal solutions including singular arcs is a particularly hard problem and only low dimensional systems (i.e. n=2,3) have been treated [START_REF] Patino | Practical optimal state feedback control law for continuous-time switched affine systems with cyclic steady state[END_REF]. Moreover, knowledge on the singular arcs are of few help in determination of the junction time between singular and regular arcs. On the other hand, standard indirect numerical methods such as multiple shooting methods are not appropriate to deal with singular arcs without a priori information on the structure of the trajectories (see [START_REF] Fraser-Andrew | Finding candidate singular optimal controls: A state of the art survey[END_REF], [START_REF] Maurer | Numerical solution of singular control problems using multiple shooting techniques[END_REF] and [START_REF] Martinon | Singular arcs in the generalized goddard's problem[END_REF] to apply multiple shooting methods in this context). This information can be achieved using regularization techniques such as the continuation method used in [START_REF] Moylan | Generalizations of singular optimal control theory[END_REF], [START_REF] Jacobson | Computation of optimal singular controls[END_REF], [START_REF] Martinon | Numerical resolution of optimal control problems by a pieciwise linear continuation method[END_REF]. In this paper, we propose to use direct method and an ad hoc formulation that takes implicitly into account the singular arcs and do not require a priori information on the solution structure.

Optimal control using complementarity system formalism

Complementarity is a useful concept that can be used to describe properly the behavior of nonsmooth systems. Complementarity systems have been largely employed in the analysis and control of mechanical systems [START_REF] Brogliato | Nonsmooth Mechanics[END_REF][START_REF] Brogliato | Dissipative Systems Analysis and Control. Theory and Applications[END_REF][START_REF] Morărescu | Passivity-based tracking control of multiconstraint complementarity lagrangian systems[END_REF] and recently they are used to describe the dynamics of electric circuits [START_REF] Çamlibe | Stability and controllability of planar bimodal linear complementarity systems[END_REF][START_REF] Vasca | A new perspective for modeling power electronics converters: complementarity framework[END_REF][START_REF] Acary | Time-stepping numerical simulation of switched circuits with the nonsmooth dynamical systems approach[END_REF]. Definition 2. A Linear Complementarity Problem (LCP) is a system given by:

   y ≥ 0 Ay + b ≥ 0 y T (Ay + b) = 0 (13)
which is compactly rewritten as

0 ≤ y ⊥ Ay + b ≥ 0 ( 14
)
Such an LCP has a unique solution for all b if and only if A is a P-matrix, i.e. all its principal minors are positive [START_REF] Facchinei | Finite-dimensional Variational Inequalities and Complementarity ProblemsResearch[END_REF].

Combining complementarity conditions with differential equations we get what usually in the literature is referred to as complementarity systems (see [START_REF] Brogliato | Some perspectives on the analysis and control of complementarity systems[END_REF] and the references therein):

     ẋ(t) = f (x(t), u(t)) y(t) = h(x(t), u(t)) 0 ≤ y(t) ⊥ u(t) ≥ 0 (15)
We also note that in some applications, the complementarity system may contain an external input (forcing term) or the adjoint variable [START_REF] Schumacher | Complementarity systems in optimisation[END_REF]. In the sequel, we propose to reformulate the Hamiltonian system and the necessary condition (8) as a complementarity system.

Relay inclusion as a complementarity constraint

Let us recall (see [START_REF] Schumacher | Complementarity systems in optimisation[END_REF]) that the relay-type function [START_REF] Bryson | Applied optimal control[END_REF] can be rewritten as a complementarity constraint and an algebraic equation as follows:

0 ≤ s 1 ⊥ u ≥ 0 (16) 0 ≤ s 2 ⊥ (1 -u) ≥ 0 (17) 0 = s 1 -s 2 -φ (18)
where s 1 and s 2 are m-dimensional vectors and define the positive and the negative part of φ(x, λ). In other words, the components of the two vectors s 1 and s 2 are defined by:

s 1i (t) = 0 if φ i (t) < 0 φ i (t) if φ i (t) ≥ 0 ∀ i = 1, . . . , m s 2i (t) = -φ i (t) if φ i (t) < 0 0 if φ i (t) ≥ 0
It is important to note that as long as s 1i > 0 or s 2i > 0 the component u i of the control law u is uniquely determined. When s 1i = 0 & s 2i = 0 the uniqueness of u i is lost and the choice of its value is a matter of optimization. We also observe that the situation s 1i • s 2i > 0 cannot occur since this will contradict either [START_REF] Hauroigné | Switched affine systems using sampleddata controllers: robust and guaranteed stabilization[END_REF] or [START_REF] Ingalls | An infinite-time relaxation theorem for differential inclusions[END_REF].

Path constraints

Until now, no consideration has been made on the path constraints (3). Like for singular controls, the index q of the state constraint is the first time where u appears explicitly in the successive time differentiation of c along the trajectories. This index allows to define the mixed control-state path constraints occurring on the boundary c(x) = 0:

p(x, u) = d q dt q c(x) ≤ 0. ( 19
)
and the Lagrangian function:

L(x, u, λ, µ) = H(x, u, λ) + µ T p(x, u) (20)
where µ ≥ 0 represents the r-dimensional vector of Lagrange multipliers.

Assumption 1. We assume in the sequel, that q = 1.

When it is not the case, the co-state might be only a measure and the given version of PMP does not apply [START_REF] Clarke | Optimization and Nonsmooth Analysis[END_REF].

Theorem 1. If u * is the optimal control for the state constraint system (1-3) when the cost is defined by ( 6) then u * satisfies the following constraint optimization problem:

COP : min u(•) T 0 L(x(t), x ref )dt (21)
s.t. ẋ = L λ λ = -L x (22)
x(0) = x 0 λ(T ) = 0 (23)

0 ≤ s 1 ⊥ u ≥ 0 (24) 0 ≤ s 2 ⊥ (1 -u) ≥ 0 (25) 0 = s 1 -s 2 -L u (x, λ, µ) (26)
0 ≤ µ i ⊥ (s 1 + s 2 ) j ≥ 0, i = 1, • • • , r j = 1, • • • , m (27)
0 ≤ µ ⊥ -c(x) ≥ 0 (28)
Proof. These necessary conditions are directly deduced from PMP in case of state constraint (Chap.6; [START_REF] Pontryagin | Théorie mathématique des processus optimaux[END_REF]) and in presence of complementary constraints as explained in the following comments:

• Generally when path constraints are considered, jumps occur on the costate at junction time τ . They are characterized by λ + (τ ) = λ -(τ ) + α∇c(x(τ )). In fact, α can be taken equal to zero when the motion follows the border c(x) = 0 for t ≥ τ as proven in the pioneer work (Chap.6; [START_REF] Pontryagin | Théorie mathématique des processus optimaux[END_REF]).

• When µ equals zero, [START_REF] Kupka | The ubiquity of Fuller's phenomenon Nonlinear controllability and optimal control[END_REF] allows us to retrieve the unconstraint version of PMP. Note that when µ = 0, (26) is equivalent to [START_REF] Jacobson | Computation of optimal singular controls[END_REF]. The complementarity relation [START_REF] Martinon | Singular arcs in the generalized goddard's problem[END_REF] assures that µ = 0 when c(x) is not active (i.e. c(x) > 0).

• The constraint c i (x) is activated (i.e. c i (x) = 0) when µ i becomes positive and modifies the co-state dynamics as it is required (Chap.6; [START_REF] Pontryagin | Théorie mathématique des processus optimaux[END_REF]).

• The complementarity conditions 0 ≤ µ i ⊥ (s 1 + s 2 ) j ≥ 0 are necessary for any i = 1, • • • , r and for any j = 1, • • • , m to ensure the necessary condition L u = 0 when some components of the path constraints are active. Indeed, if at least one of the constraints is strongly active, says the ith, then µ i > 0 and s 1 = s 2 = 0 and all components of u ∈ [0 1] m are subject to L u = 0 as required by the minimization of the Lagrangian L (augmented Hamiltonian).

It has to be mentioned here two important features of the above formalism. Firstly, this formulation clearly takes into account both singular arcs and path constraints. Secondly, no assumption is made on the structure (singular/regular) of the trajectories. This is implicitly captured by the values of x and λ through the switching function φ and the complementarity constraints. Consequently, we do not require any initial information on the existence of singular arcs entering in the optimal trajectory.

The optimization problem (COP) can be solved using direct method i.e. by minimizing the cost function [START_REF] Martinon | Numerical resolution of optimal control problems by a pieciwise linear continuation method[END_REF] subject to the complementarity system [START_REF] Maurer | Numerical solution of singular control problems using multiple shooting techniques[END_REF][START_REF] Michel | Singular optimal control -the state of the art[END_REF][START_REF] Moreau | Unilateral contact and dry friction in finite freedom dynamics[END_REF][START_REF] Morărescu | Passivity-based tracking control of multiconstraint complementarity lagrangian systems[END_REF][START_REF] Moylan | Generalizations of singular optimal control theory[END_REF][START_REF] Patino | Practical optimal state feedback control law for continuous-time switched affine systems with cyclic steady state[END_REF][START_REF] Martinon | Singular arcs in the generalized goddard's problem[END_REF]. Of course, in order to determine accurate solution, recall that it is important to scale the problem and to use code that use multiple phase formulation to reduce the sensitivity and that enable grid refinement procedure. Among the possible alternatives, for all the examples given in the next section, we have used the beta version GPOPS Toolbox for Matlab. This toolbox solves multiphase optimal control problems [START_REF] Betts | Practical methods for optimal control using nonlinear programming, Advanced design and control[END_REF] and is based on Radau pseudo spectral methods to parametrize the solution. In this orthogonal collocation method, the collocation points are the Legendre-Gauss-Radau points [START_REF] Garg | A unified framework for the numerical solution of optimal control problems using pseudospectral methods[END_REF] and an interesting feature is that it is a Gaussian quadrature implicit integration scheme. From a practical point of view, complementary constraints is achieved by penalization terms in the cost of the form ρyw if 0 ≤ y ⊥ w ≥ 0, with weight ρ > 0 and chosen sufficiently large.

Remark 1. The proposed numerical framework does not catch Fuller or zeno phenomena [START_REF] Kupka | The ubiquity of Fuller's phenomenon Nonlinear controllability and optimal control[END_REF]. These phenomena characterized by an infinite number of switchings in finite time which can occur when the trajectories hits the path constraint or the singular surfaces, are not taken into account by the proposed numerical method. In fact, these phenomena is avoided by the discretization of the problem and is ultimately approximated.

A practical and significant improvement in minimizing the cost function (21) subject to the complementarity system (22-28) can be obtained by including the algebraic constraints [START_REF] Chitour | Singular trajectories of control-affine systems[END_REF] for q = 1, • • • , q * . The last constraint when q = q * is particularly beneficial since the control appears in it explicitly. Of course, as these constraints correspond to the case where the control is singular, these additions are only possible when path constraints are not active (that is when µ = 0 and λ = -H x = -L x ). If the path constraints are active, they are unnecessary since u appears this time in the path constraints.

Theorem 2. If u * is the optimal control of problem defined by cost (6) and state constraint system (1-3) then u * satisfies COP of Theorem 1 and the following additional constraints related to the order of the singularity (10):

0 = s 2q+1 -s 2q+2 - d q dt q φ, q = 1, • • • , q * (29) 0 ≤ r i=1 c i (x)u(1 -u) ⊥ (s 2q+1 + s 2q+2 ) ≥ 0 (30) 0 ≤ s 2q+1 ⊥ s 2q+2 ≥ 0 ( 31
)
where s 2q+1 , s 2q+2 q = 1, • • • , q * are additional m-dimension slack variables.

Proof. It is easy to show from equation ( 29) and ( 31) that s 2q+1 and s 2q+2 are respectively the positive and the negative part of d q dt q φ. Then, [START_REF] Rao | Algorithm 902: Gpops, a matlab software for solving multiple-phase optimal control problems using the gauss pseudospectral method[END_REF] imposes that the i th component of | d q dt q φ| equals zero when u i is singular and the state x does not satisfy one of the constraints given by [START_REF] Bonnans | Singular arcs in the generalized goddard's problem[END_REF]. Following singular arc definition, these relations are fulfilled and their inclusion in (COP) improves the numerical solution notably in the control determination as we will show in the next section.

Application to power converters

DC-DC converters such as buck, boost, buck-boost, flying capacitor converters enter clearly in the class of constraint switched affine systems. We have applied our numerical approach for all these converters and we present in the sequel two selected cases to illustrate the effectiveness of the proposed procedure.

FCC converter

In the case of a few megawatt industrial power applications, the classical power converters have a very high voltage in the switching components (several kilovolts). To compensate this, a new class of power converters called Flying Capacitor Converters (FCC) appeared (or multicellular converter). The structure of the FCC converter reduces the voltage throughout the switches. It is composed of serial connections between semiconductor switching devices and passive storage elements to achieve the target operating voltage as illustrated in Figure 1.

Three switching cells can be isolated, each of them being able to operate in two complementary mode. The behavior of each cell can be described using only one boolean control variable u i ∈ {0, 1} with i = 1, 2, 3. u i = 1 means that the upper switch is closed and the lower switch is open whereas u i = 0 means that the upper switch is open and the lower switch is closed (Figure 1). The state equations of the converter have an affine form given by

  ẋ1 ẋ2 ẋ3   =   0 0 -R L x 3   +   -x3 C1 x3 C1 0 0 -x3 C2 x3 C2 x1 L x2-x1 L E-x2 L     u 1 u 2 u 3   ( 32
)
where x 1 , x 2 are the voltage on each capacitor and x 3 the load current. The chosen parameters are E = 30 V , R = 10 Ω, C 1 = C 2 = 40µF and L = 10 mF . The capacitor voltages must be balanced to 2E/3 and E/3, while the demanding load current is fixed to 2 A. Then,

x ref = E/3 2E/3 2
T . The optimization problem consists in minimizing the quadratic criteria:

min u(•) T 0 (x -x ref ) ′ Q(x -x ref )dt.
The weight matrix Q is taken to:

Q =   0.2 -0.1 0 -0.1 0.1 0 0 0 200   Figure 2
and 3 show the control and state trajectories starting from the origin. The objective value is J = 0.129. As expected, the control are totally singular and are properly determined using the proposed formulation. In comparison, a direct transcription of equation ( 6) and (1-2) using the same GPOPS toolbox, yields the results provided in Figure 4 and Figure 5. The solver returns a flag indicating that the optimization has finished successfully and that the optimality conditions are satisfied. In fact, we can observe that the trajectories are similar but the control is far from being accurate due to Hamiltonian singularities. All these simulations have been done with the same parameters: 3 phases formulations, 3 mesh iterations, analytic derivative provided and the same mesh tolerance (1e-3), see [START_REF] Betts | Practical methods for optimal control using nonlinear programming, Advanced design and control[END_REF], [START_REF] Garg | A unified framework for the numerical solution of optimal control problems using pseudospectral methods[END_REF] and website dedicated to GPOPS for more explanation. For this example, there is no path constraint. So, the differences in the numerical results are determined by the adopted formulation. In view of the results, the Karush-Kuhn-Tucker conditions used to solve directly the problem ( 6) and (1-2) does not allow to determine properly the control in singular cases while the additional algebraic constraints given by Theorem 1 and 2 force this determination.

Boost converter

The topology of a boost converter is given in Figure [START_REF] Brogliato | Some perspectives on the analysis and control of complementarity systems[END_REF]. In continuous conduction mode, following the position of the switch u, two subsystems ẋ =

A i x + B i , i = 1, 2 can be considered with matrices A 1 = -R L 0 0 -1 R0C , A 2 = -R L -1 L 1 C -1 R0C , B 1 = E L 0 and B 2 = B 1 .
Generally the control strategies proposed in the literature do not take into account the discontinuous mode that may appears when the demanding current in the load is low. In this case, the current in the diode vanishes and produces an autonomous switch. Few results concerning optimal control of hybrid systems are related to the case of autonomous switches. The third subsystem is then described by

A 3 = 0 0 0 -1

R0C

, and B 3 = 0 0 .

In fact, it is not necessary to add this last subsystem when x 1 = 0 since there exists an equivalent control u eq (x) ∈ [0 1] which forces ẋ1 = 0 and such that the dynamics of ẋ = u eq (A 1 x + B 1 ) + (1 -u eq )(A 2 x + B 2 ) matches the one of the third subsystem. So, the optimal control problem is solved with path constraint corresponding to x 1 ≥ 0.

The parameters are chosen as follow: E = 20V , R 0 = 50 Ω, R = 1 Ω, L = 2 mH and C = 100 µF .

The optimization problem consists in minimizing, for a given equilibrium x ref , the quadratic criteria:

min u(.) T 0 (x -x ref ) ′ Q(x -x ref )dt.
We have applied the following scenario: Starting from zero initial condition, the state is steered to equilibrium x ref = (2.2, 44.4) obtained for u ref = 0.6 then, after 5ms a new reference x ref = (0.78, 27.46) corresponding to u ref = 0.3 is applied.

Figures 8 and7 show the state trajectories and the optimal control as well as the Lagrange multiplier obtained for the weight matrix Q = diag [START_REF] Acary | Time-stepping numerical simulation of switched circuits with the nonsmooth dynamical systems approach[END_REF][START_REF] Chitour | Singular trajectories of control-affine systems[END_REF]. The time scale is expressed in ms. The numerical results show that just at the beginning of the simulation the control switches from 1 to 0 before the optimal trajectory reaches the singular arc which happens after approximatively 1ms.

When a new reference is applied at time t = 5ms, control switches to zero and the system enters in discontinuous conduction mode when the current vanishes. The value of the Lagrangien multiplier clearly indicates this while the control values allow to meet the constraint ẋ1 = 0. The system returns in continuous conduction mode with a short activation of mode 2 at time t = 7.5ms. The control becomes singular once the reference is reached. Now, Figure 9 compares the precision with which the optimal control is determined according to the formulation adopted to solve the optimal control problem. Starting from the origin, the cost function consists to minimize the quadratic criteria min u(.) At the bottom (c), a direct transcription into a NLP leads to poor results as expected when the control is singular. A gap in the accuracy is obtained with a complementarity formulation like in Theorem 1 as it is shown in the (b) part of the Figure 9. A full improvement is reached in the top of Figure 9 (a) when additional constraints associated to the order of the singularity [START_REF] Chitour | Singular trajectories of control-affine systems[END_REF] are taken into account (Theorem 2). Thus, this example reflects the ability of the formulation given in Theorem 2 to determine properly the optimal control without any information on the structure of the solution.

T 0 (x -x ref ) ′ Q(x -x ref )dt

buckboost converter

The last example concerns a buck-boost converter and it is chosen to show that this numerical approach can be useful not only to compute optimal openloop control (in case of predictive control for example) but also to design robust close-loop controller.

In Figure 10 the red circle is the reference and the optimal trajectories starting from different initial conditions are plotted in blue. We can observe that discontinuous conduction mode appears along the negative part of x 2 -axis and that all the trajectories reach the target x ref following a singular arcs. As Figure 10 shows, the state space is partitioned following the control to be used. It can be observed that the singular trajectories, at the junction between the different parts, defined optimal sliding surfaces.

Clearly, there is a partition that defines u as a state feedback u(x). We think that this partition can be achieved using learning machines such as neural networks.

The parameters used in the simulations above are:

E = R = L = C = 1, A 1 = 0 0 0 -1 RC A 2 = 0 1 L -1 C -1 RC B 1 = E L 0 B 2 = 0 0 weight matrice Q = diag(q 1 , q 2
) with q 1 = 1 and q 2 = 10.

How to implement suboptimal switched control law ?

The optimal controls determined in this paper take their values in co(U ) and are generally (when singular) not admissible for the original switched systems (SS). The density theorem given in [START_REF] Ingalls | An infinite-time relaxation theorem for differential inclusions[END_REF] shows that all trajectories of the relaxed system (RS) can be approached as close as desired by the one of the switched systems (SS). So, the optimal one, too. In order to approach an optimal trajectory of (RS) by the one of (SS) can be simply obtained using a Pulsewise Modulation technic (PWM) to generate the switching law as it is well known in the field of power electronic. In the ideal case, higher switching frequency f s leads to better approximations of the optimal trajectory. This fact explains also why (SS) has only suboptimal solutions when the optimal solution of (RS) possesses singular arcs. The limit of the switching law sequence u(t, f s ) ∈ U obtained by increasing f s → +∞, is the singular control almost everywhere.

Conclusion

In this paper we have proposed a numerical framework to solve optimal control problem for switched input affine nonlinear systems. One specific feature of this class is that singular controls have to be considered in order to obtain the optimal solution. As singular controls are determined by an inclusion depending on the state and the co-state, we have reformulated the optimization problem using the augmented (in case of path constraints) Hamiltonian system and a set of slack variables defining a set of complementarity constraints. This constraint augmented optimization problem is then solved with a direct method dedicated to optimal control.

The contribution of the proposed methodology is twofold: an accurate optimal control is determined without any additional information concerning the existence and the number of the singular arcs belonging to the optimal trajectory and, the optimal control is determined even in the presence of autonomous switches. The first contribution is an important relaxation since generally in the provided singular control examples in the literature, an a priori knowledge of the number of singular arcs is required (see for example the Godart Rocket example). The second contribution allows to complete the simulation of electric circuits containing switching elements, including the discontinuous conduction mode.

It is noteworthy that a direct transcription of the optimal control problem as a non linear program leads to poor results as the FCC converter example has shown. The effectiveness of our method has been illustrated in several examples.

Definition 1 .

 1 For a single control (m=1), if φ vanishes identically on the time interval [a, b], b > a we say that x belongs to a singular arc for all t ∈ [a, b].

Figure 1 :

 1 Figure 1: Fying capacitor converter

3 Figure 2 : 3 Figure 3 : 3 Figure 4 : 3 Figure 5 :Figure 6 :

 323334356 Figure 2: Optimal singular controls using Hamiltonian and complementarity constraints

Figure 7 :

 7 Figure 7: Boost converter: Optimal controls

Figure 8 :

 8 Figure 8: Boost converter : State trajectories

  where x ref corresponds to the equilibrium given by u ref = 0.5.

Figure 9 :Figure 10 :

 910 Figure 9: Boost converter: Improvement in the numerical control determination; c: direct transcription, b: Hamiltonian like a Complementarity Problem; a: Full Constraint formulation using order of the singularity

Acknowledgments This work was partially supported by ANR project ArHyCo, Programme "Systèmes Embarqués et Grandes Infrastructures"-ARPEGE, contract number ANR-2008 SEGI 004 01-30011459. The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n • 257462: HYCON2 Network of Excellence "Highly-Complex and Networked Control Systems", and from Contrat de Projet État-Région 2007-2013, Région Lorraine.